Ciclu (teoria grafurilor)

În teoria grafurilor, un ciclu este un drum format din muchii și noduri, în care de la un nod se ajunge la el însuși.

Un ciclu orientat într-un graf orientat este un drum orientat nevid în care se repeta doar primul și ultimul nod.

Un graf fără cicluri se numește graf aciclic. Un graf orientat fără cicluri orientate se numește graf orientat aciclic^⁠(d). Un graf conex fără cicluri se numește arbore.

Definiții

Un drum închis constă dintr-o secvență de noduri care pornește și se termină în același nod, cu fiecare două noduri consecutive din secvență fiind adiacente reciproc în graf. Într-un graf orientat, fiecare muchie trebuie să fie parcursă în direcția sa: muchia trebuie să fie orientată de la primul din cele două noduri consecutive la al doilea. Alegerea nodului de început nu este importantă: dacă se parcurge aceeași secvență ciclică pornind din noduri diferite, rezultă același drum închis.

Un ciclu simplu poate fi definit fie ca un drum închis în care nu se acceptă repetiții de noduri sau muchii, altele decât repetarea la sfârșit a nodului de început, sau ca o mulțime de muchii într-un astfel de drum. Cele două definiții sunt echivalente în grafurile orientate, unde ciclurile simple se numesc și cicluri orientate: secvența ciclică de noduri și muchii într-un drum este complet determinată de mulțimea muchiilor pe care le folosește. În grafurile neorientate, mulțimea muchiilor unui ciclu poate fi parcursă cu un drum în oricare dintre cele două direcții, oferind două cicluri orientate posibile pentru fiecare ciclu neorientat. (Pentru drumurile închise în general, în grafuri orientate sau neorientate, multimulțimea muchiilor nu determină fără echivoc ordonarea nodurilor.) Un circuit poate fi un drum închis ce permite repetări de noduri, dar nu de muchii; cu toate acestea, acesta poate fi tot un ciclu simplu, astfel că la orice folosire a noțiunii, este necesară o definiție explicită.^[1]

În acest graf, ciclul verde (A-B-C-D-E-F-A) este indus, pe când cel roșu (G-H-I-J-K-L-G) nu este, deoarece muchia K-I este o coardă.

Pentru a menține o terminologie coerentă, în restul acestui articol, „ciclu” înseamnă ciclu simplu, cu excepția cazului în care se spune altfel.

Cicluri induse

Un ciclu indus^⁠(d) (numit și ciclu cu coardă) într-un graf este un ciclu astfel încât nu există două noduri conectate printr-o muchie dacă muchia respectivă nu face parte din ciclu. Ciclurile induse pot fi utilizate pentru a caracteriza grafurile perfecte^⁠(d): conform teoremei tari a grafurilor perfecte^⁠(d), un graf este perfect dacă și numai dacă niciunul dintre ciclurile induse și complementele lor nu au un număr impar de noduri mai mare ca trei. Un graf indus^⁠(d), un tip special de graf perfect, nu are cicluri induse de dimensiune mai mare ca trei.

Calibrul^⁠(d) unui graf este lungimea celui mai scurt ciclu al său; acest ciclu este obligatoriu indus. Cuștile^⁠(d) sunt definite ca cele mai mici grafuri regulate cu o anumită combinație de grad și calibru.

Un ciclu periferic este un ciclu care are proprietatea că orice două muchii care nu sunt în ciclu pot fi conectate printr-un drum ale cărui noduri interioare evită ciclul. Într-un graf care nu este format prin adăugarea unei muchii la un ciclu, un ciclu periferic este obligatoriu indus.

Spațiul ciclurilor

Termenul de ciclu se poate referi și la un element al spațiului ciclurilor^⁠(d) unui graf. Există multe spații de cicluri, câte unul pentru fiecare corp sau inel. Cel mai frecvente este spațiul binar al ciclurilor (numit de regulă spațiu de cicluri), care este format din mulțimile de muchii ale căror noduri au grad par; mulțimea formează un spațiu vectorial peste corpul cu două elemente. Conform teoremei lui Veblen^⁠(d), fiecare element al spațiului ciclurilor poate fi format ca o reuniune cu muchii disjuncte a ciclurilor simple. O bază de cicluri^⁠(d) a grafului este o mulțime de cicluri simple ce formează o bază în spațiul ciclurilor.^[2]

Folosind idei din topologia algebrică, spațiul binar al ciclurilor se generalizează la spații vectoriale sau module^⁠(d) peste alte inele, cum ar fi numerele întregi, numerele raționale sau reale etc.^[3]

Detecția ciclurilor

Existența unui ciclu în grafuri orientate și neorientate poate fi determinată prin efectuarea unei căutări în adâncime (DFS), verificând dacă se găsește o muchie care duce la un strămoș al nodului curent în arborele de căutare (adică acesta conține o muchie înapoi).^[4] Într-un graf neorientat, găsirea oricărui nod deja vizitat indică o muchie înapoi. Toate muchiile înapoi peste care DFS sare fac parte din cicluri.^[5] În cazul grafurilor neorientate, este necesar doar un timp O(n) pentru a găsi un ciclu într-un graf cu n noduri, deoarece cel mult n − 1 muchii pot fi muchii de arbore.

Mulți algoritmi de sortare topologică^⁠(d) vor detecta ciclurile, deoarece acestea sunt obstacole față de existența ordinii topologice. De asemenea, dacă un graf orientat a fost împărțit în componente tare conexe^⁠(d), există cicluri doar în cadrul componentelor și nu între ele, deoarece ciclurile sunt tare conexe.

Pentru grafuri orientate, algoritmul Rocha–Thatte^⁠(d)^[6] este un algoritm distribuit de detecție a ciclurilor. Algoritmii distribuiți de detecție a ciclurilor sunt utile pentru prelucrarea grafurilor mari folosind un sistem distribuit de prelucrare a grafurilor pe un cluster de calculatoare^⁠(d) (sau pe un supercomputer).

Printre aplicațiile detecției ciclurilor se numără identificarea blocajelor^⁠(d) în sistemele concurente.^[7]

Acoperirea grafurilor prin cicluri

În lucrarea sa din 1736 despre cele șapte poduri din Königsberg, considerată a fi actul de naștere a teoriei grafurilor, Leonhard Euler a demonstrat că, pentru ca un graf neorientat finit să aibă un drum închis care vizitează fiecare muchie exact o dată, este necesar și suficient ca acesta să fie conex cu excepția nodurilor izolate (adică toate muchiile să facă parte din aceeași componentă conexă) și ca fiecare nod să aibă grad par. Caracterizarea corespunzătoare pentru existența unui drum închis ce vizitează fiecare muchie exact o dată într-un graf orientat este ca graficul să fie tare conex^⁠(d) și să aibă un număr egal de muchii care intră și care ies din fiecare nod. În orice caz, drumul rezultat se numește ciclu eulerian. Dacă un graf neorientat finit are grad par la toate nodurile, indiferent dacă este conex sau nu, atunci este posibil să se găsească o mulțime de cicluri simple care împreună acoperă toate muchiile exact o dată: aceasta este teorema lui Veblen^⁠(d).^[8] Când un graf conex nu îndeplinește condițiile teoremei lui Euler, se poate găsi un drum închis de lungime minimă care acoperă fiecare muchie cel puțin o dată în timp polinomial prin rezolvarea problemei inspecției drumurilor^⁠(d).

Problema de a găsi un singur ciclu simplu care acoperă o singură dată toate nodurile, și nu muchiile, este mult mai grea. Un astfel de ciclu se numește ciclu hamiltonian și determinarea existenței lui este NP-completă.^[9] S-au publicat multe cercetări referitoare la clasele de grafuri care conțin în mod garantat cicluri hamiltoniene; un exemplu este teorema lui Ore, conform căreia se poate găsi întotdeauna un ciclu hamiltonian într-un graf pentru care suma gradelor oricărei perechi de noduri neadiacente este cel puțin numărul total de noduri din graf.^[10]

Conjectura dublei acoperiri cu cicluri prevede că, pentru fiecare graf fără punți, există o multimulțime de cicluri simple care acoperă toate muchiile grafului exact de două ori. Demonstrarea că acest lucru este adevărat (sau găsirea unui contraexemplu) rămâne o problemă deschisă.^[11]

Clase de grafuri definite cu ajutorul noțiunii de ciclu

Mai multe clase importante de grafuri pot fi definite prin ciclurile lor. De exemplu:

Graful bipartit, un graf fără cicluri impare.
Graful cactus^⁠(d), un graf în care fiecare componentă netrivială biconexă este un ciclu
Graful ciclu^⁠(d), un graf care constă dintr-un singur ciclu.
Graf indus^⁠(d) (cordal), un graf în care orice ciclu indus este un triunghi
Graf orientat aciclic^⁠(d), un graf fără cicluri
Graf linie perfect^⁠(en)^[traduceți], un graf în care orice ciclu impar este un triunghi
Graf perfect^⁠(d), un graf fără cicluri induse și fără complemente de grafuri induse de lungime mai mare ca trei
Pseudopădure^⁠(d), un graf în care orice componentă conexă are cel mult un singur ciclu
Graf strangulat^⁠(d), un graf în care orice ciclu periferic este un triunghi
Graf tare conex^⁠(d), un graf orientat în care orice muchie face parte dintr-un ciclu
Graf fără triunghiuri^⁠(d), un graf fără cicluri de trei noduri

Bibliografie

^ Balakrishnan, V.K. (2005). Schaum's outline of theory and problems of graph theory (ed. [Nachdr.].). McGraw–Hill. ISBN 978-0070054899.
^ Gross, Jonathan L.; Yellen, Jay (2005), „4.6 Graphs and Vector Spaces”, Graph Theory and Its Applications (ed. 2nd), CRC Press, pp. 197–207, ISBN 9781584885054 Mai multe valori specificate pentru |ISBN= și |isbn= (ajutor)
^ Diestel, Reinhard (2012), „1.9 Some linear algebra”, Graph Theory, Graduate Texts in Mathematics, 173, Springer, pp. 23–28 .
^ Tucker, Alan (2006). „Chapter 2: Covering Circuits and Graph Colorings”. Applied Combinatorics (ed. 5th). Hoboken: John Wiley & sons. p. 49. ISBN 978-0-471-73507-6.
^ Sedgewick, Robert (1983), „Graph algorithms”, Algorithms, Addison–Wesley, ISBN 0-201-06672-6 Mai multe valori specificate pentru |ISBN= și |isbn= (ajutor)
^ Rocha, Rodrigo Caetano; Thatte, Bhalchandra (2015), Distributed cycle detection in large-scale sparse graphs (PDF), Simpósio Brasileiro de Pesquisa Operacional (SBPO)
^ Silberschatz, Abraham; Peter Galvin; Greg Gagne (2003). Operating System Concepts. John Wiley & Sons, INC. p. 260. ISBN 0-471-25060-0. Mai multe valori specificate pentru |autor2= și |nume2= (ajutor); Mai multe valori specificate pentru |autor3= și |nume3= (ajutor)
^ Veblen, Oswald (1912), „An Application of Modular Equations in Analysis Situs”, Annals of Mathematics^⁠(d), Second Series, 14 (1): 86–94, doi:10.2307/1967604 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
^ Richard M. Karp (1972), „Reducibility Among Combinatorial Problems” (PDF), În R. E. Miller and J. W. Thatcher, Complexity of Computer Computations, New York: Plenum, pp. 85–103 .
^ Ore, Ø. (1960), „Note on Hamilton circuits”, American Mathematical Monthly^⁠(d), 67 (1): 55, doi:10.2307/2308928 Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor); Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
^ Jaeger, F. (1985), „A survey of the cycle double cover conjecture”, Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).

[schaum-1] Balakrishnan, V.K. (2005). Schaum's outline of theory and problems of graph theory (ed. [Nachdr.].). McGraw–Hill. ISBN 978-0070054899.

[gy-2] Gross, Jonathan L.; Yellen, Jay (2005), „4.6 Graphs and Vector Spaces”, Graph Theory and Its Applications (ed. 2nd), CRC Press, pp. 197–207, ISBN 9781584885054 Mai multe valori specificate pentru |ISBN= și |isbn= (ajutor)

[diestel-3] Diestel, Reinhard (2012), „1.9 Some linear algebra”, Graph Theory, Graduate Texts in Mathematics, 173, Springer, pp. 23–28 .

[4] Tucker, Alan (2006). „Chapter 2: Covering Circuits and Graph Colorings”. Applied Combinatorics (ed. 5th). Hoboken: John Wiley & sons. p. 49. ISBN 978-0-471-73507-6.

[sedgewick-5] Sedgewick, Robert (1983), „Graph algorithms”, Algorithms, Addison–Wesley, ISBN 0-201-06672-6 Mai multe valori specificate pentru |ISBN= și |isbn= (ajutor)

[rcor2015-6] Rocha, Rodrigo Caetano; Thatte, Bhalchandra (2015), Distributed cycle detection in large-scale sparse graphs (PDF), Simpósio Brasileiro de Pesquisa Operacional (SBPO)

[7] Silberschatz, Abraham; Peter Galvin; Greg Gagne (2003). Operating System Concepts. John Wiley & Sons, INC. p. 260. ISBN 0-471-25060-0. Mai multe valori specificate pentru |autor2= și |nume2= (ajutor); Mai multe valori specificate pentru |autor3= și |nume3= (ajutor)

[8] Veblen, Oswald (1912), „An Application of Modular Equations in Analysis Situs”, Annals of Mathematics^⁠(d), Second Series, 14 (1): 86–94, doi:10.2307/1967604 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).

[9] Richard M. Karp (1972), „Reducibility Among Combinatorial Problems” (PDF), În R. E. Miller and J. W. Thatcher, Complexity of Computer Computations, New York: Plenum, pp. 85–103 .

[10] Ore, Ø. (1960), „Note on Hamilton circuits”, American Mathematical Monthly^⁠(d), 67 (1): 55, doi:10.2307/2308928 Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor); Mai multe valori specificate pentru |DOI= și |doi= (ajutor).

[11] Jaeger, F. (1985), „A survey of the cycle double cover conjecture”, Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]