Graficul oblic-simetric

Un graf simetric oblic  este un graf direcționat izomorf la propriul graf transpus . Acest grafic este format prin inversarea tuturor arcelor cu izomorfism și este o involuție fără puncte fixe . Graficele cu simetrie oblică sunt identice cu acoperirile duble ale graficelor bidirecționale .

Graficele skew-symmetric au fost introduse mai întâi sub denumirea de digrafe antisimetrice de către Tutt [1] , mai târziu sub denumirea de grafice cu acoperire dublă ale graficelor polare au fost folosite de Zelinka [2] , iar mai târziu sub numele de grafice cu acoperire dublă ale graficelor bidirecționale folosit de Zaslavsky [3] . Ele apar, de exemplu, în modelarea căutării de căi și cicluri alternative , în algoritmi de găsire a potrivirilor în grafice pentru testare, în problema descompunerii unei configurații în Jocul Vieții în componente mai mici, în problema vizualizării grafice și în problema construirii graficelor de ieșire .folosit pentru a rezolva eficient problema 2-satisfiability .

Definiție

Așa cum este definit, de exemplu, de Goldberg și Karzanov [4] , un graf simetric oblic  este un graf direcționat împreună cu o funcție care mapează vârfurile graficului la celelalte vârfuri ale acestuia și satisface proprietățile:

  1. Pentru orice top
  2. Pentru orice top
  3. Pentru orice arc trebuie să fie și un arc.

Puteți folosi a treia proprietate pentru a extinde la funcția de inversare a orientării arcului grafic .

Graficul transpus al unui grafic este graficul format prin inversarea fiecărei margini a graficului și definește un izomorfism de la graficul transpus. Cu toate acestea, pentru un grafic simetric oblic, există o cerință suplimentară ca izomorfismul să ducă fiecare vârf la un alt vârf fără a permite unui vârf să se mapeze în sine sau să grupeze mai mult de două vârfuri într-un ciclu de izomorfism.

Un drum sau un ciclu într-un grafic cu simetrie oblică se spune că este regulat dacă, pentru fiecare vârf al căii sau ciclului, vârful corespunzător nu face parte din cale sau ciclu.

Exemple

Orice cale orientată cu un număr par de vârfuri este simetrică oblică, conform simetriei care schimbă cele două capete ale căii. Cu toate acestea, căile cu un număr impar de vârfuri nu sunt simetrice oblice, deoarece simetria de orientare inversă a acestui grafic mapează vârful mijlociu al acestui grafic în sine, ceea ce nu este permis pentru graficele simetrice oblice.

În mod similar, un ciclu orientat este simetric oblic dacă și numai dacă are un număr par de vârfuri. În acest caz, numărul de mapări diferite care implementează simetria oblică a graficului este egal cu jumătate din lungimea ciclului.

Grafice polare și săgeți de cale, grafice duble de acoperire și grafice bidirecționale

Un grafic skew-simetric poate fi definit în mod echivalent ca un grafic al unei acoperiri duble a unui grafic polar (introdus de Zelinka [5] [6] , iar Cook numit grafice cu săgeți de cale [7] [8] ), care sunt grafice nedirecționate și în care muchiile adiacente fiecărui vârf sunt împărțite în două submulțimi. Fiecare vârf al unui grafic polar corespunde la două vârfuri ale unui grafic cu simetrie oblică, iar fiecare muchie a unui grafic polar corespunde cu două muchii ale unui grafic cu simetrie oblică. Această echivalență a fost folosită de Goldberg și Karzanov [4] pentru a modela probleme de potrivire în termeni de grafice simetrice. Într-o astfel de aplicație, cele două subseturi de muchii de la fiecare vârf sunt muchii care se potrivesc și care nu se potrivesc. Zelinka (conform lui F. Zaitek) și Cook au vizualizat vârfurile graficului polar ca puncte în care converg mai multe șine de cale ferată  dacă un tren intră într-un comutator de cale pe o cale ferată care vine dintr-o direcție, trebuie să iasă prin șină în altă direcție. Problema găsirii unor curbe netede care nu se intersectează între punctele date ale unei căi ferate apare atunci când se verifică dacă un fel de vizualizare grafică este admisibilă [9] , și poate fi modelată ca găsirea unei căi regulate într-un grafic oblic-simetric.

Un concept strâns legat este graficul bidirecțional Edmonds și Johnson [10] (un „graf polarizat” în terminologia lui Zelinka [5] [6] ), un grafic în care fiecare dintre cele două vârfuri ale oricărei muchii poate fi fie începutul sau sfârșitul, indiferent de alt vârf. Un grafic bidirecțional poate fi interpretat ca un grafic polar dacă muchiile fiecărui vârf sunt împărțite în funcție de orientarea muchiei la acel vârf - începutul sau sfârșitul. Totuși, schimbul de roluri de început și sfârșit într-un vârf separat („comutarea” unui vârf în terminologia lui Zaslavsky [3] ) dă un alt graf bidirecțional, dar același graf polar.

Pentru corespondența dintre graficele bidirecționale și graficele skew-simetrice, vezi Zaslavsky [11] sau Babenko [12] .

Pentru a forma un grafic de acoperire dublă (adică, graficul oblic-simetric corespunzător) dintr-un grafic polar , creăm două vârfuri din fiecare vârf al graficului , și , și fie . Pentru fiecare muchie de grafic , creați două muchii direcționate în graficul de acoperire, una de la până și una de la până la . Dacă se află în primul subset de muchii în , aceste două arce merg de la la și de la la , dar dacă aparține altui submult, arcele vor fi de la la și de la la . Dimpotrivă, având în vedere un grafic simetric oblic , se poate forma un grafic polar care are un vârf pentru orice pereche corespunzătoare de vârfuri din grafic și o muchie nedirecționată pentru fiecare pereche de muchii corespunzătoare în . Muchiile nedirecționate de la fiecare vârf al graficului polar pot fi împărțite în două subseturi în funcție de care vârful graficului original pleacă și intră arcul.

O cale sau ciclu obișnuit într-un grafic cu simetrie oblică corespunde unei căi sau cicluri într-un grafic polar care utilizează cel mult o muchie din fiecare subset de muchii la fiecare dintre vârfurile sale.

Potrivire

Atunci când construiți o potrivire într-un graf nedirecționat, este important să găsiți o cale alternativă , o cale prin vârfuri care începe și se termină la vârfuri care nu aparțin potrivirii și ale cărei margini în poziții impare ale căii nu aparțin acestuia. potrivire parțială și ale căror margini în pozițiile pare ale traseului sunt margini ale potrivirii. Prin eliminarea din potrivire a muchiilor din acea cale care aparțin potrivirii și adăugând la acesta marginile rămase ale căii, dimensiunea potrivirii poate fi mărită. În mod similar, ciclurile care alternează între muchiile care se potrivesc și cele care nu se potrivesc sunt importante în problemele de potrivire ponderată. După cum au arătat Goldberg și Karzanov [4] , o cale sau un ciclu alternativ într-un grafic nedirecționat poate fi modelat ca o cale sau ciclu obișnuit într-un grafic orientat simetric. Pentru a crea un grafic cu simetric oblic dintr-un grafic nedirecționat cu o potrivire dată , considerați graficul ca un grafic cu săgeți în care muchiile de la fiecare vârf sunt împărțite în aparținând și nu aparținând combinației. O cale alternativă într-un grafic este apoi o cale obișnuită în acel grafic cu săgeți, iar un ciclu alternativ în grafic este un ciclu regulat în graficul săgeată.

Goldberg și Karzanov [4] au generalizat algoritmi de cale alternativă pentru a arăta că existența unei căi regulate între oricare două vârfuri ale unui graf cu simetrie oblică poate fi verificată în timp liniar. Dacă, în plus, este dată o funcție de lungime nenegativă pe marginile graficului care atribuie lungimi egale unei muchii și unei muchii , cea mai scurtă cale regulată care conectează o pereche dată de noduri într-un grafic oblic-simetric cu muchii și vârfuri poate fi găsit în timp . Dacă funcția de lungime poate lua valori negative, existența unui ciclu regulat negativ poate fi verificată în timp polinomial .

Pe lângă problemele cu traseele care apar atunci când se lucrează cu potriviri, au fost studiate și generalizări simetrice oblice ale teoremei debitului maxim și tăieturii minime [1] [13] .

Teoria jocului vieții

Cook [8] a arătat că o configurație din Jocul Vieții poate fi împărțită în două configurații mai mici dacă și numai dacă graficul graficului săgeată de călătorie asociat conține un ciclu regulat. Pentru graficele cu săgeți care conțin nu mai mult de trei muchii pe vârf, acest lucru poate fi verificat în timp polinomial prin eliminarea una câte una a podurilor (muchiile a căror eliminare face graficul deconectat) și a vârfurilor în care toate muchiile aparțin aceleiași părți a partiției, în timp ce există posibilitatea implementării unor astfel de simplificări. Dacă rezultatul este un grafic gol, nu există un ciclu regulat în grafic. În caz contrar, un ciclu obișnuit poate fi găsit în orice componentă fără punte. Căutarea punților în acest algoritm se poate face eficient folosind algoritmul dinamic Sorup [14] . O tehnică similară pentru îndepărtarea punților în contextul potrivirilor a fost anterior luată în considerare de Gabov, Kaplan și Tarjan [15] .

Fezabilitate

Problema 2-satisfiability , adică o expresie în formă normală conjunctivă cu două variabile sau negația lor, poate fi transformată într- un grafic de ieșire prin înlocuirea fiecărei expresii cu două implicații și . În acest grafic, fiecare vârf reprezintă o variabilă sau negația acesteia, iar fiecare muchie direcționată reprezintă o implicație. Graficul este prin construcție skew-simetric cu o funcție care mapează fiecare variabilă la negația sa. După cum au arătat Asvall, Plass și Tarjan [16] , găsirea unui set satisfăcător de valori pentru o instanță a unei probleme de satisfacție 2 este echivalent cu împărțirea acestui grafic de ieșire în două subseturi de vârfuri și , astfel încât să nu înceapă niciun arc. la și se termină la . Dacă există o astfel de împărțire, un set satisfăcător de valori poate fi obținut prin atribuirea unei valori True fiecărei variabile în și a unei valori False fiecărei variabile în . Acest lucru se poate face dacă și numai dacă nicio componentă puternic conectată a graficului nu conține atât un vârf, cât și un vârf complementar . Dacă două vârfuri aparțin aceleiași componente puternic conectate, variabilele corespunzătoare sau negațiile lor sunt în mod necesar egale între ele în orice set satisfăcător de valori a unei instanțe a problemei de satisfacție 2. Timpul total de verificare a conectivității puternice și de găsire a unei partiții a graficului de ieșire este liniar în dimensiunea unei anumite expresii 2-CNF.

Recunoaștere

Problema recunoașterii dacă un graf direcționat dat este simetric oblic este NP-complet . Acest lucru rezultă din rezultatul lui Lalonde [17] că problema găsirii unei involuții de inversare a culorii într-un graf bipartit este NP-complet dacă și numai dacă graficul direcționat dat de orientarea fiecărei muchii de la o clasă de culoare la alta este simetric-simetric. . Această complexitate nu afectează algoritmii de identificare a căii pentru graficele simetrice asimetrice, deoarece acești algoritmi presupun că structura simetrică asimetrică este dată ca parte a intrării algoritmului, mai degrabă decât derivată numai din grafic.

Note

  1. ↑ 1 2 Tutte, 1967 .
  2. ↑ Zelinka, 1976b .
  3. ↑ 12 Zaslavsky , 1991 .
  4. ↑ 1 2 3 4 Goldberg, Karzanov, 1996 .
  5. ↑ 1 2 Zelinka, 1974 .
  6. ↑ 12 Zelinka , 1976a .
  7. ↑ Graficul prezenței la vot provine din reprezentarea graficului ca analog cu șinele de cale ferată, cu joncțiunile ramurilor individuale ca săgeți de comutare.
  8. ↑ 12 Cook , 2003 .
  9. ↑ Hui, Schaefer, Štefankovič, 2004 .
  10. ↑ Edmonds, Johnson, 1970 .
  11. ↑ Zaslavsky, 1991 , p. Secțiunea 5.
  12. ↑ Babenko, 2006 .
  13. ↑ Goldberg, Karzanov, 2004 .
  14. ↑ Thorup, 2000 .
  15. ↑ Gabow, Kaplan, Tarjan, 1999 .
  16. ↑ Aspvall, Plass, Tarjan, 1979 .
  17. ↑ Lalonde, 1981 .

Literatură