Összehasonlíthatósági gráf

A matematika, azon belül a gráfelmélet területén egy összehasonlíthatósági gráf, összehasonlítási gráf vagy hasonlítási gráf (comparability graph) olyan irányítatlan gráf, amiben 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. Egyéb elnevezéseik: transitively orientable graphs (tranzitívan orientálható gráfok), partially orderable graphs (részben rendezhető gráfok) és containment graphs (tartalmazási gráfok).[1] Egy összehasonlíthatatlansági gráf vagy össze nem hasonlíthatósági gráf (incomparability graph) olyan irányítatlan gráf, amiben egy részbenrendezett halmaz azon elemeinek megfelelő csúcsok vannak páronként összekötve, melyek a részbenrendezésben egymással nem hasonlíthatóak össze.

Definíciók és jellemzés

Egy részbenrendezett halmaz Hasse-diagramja (balra) és a hozzá tartozó összehasonlítási gráf (jobbra)
Az összehasonlíthatósági gráfok egyik tiltott részgráfja. A gráf a–b–d–f–d–c–e–c–b–a általánosított köre páratlan hosszúságú (9), de nincsenek benne háromszöghúrok.

Bármely (S,<) szigorúan részbenrendezett halmaz esetén létezik (S, <) összehasonlíthatósági gráfja, az (S, ⊥), melynek csúcsai az S elemei, élei pedig azon {u, v} elemek között húzódnak, melyekre u < v. Tehát a részbenrendezett halmaz irányított körmentes gráfjára tranzitív lezárást alkalmazunk, és a lezártból eltávolítjuk az irányítottságot.

Ezzel ekvivalens, hogy az összehasonlítási gráf olyan gráf, aminek tranzitív irányítása van,[2] tehát a gráf éleihez irány rendelése (tehát a gráf irányítása) oly módon, hogy az eredményül kapott irányított gráf szomszédsági relációja tranzitív legyen: ha létezik az (x,y) és az (y,z) irányított él, akkor minden esetben léteznie kell az (x,z) élnek is.

Az összehasonlíthatósági gráf klikkjei a részben rendezés egy-egy láncának felelnek meg, a független csúcshalmazai pedig egy-egy antiláncnak.

Bármely részbenrendezés ábrázolható olyan halmazcsaládként, hogy a részbenrendezés x < y relációja akkor áll fenn, ha az x-nek megfelelő halmaz az y-nak megfelelő halmaz részhalmaza. Ily módon megmutatható, hogy az összehasonlíthatósági gráfok ekvivalensek halmazcsaládok tartalmazási gráfjaival (containment graphs); tehát olyan gráfokkal, melyekben a család minden halmazához egy csúcs tartozik, és két csúcs között akkor húzódik él, ha egyik részhalmaza a másiknak.[3]

Más megközelítésben,[4] egy összehasonlíthatósági gráf olyan gráf, melyben minden páratlan hosszú általánosított körhöz (generalized cycle) található olyan (x,y) él, ami a körben kettő távolságra lévő csúcsokat köt össze. Az ilyen él neve háromszögelési húr (triangular chord). Ebben a kontextusban általánosított kör alatt olyan zárt sétát értünk, ami a gráf minden élét legfeljebb egyszer használja fel adott irányban.

Az összehasonlíthatósági gráfok karakterizálhatók tiltott részgráfjaik alapján is.[5]

Más gráfcsaládokkal való kapcsolata

Minden teljes gráf összehasonlíthatósági gráf is, méghozzá egy teljes rendezésé. Egy teljes gráf minden körmentes irányítása tranzitív. Minden páros gráf is összehasonlíthatósági gráf. A páros gráf egyik feléből a másikba mutató élek irányításával trazitív irányítást kapunk, ami egy 2 magas részbenrendezésnek felel meg. (Seymour 2006) alapján minden olyan összehasonlíthatósági gráf, ami se nem teljes gráf, se nem páros gráf, rendelkezik ferde partícióval.

Minden intervallumgráf komplementer gráfja az intervallumrendezésnek megfelelő összehasonlíthatósági gráf. Az intervallumgráfok pontosan azon a gráfok, melyek húrgráfok és komplementerük összehasonlíthatósági gráf.[6]

Egy permutációgráf intervallumok halmazának tartalmazási gráfja.[7] Ilyenformán, a permutációgráfok az összehasonlíthatósági gráfok egyik alosztályát képezik.

A triviálisan perfekt gráfok a gyökeres fák összehasonlíthatósági gráfjai.[8] A kográfok karakterizációjuk szerint a soros-párhuzamos részbenrendezések összehasonlíthatósági gráfjai, tehát szintén az összehasonlíthatósági gráfok egyik alosztálya.[9]

A küszöbgráfok szintén az összehasonlíthatósági gráfok közé tartoznak.

Minden összehasonlíthatósági gráf perfekt. Ezt a Mirsky-tétel igazolja, komplementer gráfjaik perfektségét pedig a Dilworth-tétel; ezek a tények, a perfekt gráfok komplementer-tulajdonságával együtt felhasználhatók arra, hogy a Dilworth-tételből a Mirsky-tételt igazoljuk, vagy megfordítva.[10] Specifikusabban, az összehasonlíthatósági gráfok perfekt rendezhető gráfok (perfectly orderable graph), a perfekt gráfok alesetei: a gráf egy tranzitív irányításának valamely topologikus rendezésén futtatott mohó színezési algoritmus optimálisan fogja színezni azt.[11]

Minden összehasonlíthatósági gráf komplementere füzérgráf (síkgörbék metszetgráfja).[12]

Algoritmusok

Ha egy gráfnak létezik tranzitív irányítása, az lineáris időben megtalálható.[13] 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ű.

Mivel az összehasonlíthatósági gráfok perfektek, számos, az általános gráfokon nehéz probléma, köztük a gráfszínezés és a független csúcshalmaz-probléma ezekre a gráfokra polinom időben megoldható.

Fordítás

  • Ez a szócikk részben vagy egészben a Comparability graph 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. ↑ (Golumbic 1980), p. 105; (Brandstädt, Le & Spinrad 1999), p. 94.
  2. ↑ (Ghouila-Houri 1962); lásd (Brandstädt, Le & Spinrad 1999), theorem 1.4.1, p. 12. Bár a részben rendezésből jövő orientációk körmentesek, nem feltétlenül szükséges, hogy a körmentesség a karakterizáció feltételei között szerepeljen.
  3. ↑ (Urrutia 1989); (Trotter 1992); (Brandstädt, Le & Spinrad 1999), section 6.3, pp. 94–96.
  4. ↑ (Ghouila-Houri 1962) és (Gilmore & Hoffman 1964). Lásd még (Brandstädt, Le & Spinrad 1999), theorem 6.1.1, p. 91.
  5. ↑ (Gallai 1967); (Trotter 1992); (Brandstädt, Le & Spinrad 1999), p. 91 and p. 112.
  6. ↑ Az intervallumgráfok komplementereinek tranzitív irányíthatóságát (Ghouila-Houri 1962) igazolta; az intervallumgráfok karakterizálását (Gilmore & Hoffman 1964) végezte el. Lásd még (Golumbic 1980), prop. 1.3, pp. 15–16.
  7. ↑ (Dushnik & Miller 1941). (Brandstädt, Le & Spinrad 1999), theorem 6.3.1, p. 95.
  8. ↑ (Brandstädt, Le & Spinrad 1999), theorem 6.6.1, p. 99.
  9. ↑ (Brandstädt, Le & Spinrad 1999), corollary 6.4.1, p. 96; (Jung 1978).
  10. ↑ (Golumbic 1980), theorems 5.34 and 5.35, p. 133.
  11. ↑ (Maffray 2003).
  12. ↑ (Golumbic, Rotem & Urrutia 1983) és (Lovász 1983). Lásd még (Fox & Pach 2012).
  13. ↑ (McConnell & Spinrad 1997); see (Brandstädt, Le & Spinrad 1999), p. 91.
  • Brandstädt, Andreas; Le, Van Bang & Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
  • Dushnik, Ben & Miller, E. W. (1941), "Partially ordered sets", American Journal of Mathematics (The Johns Hopkins University Press) 63 (3): 600–610, DOI 10.2307/2371374.
  • Fox, J. & Pach, J. (2012), "String graphs and incomparability graphs", Advances in Mathematics 230 (3): 1381–1401, doi:10.1016/j.aim.2012.03.011, <http://www.renyi.hu/~pach/publications/stringpartial071709.pdf>.
  • Gallai, Tibor (1967), "Transitiv orientierbare Graphen", Acta Math. Acad. Sci. Hung. 18: 25–66, DOI 10.1007/BF02020961.
  • 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.
  • Gilmore, P. C. & Hoffman, A. J. (1964), "A characterization of comparability graphs and of interval graphs", Canadian Journal of Mathematics 16: 539–548, DOI 10.4153/CJM-1964-055-5.
  • Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7.
  • Golumbic, M.; Rotem, D. & Urrutia, J. (1983), "Comparability graphs and intersection graphs", Discrete Mathematics 43 (1): 37–46, DOI 10.1016/0012-365X(83)90019-5.
  • Jung, H. A. (1978), "On a class of posets and the corresponding comparability graphs", Journal of Combinatorial Theory, Series B 24 (2): 125–133, DOI 10.1016/0095-8956(78)90013-8.
  • Lovász, L. (1983), "Perfect graphs", Selected Topics in Graph Theory, vol. 2, London: Academic Press, pp. 55–87.
  • Maffray, Frédéric (2003), "On the coloration of perfect graphs", in Reed, Bruce A. & Sales, Cláudia L., Recent Advances in Algorithms and Combinatorics, vol. 11, CMS Books in Mathematics, Springer-Verlag, pp. 65–84, DOI 10.1007/0-387-22444-0_3.
  • McConnell, R. M. & Spinrad, J. (1997), "Linear-time transitive orientation", 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 19–25.
  • Seymour, Paul (2006), "How the proof of the strong perfect graph conjecture was found", Gazette des Mathématiciens (no. 109): 69–83, <http://users.encs.concordia.ca/~chvatal/perfect/pds.pdf>.
  • Trotter, William T. (1992), Combinatorics and Partially Ordered Sets — Dimension Theory, Johns Hopkins University Press.
  • Urrutia, Jorge (1989), Rival, I., ed., Partial orders and Euclidean geometry, Kluwer Academic Publishers, pp. 327–436.