Összehasonlíthatósági gráf

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

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

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

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

  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.
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Összehasonlíthatósági_gráf&oldid=20412246”