From Wikipedia, the free encyclopedia
Î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.
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]
Pentru a menține o terminologie coerentă, în restul acestui articol, „ciclu” înseamnă ciclu simplu, cu excepția cazului în care se spune altfel.
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.
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]
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]
Î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]
Mai multe clase importante de grafuri pot fi definite prin ciclurile lor. De exemplu:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
