Orientering (grafteori)

Orienteringen af ​​en ikke-rettet graf er tildelingen af ​​retninger til hver kant, hvilket gør den originale graf til en rettet graf .

Styrede grafer

En rettet graf kaldes rettet , hvis ingen af ​​dens par af hjørner er forbundet med to symmetriske (flerretnings)kanter. Blandt rettede grafer er disse grafer kendetegnet ved fraværet af 2-cyklusser (det vil sige, at kun én af buerne ( x , y ) og ( y , x ) kan være til stede i grafen) [1] [2] .

Turneringen er retningen for hele grafen . Polytree er orienteringen af ​​et urettet træ [3] . Sumners formodning siger, at enhver vertex-turnering indeholder et hvilket som helst polytræ med n hjørner [4] .

Antallet af ikke-isomorfe rettede grafer med n toppunkter (for n =1, 2, 3, …) er

en; 2; 7; 42; 582; 21.480; 2.142.288; 575.016.219; 415.939.243.032; … (sekvens A001174 i OEIS ).

Direkte grafer er i en en-til-en korrespondance med komplette rettede grafer (grafer, der har en rettet bue mellem et hvilket som helst par af distinkte hjørner). En komplet rettet graf kan konverteres til en rettet graf ved at fjerne alle 2-cyklusser, og omvendt kan en rettet graf konverteres til en komplet rettet graf ved at tilføje en 2-cyklus mellem hvert par af hjørner, der ikke er ender af nogen bue. Disse korrespondancer er bijektive . Derfor løser den samme talfølge problemet med graftælling for komplette digrafer. Der er en eksplicit, men kompleks formel for tallene i denne rækkefølge [5] .

Begrænsede orienteringer

En stærk orientering er en orientering, der resulterer i en stærkt forbundet digraf . Nært beslægtede fuldstændig cykliske orienteringer er orienteringer, hvor hver bue tilhører mindst en simpel cyklus. En orientering af en urettet graf G er fuldstændig cyklisk, hvis og kun hvis det er en stærk orientering af en hvilken som helst forbundet komponent af G . Robbins' sætning siger, at en graf har en stærk orientering, hvis og kun hvis den er 2-kant-forbundet . Afbrudte grafer kan have fuldstændig cykliske orienteringer, men kun hvis de ikke har nogen broer [6] .

En acyklisk orientering er en orientering, der resulterer i en rettet acyklisk graf . Enhver graf har en acyklisk orientering. Alle acykliske orienteringer kan opnås ved at placere toppunkter i en række og derefter rette en bue fra en tidligere toppunkt til en senere i den række. Gallai-Hasse-Roy-Vitaver-sætningen siger, at en graf har en acyklisk orientering, hvor den længste vej højst har k toppunkter, hvis og kun hvis den kan farves med højst k farver [7] . Acykliske orienteringer og fuldstændig cykliske orienteringer er relateret til hinanden ved plan dualitet . En acyklisk orientering med en enkelt kilde og en enkelt sink kaldes en bipolær orientering [8] .

En transitiv orientering er en orientering sådan, at den resulterende rettede graf er dens transitive lukning . Grafer med transitive orienteringer kaldes sammenlignelighedsgrafer . De kan bestemmes ud fra et delvist ordnet sæt ved at lave to elementer ved siden af ​​i alle tilfælde, hvor de er sammenlignelige i delvis rækkefølge [9] . En transitiv orientering, hvis den findes, kan findes i lineær tid [10] . Det tager dog længere tid at kontrollere, om den resulterende orientering (eller en given orientering) virkelig er transitiv, da den i kompleksitet svarer til matrixmultiplikation .

Euler-orienteringen af ​​en urettet graf er en orientering, hvor hvert toppunkt har den samme in - grad og ud-grad . Euler-orienteringen af ​​gitter vises i statistisk mekanik i teorien om is-type modeller [11] .

Pfaffisk orientering har den egenskab, at visse cyklusser af lige længde i en graf har et ulige antal buer i to forskellige retninger. Sådanne orienteringer findes altid for plane grafer , men ikke altid for andre typer grafer. Denne orientering bruges i FKT-algoritmen til at tælle perfekte matchninger [12] .


Noter

  1. ↑ Diestel, 2005 .
  2. ↑ Det skal bemærkes, at i oversættelsen af ​​Distels bog er oriented oversat som rettet, og rettet er oversat til orienteret, det vil sige, at begreberne omarrangeres. Dette kan føre til forvirring. I denne artikel, som i andre Wikipedia-artikler, er definitioner taget fra den russiske oversættelse.
  3. ↑ Rebane, Pearl, 1987 , s. 222-228.
  4. ↑ Sumner's Universal Tournament Conjecture Arkiveret 27. februar 2014 på Wayback Machine , Douglas B. West, hentet 2012-08-02.
  5. ↑ Harary, Palmer, 1973 , s. 133.
  6. ↑ Robbins, 1939 , s. 281-283.
  7. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 42.
  8. ↑ de Fraysseix, Ossona de Mendez, Rosentiehl, 1995 , s. 157-179.
  9. ↑ Ghouila-Houri, 1962 , s. 1370-1371.
  10. ↑ McConnell, Spinrad, 1997 , s. 19-25.
  11. ↑ Michael og Winkler 1992 , s. 138-145.
  12. ↑ Thomas, 2006 , s. 963-984.

Litteratur

Links