Доматик подела

У теорији графова, доматик подела графа $G=(V,E)$ је подела скупа чворова $V_{1}$ у дисјунктне скупове $V_{2}$ ,..., $V_{K}$ такве да сваки V_i је доминантни скуп за G. Слика на десној страни приказује доматик поделу графа; овде је доминирајући скуп $V_{1}$ садржи жуте чворове, $V_{2}$ садржи зелене чворове и $V_{3}$ садржи плаве чворове.

Доматик број је максимална вредност доматик поделе, то јест, максимални број дисјунктних доминирајућих скупова. Граф на слици има доматик број 3. Лако је да се види да је доматик број бар 3 зато што смо направили доматик поделу вредности 3. Да би видели да је доматик број највише 3, прво показимо једноставну горњу границу.

Горње границе[уреди | уреди извор]

Нека је $\delta$ минимални степен графа $G$ . Доматик број од $G$ је највише $\delta +1$ . Да би то показали, посматрајмо чвор $v$ степена $\delta$ . Нека $N$ чине $v$ и његови суседни чворови. Знамо да (1) сваки доминирајући скуп $V_{i}$ мора садржати најмање један чвор из $N$ (доминација), и (2) сваки чвор у $N$ је садржан у највише једном доминирајућем скупу $V_{i}$ (дисјунктност). Дакле постоји највисе $|N|=\delta +1$ дисјунктних доминирајућих скупова.

Граф на слици има минимални степен $\delta =2$ и, дакле, његов доматик број је највише 3. Дакле, показали смо да је његов доматик број тачно 3; на слици је приказана доматик подела највеће величине.

Доње границе[уреди | уреди извор]

Ако нема изолованих чворова у графу (што значи, $\delta$ ≥ 1), онда је доматик број најмање 2. Да би то видели, уочимо да је (1) слаба обојеност са две боје доматик подела ако нема изолованих чворова и (2) сваки граф има слабу обојеност са две боје. Алтернативно, (1) максимални независни скуп је доминирајући скуп и (2) комплемент максималног независног скупа је такође доминантни скуп ако нема изолованих чворова.

Слика на десној страни приказује слабу обојеност са две боје, која је такође доматик подела величине 2: тамни чворови чине доминирајући скуп, а светли чворови чине други доминирајући скуп (светли чворови формирају максимални независни скуп). Видети слабу обојеност за више информација.

Комплексност израчунавања[уреди | уреди извор]

Налажење доматик поделе величине 1 је тривијално: нека је $V_{1}=V$ . Налажење доматик поделе величине 2 (или одређивање да она не постоји) је једноставно: проверити да ли постоје изоловани чворови, и ако не постоје, пронаћи слабу обојеност са две боје.

Дакако, налажење максималне величине доматик поделе је рачунски тешко. Специјално, следећи проблем одлучивања, познат као проблем доматик броја, је НП-комплетан: за дати граф $G$ и цео број $K$ , одредити да ли је доматик број од $G$ најмање $K$ . Дакле, проблем одређивања доматик броја датог графа је НП-тежак и проблем налаћења доматик поделе максималне величине је НП-тежак такође.

Постоји алгоритам полиномијалног времена са гарантованом логаритамском апроксимацијом^[1], то јест, могуће је наћи доматик поделу чија величина је оптимална до на фактор $O(\log |V|)$ .

Дакако, не постоји приближни алгоритам полиномијалне сложености са подлогаритамским приближним фактором.^[1] Прецизније, приближни алгоритам полиномијалне слозености за доматик поделу са приближним фактором $(1-\epsilon )\ln |V|$ за константно $\epsilon >0$ би указало да сви НП проблеми могу бити решени у скоро супер-полиномијалној слозености $n^{O(\log \log n)}$ .

Поређење са сличним приступима[уреди | уреди извор]

Доматик подела: Подела чворова у дисјунктне доминирајуће скупове. Доматик број је максимални број оваквих скупова.
Бојење чворова: Подела чворова у дисјунктне независне скупове. Хроматски број је минимални број оваквих скупова.
Подела клика: Подела чворова у дисјунктне клике. Еквиваленто са бојењем чворова комплементарног графа.
Бојење ивица: Подела ивица на неповезана упарења. Хроматски број ивице је најмањи број ових скупова.

Нека је G = (U ∪ V, E) бипартитни граф без изолованих чворова; све ивице су облика {u, v} ∈ E и са u ∈ U v ∈ V. Тада, {U, V} је уједно и бојење чворова са две боје и доматик подела величине 2; скупови U и V су независни доминирајући скупови. Хроматски број од G је тачно 2; не постоји чвор бојење једном бојом. Доматик број од G је најмање 2. Могуће је да постоји већа доматик подела; на пример, комплетан бипартитан граф K_{n, n} за свако n ≥ 2 има доматик број n.

Напомене[уреди | уреди извор]

^ ^а ^б Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy; Srinivasan, Aravind (март 2002), „Approximating the domatic number”, SIAM Journal on Computing, 32 (1): 172—195, MR 1954859, doi:10.1137/S0097539700380754

Референце[уреди | уреди извор]

Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5 . A1.1: GT3, p. 190.
Cockayne, E. J.; Hedetniemi, Stephen T. (1975), „Optimal domination in graphs”, IEEE Transactions on Circuits and Systems, CAS-22 (11): 855—857, MR 0384608, doi:10.1109/TCS.1975.1083994 .

[feige-2002-1] а ^б Feige, Uriel; Halldórsson, Magnús M.; Kortsarz, Guy; Srinivasan, Aravind (март 2002), „Approximating the domatic number”, SIAM Journal on Computing, 32 (1): 172—195, MR 1954859, doi:10.1137/S0097539700380754

[1]