Erős orientáció (gráfelmélet)

Az irányítatlan gráf erős orientációja az  irányok hozzárendelése az egyes élekhez ( gráf orientáció ), amelyben a gráf erősen összefüggő gráfrá válik .

Az erős tájolások segítségével egyirányú úthálózat tervezhető. Robbins tétele szerint az erős orientációjú gráfok pontosan hidak nélküli gráfok . Az Euler-orientáció és a jól kiegyensúlyozott orientáció az erős orientáció fontos speciális esetei. Az erős orientációk viszont a szétválasztott gráfok teljesen ciklikus orientációira általánosíthatók. Egy gráf erős orientációinak halmaza egy részleges kockát alkot , amelyben a szomszédos orientációk csak egy ív orientációjában térnek el. Lehetséges egyetlen erős orientációt találni lineáris időben, de egy adott gráf erős orientációinak megszámlálása #P-teljes.

Alkalmazás a forgalomszabályozásban

Robbins [1] egy erős tájékozódási problémát javasolt egy olyan város történetében, amelynek utcáit és metszéspontjaikat egy G gráf ábrázolja . Robbins története szerint a város lakói munkanapokon belül szeretnék rendbe tenni az út bármely szakaszát, miközben a megmaradt (kétkocsis) utakon keresztül a város bármely részét el tudják érni bármely más részről. Hétvégén minden út járható, de a nagy forgalom miatt a lakosok minden utat egyirányúvá akarnak alakítani, de meg kell maradni annak, hogy a város bármely pontja más részről elérhető legyen. Robbins tétele kimondja, hogy egy útrendszert akkor és csak akkor lehet megjavítani hétköznap, ha hétvégén egyirányú utakra lehet alakítani. Emiatt a tételt néha egyirányú utca tételnek is nevezik [2] .

Robbins munkája nyomán egy sor tanulmányban Roberts és Xu pontosabban modellezte a kétirányú városi utcák rácsának egyirányú utcákká való fordításának problémáját, és megvizsgálta e fordítások hatását a rácsban lévő pontpárok közötti távolságokra. . Mint kimutatták, az egyirányú utcák hagyományos eloszlása, amelyben a párhuzamos utcákon a forgalom iránya váltakozik, páros távolságok esetén nem optimális. Az általuk talált javított tájolás azonban olyan pontokat tartalmaz, ahol az irányok ütköznek (két ellentétes irányú forgalom érkezik a kereszteződésbe), ami megoldásaik hibájának tekinthető.

Kapcsolódó típusú tájolások

Ha egy irányítatlan gráfnak Euler-ciklusa van , akkor a gráf Euler-orientációja (az az orientáció, amelyhez minden csúcsnak ugyanannyi bejövő és kimenő íve van) az élek Euler-ciklus szerinti orientálásával [3] kereshető meg . Ezek az irányok automatikusan erős orientációk lesznek.

A Nash-Williams tétel [4] [5] kimondja, hogy minden irányítatlan G gráf jól kiegyensúlyozott orientációval rendelkezik . Ez egy olyan orientáció, amelyben G bármely két u és v csúcsa esetén a páronként diszjunkt (ívekkel) u -tól v -ig irányított utak száma az eredményül kapott irányított gráfban legalább , ahol k  a pályák maximális száma a diszjunkt (élekkel ) irányítatlan utak halmaza u -tól v -ig . A Nash-Williams orientációknak megvan az a tulajdonsága is, hogy nagyon közel állnak az Euler-orientációhoz – minden csúcson a bejövő és kimenő helyek száma eggyel különbözik. A jól kiegyensúlyozott orientációk létezéséből a Menger- tétellel együtt rögtön a Robbins-tétel következik – Menger tétele szerint egy dupla élű gráfnak legalább két olyan útja van bármely két csúcs között, amelyek nem metszik egymást az élek mentén, ami azt jelenti, hogy hogy minden jól kiegyensúlyozott orientációnak erősen össze kell kapcsolódnia. Ugyanez az eredmény azt jelenti, hogy bármely 2k élhez kapcsolódó irányítatlan gráf orientálható egy k élhez kapcsolódó irányított gráf létrehozására.

A G gráf teljesen ciklikus orientációja  olyan orientáció, amelyben minden él egy irányított ciklushoz tartozik. Összekapcsolt gráfoknál ez megegyezik az erős orientációval, de a szétkapcsolt gráfokhoz teljesen ciklikus orientáció definiálható, és ez egy olyan orientáció, amelyben G minden összekapcsolt komponense erősen összekapcsolódik. Robbins tétele megismételhető, hogy egy gráfnak akkor és csak akkor van teljesen ciklikus orientációja, ha nincs hidaja. A teljesen ciklikus orientációk kettős és aciklikus orientációk (azok az irányok, amelyek a G gráfot irányított aciklikus gráfrá alakítják ), abban az értelemben, hogy ha G sík , és G orientációi átkerülnek G kettős sík gráfjának orientációiba az éleket 90 fokkal az óramutató járásával megegyezően elforgatva, akkor a G gráf teljesen ciklikus orientációja megfelel az így felépített duális gráf aciklikus orientációjának, és fordítva [6] [7] . Bármely G gráf különálló teljesen ciklikus orientációinak száma , ahol  a gráf Tatta-polinomja, az aciklikus orientációk (kettős) száma pedig [8] . Következményként Robbins tétele azt jelenti, hogy a Tutt-polinomnak akkor és csak akkor van gyöke (0,2) , ha G -ben van híd .

Ha egy erős orientációnak megvan az a tulajdonsága, hogy minden irányított ciklus ugyanazon az st élen megy keresztül (egyenértékű, ha az él orientációjának megváltoztatása aciklikus orientációt eredményez), akkor az st ív irányának megváltoztatásával kapott aciklikus orientáció bipoláris . orientáció . Bármilyen bipoláris orientáció erős orientációhoz kapcsolódik ilyen módon [9] .

Az ív irányváltási grafikonja

Ha a G gráf 3 élösszefüggésben van, és X és Y a G gráf két különböző erős orientációja , akkor lehetőség van X -et Y -re alakítani úgy, hogy egyszerre egy ív tájolását változtatjuk oly módon, hogy a az orientáció minden lépésben erős marad [10] . Így egy reverzális gráf (az ívek változó irányainak gráfja), amelynek csúcsai a G gráf erős orientációinak felelnek meg, élei pedig az egyik él irányában eltérő erős orientációpároknak felelnek meg, részkockát alkot .

Algoritmusok és összetettség

Egy adott irányítatlan híd nélküli gráf erős orientációja lineáris időben megkereshető úgy , hogy a gráfon mélységi keresést hajtunk végre , a gyökér felőli kereséskor minden élt orientálunk, és a fennmaradó éleket (melyeknek mélységben össze kell kötniük a szülőt és a gyermeket) -első keresési fa) gyermektől szülőig [11] . Adott egy irányítatlan áthidalt G gráf , valamint azon irányított csúcspárok listája, amelyeket irányított útvonalakkal kell összekötni, polinomiális időben meg lehet találni G olyan orientációját, amely az összes adott párt összeköti, ha létezik ilyen orientáció. Ugyanez a probléma azonban NP-teljes , ha a bemenet lehet vegyes gráf [12] .

Egy adott G gráf erős orientációinak megszámlálása #P-teljes akkor is, ha G sík és kétrészes [6] [13] . Sűrű gráfoknál (pontosabban olyan gráfoknál, amelyekben minden csúcsnak lineáris számú szomszédja van) az erős orientációk száma megbecsülhető egy polinom-idő sztochasztikus közelítési séma segítségével [6] [14] . A korlátozott faszélességű gráfok esetében az erős orientációk számolásának problémája pontosan polinomiális időben megoldható [6] .

Jegyzetek

  1. ↑ Robbins, 1939 .
  2. ↑ Koh, Tay, 2002 .
  3. ↑ Schrijver, 1983 .
  4. ↑ Nash-Williams, 1960 .
  5. ↑ Nash-Williams, 1969 .
  6. ↑ 1 2 3 4 walesi, 1997 .
  7. ↑ Noy, 2001 .
  8. ↑ Las Vergnas, 1980 .
  9. ↑ de Fraysseix, Ossona de Mendez, Rosentiehl (1995) .
  10. ↑ Fukuda, Prodon, Sakuma, 2001 .
  11. ↑ Lásd például ( Atallah 1984 ) és ( Roberts 1978 ).
  12. ↑ Arkin, Hassin, 2002 .
  13. ↑ Vertigan, walesi, 1992 .
  14. ↑ Alon, Frieze, walesi, 1995 .

Irodalom