Gráf irányítása

A matematika, azon belül a gráfelmélet területén egy irányítatlan gráf orientációja vagy irányítása során éleihez irányokat rendelnek, melynek során az eredeti gráf irányított gráffá válik.

Irányított gráfok

Egy irányított gráfot akkor nevezünk orientált gráfnak, ha nincs olyan csúcspárja, amit szimmetrikus élek kötnek össze. Más szóval az irányított gráfok közül azok az orientált gráfok, melyek nem rendelkeznek 2-körrel (tehát az (x, y) és (y, x) irányított élek közül legfeljebb egy létezhet a gráfban).[1]

A teljes gráfok orientációi a tournamentek. A fák irányításai pedig a polifák.[2] A Sumner-sejtés kimondja, hogy bármely 2n − 2 csúcsú tournament tartalmazza az összes n csúcsú polifát.[3]

Az n csúcsú (n = 1, 2, 3…-ra) nem izomorf orientált gráfok száma:

1; 2; 7; 42; 582; 21,480; 2,142,288; 575,016,219; 415,939,243,032; … (A001174 sorozat az OEIS-ben).

Az orientált gráfok és a teljes irányított gráfok (olyan gráfok, melynek bármely csúcspárja között van legalább egy irányított él) között kölcsönösen egyértelműen megfeleltethetők egymásnak. A teljes irányított gráf orientált gráffá alakítható a 2-köreinek eltávolításával, illetve egy orientált gráf teljes irányított gráffá alakítható úgy, hogy 2-kört adunk a csúcsokhoz, amik nem egy él végpontjai; ezek a megfeleltetések bijektívek. Ezért az előző sorozat megoldja a teljes irányított gráfok leszámlálási problémáját is. A sorozat tagjai előállnak egy bonyolult, de zárt képlet alapján.[4]

Speciális irányítások

Egy erős orientáció olyan orientáció, ami erősen összefüggő gráfot eredményez. A kapcsolódó teljesen ciklikus orientációk olyan orientációk, melyben minden él legalább egy egyszerű körhöz tartozik. A G irányítatlan gráf egy orientációja pontosan akkor teljesen ciklikus, ha G minden összefüggő komponensének erős orientációját adja. A Robbins-tétel szerint egy gráfnak pontosan akkor van erős orientációja, ha 2-szeresen élösszefüggő; nem összefüggő gráfoknak is lehetnek teljesen ciklikus orientációik, de csak ha nem rendelkeznek elválasztó éllel.[5]

Egy körmentes orientáció olyan orientáció, ami irányított körmentes gráfot eredményez. Minden gráfnak van körmentes orientációja; az összes ilyen orientáció előállítható úgy, hogy a csúcsokat valamilyen sorba rendezzük, majd az élek irányát úgy választjuk meg, hogy a korábbi csúcstól a későbbi csúcs felé mutasson. A Gallai–Hasse–Roy–Vitaver-tétel kimondja, hogy egy gráfnak pontosan akkor van olyan körmentes orientációja, melyben a leghosszabb út legfeljebb k csúcsból áll, ha legfeljebb k színnel színezhető.[6] A körmentes orientációk és a teljesen ciklikus orientációk a síkdualitáson keresztül kapcsolódnak egymással. Az olyan körmentes orientációt, melyben egyetlen forrás és egyetlen nyelő van, bipoláris orientációnak nevezik.[7]

Egy tranzitív orientáció olyan orientáció, melyben az eredményül kapott irányított gráf a saját tranzitív lezárása. A tranzitív orientációval rendelkező gráfok az összehasonlíthatósági gráfok; ezek olyan irányítatlan gráfok, amikben egy részbenrendezett halmaz (poset) azon elemeinek megfelelő csúcsok vannak páronként összekötve, melyek a részbenrendezésben egymással összehasonlíthatóak.[8] Ha egy gráfnak létezik tranzitív irányítása, az lineáris időben megtalálható.[9] Az ezt végrehajtó algoritmus azonban bármely gráf éleihez irányítást fog rendelni, így adott gráf összehasonlíthatósági gráf voltának teszteléséhez még szükség van annak vizsgálatára, hogy az eredményül kapott irányítás tranzitív-e, aminek komplexitása bizonyíthatóan a mátrixszorzással egyenértékű.

Egy irányítatlan gráf Euler-orientációja olyan orientáció, melyben minden egyes csúcs kifoka és befoka egyenlő. A rácsgráfok Euler-orientációi a statisztikus mechanika területén, a jégtípus-modellekben is előfordulnak.[10]

Egy Pfaff-orientáció azzal a tulajdonsággal bír, hogy a gráf bizonyos páros hosszúságú köreiben páratlan számú él van, melyek mindkét irányba mutatnak. Síkbarajzolható gráfoknak mindig van Pfaff-orientációjuk, más gráfoknak nem minden esetben. A teljes párosítások számolásának FKT-algoritmusában használják.[11]

Fordítás

  • Ez a szócikk részben vagy egészben az Orientation (graph theory) című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

  1. ↑ Diestel, Reinhard (2005), "1.10 Other notions of graphs", Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6, <http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf>.
  2. ↑ Rebane, George & Pearl, Judea (1987), "The recovery of causal poly-trees from statistical data", in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987, pp. 222–228, <ftp://ftp.cs.ucla.edu/tech-report/198_-reports/870031.pdf>[halott link].
  3. ↑ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2012-08-02.
  4. ↑ Harary, Frank & Palmer, Edgar M. (1973), "Formula 5.4.13", Graphical Enumeration, New York: Academic Press, p. 133.
  5. ↑ Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem of traffic control", The American Mathematical Monthly 46 (5): 281–283, DOI 10.2307/2303897.
  6. ↑ Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), "Theorem 3.13", Sparsity: Graphs, Structures, and Algorithms, vol. 28, Algorithms and Combinatorics, Heidelberg: Springer, p. 42, ISBN 978-3-642-27874-7, DOI 10.1007/978-3-642-27875-4.
  7. ↑ de Fraysseix, Hubert; Ossona de Mendez, Patrice & Rosenstiehl, Pierre (1995), "Bipolar orientations revisited", Discrete Applied Mathematics 56 (2–3): 157–179, DOI 10.1016/0166-218X(94)00085-R.
  8. ↑ Ghouila-Houri, Alain (1962), "Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre", Les Comptes rendus de l'Académie des sciences 254: 1370–1371.
  9. ↑ McConnell, R. M. & Spinrad, J. (1997), "Linear-time transitive orientation", 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 19–25.
  10. ↑ Mihail, Milena & Winkler, Peter (1992), "On the Number of Eularian Orientations of a Graph", Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '92, Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, pp. 138–145, ISBN 0-89791-466-X, <http://dl.acm.org/citation.cfm?id=139404.139434>.
  11. ↑ Thomas, Robin (2006), "A survey of Pfaffian orientations of graphs", International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich, pp. 963–984, doi:10.4171/022-3/47

További információk

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!