Domatik podela

U teoriji grafova, domatik podela grafa $G=(V,E)$ je podela skupa čvorova $V_{1}$ u disjunktne skupove $V_{2}$ ,..., $V_{K}$ takve da svaki V_i je dominantni skup za G. Slika na desnoj strani prikazuje domatik podelu grafa; ovde je dominirajući skup $V_{1}$ sadrži žute čvorove, $V_{2}$ sadrži zelene čvorove i $V_{3}$ sadrži plave čvorove.

Domatik broj je maksimalna vrednost domatik podele, to jest, maksimalni broj disjunktnih dominirajućih skupova. Graf na slici ima domatik broj 3. Lako je da se vidi da je domatik broj bar 3 zato što smo napravili domatik podelu vrednosti 3. Da bi videli da je domatik broj najviše 3, prvo pokazimo jednostavnu gornju granicu.

Gornje granice[uredi | uredi izvor]

Neka je $\delta$ minimalni stepen grafa $G$ . Domatik broj od $G$ je najviše $\delta +1$ . Da bi to pokazali, posmatrajmo čvor $v$ stepena $\delta$ . Neka $N$ čine $v$ i njegovi susedni čvorovi. Znamo da (1) svaki dominirajući skup $V_{i}$ mora sadržati najmanje jedan čvor iz $N$ (dominacija), i (2) svaki čvor u $N$ je sadržan u najviše jednom dominirajućem skupu $V_{i}$ (disjunktnost). Dakle postoji najvise $|N|=\delta +1$ disjunktnih dominirajućih skupova.

Graf na slici ima minimalni stepen $\delta =2$ i, dakle, njegov domatik broj je najviše 3. Dakle, pokazali smo da je njegov domatik broj tačno 3; na slici je prikazana domatik podela najveće veličine.

Donje granice[uredi | uredi izvor]

Ako nema izolovanih čvorova u grafu (što znači, $\delta$ ≥ 1), onda je domatik broj najmanje 2. Da bi to videli, uočimo da je (1) slaba obojenost sa dve boje domatik podela ako nema izolovanih čvorova i (2) svaki graf ima slabu obojenost sa dve boje. Alternativno, (1) maksimalni nezavisni skup je dominirajući skup i (2) komplement maksimalnog nezavisnog skupa je takođe dominantni skup ako nema izolovanih čvorova.

Slika na desnoj strani prikazuje slabu obojenost sa dve boje, koja je takođe domatik podela veličine 2: tamni čvorovi čine dominirajući skup, a svetli čvorovi čine drugi dominirajući skup (svetli čvorovi formiraju maksimalni nezavisni skup). Videti slabu obojenost za više informacija.

Kompleksnost izračunavanja[uredi | uredi izvor]

Nalaženje domatik podele veličine 1 je trivijalno: neka je $V_{1}=V$ . Nalaženje domatik podele veličine 2 (ili određivanje da ona ne postoji) je jednostavno: proveriti da li postoje izolovani čvorovi, i ako ne postoje, pronaći slabu obojenost sa dve boje.

Dakako, nalaženje maksimalne veličine domatik podele je računski teško. Specijalno, sledeći problem odlučivanja, poznat kao problem domatik broja, je NP-kompletan: za dati graf $G$ i ceo broj $K$ , odrediti da li je domatik broj od $G$ najmanje $K$ . Dakle, problem određivanja domatik broja datog grafa je NP-težak i problem nalaćenja domatik podele maksimalne veličine je NP-težak takođe.

Postoji algoritam polinomijalnog vremena sa garantovanom logaritamskom aproksimacijom^[1], to jest, moguće je naći domatik podelu čija veličina je optimalna do na faktor $O(\log |V|)$ .

Dakako, ne postoji približni algoritam polinomijalne složenosti sa podlogaritamskim približnim faktorom.^[1] Preciznije, približni algoritam polinomijalne slozenosti za domatik podelu sa približnim faktorom $(1-\epsilon )\ln |V|$ za konstantno $\epsilon >0$ bi ukazalo da svi NP problemi mogu biti rešeni u skoro super-polinomijalnoj slozenosti $n^{O(\log \log n)}$ .

Poređenje sa sličnim pristupima[uredi | uredi izvor]

Domatik podela: Podela čvorova u disjunktne dominirajuće skupove. Domatik broj je maksimalni broj ovakvih skupova.
Bojenje čvorova: Podela čvorova u disjunktne nezavisne skupove. Hromatski broj je minimalni broj ovakvih skupova.
Podela klika: Podela čvorova u disjunktne klike. Ekvivalento sa bojenjem čvorova komplementarnog grafa.
Bojenje ivica: Podela ivica na nepovezana uparenja. Hromatski broj ivice je najmanji broj ovih skupova.

Neka je G = (U ∪ V, E) bipartitni graf bez izolovanih čvorova; sve ivice su oblika {u, v} ∈ E i sa u ∈ U v ∈ V. Tada, {U, V} je ujedno i bojenje čvorova sa dve boje i domatik podela veličine 2; skupovi U i V su nezavisni dominirajući skupovi. Hromatski broj od G je tačno 2; ne postoji čvor bojenje jednom bojom. Domatik broj od G je najmanje 2. Moguće je da postoji veća domatik podela; na primer, kompletan bipartitan graf K_{n, n} za svako n ≥ 2 ima domatik broj n.

Napomene[uredi | uredi izvor]

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

Reference[uredi | uredi izvor]

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 (mart 2002), „Approximating the domatic number”, SIAM Journal on Computing, 32 (1): 172—195, MR 1954859, doi:10.1137/S0097539700380754

[1]