Domatiskt nummer

I grafteorin är en domatisk partition av en graf en uppdelning av en uppsättning hörn i disjunkta uppsättningar , ,..., , så att varje uppsättning Vi är en dominerande uppsättning av grafen G . Bilden till höger visar en domatisk partition av en graf. I figuren består den dominerande mängden av gula hörn, består av gröna hörn och består av blå hörn. $G=(V,E)$ $V$ $V_{1}$ $V_{2}$ $V_{K}$ $V_{1}$ $V_{2}$ $V_{3}$

Det domatiska numret är den maximala storleken på en domatisk partition, det vill säga det maximala antalet icke-överlappande dominerande uppsättningar. Grafen i figuren har ett domatiskt nummer 3. Det är lätt att se att det domatiska talet är minst 3, eftersom vi har presenterat en domatisk partition av storlek 3. För att förstå att ett domatiskt nummer inte överstiger 3, måste vi först överväga de övre gränserna.

Övre gränser

Låt vara den lägsta graden av grafen . Grafens domatiska nummer överstiger inte . För att förstå detta, överväg toppen av graden . Låt den bestå av en vertex och dess grannar. Vi vet att (1) varje dominerande mängd måste innehålla minst ett hörn från (dominans), och (2) varje hörn från finns i högst en dominerande mängd (inga skärningar). Således finns det ett maximum av icke-överlappande dominerande uppsättningar. $\delta$ $G$ $G$ $\delta +1$ $v$ $\delta$ $N$ $v$ $V_i$ $N$ $N$ $V_i$ $|N|=\delta +1$

Grafen i figuren har en lägsta grad , och därför överstiger dess dominerande antal inte 3. Vi har alltså visat att det domatiska talet är exakt 3. Figuren visar en domatisk partition av maximal storlek. $\delta=2$

Nedre gränser

Om grafen inte har några isolerade hörn (det vill säga ≥ 1), så är det domatiska talet minst 2. För att förstå detta, notera att (1) en svag 2-färgning är en domatisk sida om det inte finns några isolerade hörn, och (2) vilken graf som helst har en svag 2-färgning. Alternativt är (1) den största oberoende mängden den dominanta mängden och (2) komplementet till den maximala oberoende mängden är också den dominanta mängden om det inte finns några isolerade hörn. $\delta$

Figuren till höger visar en svag 2-färgning, vilket är en domatisk plattsättning av storlek 2 - mörka hörn är den dominerande uppsättningen och ljusa hörn är en annan dominant uppsättning (ljusa hörn bildar den största oberoende mängden). Se artikeln " Svag färg " för mer information.

Beräkningskomplexitet

Sökandet efter en domatisk partition av storlek 1 är trivial - det är . Att hitta en domatisk partition av storlek 2 (eller ta reda på att en sådan partition inte finns) är enkelt - kontrollera att det inte finns några isolerade hörn, och om inte, hitta en svag 2-färgning. $V_{1}=V$

Det är dock svårt att hitta en domatisk partition med maximal storlek. I synnerhet är följande lösbarhetsproblem , känt som det domatiska talproblemet , NP-komplett : givet en graf och ett heltal, avgör om värdegrafens domatiska nummer är mindre än eller inte . Således är problemet med att hitta det domatiska numret för en given graf NP-hårt , så problemet med att hitta den maximala storleken på den domatiska partitionen är också NP-hårt. $G$ $K$ $G$ $K$

Det finns en polynom- tidsapproximationsalgoritm med en logaritmisk garanti för approximation [1] , det vill säga man kan hitta en domatisk partition vars storlek inte är längre än en faktor från det optimala. $O(\log |V|)$

Men under välgrundade antaganden finns det ingen polynom-tidsapproximationsalgoritm med en sublogaritmisk approximationsfaktor [1] . Mer specifikt innebär polynom-tidsapproximationsalgoritmen för en domatisk partition med en approximationskoefficient för en konstant att alla problem i klass NP kan lösas i lätt superpolynomisk tid . $(1-\epsilon )\ln |V|$ $\epsilon > 0$ ${\displaystyle n^{O(\log \log n)))$

Jämförelse med liknande begrepp

Domatisk partition Uppdelning av hörn i icke-korsande dominanta mängder. Det domatiska numret är det maximala antalet sådana uppsättningar. Vertexfärgning Uppdelning av hörn i icke-korsande oberoende uppsättningar . Det kromatiska antalet är det minsta antalet sådana uppsättningar. Delas upp i klick Dela upp hörn i icke-korsande klickar . Motsvarar vertexfärgning av grafens komplement . kantfärgning Dela kanter till icke-korsande matchningar . Det kromatiska kanttalet är det minsta antalet sådana uppsättningar.

Låt G = ( U ∪ V , E ) vara en tvådelad graf utan isolerade hörn. Alla kanter har formen { u , v } ∈ E , där u ∈ U och v ∈ V . Då är { U , V } en färgning med 2 vertex och en dominant partition av storlek 2. Uppsättningarna U och V är oberoende dominerande uppsättningar. Det kromatiska talet för G är exakt 2. Det finns ingen vertex 1-färgning. Det dominerande talet för grafen G är minst 2. Det kan finnas en större domatisk partition. Till exempel har en komplett tvådelad graf K n , n för vilken som helst n ≥ 2 ett domatiskt nummer n .

Anteckningar

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

Litteratur

Michael R. Garey, David S. Johnson. Datorer och svårhanterlighet: En guide till teorin om NP-fullständighet . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 . A1.1. . A1.1: GT3
EJ Cockayne, Stephen T. Hedetniemi. Optimal dominans i grafer // IEEE-transaktioner på kretsar och system. - 1975. - T. CAS-22 , nr. 11 . — S. 855–857 . - doi : 10.1109/TCS.1975.1083994 .
Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz, Aravind Srinivasan. Uppskattning av domatiskt nummer // SIAM Journal on Computing . - 2002. - T. 32 , nr. 1 . — S. 172–195 . - doi : 10.1137/S0097539700380754 .