Gráf irányítása

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés]

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[szerkesztés]

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[szerkeszté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[szerkesztés]

  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[szerkesztés]

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Gráf_irányítása&oldid=21308511”