Calea generată

În teoria grafurilor, o cale generată într-un graf nedirecționat G este o cale care este un subgraf generat al lui G. Astfel, este o succesiune de vârfuri în G astfel încât oricare două vârfuri adiacente din secvență sunt conectate printr-o muchie în G și orice două vârfuri neadiacente ale secvenței nu sunt conectate printr-o muchie în G . O cale generată este uneori numită șarpe , iar problema găsirii celei mai lungi căi generate în graficele hipercube este cunoscută sub numele de problema șarpelui în cutie .

Denumit și ciclu generat este un ciclu care este un subgraf generat al lui G. Ciclurile generate sunt numite și cicluri fără coarde sau (dacă lungimea ciclului este de cel puțin patru) găuri . O antigaura este o gaură în complementul unui grafic G , adică o antigaura este complementul unei găuri.

Lungimea celei mai lungi căi generate într-un grafic este uneori numită numărul de traversare a graficului [1] . Pentru graficele rare, existența unui număr de traversare mărginit este echivalentă cu existența unei adâncimi de arbore mărginite [2] . Numărul de traversare generat al unui grafic G este cel mai mic număr de subseturi de vârfuri în care pot fi descompuse vârfurile graficului, astfel încât fiecare submulțime să formeze o cale generată [3] , iar acest concept este strâns legat de numărul de acoperire a căii. - numărul minim de căi deconectate care sunt generate subgrafe ale lui G , acoperind toate vârfurile G [4] . Circumferința unui grafic este lungimea celui mai scurt ciclu al său, dar acest ciclu trebuie să fie un ciclu generat, deoarece orice coardă ar putea forma un ciclu mai scurt. Din aceleași motive, circumferința impară a unui grafic este lungimea celui mai scurt ciclu impar generat.

Exemplu

Figura prezintă un cub, un grafic cu opt vârfuri, douăsprezece muchii și o cale generată de lungimea patru. Analiza directă arată că nu mai există o cale generată în cub, deși există un ciclu generat de lungimea șase. Problema găsirii celui mai mare drum sau ciclu generat într-un hipercub, pusă pentru prima dată de Kautz [5] , este cunoscută sub numele de problema șarpelui într-o cutie și a fost studiată pe larg datorită utilizării sale în teoria și construcția codificării.

Descrierea familiilor de grafice

Multe familii importante de grafice pot fi descrise în termeni de trasee sau cicluri generate ale graficelor din familie.

Algoritmi și complexitate

Problema determinării dacă un grafic G are o cale generată de lungime de cel puțin k este NP-complet. Gary și Johnson [6] au exprimat acest rezultat într-o comunicare nepublicată către Michalis Giannakakis . Totuși, această problemă poate fi rezolvată în timp polinomial pentru anumite familii de grafice, cum ar fi grafice fără triple de asteroizi [7] sau grafice fără găuri lungi [8] .

Este, de asemenea, o problemă NP-complet să se determine dacă vârfurile unui graf pot fi descompuse în două căi generate sau două cicluri generate [9] . În consecință, determinarea numărului de căi generate într-un grafic este o problemă NP-hard.

Complexitatea problemei aproximării celui mai mare drum sau ciclu generat poate fi asociată cu problema găsirii celor mai mari mulțimi independente în grafice [10] .

Găurile (și antigăurile în graficele fără cicluri de lungime 5 fără coarde) într-un grafic cu n vârfuri și m muchii pot fi găsite în timp (n+m 2 ) [11] .

Cicluri atomice

Ciclurile atomice sunt o generalizare a ciclurilor fără coarde. Dacă este dat un ciclu, o coardă n este definită ca o cale de lungime n care conține două puncte de ciclu, unde n este mai mică decât lungimea celei mai scurte căi din ciclul care leagă acele puncte. Dacă un ciclu nu are n acorduri, se numește ciclu atomic deoarece nu poate fi descompus în cicluri mai mici [12] . În cel mai rău caz, ciclurile atomice dintr-un grafic pot fi enumerate în timp O( m 2 ), unde m este numărul de muchii din grafic.

Note

  1. ↑ Buckley, Harary, 1988 .
  2. ↑ Nešetřil, Ossona de Mendez, 2012 , Propunerea 6.4, p. 122.
  3. ↑ Chartrand și colab., 1994 .
  4. ↑ Barioli, Fallat, Hogben, 2004 .
  5. ↑ Kautz, 1958 .
  6. ↑ Garey, Johnson, 1979 .
  7. ↑ Kratsch, Müller, Todinca, 2003 .
  8. ↑ Gavril, 2002 .
  9. ↑ Le, Le, Müller, 2003 .
  10. ↑ Berman, Schnitger, 1992 .
  11. ↑ Nikolopoulos, Palios, 2004 .
  12. ↑ Gashler, Martinez, 2012 .

Literatură