Orientering (grafteori)

Orienteringen av en oriktad graf är tilldelningen av riktningar till varje kant, vilket förvandlar den ursprungliga grafen till en riktad graf .

Riktade grafer

En riktad graf kallas riktad om inget av dess par av hörn är förbundna med två symmetriska (flerriktade) kanter. Bland riktade grafer kännetecknas dessa grafer av frånvaron av 2-cykler (det vill säga endast en av bågarna ( x , y ) och ( y , x ) kan finnas i grafen) [1] [2] .

Turneringen är orienteringen av hela grafen . Polytree är orienteringen av ett oriktat träd [3] . Sumners gissningar säger att varje vertexturnering innehåller vilket polyträd som helst med n hörn [4] .

Antalet icke-isomorfa riktade grafer med n hörn (för n =1, 2, 3, …) är

ett; 2; 7; 42; 582; 21,480; 2,142,288; 575,016,219; 415.939.243.032; … (sekvens A001174 i OEIS ).

Riktade grafer är i en en-till-en-överensstämmelse med kompletta riktade grafer (grafer som har en riktad båge mellan valfritt par av distinkta hörn). En fullständig riktad graf kan konverteras till en riktad graf genom att ta bort alla 2-cykler, och vice versa, en riktad graf kan konverteras till en fullständig riktad graf genom att lägga till en 2-cykel mellan varje par av hörn som inte är ändar på någon båge. Dessa korrespondenser är bijektiva . Därför löser samma talföljd grafuppräkningsproblemet för kompletta digrafer. Det finns en explicit men komplex formel för talen i denna sekvens [5] .

Begränsade orienteringar

En stark orientering är en orientering som resulterar i en starkt sammankopplad digraf . Närbesläktade helt cykliska orienteringar är orienteringar där varje båge tillhör åtminstone en enkel cykel. En orientering av en oriktad graf G är helt cyklisk om och endast om det är en stark orientering av någon ansluten komponent av G . Robbins teorem säger att en graf har en stark orientering om och bara om den är 2-kantskopplad . Frånkopplade grafer kan ha helt cykliska orienteringar, men bara om de inte har några broar [6] .

En acyklisk orientering är en orientering som resulterar i en riktad acyklisk graf . Varje graf har en acyklisk orientering. Alla acykliska orienteringar kan erhållas genom att placera hörn i en rad och sedan rikta en båge från en tidigare vertex till en senare i den raden. Gallai-Hasse-Roy-Vitaver-satsen säger att en graf har en acyklisk orientering där den längsta banan har högst k hörn om och bara om den kan färgas med högst k färger [7] . Acykliska orienteringar och helt cykliska orienteringar är relaterade till varandra genom plan dualitet . En acyklisk orientering med en enda källa och en enda sänka kallas bipolär orientering [8] .

En transitiv orientering är en orientering så att den resulterande riktade grafen är dess transitiva stängning . Grafer med transitiva orienteringar kallas jämförbarhetsgrafer . De kan bestämmas från en delvis ordnad uppsättning genom att göra två element intill varandra i alla fall där de är jämförbara i partiell ordning [9] . En transitiv orientering, om den finns, kan hittas i linjär tid [10] . Att kontrollera om den resulterande orienteringen (eller någon given orientering) verkligen är transitiv tar dock längre tid, eftersom den är likvärdig i komplexitet med matrismultiplikation .

Euler-orienteringen för en oriktad graf är en orientering där varje vertex har samma in - grad och ut-grad . Euler-orienteringen av gitter visas i statistisk mekanik i teorin om istypsmodeller [11] .

Pfaffisk orientering har egenskapen att vissa cykler med jämn längd i en graf har ett udda antal bågar i två olika riktningar. Sådana orienteringar finns alltid för plana grafer , men inte alltid för andra typer av grafer. Denna orientering används i FKT-algoritmen för att räkna perfekta matchningar [12] .


Anteckningar

  1. ↑ Diestel, 2005 .
  2. ↑ Det bör noteras att i översättningen av Distels bok översätts oriented som riktad och riktad översätts som orienterad, det vill säga begreppen omarrangeras. Detta kan leda till förvirring. I den här artikeln, liksom i andra Wikipedia-artiklar, är definitioner hämtade från den ryska översättningen.
  3. ↑ Rebane, Pearl, 1987 , sid. 222–228.
  4. ↑ Sumners Universal Tournament Conjecture Arkiverad 27 februari 2014 på Wayback Machine , Douglas B. West, hämtad 2012-08-02.
  5. ↑ Harary, Palmer, 1973 , sid. 133.
  6. ↑ Robbins, 1939 , sid. 281–283.
  7. ↑ Nešetřil, Ossona de Mendez, 2012 , sid. 42.
  8. ↑ de Fraysseix, Ossona de Mendez, Rosentiehl, 1995 , sid. 157–179.
  9. ↑ Ghouila-Houri, 1962 , sid. 1370–1371.
  10. ↑ McConnell, Spinrad, 1997 , sid. 19–25.
  11. ↑ Michael och Winkler 1992 , sid. 138–145.
  12. ↑ Thomas, 2006 , sid. 963–984.

Litteratur

Länkar