Domatikus szám

A gráfelméletben a gráf domatikus partíciója egy csúcshalmaz diszjunkt , ,..., halmazokra történő felosztása úgy , hogy minden V i halmaz a G gráf domináns halmaza . A jobb oldali ábra egy gráf egy domatikus partícióját mutatja. Az ábrán a domináns halmaz sárga csúcsokból áll, zöld csúcsokból és kék csúcsokból áll. $G=(V,E)$ $V$ $V_{1}$ $V_{2}$ $V_{K}$ $V_{1}$ $V_{2}$ $V_{3}$

A domináns szám a domináns partíció maximális mérete, azaz a nem átfedő domináns halmazok maximális száma. Az ábrán látható grafikon domatikus száma 3. Könnyen belátható, hogy a domatikus szám legalább 3, mivel egy 3-as méretű domatikus partíciót mutattunk be. Ahhoz, hogy megértsük, egy domatikus szám nem haladja meg a 3-at, először vegyük figyelembe a felső határt.

Felső határok

Legyen a gráf minimális foka . A gráf domatikus száma nem haladja meg a . Ennek megértéséhez vegye figyelembe a diploma felső részét . Álljon egy csúcsból és szomszédaiból. Tudjuk, hogy (1) minden domináns halmaznak tartalmaznia kell legalább egy csúcsot a (dominancia)-ból, és (2) minden csúcsnak legfeljebb egy domináns halmazban kell szerepelnie (nincs metszéspont). Így maximum nem átfedő domináns halmazok vannak. $\delta$ $G$ $G$ $\delta +1$ $v$ $\delta$ $N$ $v$ $V_i$ $N$ $N$ $V_i$ $|N|=\delta +1$

Az ábra gráfjának minimális foka van , ezért domináns száma nem haladja meg a 3-at. Így megmutattuk, hogy a domatikus szám pontosan 3. Az ábrán egy maximális méretű domatikus partíció látható. $\delta=2$

Alsó határok

Ha a gráfnak nincsenek izolált csúcsai (vagyis ≥ 1), akkor a domatikus szám legalább 2. Ennek megértéséhez vegye figyelembe, hogy (1) a gyenge 2-színezés egy domatikus csempézés, ha nincsenek elszigetelt csúcsok, és (2) bármely gráfnak gyenge 2-színe van. Alternatív megoldásként (1) a legnagyobb független halmaz a domináns halmaz, és (2) a maximális független halmaz komplementere is a domináns halmaz, ha nincsenek izolált csúcsok. $\delta$

A jobb oldali ábra egy gyenge 2-színezést mutat, ami egy 2-es méretű domatikus csempézés - a sötét csúcsok a domináns halmaz, a világos csúcsok pedig egy másik domináns halmaz (a világos csúcsok alkotják a legnagyobb független halmazt). További információért lásd a " Gyenge színezés " című cikket .

Számítási összetettség

Az 1-es méretű domatic partíció keresése triviális – ez az . A 2-es méretű domatikus partíció megtalálása (vagy annak megállapítása, hogy ilyen partíció nem létezik) egyszerű - ellenőrizze, hogy nincsenek-e elszigetelt csúcsok, és ha nem, keressen egy gyenge 2-színezést. $V_{1}=V$

Nehéz azonban maximális méretű domatikus partíciót találni. Konkrétan a következő , domatikus számproblémaként ismert megoldhatósági probléma NP-teljes : adott egy gráf és egy egész szám, határozza meg, hogy az értékgráf domatikus száma kisebb-e vagy sem . Így egy adott gráf domatikus számának megtalálása NP-nehéz , így a maximális méretű domatikus partíció megtalálása is NP-nehéz. $G$ $K$ $G$ $K$

Létezik egy polinomiális idejű közelítő algoritmus , amely logaritmikus közelítési garanciával rendelkezik [1] , vagyis találhatunk olyan domatikus partíciót, amelynek mérete legfeljebb egy tényezővel van távolabb az optimumtól. $O(\log |V|)$

Jól megalapozott feltevések mellett azonban nem létezik szublogaritmikus közelítési tényezővel rendelkező polinomiális idő közelítési algoritmus [1] . Pontosabban, egy állandó közelítési együtthatóval rendelkező domatikus partíció polinomiális idő közelítő algoritmusa azt jelenti, hogy az NP osztály összes problémája megoldható kissé szuperpolinom időben . $(1-\epszilon )\ln |V|$ $\epsilon > 0$ ${\displaystyle n^{O(\log \log n)))$

Összehasonlítás hasonló fogalmakkal

Domatikus partíció A csúcsok felosztása nem metsző domináns halmazokra. A domatic szám az ilyen készletek maximális száma. Vertex színezés A csúcsok felosztása nem metsző független halmazokra . A kromatikus szám az ilyen halmazok minimális száma. Kattintásokra bontás Csúcsok felosztása nem metsző klikkekre . Egyenértékű a gráf komplementerének csúcsszínezésével . élszínezés Élek felosztása nem metsző illesztésekre . Az élkromatikus szám az ilyen halmazok minimális száma.

Legyen G = ( U ∪ V , E ) egy kétrészes gráf izolált csúcsok nélkül. Minden él { u , v } ∈ E alakú , ahol u ∈ U és v ∈ V . Ekkor az { U , V } egy 2 csúcsú színezés és egy 2 méretű domináns partíció. Az U és V halmazok független domináns halmazok. G kromatikus száma pontosan 2. Nincs csúcs 1-színezés. A G gráf domináns száma legalább 2. Lehet, hogy nagyobb tartományi partíció. Például egy teljes kétrészes gráf K n , n bármely n ≥ 2 esetén n domatikus számmal rendelkezik .

Jegyzetek

↑ 1 2 Feige, Halldórsson, Kortsarz, Srinivasan, 2002 , p. 172–195.

Irodalom

Michael R. Garey, David S. Johnson. Számítógépek és kezelhetetlenség: Útmutató az NP-teljesség elméletéhez . - W. H. Freeman, 1979. - ISBN 0-7167-1045-5 . A1.1. . A1.1: GT3
EJ Cockayne, Stephen T. Hedetniemi. Optimális dominancia a grafikonokban // IEEE Transactions on Circuits and Systems. - 1975. - T. CAS-22 , sz. 11 . – S. 855–857 . - doi : 10.1109/TCS.1975.1083994 .
Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz, Aravind Srinivasan. A domatikus szám közelítése // SIAM Journal on Computing . - 2002. - T. 32 , sz. 1 . – S. 172–195 . - doi : 10.1137/S0097539700380754 .