Orientare (teoria graficelor)

Orientarea unui grafic nedirecționat este alocarea de direcții fiecărei muchii, ceea ce transformă graficul original într-un grafic direcționat .

Grafice dirijate

Un graf direcționat se numește direcționat dacă niciuna dintre perechile sale de vârfuri nu este conectată prin două muchii simetrice (multidirecționale). Dintre graficele direcționate, aceste grafice se disting prin absența a 2-cicluri (adică doar unul dintre arce ( x , y ) și ( y , x ) poate fi prezent în grafic) [1] [2] .

Turneul este orientarea graficului complet . Polytree este orientarea unui arbore nedirecționat [3] . Conjectura lui Sumner afirmă că orice turneu de vârf conține orice arbore polivalent cu n vârfuri [4] .

Numărul de grafice direcționate neizomorfe cu n vârfuri (pentru n =1, 2, 3, …) este

unu; 2; 7; 42; 582; 21,480; 2.142.288; 575.016.219; 415.939.243.032; … (secvența A001174 în OEIS ).

Graficele direcționate sunt într-o corespondență unu-la-unu cu graficele direcționate complete (grafice care au un arc direcționat între orice pereche de vârfuri distincte). Un grafic dirijat complet poate fi convertit într-un grafic dirijat prin eliminarea tuturor ciclurilor de 2, și invers, un grafic dirijat poate fi convertit într-un grafic dirijat complet adăugând un ciclu de 2 între fiecare pereche de vârfuri care nu sunt capetele niciunuia. arc. Aceste corespondențe sunt bijective . Prin urmare, aceeași succesiune de numere rezolvă problema de enumerare a graficelor pentru digrafele complete. Există o formulă explicită, dar complexă pentru numerele din această secvență [5] .

Orientări limitate

O orientare puternică este o orientare care are ca rezultat un digraf puternic conectat . Orientările complet ciclice strâns legate sunt orientările în care fiecare arc aparține cel puțin unui ciclu simplu. O orientare a unui graf nedirecționat G este complet ciclică dacă și numai dacă este o orientare puternică a oricărei componente conexe a lui G. Teorema lui Robbins afirmă că un graf are o orientare puternică dacă și numai dacă este conectat pe două muchii . Graficele deconectate pot avea orientări complet ciclice, dar numai dacă nu au punți [6] .

O orientare aciclică este o orientare care are ca rezultat un grafic aciclic direcționat . Orice grafic are o orientare aciclică. Toate orientările aciclice pot fi obținute prin plasarea vârfurilor într-un rând și apoi direcționarea unui arc de la un vârf anterior către unul mai târziu din acel rând. Teorema Gallai-Hasse-Roy-Vitaver afirmă că un graf are o orientare aciclică în care calea cea mai lungă are cel mult k vârfuri dacă și numai dacă poate fi colorat cu cel mult k culori [7] . Orientările aciclice și orientările complet ciclice sunt legate între ele prin dualitate plană . O orientare aciclică cu o singură sursă și un singur absorbant se numește orientare bipolară [8] .

O orientare tranzitivă este o orientare astfel încât graficul direcționat rezultat este închiderea sa tranzitivă . Graficele cu orientări tranzitive se numesc grafice de comparabilitate . Ele pot fi determinate dintr-o mulțime parțial ordonată făcând două elemente adiacente în toate cazurile în care sunt comparabile în ordine parțială [9] . O orientare tranzitivă, dacă există, poate fi găsită în timp liniar [10] . Cu toate acestea, verificarea dacă orientarea rezultată (sau orice orientare dată) este cu adevărat tranzitivă necesită mai mult timp, deoarece este echivalentă ca complexitate cu înmulțirea matricei .

Orientarea Euler a unui graf nedirecționat este o orientare în care fiecare vârf are același grad în interior și în exterior . Orientarea Euler a rețelelor apare în mecanica statistică în teoria modelelor de tip gheață [11] .

Orientarea pfaffiană are proprietatea că anumite cicluri de lungime pară dintr-un grafic au un număr impar de arce în două direcții diferite. Astfel de orientări există întotdeauna pentru graficele plane , dar nu întotdeauna pentru alte tipuri de grafice. Această orientare este utilizată în algoritmul FKT pentru numărarea potrivirilor perfecte [12] .


Note

  1. ↑ Diesel, 2005 .
  2. ↑ De remarcat că în traducerea cărții lui Distel, orientat se traduce prin direcționat, iar îndreptat se traduce ca orientat, adică conceptele sunt rearanjate. Acest lucru poate duce la confuzie. În acest articol, ca și în alte articole Wikipedia, definițiile sunt preluate din traducerea rusă.
  3. ↑ Rebane, Pearl, 1987 , p. 222–228.
  4. ↑ Sumner's Universal Tournament Conjecture Arhivat la 27 februarie 2014 la Wayback Machine , Douglas B. West, preluat 2012-08-02.
  5. ↑ Harary, Palmer, 1973 , p. 133.
  6. ↑ Robbins, 1939 , p. 281–283.
  7. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 42.
  8. ↑ de Fraysseix, Ossona de Mendez, Rosentiehl, 1995 , p. 157–179.
  9. ↑ Ghouila-Houri, 1962 , p. 1370–1371.
  10. ↑ McConnell, Spinrad, 1997 , p. 19–25.
  11. ↑ Michael și Winkler 1992 , p. 138–145.
  12. ↑ Thomas, 2006 , p. 963–984.

Literatură

Link -uri