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
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áratranzití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áfszomszédsági relációjatranzití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.
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.
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.
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 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]
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.
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.
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 sciences254: 1370–1371.
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.