Numără fără clește

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 12 septembrie 2021; verificarea necesită 1 editare .

În teoria grafurilor, un graf fără gheare este un graf care nu conține subgrafe generate izomorfe cu K 1,3 ( gheare ).

O gheară este un graf bipartit complet K 1,3 (adică o stea cu trei margini, trei frunze și un vârf central). Un grafic fără gheare este un grafic în care niciun subgraf generat nu este o gheară, adică nu există patru vârfuri A , B , C și O astfel încât O să fie conectat la A , B și C , dar vârfurile A , B și C nu sunt legate între ei. De asemenea, este posibil să se definească un graf fără gheare ca unul în care vecinătatea oricărui vârf formează complementul grafului fără triunghi .

Graficele fără gheare au fost studiate inițial ca o generalizare a graficelor cu linii și au primit un stimul suplimentar atunci când au fost descoperite trei fapte cheie despre ele:

1. faptul că toate grafurile conectate fără gheare de ordine uniformă au potriviri perfecte ;
2. descoperirea unui algoritm timp-polinom pentru găsirea mulţimii independente maxime în grafice fără gheare;
3. descrierea graficelor perfecte fără gheare [1] . Sute de lucrări și câteva recenzii au fost dedicate graficelor fără gheare [2] .

Exemple

• Graficul de linii L ( G ) al oricărui grafic G nu are gheare. L ( G ) conține un vârf pentru fiecare arc în G și vârfurile sunt conjugate în L ( G ) când muchiile corespunzătoare împărtășesc un vârf în G . Graficul de linii L ( G ) nu poate avea gheare, deoarece dacă fiecare dintre cele trei muchii e 1 , e 2 și e 3 din G are un vârf comun cu a patra muchie e 4 , atunci după principiul Dirichlet există cel puțin 2 muchiile de la e 1 , e 2 şi e 3 au un vârf comun. Graficele cu linii pot fi descrise prin nouă subgrafe interzise [3] și gheara este cea mai simplă dintre aceste nouă grafice. Aceasta oferă un motiv pentru studierea graficelor fără gheare [1] .

• Graficele De Bruijn (grafice ale căror vârfuri corespund șirurilor binare de n -biți pentru unele n și ale căror arce corespund potrivirilor de ( n −1)-biți) nu au gheare. O modalitate de a arăta acest lucru este de a construi graficul de Bruijn pentru șiruri de n -biți ca graficul de linii de Bruijn pentru șiruri de ( n - 1) biți.
• Complementul oricărui graf fără triunghi nu are gheare [4] . Aceste grafice includ orice grafic complet ca caz special.
• Graficele cu intervale proprii  sunt grafice cu intervale formate ca grafice ale intersecțiilor prin familii de intervale în care niciun interval nu conține un alt interval al familiei; nu au gheare, deoarece patru astfel de intervale nu se pot intersecta într-un model de gheare [4] .
• Axul lui Moser  este un grafic cu șapte vârfuri, care este folosit pentru a demonstra că limita inferioară a numărului cromatic al planului nu are gheare.
• Graficele unor poliedre și politopi nu au gheare. Aceasta include graficul unui tetraedru și, în general, orice simplex (graf complet), graficul unui octaedru și, în general, orice politop încrucișat ( izomorf cu graficul cocktail party , care se obține prin eliminarea unei potriviri perfecte dintr-un grafic complet), graficul unui icosaedru regulat [5] , și un număr de șaisprezece celule .
• Graficul Schläfli , un graf puternic regulat cu 27 de vârfuri, nu are gheare [5] .

Recunoaștere

Se poate verifica direct că un graf dat cu n vârfuri și m muchii nu are gheare în timp O( n 4 ) verificând la fiecare patru vârfuri pentru a vedea dacă generează o gheare [6] . Ceva mai eficient, dar mai dificil, se poate verifica dacă un graf nu are gheare verificând pentru fiecare vârf al grafului că complementul grafului vecin al vârfului nu conține un triunghi. Un grafic conține un triunghi dacă și numai dacă cubul matricei de adiacență conține un element diagonal diferit de zero, deci căutarea unui triunghi se poate face în același timp asimptotic ca înmulțirea matricei n  ×  n [7] . Astfel, folosind algoritmul Coppersmith-Winograd , timpul total pentru a determina dacă un grafic are gheare va fi O( n 3,376 ).

Kloks, Kratsch și Müller ( Kloks, Kratsch, Müller ) [8] au atras atenția asupra faptului că într-un graf fără gheare fiecare vârf are un maxim de vecini, în caz contrar, conform teoremei Turan , vecinătatea vârfului nu va avea suficiente muchii pentru a forma complementul graficului fără triunghiuri. Această observație ne permite să verificăm vecinii folosind algoritmul de produs matrice rapid menționat anterior în același timp asimptotic . Cel mai rău caz al acestui algoritm apare atunci când vârfurile Ω(√ m ) au fiecare vecin Ω(√ m ) , iar vârfurile rămase au puține vecine, caz în care timpul total este ( m 3.376/2 ) = O( m 1.688 ).

Enumerare

Deoarece graficele fără gheare includ toate complementele graficelor fără triunghi, numărul de grafice fără gheare cu n vârfuri crește cel puțin la aceeași rată cu numărul de grafice fără triunghi, adică exponențial de la rădăcina lui n . Numărul de grafice fără gheare conectate cu n muchii, pentru n = 1, 2, …

1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, ... secvența OEIS A022562 .

Dacă graficele pot fi deconectate, numărul de grafice este mai mare:

1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... secvența OEIS A086991 .

Tehnica lui Palmer, Read, Robinson ( Palmer, Read, Robinson, 2002 ) [9] face posibilă calcularea numărului de grafice cubice fără gheare foarte eficient, ceea ce este neobișnuit pentru problemele de enumerare a graficelor .

Potrivire

Sumner ( Sumner, 1974 ) [10] și, în mod independent, Las Vergnas ( Las Vergnas, 1975 ) [11] au demonstrat că orice graf conex fără gheare cu un număr par de vârfuri are o potrivire perfectă [12] . Adică, există un set de muchii în grafic astfel încât fiecare vârf să fie vârful de capăt al exact o muchie din potrivire. Rezultă de aici că pentru graficele de linii cu un număr par de muchii, este posibil să se împartă toate muchiile pe o cale de lungimea doi. Potrivirile perfecte pot fi folosite pentru o altă caracteristică a graficelor fără gheare - acestea sunt exact acele grafice în care orice subgraf generat conectat de ordine pară are o potrivire perfectă [12] .

Dovada lui Sumner arată, strict vorbind, că în orice graf conex fără gheare se poate găsi o pereche de vârfuri conjugate a căror eliminare lasă graful conectat. Pentru a demonstra acest lucru, Sumner găsește o pereche de vârfuri u și v care sunt cât mai îndepărtate una dintre ele și alege w dintre vecinii vârfului v care este cât mai departe de u . După cum a arătat, nici v , nici w nu se pot afla pe calea cea mai scurtă de la orice alt vârf la u , așa că eliminarea v și w lasă graficul conectat. Îndepărtarea succesivă a unor astfel de perechi formează o potrivire perfectă într-un grafic fără gheare.

Aceeași idee a demonstrației funcționează în cazul mai general: dacă u  este orice vârf, v  este orice vârf care este cât mai departe posibil de u și w  este orice vârf vecin al lui v care este cât mai departe posibil de u . Acum eliminarea v și w din grafic nu modifică distanțele la u . Astfel, procesul de formare a potrivirilor prin găsirea și eliminarea perechilor de vw care sunt la distanță maximă de u poate fi finalizat în timp liniar prin simpla parcurgere a arborelui de căutare în lățime , începând de la vârful u . Chrobak, Naor și Novick ( 1989 ) [13] au oferit un alt algoritm liniar în timp bazat pe căutarea depth-first , precum și algoritmi eficienți paraleli pentru aceeași problemă.

Faudree , Flandrin, Ryjáček [2] au dat mai multe rezultate strâns legate, inclusiv următoarele:

1. Un graf conectat ( r − 1) care nu conține K 1, r subgrafe de ordin impar are potriviri perfecte pentru orice r ≥ 2.
2. Graficele de ordine impară fără gheare cu cel mult un vârf de grad unu pot fi împărțite într-un ciclu impar și o potrivire.
3. Pentru orice k care este cel puțin jumătate din gradul minim al unui graf fără gheare în care fie k , fie numărul de vârfuri este par, graficul are un factor k .
4. Dacă un grafic fără gheare este ( 2k + 1)-conectat, atunci orice potrivire k -muchie poate fi extinsă la o potrivire perfectă.

Seturi independente

O mulțime independentă într-un grafic cu linii corespunde unei potriviri în graficul original, adică unui set de muchii în care două muchii nu au un punct comun. După cum a arătat Edmonds ( 1965) [14] , potrivirea maximă în orice grafic poate fi găsită în timp polinomial; Sbihi ( 1980 ) [15] a extins acest algoritm astfel încât noul algoritm găsește mulțimea independentă maximă în orice graf fără gheare [16] . Minty ( Minty, 1980 ) [17] (corectat de Nakamura și Tamura ( Nakamura, Tamura, 2001 ) [18] ) a dat o altă extensie a algoritmilor lui Edmond pentru grafice fără gheare, care transformă problema în potrivire într-un grafic auxiliar obținut din grafic original fără gheare . Abordarea lui Minty poate fi folosită pentru a rezolva problema mai generală a găsirii unui set independent de greutate maximă în timp polinomial. Există o generalizare a acestor rezultate la o clasă largă de grafice [16] .

După cum a observat Sbihi, dacă  este o mulțime independentă într-un graf fără gheare, atunci orice vârf al grafului poate avea cel mult două vârfuri învecinate din  trei vârfuri învecinate ar forma o gheară. Sbihi numește un vârf saturat dacă are doi vecini din și nesaturat dacă nu aparține și în același timp are mai puțin de doi vecini din . Din observația lui Sbyha rezultă că dacă și există mulțimi independente, graficul generat de , trebuie să aibă gradul cel mult doi. Astfel, este uniunea de căi și cicluri. În special, dacă  nu este o mulțime independentă maximă, aceasta diferă de orice mulțime independentă maximă prin cicluri și căi complementare , adică căi în care vârfuri din și nu din alterne și pentru care ambele vârfuri finale nu sunt saturate. Diferența simetrică a graficelor și calea de completare este mulțimea independentă maximă (Diferența simetrică a graficelor H și G având același set de vârfuri V este un grafic cu același set de vârfuri V, care conține muchiile G și H, dar care nu conține muchii comune aparținând atât lui G cât și lui H). Algoritmul lui Sbiha mărește în mod incremental dimensiunea setului independent prin găsirea de căi complementare , atâta timp cât astfel de căi pot fi găsite.

Găsirea unei căi de creștere este dificilă deoarece este posibil ca o extensie de cale să nu existe dacă conține o margine între două vârfuri care nu aparțin . Din fericire, acest lucru se poate întâmpla doar în două cazuri: două vârfuri adiacente pot fi vârfurile finale ale căii sau există un vârf între ele care este adiacent ambelor. Orice alt vârf adiacent va duce la o gheară. Nodurile terminale adiacente pot fi eliminate prin eliminarea temporară a tuturor vârfurilor v adiacente înainte de a căuta o cale de completare care începe la v . Dacă calea nu este găsită, vârful v poate fi îndepărtat din grafic până la sfârșitul algoritmului. După o astfel de reducere a grafului, problema poate fi descrisă în termenii unui graf comutator , deși Sbihy nu a folosit această terminologie. Un grafic de comutare este un grafic nedirecționat în care arcele oricărui vârf sunt împărțite în două grupuri, iar orice cale care trece prin vârf trebuie să conțină muchii din ambele grupuri. Este posibil să se construiască un graf comutator pe mulțimea de vârfuri saturate și nesaturate ale unui graf fără gheare ale cărui muchii leagă vârfurile dacă nu sunt adiacente în graficul original și există o cale de lungime 2 între ele care trece printr-un vârf de la I. . Cele două seturi de muchii de la fiecare vârf sunt formate din cele două vârfuri I prin care trec aceste căi de lungime 2. Calea din graficul de comutare între două vârfuri nesaturate corespunde căii complementare din graficul original. Graficul de comutare are complexitate pătratică și calea în el poate fi găsită în timp liniar, iar pentru tot timpul algoritmului poate fi necesar să se găsească căi de completare a O( n ). Astfel, algoritmul lui Sbiha necesită timp de rulare O( n 3 ).

Colorare, clicuri și dominare

Un grafic perfect  este un grafic în care numărul cromatic și dimensiunea clicei maxime sunt egale și în care această egalitate există în orice subgraf indus. [ _ _ _ _ _ 5] . Cu toate acestea, timp de mulți ani, acest fapt a rămas o presupunere, dovedită doar pentru subclase speciale de grafice. O astfel de subclasă a fost familia grafurilor fără gheare – câțiva autori au descoperit că grafurile fără gheare și fără cicluri impare și găuri sunt perfecte. Perfecțiunea unui grafic fără gheare poate fi verificată în timp polinomial. Într-un graf perfect fără gheare, vecinătatea oricărui vârf formează complementul unui graf bipartit . Puteți colora un grafic perfect fără gheare sau puteți găsi clica maximă în el în timp polinomial [19] .

Dacă graficul fără gheare nu este perfect, problema găsirii clicei maxime devine NP-hard [6] . Problema găsirii colorării optime a unui astfel de grafic este, de asemenea, NP-hard, întrucât (prin graficul liniare) această problemă generalizează problema NP-hard a calculării numărului cromatic al unui grafic [6] . Din același motiv, este NP-greu să găsești un algoritm de colorare a cărui eficiență garantată este mai bună decât 4/3. Cu toate acestea, o eficiență garantată de doi poate fi obținută în algoritmul de colorare lacom , deoarece numărul cromatic al unui grafic fără gheare este mai mare de jumătate din puterea sa maximă.

Deși nu toate graficele fără gheare sunt perfecte, graficele fără gheare satisfac o altă proprietate legată de perfecțiune. Un graf se numește graf de dominație perfectă dacă are o mulțime dominantă minimă , care este o mulțime independentă de vârfuri și dacă toate subgrafele generate au aceeași proprietate. Graficele fără erupții au această proprietate. Pentru a arăta acest lucru, să presupunem că D  este o mulțime dominantă într-un grafic fără gheare și să fie v și w  două vârfuri conjugate ale lui D . Atunci mulțimea de vârfuri dominate de v dar nu de w trebuie să fie o clică (altfel v ar fi centrul ghearei). Dacă fiecare vârf al acestei clici este deja dominat de cel puțin un membru al lui D , atunci v poate fi îndepărtat pentru a genera o mulțime dominantă independentă mai mică. În caz contrar, v poate fi înlocuit cu unul dintre vârfurile nedominate din clică, generând o mulțime dominantă cu mai puține vârfuri adiacente. Repetând aceste substituții, vom ajunge la o mulțime dominantă nu mai mare decât D , astfel încât dacă D inițial  este mulțimea dominantă minimă, procesul se va termina cu o mulțime dominantă independentă de dimensiuni egale [20] .

În ciuda proprietății de dominanță perfectă, determinarea mărimii mulțimii dominante minime într-un grafic fără gheare este o problemă NP-hard [6] . Totuși, spre deosebire de clasele mai generale de grafice, găsirea mulțimii dominante minime într-un graf fără gheare are complexitate parametrică cu parametri fiși  — problema poate fi rezolvată în timp care depinde polinom de dimensiunea graficului și exponențial de mărimea setului dominant [21] [22 ] .

Structura

Într-o serie de lucrări, Chudnovskaya și Seymour [23] au demonstrat o teorie a grafurilor structurale fără gheare, similară cu teorema structurii grafurilor pentru familiile de grafuri minore-închise demonstrate de Robertson și Seymour , și teoria structurală pentru grafurile perfecte pe care Chudnovsky ), Seymour și coautorii lor obișnuiau să demonstreze teorema grafului strict perfect [5] . Teoria este prea complexă pentru a fi descrisă în detaliu aici, dar pentru a-i arăta frumusețea, descriem câteva dintre rezultatele lor. În primul rând, pentru o subclasă specială de grafuri fără gheare, pe care le-au numit grafuri cvasi-linii (sau grafuri cvasi-bipartite local), ei susțin că fiecare astfel de graf are una dintre cele două forme:

1. Un grafic de interval circular fuzzy  este o clasă de grafice care pot fi reprezentate geometric ca puncte și arce pe un cerc.
2. Un grafic care poate fi construit dintr-un multigraf prin înlocuirea fiecărei muchii cu un grafic de interval liniar fuzzy . Acest lucru generalizează construcția graficelor de linii, în care fiecare muchie a multigrafului este înlocuită cu un vârf. Graficele cu intervale liniare fuzzy sunt construite în același mod ca și graficele cu intervale circulare fuzzy, numai pe un segment și nu pe un cerc.

Chudnovskaya și Seymour au clasificat graficele conexe arbitrare fără gheare, după cum urmează:

1. Șase grafice specifice fără gheare. Trei dintre ele sunt grafice cu linii, unele grafice cu arc și subgrafe generate ale icosaedrului . Celelalte trei necesită definiții suplimentare.
2. Grafice formate în patru moduri simple din grafice mai mici fără gheare.
3. Graficele antiprismatice  , o clasă de grafice dense , sunt definite ca grafice fără gheare în care oricare patru vârfuri generează un subgraf cu cel puțin două muchii.

Majoritatea lucrărilor lor de clasificare este dedicată analizei graficelor antiprismatice. Graficul Schläfli , un graf fără gheare puternic regulat cu parametrii srg(27,16,10,8), joacă un rol important în această parte a analizei. Această teorie structurală a condus la noi progrese în combinatoria poliedrelor și noi limite ale numerelor cromatice ale grafurilor fără gheare [5] , precum și noi algoritmi de complexitate parametrică cu parametri fixe pentru mulțimi dominante în grafurile fără gheare [22] .

Note

1. ↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , p. 88.
2. ↑ 1 2 Faudree, Flandrin, Ryjáček, 1997 .
3. ↑ LW Beineke. Beitrage zur Graphentheorie. - Teubner, 1968. - S. 17-33 .
4. ↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , p. 89.
5. ↑ 1 2 3 4 5 Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Teorema grafului perfect puternic. - 2006. - T. 164 , nr. 1 . - S. 51-229 . doi : 10.4007 / anals.2006.164.51 .
6. ↑ 1 2 3 4 Faudree, Flandrin, Ryjáček, 1997 , p. 132.
7. ↑ Alon Itai, Michael Rodeh. Găsirea unui circuit minim într-un grafic // SIAM Journal on Computing . - 1978. - V. 7 , nr. 4 . - S. 413-423 . - doi : 10.1137/0207033 .
8. ↑ Ton Kloks, Dieter Kratsch, Haiko Müller. Găsirea și numărarea eficientă a subgrafelor mici induse // Litere de procesare a informațiilor. - 2000. - T. 74 , nr. 3-4 . - S. 115-121 . - doi : 10.1016/S0020-0190(00)00047-8 .
9. ↑ Edgar M. Palmer, Ronald C. Read, Robert W. Robinson. Numărarea graficelor cubice fără gheare // SIAM Journal on Discrete Mathematics . - 2002. - T. 16 , nr. 1 . - S. 65-73 . - doi : 10.1137/S0895480194274777 .
10. ↑ David P. Sumner. Grafice cu 1-factori. - 1974. - T. 42 , nr. 1 . - S. 8-12 . - doi : 10.2307/2039666 . — .
11. ↑ M. Las Vergnas. O notă despre potrivirile din grafice // Cahiers du Centre d'Études de Recherche Opérationnelle. - 1975. - T. 17 , nr. 2-3-4 . - S. 257-260 .
12. ↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , p. 120-124.
13. ↑ Marek Chrobak, Joseph Naor, Mark B. Novick. Algoritmi și structuri de date : Workshop WADS '89, Ottawa, Canada, august 1989, Proceedings. - Springer, 1989. - T. 382 . - S. 147-162 . - doi : 10.1007/3-540-51542-9_13 .
14. ↑ Jack Edmonds. Cărări, copaci și flori // Canadian J. Math. - 1965. - T. 17 , nr. 0 . - S. 449-467 . - doi : 10.4153/CJM-1965-045-4 .
15. ↑ Najiba Sbihi. Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile // Discrete Mathematics. - 1980. - T. 29 , nr. 1 . - S. 53-76 . - doi : 10.1016/0012-365X(90)90287-R .
16. ↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , p. 133-134.
17. ↑ George J. Minty. Pe seturi independente maxime de vârfuri în grafice fără gheare // Journal of Combinatorial Theory. Seria B. - 1980. - T. 28 , nr. 3 . - S. 284-304 . - doi : 10.1016/0095-8956(80)90074-X .
18. ↑ Daishin Nakamura, Akihisa Tamura. O revizuire a algoritmului lui Minty pentru găsirea unui set stabil ponderat maxim al unui grafic fără gheare // Journal of the Operations Research Society of Japan. - 2001. - T. 44 , nr. 2 . - S. 194-204 .
19. ↑ Faudree, Flandrin, Ryjáček, 1997 , p. 135-136.
20. ↑ Faudree, Flandrin, Ryjáček, 1997 , p. 124-125.
21. ↑ Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Setul dominant este un parametru fix care poate fi tratat în grafice fără gheare. — 2010.
22. ↑ 1 2 Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard Woeginger. Dominație când stelele sunt afară. — 2010.
23. ↑ Maria Chudnovsky, Paul Seymour. Anchete în combinatorică 2005. — Cambridge University Press, 2005. - T. 327 . - S. 153-171 .

Literatură

• Ralph Faudree, Evelyne Flandrin, Zdeněk Ryjáček. Grafice fără gheare - Un sondaj // Matematică discretă. - 1997. - T. 164 , nr. 1-3 . - S. 87-147 . - doi : 10.1016/S0012-365X(96)00045-3 .

Link -uri

• Grafice fără gheare , Sistem de informații privind incluziunile claselor de grafice
• Mugan, Jonathan William; Weisstein, Eric W. Claw-Free Graph  (engleză) pe site-ul Wolfram MathWorld .