Domatiskt nummer - Domatic number

I grafteori , en Domatic partition av en graf är en partition av i disjunkta uppsättningar , , ..., så att varje V _i är en dominerande uppsättning för G . Figuren till höger visar en domatisk delning av ett diagram; här består den dominerande uppsättningen av de gula hörnen, består av de gröna hörnen och består av de blå hörnen. ${\ displaystyle G = (V, E)}$${\ displaystyle V}$${\ displaystyle V_ {1}}$${\ displaystyle V_ {2}}$${\ displaystyle V_ {K}}$${\ displaystyle V_ {1}}$${\ displaystyle V_ {2}}$${\ displaystyle V_ {3}}$

Det domatiska talet är den maximala storleken på en domatisk partition, det vill säga det maximala antalet osammanhängande dominerande uppsättningar. Grafen i figuren har domatiskt nummer 3. Det är lätt att se att det domatiska talet är minst 3 eftersom vi har presenterat en domatisk partition med storlek 3. För att se att det domatiska talet är högst 3, granskar vi först en enkel övre gräns.

Övre gränser

Låt vara den minsta graden av grafen . Det domatiska antalet är högst . För att se detta, överväg en toppunkt av grad . Låt bestå av och dess grannar. Vi vet att (1) varje dominerande uppsättning måste innehålla minst en toppunkt i (dominans), och (2) varje toppunkt i finns i högst en dominerande uppsättning (disjointness). Därför finns det högst oregelbundna dominerande uppsättningar. ${\ displaystyle \ delta}$${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle \ delta +1}$${\ displaystyle v}$${\ displaystyle \ delta}$${\ displaystyle N}$${\ displaystyle v}$${\ displaystyle V_ {i}}$${\ displaystyle N}$${\ displaystyle N}$${\ displaystyle V_ {i}}$${\ displaystyle | N | = \ delta +1}$

Grafen i figuren har minsta grad , och därför är dess domatiska tal högst 3. Därför har vi visat att dess domatiska tal är exakt 3; figuren visar en domatisk partition med maximal storlek. ${\ displaystyle \ delta = 2}$

Lägre gränser

Om det inte finns någon isolerad toppunkt i grafen (det vill säga  ≥ 1), är det domatiska talet minst 2. För att se detta, observera att (1) en svag 2-färgning är en domatisk partition om det inte finns någon isolerad toppunkt och (2) alla diagram har en svag 2-färgning. Alternativt är (1) en maximal oberoende uppsättning en dominerande uppsättning, och (2) komplementet till en maximal oberoende uppsättning är också en dominerande uppsättning om det inte finns några isolerade hörn. ${\ displaystyle \ delta}$

Figuren till höger visar en svag 2-färgning, som också är en domatisk delning av storlek 2: de mörka noderna är en dominerande uppsättning, och de ljusa noderna är en annan dominerande uppsättning (ljusknapparna bildar en maximal oberoende uppsättning). Se svag färgning för mer information.

Beräkningskomplexitet

Att hitta en domatisk partition i storlek 1 är trivialt: låt . Det är enkelt att hitta en domatisk partition i storlek 2 (eller bestämma att den inte finns): kontrollera om det finns isolerade noder, och om inte, hitta en svag 2-färgning. ${\ displaystyle V_ {1} = V}$

Att hitta en domatisk partition med maximal storlek är dock beräkningsmässigt svårt. Specifikt är följande beslutsproblem , känt som problemet med domatiskt tal , NP-komplett : med en graf och ett heltal , avgör om det domatiska antalet är minst . Därför är problemet med att bestämma det domatiska antalet för en given graf NP-hårt , och problemet med att hitta en domatisk partition med maximal storlek är också NP-hårt. ${\ displaystyle G}$${\ displaystyle K}$${\ displaystyle G}$${\ displaystyle K}$

Det finns en approximationsalgoritm för polynom-tid med en logaritmisk approximationsgaranti, det vill säga det är möjligt att hitta en domatisk partition vars storlek ligger inom en faktor av det optimala. ${\ displaystyle O (\ log | V |)}$

Under troliga komplexitetsteoretiska antaganden finns det dock ingen polynom-tids-approximationsalgoritm med en sub-logaritmisk approximationsfaktor. Mer specifikt skulle en approximationsalgoritm för polynomtid för domatisk partition med approximationsfaktorn för en konstant innebära att alla problem i NP kan lösas på något superpolynomtid . ${\ displaystyle (1- \ epsilon) \ ln | V |}$${\ displaystyle \ epsilon> 0}$${\ displaystyle n^{O (\ log \ log n)}}$

Jämförelse med liknande begrepp

Domatisk partition

Uppdelning av hörn i osammanhängande dominerande uppsättningar. Det domatiska talet är det maximala antalet sådana uppsättningar.

Vertex färgning

Delning av hörn i oskiljaktiga oberoende uppsättningar . Det kromatiska talet är det minsta antalet sådana uppsättningar.

Klicka partition

Uppdelning av hörn i olika klickar . Lika med vertexfärgning i komplementgrafen .

Kantfärgning

Delning av kanter i oskarvade matchningar . Det kanten kromatiska numret är det minsta antalet sådana uppsättningar.

Låt G  = ( U  ∪  V ,  E ) vara en tvåpartig graf utan isolerade noder; alla kanter är på formen { u ,  v } ∈  E med u  ∈  U och v  ∈  V . Då är { U ,  V } både en toppunkt 2-färgning och en domatisk partition av storlek 2; uppsättningarna U och V är oberoende dominerande uppsättningar. Det kromatiska antalet G är exakt 2; det finns ingen toppunkt 1-färgning. Det domatiska antalet G är minst 2. Det är möjligt att det finns en större domatisk partition; till exempel har hela bipartitdiagrammet K _{n , n} för alla n  ≥ 2 ett domatiskt tal n .

Anteckningar

Referenser

• Garey, Michael R .; Johnson, David S. (1979), Computers and Intractability: A Guide to theory of NP-Completeness , W. H. Freeman , ISBN 0-7167-1045-5. A1.1: GT3, sid. 190.
• Cockayne, EJ; Hedetniemi, Stephen T. (1975), "Optimal dominans i grafer", IEEE-transaktioner på kretsar och system , CAS-22 (11): 855–857, doi : 10.1109/TCS.1975.1083994 , MR  0384608.