Graficul panciclic

Un graf panciclic  este un graf direcționat sau nedirecționat care conține cicluri de toate lungimile posibile de la trei până la numărul de vârfuri ale grafului [1] . Graficele panciclice sunt o generalizare a graficelor hamiltoniene , grafice care au cicluri de lungime maximă posibilă.

Definiții

Un grafic cu vârfuri este panciclic dacă, pentru oricare dintre ele, graficul conține un ciclu de lungime [1] . Un grafic este vertex-panciclic dacă, pentru orice vârf și oricare din aceleași limite, graficul conține un ciclu de lungime care conține vârful [2] . În mod similar, un grafic este muchie-panciclic dacă, pentru orice muchie și pentru oricare din aceleași limite, conține un ciclu de lungime care conține muchia [2] .

Un graf bipartit nu poate fi panciclic deoarece nu conține cicluri de nicio lungime impară, dar se spune că un graf este bipanciclic dacă conține cicluri de toate lungimile pare de la 4 la [3] .

Grafice plane

Un grafic maxim exterior planar  este un grafic format dintr -un poligon simplu în plan prin triagularizarea interiorului acestuia. Orice grafic maxim exterior planar este panciclic, care poate fi arătat prin inducție. Fața exterioară a graficului este un ciclu cu n vârfuri, iar ștergerea oricărui triunghi conectat la restul graficului printr-o singură muchie (o frunză a arborelui care formează graficul de triunghiulare dublă ) formează un grafic maxim exterior planar cu un număr mai puțin. de vârfuri, iar prin presupunerea inductivă acest grafic are toate ciclurile de toate lungimile rămase. Dacă se acordă mai multă atenție alegerii triunghiului de eliminat, atunci aceleași argumente arată rezultatul mai riguros că orice graf maxim exterior planar este vârf-panciclic [4] . Același lucru este valabil și pentru graficele care au un graf maxim exterior planar ca subgraf de întindere , în special pentru roți .

Un graf planar maximal  este un graf plan în care toate fețele, inclusiv cea exterioară, sunt triunghiuri. Un graf planar maximal este vertex-panciclic dacă și numai dacă conține un ciclu hamiltonian [5]  — dacă nu este hamiltonian, cu siguranță nu este panciclic, iar dacă este hamiltonian, atunci interiorul ciclului hamiltonian formează fața exterioară a grafului maxim exterior planar la aceleași vârfuri și muchii, la care se pot aplica argumentele anterioare pentru grafurile exterioare [6] . De exemplu, în figură[ ce? ] arată panciclicitatea grafului octaedric , un graf planar maximal hamiltonian cu șase vârfuri. Mai strict, din aceleași motive, dacă un graf planar maximal are un ciclu de lungime , el are cicluri de toate lungimile mai mici [7] .

Graficele Halin sunt grafice plane formate dintr-un desen plan al unui copac fără vârfuri de gradul doi, prin adăugarea unui ciclu care leagă frunzele copacului. Graficele halin nu sunt neapărat panciclice, dar sunt aproape panciclice în sensul că nu există un ciclu de cel mult o lungime. Lungimea ciclului lipsă este în mod necesar egală. Dacă niciunul dintre vârfurile interne ale grafului Halin nu are gradul trei, atunci graficul este în mod necesar panciclic [8] .

În 1971, s-a remarcat [1] că multe condiții clasice pentru existența unui ciclu hamiltonian sunt, de asemenea, suficiente pentru panciclicitate și, prin urmare, s-a presupus că orice graf planar cu 4 conexiuni este panciclic, dar s-a găsit în curând o familie de contraexemple . 9] .

Turnee

Un turneu  este un grafic direcționat cu un arc direcționat între orice pereche de vârfuri. În mod intuitiv, un turneu poate fi folosit pentru a simula un round robin desenând un arc de la câștigător la învins pentru fiecare joc din competiție. Se spune că un turneu este puternic conectat sau pur și simplu puternic dacă și numai dacă nu poate fi împărțit în două subseturi nevide de perdanți și câștigători, astfel încât orice participant învinge orice participant în [10] . Orice turneu puternic este panciclic [11] și panciclic vertex [12] . Dacă un turneu este obișnuit (orice participant are același număr de câștiguri și pierderi ca alți participanți), atunci este și edge-panciclic [13] , dar turneele puternice cu patru vârfuri nu pot fi edge-panciclice.

Grafice cu un număr mare de muchii

Teorema lui Mantel afirmă că orice grafde vârf nedirecționat care are cel puținmuchii și nu are mai multe muchii sau bucle fie conține un triunghi, fie este un graf bipartit complet . Această teoremă poate fi întărită - orice graf hamiltonian nedirecționat cu cel puținmuchii este fie panciclic, fie este [1] .

Există grafuri dirijate hamiltoniene cu vârfuri și arce care nu sunt panciclice, dar orice graf dirijat hamiltonian cu cel puțin arce este panciclic. În plus, un graf de vârfuri strict conectat în care fiecare vârf are cel puțin grad (arcurile de intrare și de ieșire sunt numărate împreună) este fie panciclic, fie este un graf bipartit complet [14] .

Gradele unui grafic

Pentru orice grafic, gradul său al graficului este definit ca un grafic pe același set de vârfuri care are o muchie între oricare două vârfuri, distanța dintre care nu depășește . Dacă vârful 2-conectat , atunci după teorema lui Fleischner este un graf hamiltonian. Afirmația poate fi întărită: graficul va fi neapărat vertex-panciclic [15] . Mai strict, dacă este hamiltonian, este și panciclic [16] .

Complexitate computațională

Testarea unui grafic pentru panciclicitate este o problemă NP-completă chiar și pentru cazul special al graficelor cubice cu 3 conexiuni . Este, de asemenea, o problemă NP-completă testarea unui grafic pentru panciclicitatea vârfurilor chiar și pentru cazul special al graficelor poliedrice [17] . De asemenea, o sarcină NP-completă este de a testa pătratul unui grafic pentru Hamiltonianitate și, astfel, și pentru a testa panciclicitatea [18] .

Istorie

Panciclicitatea a fost explorată pentru prima dată de Harari și Moser în contextul turneelor ​​[19] , precum și de Muun [20] și Alpach [13] . Conceptul de panciclicitate a fost numit de Bondi, care a extins conceptul pentru grafuri nedirecționate [1] .

Note

  1. ↑ 1 2 3 4 5 Bondy, 1971 .
  2. ↑ 1 2 Randerath, Schiermeyer, Tewes, Volkmann, 2002 .
  3. ↑ Schmeichel, Mitchem, 1982 .
  4. ↑ Li, Corneil, Mendelsohn, 2000 , Propunerea 2.5.
  5. ↑ Helden, 2007 , Corolarul 3.78.
  6. ↑ Bernhart, Kainen, 1979 .
  7. ↑ Hakimi, Schmeichel, 1979 .
  8. ↑ Skowrońska, 1985 .
  9. ↑ Malkevitch, 1971 .
  10. ↑ Harary și Moser, 1966 , Corolarul 5b.
  11. ↑ Harary și Moser, 1966 , Teorema 7.
  12. ↑ Luna, 1966 , Teorema 1.
  13. ↑ 12 Alspach , 1967 .
  14. ↑ Häggkvist, Thomassen, 1976 , p. 20–40.
  15. ↑ Hobbs (1976) .
  16. ↑ Fleischner, 1976 .
  17. ↑ Li, Corneil, Mendelsohn, 2000 , Teoremele 2.3 și 2.4.
  18. ↑ Underground (1978) .
  19. ↑ Harary, Moser, 1966 .
  20. ↑ Luna, 1966 .

Literatură

Link -uri