Tájolás (gráfelmélet)

Az irányítatlan gráf orientációja az egyes élekhez való irányok hozzárendelése, amely az eredeti gráfot irányított gráfrá alakítja .

Irányított grafikonok

Az irányított gráfot irányítottnak nevezzük , ha egyik csúcspárját sem köti össze két szimmetrikus (többirányú) él. Az irányított gráfok közül ezeket a gráfokat a 2 ciklus hiánya különbözteti meg (vagyis az ( x , y ) és ( y , x ) ívek közül csak az egyik lehet jelen a gráfban) [1] [2] .

A verseny a teljes grafikon orientációja . A Polytree egy irányítatlan fa tájolása [3] . Sumner sejtése szerint minden vertex verseny tartalmaz tetszőleges n csúcsú polifát [4] .

Az n csúcsú nemizomorf irányított gráfok száma ( n =1, 2, 3, … esetén)

egy; 2; 7; 42; 582; 21,480; 2,142,288; 575 016 219; 415.939.243.032; … ( A001174 sorozat az OEIS -ben ).

Az irányított gráfok egy az egyhez megfeleltetésben vannak a teljes irányított gráfokkal (olyan gráfokkal, amelyeknek van egy irányított íve bármely különálló csúcspár között). Egy teljes irányított gráf átalakítható irányított gráfrá az összes 2 ciklus eltávolításával, és fordítva, egy irányított gráf teljes irányított gráfrá alakítható, ha minden olyan csúcspár közé 2 ciklust adunk, amelyek nem végei egyiknek sem. ív. Ezek a megfeleltetések bijektívek . Ezért ugyanaz a számsor megoldja a teljes digráfok gráfszámlálási problémáját . Létezik egy explicit, de összetett képlet az ebben a sorozatban szereplő számokra [5] .

Korlátozott tájolások

Az erős orientáció olyan orientáció, amely egy erősen összefüggő digráfot eredményez . A szorosan összefüggő teljesen ciklikus orientációk olyan tájolások, amelyekben minden ív legalább egy egyszerű ciklushoz tartozik. Egy irányítatlan G gráf orientációja akkor és csak akkor teljesen ciklikus, ha G bármely összefüggő komponensének erős orientációja . Robbins tétele kimondja, hogy egy gráfnak akkor és csak akkor van erős orientációja, ha kétélű . A szétválasztott gráfok teljesen ciklikus orientációjúak lehetnek, de csak akkor, ha nincsenek hidaik [6] .

Az aciklikus orientáció olyan orientáció, amely irányított aciklikus gráfot eredményez . Minden gráfnak aciklikus orientációja van. Minden aciklikus orientációt úgy kaphatunk, hogy csúcsokat helyezünk egy sorba, majd egy ívet irányítunk egy korábbi csúcsból a sorban egy későbbire. A Gallai-Hasse-Roy-Vitaver-tétel kimondja, hogy a gráfnak olyan aciklikus orientációja van, amelyben a leghosszabb útnak legfeljebb k csúcsa van, akkor és csak akkor, ha legfeljebb k színnel színezhető [7] . Az aciklikus és a teljesen ciklikus orientációk síkbeli kettősséggel kapcsolódnak egymáshoz . Az egyetlen forrással és egyetlen nyelővel rendelkező aciklikus orientációt bipoláris orientációnak nevezzük [8] .

A tranzitív orientáció olyan orientáció, amelyben az eredményül kapott irányított gráf a tranzitív lezárása . A tranzitív orientációjú grafikonokat összehasonlíthatósági gráfoknak nevezzük . Meghatározhatók egy részben rendezett halmazból úgy, hogy két elemet egymás mellé teszünk minden olyan esetben, amikor részleges sorrendben összehasonlíthatók [9] . Egy tranzitív orientáció, ha létezik, megtalálható a lineáris időben [10] . Annak ellenőrzése azonban, hogy az eredményül kapott orientáció (vagy bármely adott orientáció) valóban tranzitív-e, több időt vesz igénybe, mivel összetettsége megegyezik a mátrixszorzással .

Az irányítatlan gráf Euler-orientációja egy olyan orientáció, amelyben minden csúcsnak azonos a -fokú és a kifelé irányuló foka . A rácsok Euler-orientációja a statisztikai mechanikában a jégtípusú modellek elméletében jelenik meg [11] .

A Pfaffi-orientációnak megvan az a tulajdonsága, hogy a gráf bizonyos páros hosszúságú ciklusaiban páratlan számú ív van két különböző irányban. Az ilyen tájolások mindig léteznek síkgráfoknál , de nem mindig más típusú gráfoknál. Ezt az orientációt használja az FKT algoritmus a tökéletes egyezések számlálására [12] .


Jegyzetek

  1. ↑ Diestel, 2005 .
  2. ↑ Megjegyzendő, hogy Distel könyvének fordításában az orientált irányítottnak, az irányított pedig orientáltnak fordítódik, vagyis a fogalmak átrendeződnek. Ez zavart okozhat. Ebben a cikkben, akárcsak a Wikipédia többi cikkében, a definíciók az orosz fordításból származnak.
  3. ↑ Rebane, Pearl, 1987 , p. 222–228.
  4. ↑ Sumner's Universal Tournament Conjecture Archivált : 2014. február 27., a Wayback Machine , Douglas B. West, letöltve: 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 és Winkler 1992 , p. 138–145.
  12. ↑ Thomas, 2006 , p. 963–984.

Irodalom

Linkek