Orientare bipolară

Orientarea bipolară sau orientarea st a unui graf nedirecționat  este alocarea unei orientări fiecărei muchii ( orientare ), care transformă graficul într-un graf aciclic direcționat cu o singură sursă s și un singur sink t și numerotarea st a graficul este o sortare topologică a graficului aciclic direcționat rezultat [1] [2] .

Definiții și existență

Fie un graf nedirecționat cu vârfuri. Orientarea unui grafic G  este alocarea unei direcții fiecărei margini a graficului G , ceea ce îl transformă într-un grafic direcționat . O orientare este aciclică dacă graficul direcționat rezultat nu are cicluri direcționate . Orice graf direcționat aciclic are cel puțin o sursă (un vârf din care nu intră niciun arc) și cel puțin un sink (un vârf din care nu provine arcuri). O orientare este bipolară dacă există exact o sursă și exact o chiuvetă. În unele situații, G poate fi dat împreună cu vârfurile selectate s și t . În acest caz, orientarea bipolară ar trebui să aibă s ca unică sursă și t ca singura chiuvetă [1] [2] .

Numerotarea st a graficului G (din nou, cu cele două vârfuri s și t evidențiate ) este alocarea numerelor întregi de la 1 la n vârfurilor graficului G astfel încât

Un grafic are o orientare bipolară dacă și numai dacă are o numerotare st . Dacă graficul are o orientare bipolară, atunci o numerotare st poate fi construită prin găsirea tipului topologic al graficului aciclic direcționat având în vedere orientarea și numerotarea fiecărui vârf în funcție de poziția sa în această ordine. În direcția opusă, orice numerotare st generează o ordine topologică în care fiecare muchie a graficului G este orientată de la un punct final cu numerotare mai mică la un punct final cu numerotare mai mare [1] [2] . Într-un grafic care conține muchia st , o orientare este bipolară dacă și numai dacă este aciclică, iar orientarea formată prin inversarea muchiei st este complet ciclică [2] .

Un grafic conex G cu vârfuri distincte s și t are o orientare bipolară și o numerotare st dacă și numai dacă graficul format din G prin adăugarea unei muchii de la s la t este conectat cu 2 vârfuri [3] . Într-o direcție, dacă acest grafic este conectat cu 2 vârfuri, atunci o orientare bipolară poate fi obținută prin orientarea secvențială a fiecărei urechi în descompunerea urechii a graficului [4] . În cealaltă direcție, dacă graficul nu este conectat cu 2 vârfuri, atunci are un vârf articulat v care separă o componentă bi-conectată a lui G de s și t . Dacă această componentă conține un vârf cu un număr mai mic decât v , atunci vârful cu numărul cel mai mic din componentă nu poate avea un vecin cu un număr mai mic, iar simetric, dacă conține un vârf cu un număr mai mare decât v , atunci cel mai mare- vârful numerotat din componentă nu poate avea vecin cu un număr mare.

Aplicații la planaritate

Lempel, Even și Zederbaum [3] au formulat st -numerări ca parte a algoritmului de verificare a planarității [3] , în timp ce Rosenstiel [5] și Tarjan [1] au formulat orientarea bipolară ca parte a algoritmului de tiling al graficului planar [1] .

Orientarea bipolară a unui graf plan are ca rezultat un graf st - planar , un graf planar aciclic direcționat cu o sursă și o absorbție. Aceste grafice joacă un rol important în teoria rețelei , precum și în vizualizarea graficelor  - diagrama Hasse a unei rețele bidimensionale este în mod necesar st -planar, iar orice graf st -planar redus tranzitiv reprezintă o rețea bidimensională. în acest fel [6] . Un graf aciclic direcționat G are o reprezentare plană ascendentă dacă și numai dacă graficul G este un subgraf al unui graf st -planar [7] .

Algoritmi

Se poate găsi numerotarea st și orientarea bipolară a unui graf dat cu vârfuri distinse s și t în timp liniar folosind căutarea depth-first [8] [9] [10] . Algoritmul lui Tarjan [10] folosește o căutare în profunzime care începe la vârful s . Ca și în algoritmul de căutare în profunzime pentru a verifica dacă un grafic este dublu conectat, acest algoritm transmite mai întâi o valoare pre( v ) pentru vârful v , care este numărul de precomanda pentru trecerea în adâncime a vârfului v și un număr scăzut( v ) , care este cel mai mic număr de precomandă care poate fi obținut urmând o margine de la v într-un arbore de căutare de adâncime. Ambele numere pot fi calculate în timp liniar ca parte a unei căutări în profunzime. Un graf dat va fi bi-conectat (și va avea o orientare bipolară) dacă și numai dacă t este singurul copil al unui vârf s din arborele de căutare de adâncime și pentru toate vârfurile v, altele decât s . Odată ce aceste numere au fost calculate, algoritmul lui Tarjan efectuează o a doua trecere a arborelui df, menținând un semn numeric ( v ) pentru fiecare vârf v și o listă legată de vârfuri care în cele din urmă produce o listă a tuturor vârfurilor din grafic în ordinea dată de numerotarea st . Inițial, lista conține s și t și . Când v este găsit la prima trecere, v este inserat în listă fie înainte, fie după părintele său p( v ) în arborele de căutare depth-first conform semnului(low( v )). Apoi sign(p( v )) este setat la -sign(low( v )). După cum arată Tarjan, ordinea rezultată a vârfurilor din această procedură dă numerotarea st a graficului dat [10] .

Alternativ, algoritmii eficienți în serie și paralele se pot baza pe descompunerea urechii [4] [11] . O descompunere a urechii deschise a unui graf dat cu vârfuri distincte s și t poate fi definită ca o partiție a marginilor graficului într-o succesiune de căi numite „urechi”, în care punctele finale ale primei urechi sunt s și t , punctele finale ale fiecare ureche următoare aparține urechilor anterioare din succesiune și fiecare vârf interior al fiecărei urechi apare mai întâi în acea ureche. O descompunere a urechii deschise există dacă și numai dacă graficul obținut prin adăugarea muchiei st este biconectat (aceeași condiție ca și pentru existența unei orientări bipolare) și poate fi găsit în timp liniar. st -Orientarea poate fi obținută dând o direcție adecvată fiecărei urechi, luând precauția ca, dacă există deja o cale orientată care conectează aceleași două capete în urechile anterioare, atunci noua ureche trebuie să aibă aceeași direcție. Cu toate acestea, verificarea directă cu un calcul de accesibilitate va fi lentă. Mahon, Shiber și Vyshkin [4] au dat o procedură de căutare complexă, dar localizată, pentru determinarea orientării adecvate pentru fiecare ureche, care (spre deosebire de abordarea DFS) este potrivită pentru calculul paralel [4] .

Papamentow și Tollis [12] raportează algoritmi pentru controlul lungimii căilor direcționate într-o orientare bipolară a unui graf dat, care la rândul lor conduc la controlul pentru lungimea și înălțimea unor vizualizări de graf [12] .

Spațiul tuturor orientărilor

Pentru graficele conectate cu vârfuri 3 cu vârfuri distinse s și t , oricare două orientări bipolare pot fi conectate între ele printr-o succesiune de operații care inversează direcția unui arc, menținând orientarea bipolară la fiecare pas [2] . Mai strict, pentru grafurile plane 3-conectate, setului de orientări bipolare i se poate da structura unei rețele distributive finite cu operația de inversare a direcției arcului corespunzătoare relației de acoperire rețelei [ en] 2] . Pentru orice grafic cu o sursă și un canal dedicat, setul tuturor orientărilor bipolare poate fi enumerat în timp polinomial pe orientare [2] .

Note

  1. ↑ 1 2 3 4 5 6 Pierre Rosentiehl, Robert Tarjan. Dispoziții plane rectilinii și orientări bipolare ale graficelor plane  // Geometrie discretă și computațională . - 1986. - T. 1 , nr. 4 . — S. 343–353 . - doi : 10.1007/BF02187706 . .
  2. ↑ 1 2 3 4 5 6 7 8 Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre. Orientări bipolare revăzute // Matematică aplicată discretă. - 1995. - T. 56 , nr. 2-3 . — S. 157–179 . - doi : 10.1016/0166-218X(94)00085-R .
  3. ↑ 1 2 3 4 Abraham Lempel, Shimon Even, Cederbaum I. An algorithm for planarity testing of graphs // Theory of Graphs (Internat. Sympos., Roma, 1966). - New York: Gordon și Breach, 1967. - S. 215-232.
  4. ↑ 1 2 3 4 Maon Y., Schieber B., Vishkin U. Parallel ear decomposition search (EDS) and ST-numbering in graphs // Teoretic Computer Science . - 1986. - T. 47 , nr. 3 . - doi : 10.1016/0304-3975(86)90153-2 .
  5. ↑ Numele de familie Rosentiehl este de origine germană, iar în germană se citește Rosenstiel. În engleză, poate suna ca Rosenstiel
  6. ↑ Platt CR Rețele planare și grafuri plane // Journal of Combinatorial Theory . - 1976. - T. 21 , nr. 1 . — S. 30–39 . - doi : 10.1016/0095-8956(76)90024-1 .
  7. ↑ Giuseppe Di Battista, Roberto Tamassia. Algoritmi pentru reprezentări plane ale digrafelor aciclice // Informatică teoretică . - 1988. - T. 61 , nr. 2-3 . — S. 175–198 . - doi : 10.1016/0304-3975(88)90123-5 .
  8. ↑ Ebert J. st -ordonarea vârfurilor grafurilor biconectate // Calcul . - 1983. - T. 30 , nr. 1 . — S. 19–33 . - doi : 10.1007/BF02253293 .
  9. ↑ Shimon Even, Robert Tarjan. Calcularea unei numere st // Informatică teoretică . - 1976. - Vol. 2 , numărul. 3 . — S. 339–344 . - doi : 10.1016/0304-3975(76)90086-4 .
  10. ↑ 1 2 3 Robert Tarjan. Doi algoritmi simplificați de căutare în profunzime // Fundamenta Informaticae . - 1986. - T. 9 , nr. 1 . — S. 85–94 .
  11. ↑ Hillel Gazit. Algoritmi optimi EREW paraleli pentru conectivitate, descompunerea urechii și numerotarea st a graficelor plane // Proc. Al 5-lea simpozion internațional de procesare paralelă. - 1991. - S. 84-91. - doi : 10.1109/IPPS.1991.153761 .
  12. ↑ 1 2 Charalampos Papamanthou, Ioannis G. Tollis. Aplicații ale orientărilor st parametrizate în algoritmii de desenare grafică // Graph Drawing: 13th International Symposium, GD 2005, Limerick, Ireland, September 12–14, 2005, Revised Papers . - Berlin: Springer, 2006. - T. 3843. - S. 355–367. — (Note de curs în Informatică). - doi : 10.1007/11618058_32 .