Grafic prag

În teoria graficelor , un grafic de prag este un grafic care poate fi construit, pornind de la un grafic cu un singur vârf, aplicând în mod repetat una dintre următoarele două operații:

1. Adăugarea unui vârf izolat la grafic.
2. Adăugarea unui vârf dominant la grafic, adică un vârf conectat la toate celelalte vârfuri.

De exemplu, graficul din figura opusă este un grafic prag: poate fi construit începând cu un grafic cu un singur vârf (vârful 1), apoi adăugând celelalte șapte în ordinea în care sunt numerotate, vârfurile negre fiind izolate vârfuri și vârfuri roșii ca vârfuri dominante.

Graficele prag au fost introduse de Chvátal și Hammer în 1977. Un capitol despre graficele de prag apare în cartea lui Golumbic din 1980, iar cartea lui Mahadev și Peled din 1995 le este dedicată.

După cum remarcă Diaconis, Holmes și Janson, printre cele 64 de grafice etichetate cu 4 vârfuri, există 46 de grafice de prag; celelalte 18 sunt lanțuri cu 4 vârfuri (notate , cicluri cu 4 vârfuri (notate ) și complementele lor care sunt perechi de margini (notate ). Dacă luăm în considerare graficele neetichetate, există 11 grafice cu 4 vârfuri, dintre care 8 sunt prag grafice. P4){\ displaystyle P_ {4})}VS4{\ displaystyle C_ {4}}2K2{\ displaystyle 2K_ {2}}

Alte definiții

O definiție echivalentă este: un grafic este un grafic prag dacă există un număr real și pentru fiecare vârf o greutate (număr real) astfel încât pentru două vârfuri perechea este o muchie dacă și numai dacă . S{\ displaystyle S} v{\ displaystyle v}p(v){\ displaystyle p (v)}tu,v{\ displaystyle u, vb}tuv{\ displaystyle uv}p(tu)+p(v)>S{\ displaystyle p (u) + p (v)> S}

O altă definiție echivalentă este: un grafic este un grafic prag dacă există un număr real și, pentru fiecare vârf , o greutate reală astfel încât pentru orice set de vârfuri , mulțimea este independentă dacă și numai dacă . Denumirea „grafic prag” provine din aceste definiții: S este „pragul” pentru proprietatea de a fi o margine, sau într-un mod echivalent T este pragul pentru a fi un set independent. T{\ displaystyle T}v{\ displaystyle v}La(v){\ displaystyle a (v)}X⊆V{\ displaystyle X \ subseteq V}X{\ displaystyle X}∑v∈XLa(v)≤T.{\ displaystyle \ sum _ {v \ în X} a (v) \ leq T.}

Graficele Threshold au de asemenea o caracterizare subgrafic excluse: un grafic este un grafic prag dacă și numai dacă nici un set de patru dintre nodurile sale formează subgraful care este un grafic cale cu trei muchii , un grafic cu patru margine ciclu sau un două muchie grafic de cuplare . P4){\ displaystyle P_ {4})}VS4{\ displaystyle C_ {4}}2K2{\ displaystyle 2K_ {2}}

Descompunere

Din definiția care folosește adăugarea repetată a vârfurilor, se poate obține un alt mod de a descrie în mod unic un grafic de prag, prin intermediul unui lanț de simboluri. Primul caracter al acestui șir este simbolul și reprezintă primul vârf al graficului. Fiecare caracter ulterior este fie simbolul , care denotă adăugarea unui vârf izolat (sau vârf de unire ), fie , care denotă adăugarea unui vârf dominant (sau vârf de unire ). De exemplu, șirul reprezintă un grafic stelar cu trei foi, în timp ce reprezintă o cale cu trei vârfuri. Graficul din figură poate fi reprezentat caϵ{\ displaystyle \ epsilon}tu{\ displaystyle u}j{\ displaystyle j}ϵtutuj{\ displaystyle \ epsilon uuj}ϵtuj{\ displaystyle \ epsilon uj}ϵtututujtutuj{\ displaystyle \ epsilon uuujuuj}

Legătură cu alte clase de grafice și recunoaștere

Grafice prag sunt un caz special de cographs , grafice pe părți, și grafice trivially perfecte . Un grafic este un grafic prag dacă și numai dacă este atât un grafic cât și un grafic divizat. Orice grafic care este atât un grafic trivial perfect, cât și graficul complementar al unui grafic trivial perfect este un grafic prag. Graficele prag sunt, de asemenea, un caz special de grafice de interval . Toate aceste relații pot fi deduse din caracterizarea lor prin subgrafurile interzise induse: Un cograf este un grafic fără cale indusă pe patru vârfuri ( ), iar un grafic de prag este un grafic indus fără , nici . este un ciclu de patru vârfuri și este complementul său, adică a format două margini disjuncte. Acest lucru explică, de asemenea, de ce graficele de prag sunt închise mergând la complement; le este auto-complementar, deci dacă un grafic este fără , nici , complementul său este prea. P4{\ displaystyle P_ {4}}P4{\ displaystyle P_ {4}}VS4{\ displaystyle C_ {4}}2K2{\ displaystyle 2K_ {2}}VS4{\ displaystyle C_ {4}}2K2{\ displaystyle 2K_ {2}}P4{\ displaystyle P_ {4}}P4{\ displaystyle P_ {4}}VS4{\ displaystyle C_ {4}}2K2{\ displaystyle 2K_ {2}}

Graficele prag au, de asemenea, proprietăți spectrale speciale, studiate de Diaconis, Holmes și Janson, precum și de Lou, Wang și Huang sau Tura. Astfel, toate valorile proprii ale matricei distanței unui grafic de prag conectat, altele decât -2 și -1, sunt simple.

Heggernes & Kratsch au arătat în 2007 că graficele individuale pot fi recunoscute în timp liniar; în cazul în care un grafic nu este prag, algoritmul detectează un obstacol, adică una dintre graficele , sau . P4{\ displaystyle P_ {4}}VS4{\ displaystyle C_ {4}}2K2{\ displaystyle 2K_ {2}}

Vezi si

• Graficul intervalului curat
• Grafic serie-paralel

Note și referințe

• (fr) Acest articol este preluat parțial sau în totalitate din articolul din Wikipedia engleză intitulat „  Threshold graph  ” (a se vedea lista autorilor ) .

1. Chvátal și Hammer 1977 .
2. Golumbic 1980 .
3. Mahadev și Peled 1995 .
4. Diaconis, Holmes și Janson 2008 .
5. Lou, Wang și Huang 2018 .
6. Tura 2021 .
7. Heggernes și Kratsch 2007 .

Bibliografie

• Milica Anđelić și Slobodan K. Simić , „  Câteva note despre graficele pragului  ”, Matematică discretă , vol.  310, n os  17-18,2010, p.  2241-2248 ( DOI  10.1016 / j.disc.2010.04.022 )
• Václav Chvátal și Peter L. Hammer , „Agregarea inegalităților în programarea întreagă” , în PL Hammer, EL Johnson, BH Korte, GL Nemhauser (eds), Studies in Integer Programming (Proc. Worksh. Bonn 1975) , vol.  1, Amsterdam, Olanda de Nord, col.  „Analele matematicii discrete”,1977, p.  145–162.
• Persi Diaconis , Susan Holmes și Svante Janson, „  Limite grafice prag și grafice prag aleatorii  ”, Internet Mathematics , Taylor & Francis Online, vol.  5, n o  3,2008, p.  267-320 ( arXiv  0908.2448 , citit online , accesat la 15 iulie 2021 ).
• Martin Charles Golumbic , Teoria algoritmică a graficelor și graficele perfecte , New York, Academic Press,1980. Ediția a II-a, Annals of Discrete Mathematics, 57 , Elsevier, 2004.
• Pinar Heggernes și Dieter Kratsch , „  Algoritmi de recunoaștere a timpului liniar și subgrafe induse interzise  ”, Nordic Journal of Computing , vol.  14, n os  1-2,2007, p.  87–108 (2008) ( Math Reviews  2460558 , citește online ).
• NVR Mahadev și Uri N. Peled , Grafice prag și subiecte conexe , Elsevier,1995.
• Pallabi Manna , Peter J. Cameron și Ranjit Mehatari , „  Subgrafe interzise ale graficelor de putere  ” , The Electronic Journal of Combinatorics , vol.  28, n o  3,2021( DOI  10.37236 / 9961 , citiți online )
• Lu Lu , Qiongxiang Huang și Zhenzhen Lou , „  Pe spectrele de distanță ale graficelor de prag  ”, Algebra liniară și aplicațiile sale , vol.  553,2018, p.  223–237 ( DOI  10.1016 / j.laa.2018.05.014 )
• Zhenzhen Lou , Jianfeng Wang și Qiongxiang Huang , „  Despre distribuția valorilor proprii în grafice prag  ”, Graphs and Combinatorics , vol.  35, nr .  4,2019, p.  867–880 ( DOI  10.1007 / s00373-019-02042-1 )
• Fernando C. Tura , „  A conjecture on the eigenvalues ​​of threshold graphs  ”, Algebra liniară și aplicațiile sale , vol.  612,2021, p.  345–356 ( DOI  10.1016 / j.laa.2020.11.007 , arXiv  2006.03136 )

linkuri externe

• „Grafice prag” , Sistem de informații privind clasele de grafice și incluziunile acestora .

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">