DOMINOWANIE W
GRAFACH
Magdalena Lemańska
DOMINOWANIE W
GRAFACH
Magdalena Lemańska
Problem pięciu królowych (1850 r).
Jaka jest najmniejsza liczba królowych jaka może być
rozmieszczona na szachownicy 8 x 8 tak, by każde pole było
w zasięgu jakiejś królowej?
Problem pięciu królowych-problem znalezienia „zbioru
dominującego” o mocy 5.
G=(V,E);
V=V(G)- zbiór wierzchołków, |V(G)|=n(G);
E=E(G)- zbiór krawędzi.
Zbiór D
V(G) jest zbiorem dominującym w
grafie G, jeśli każdy wierzchołek ze zbioru
V(G)-D w grafie G jest dominowany przez
wierzchołek ze zbioru D.
Dla danych wierzchołków x,y grafu G mówimy, że x dominuje y,
jeśli x=y albo jeśli xy
E(G). W takim razie x dominuje siebie
i wszystkie wierzchołki sąsiednie z wierzchołkiem x.
Otwarte sąsiedztwo wierzchołka v: N
G
(v) –
zbiór wszystkich wierzchołków
połączonych krawędzią z v;
Domknięte sąsiedztwo wierzchołka v: N
G
[v]=
N
G
(v)
{v}
Otwarte sąsiedztwo zbioru X
V: N
G
(X) =U
v
X
N
G
(v);
Domknięte sąsiedztwo zbioru:
N
G
[X]=N
G
(X)
X.
Jest kilka sposobów zdefiniowania zbioru dominującego,
każdy z nich ilustruje różne aspekty pojęcia dominowania.
d
G
(u,v) – odległość między u i v - długość
najkrótszej
(u-v)- ścieżki w G
Zbiór D
V(G) wierzchołków grafu G=(V,E) jest zbiorem
dominującym wtedy i tylko wtedy, gdy:
(i) dla każdego wierzchołka v
V-D istnieje wierzchołek u
D
taki, że v jest sąsiedni do u;
(ii) dla każdego wierzchołka v
V-D, d
G
(v,D)
1;
(iii) N
G
[D]=V;
(iv) dla każdego wierzchołka v
V-D, |N
G
(v)
D|
1, czyli
każdy wierzchołek v
V-D jest sąsiedni do przynajmniej
jednego wierzchołka z D;
(v) dla każdego wierzchołka v
V, |N
G
[v]
D|
1.
Jeśli D jest dominujący w G, to każdy nadzbiór D’
D też jest
dominujący.
Z drugiej strony, nie każdy podzbiór D”
D jest dominujący w G.
Zbiór dominujący D jest minimalny dominujący, jeśli żaden
podzbiór właściwy D”
D nie jest dominujący.
Twierdzenie 1. Zbiór dominujący D jest minimalnym zbiorem
dominującym wtedy i tylko wtedy, gdy dla każdego wierzchołka
u
D zachodzi jeden z dwóch warunków:
a) u jest izolowany w D;
b) istnieje v
V-D, dla którego N
G
(v)
D = {u}.
Niech D - zbiór dominujący i niech u
D. Mówimy, że
wierzchołek v jest prywatnym sąsiadem wierzchołka u
(w odniesieniu do D), jeśli N
G
[v]
D = {u}.
Zbiór prywatnych sąsiadów wierzchołka u:
PN[u,D]={v : N
G
[v]
D = {u} }.
u
PN[u,D], jeśli jest izolowany w podgrafie indukowanym
G[D], wtedy mówimy, że u jest swoim własnym prywatnym
sąsiadem.
Zbiór dominujący D jest minimalny dominujący wtedy i tylko
wtedy, gdy każdy wierzchołek z D ma przynajmniej jednego
prywatnego sąsiada.
Twierdzenie 2. Każdy spójny graf G rzędu co najmniej dwa
posiada zbiór dominujący D, którego dopełnienie V-D też jest
zbiorem dominującym.
Twierdzenie 3. Jeśli G jest grafem bez wierzchołków izolowanych,
to dopełnienie V-D każdego minimalnego zbioru dominującego D
jest zbiorem dominującym w G.
Moc najmniejszego zbioru dominującego w grafie G nazywamy
liczbą dominowania grafu G i oznaczamy
(G).
Moc największego zbioru minimalnego dominującego w grafie G
nazywamy górną liczbą dominowania grafu G i oznaczamy
(G).
(G)=3
(G)=5
Ograniczenia na liczbę dominowania.
Twierdzenie 4 (Ore) Jeśli graf G nie ma wierzchołków
izolowanych, to
(G)
n/2.
Twierdzenie 5. Dla grafu G bez wierzchołków izolowanych,
rzędu n, gdzie n jest parzyste,
(G) = n/2 wtedy i tylko wtedy,
gdy składowymi grafu G są cykl C
4
albo korona H
K
1
dla
dowolnego grafu spójnego H.
Korona dwóch grafów G
1
i G
2
jest to graf G = G
1
G
2
powstały
z jednej kopii G
1
oraz |V(G
1
)| kopii G
2
gdzie i-ty wierzchołek G
1
jest sąsiedni do każdego wierzchołka w i-tej kopii G
2
.
W szczególności, G = H
K
1
jest grafem powstałym z kopii H
gdzie do każdego wierzchołka v
V(H) dodajemy nowy
wierzchołek v’ i krawędź wiszącą vv’.
Twierdzenie 6. Dla każdego grafu G,
(G)
n -
(G).
Podział krawędzi uv w grafie G otrzymujemy przez usunięcie
krawędzi uv, dodanie nowego wierzchołka w oraz dodanie
krawędzi uw i vw.
Ranny pająk jest to graf powstały przez podział co najwyżej
t-1 krawędzi gwiazdy K
1,t
dla t
0.
Twierdzenie 7. Dla każdego drzewa T,
(T) = n -
(T) wtedy
i tylko wtedy, gdy T jest rannym pająkiem.
Twierdzenie 8. Jeśli graf G nie ma wierzchołków izolowanych
oraz diam(G)
3, to
(Gd) = 2, gdzie Gd jest dopełnieniem grafu G.
Twierdzenie 9. Jeśli
(Gd)
3, to diam(G)
2.
Obwód grafu G, ozn. g(G) jest to długość najkrótszego cyklu
w G (jeśli graf posiada cykl).
Twierdzenie 10. Dla każdego grafu G,
(a)jeśli g(G)
5, to
(G)
(G),
(b)jeśli g(G)
6, to
(G)
2(
(G)-1).
Zbiory niezależne.
Niech i(G) oznacza moc najmniejszego maksymalnego zbioru
niezależnego w grafie G;
0
– moc największego zbioru niezależnego w G.
Drzewo T ma zbiory maksymalne niezależne o trzech rozmiarach.
i(T)=3
0
(T)=5
Twierdzenie 11. Niezależny zbiór S jest maksymalny niezależny
wtedy i tylko wtedy, gdy jest niezależny i dominujący.
Zbiory dominujące.
Drzewo T ma zbiory minimalne dominujące o czterech rozmiarach.
(T)=2
(T)=5
Wniosek: Każdy zbiór maksymalny niezależny jest zbiorem
dominującym.
Twierdzenie 12. Każdy zbiór maksymalny niezależny w G jest
minimalnym zbiorem dominującym w G.
Wniosek: Dla każdego grafu G,
(G)
i(G)
0
(G)
(G).
Zbiory nienadmierne.
Możemy powiedzieć, że zbiór D jest zbiorem minimalnym
dominującym w G wtedy i tylko wtedy, gdy:
(*) dla każdego wierzchołka v
D, istnieje wierzchołek
w
V-(D-{v}), który nie jest dominowany przez D-{v}.
Warunek (*) można wyrazić w języku „prywatnych sąsiadów”.
PN[4,D]={1,2,3,4}PN[6,D]={6} PN[7,D]={7}
PN[v,D]=N
G
[v]-N
G
[D-{v}]
W warunku (*) wierzchołek w musi być prywatnym sąsiadem
wierzchołka v w odniesieniu do D (możliwe jest w=v).
(**) zbiór D jest zbiorem minimalnym dominującym w G wtedy
i tylko wtedy, gdy dla każdego wierzchołka v
D, PN[v,D]
,
czyli każdy wierzchołek v
D ma przynajmniej jednego
prywatnego sąsiada.
Jeśli jest spełniony warunek (**), to mówimy, że zbiór D jest
zbiorem nienadmiernym.
Twierdzenie 13. Zbiór dominujący D jest minimalny dominujący
wtedy i tylko wtedy, gdy jest dominujący i nienadmierny.
Rozważmy maksymalne zbiory nienadmierne w grafie G.
Zbiór nienadmierny S jest maksymalny nienadmierny, jeśli
dla każdego wierzchołka u
V-S, zbiór S
{u} nie jest
nienadmierny, czyli istnieje przynajmniej jeden wierzchołek
w
S
{u}, który nie ma prywatnego sąsiada.
W takim razie, nienadmierny zbiór S jest maksymalny
nienadmierny, jeśli zachodzi następujący warunek:
(***) dla każdego wierzchołka w
V-S istnieje wierzchołek
v
S
{w}, dla którego PN[v, S
{w}] =
.
Moc najmniejszego zbioru maksymalnego nienadmiernego
w G oznaczamy ir(G) i nazywamy liczbą nienadmierności.
Moc największego zbioru nienadmiernego w G oznaczamy
IR(G) i nazywamy górną liczbą nienadmierności.
Na czerwono zaznaczone są zbiory maksymalne nienadmierne.
ir(G)=2
IR(G)=3
Twierdzenie 14. Każdy zbiór minimalny dominujący w G jest
zbiorem maksymalnym nienadmiernym w G.
Twierdzenie 15. Dla każdego grafu G,
ir(G)
(G)
i(G)
0
(G)
(G)
IR(G) .
ir(G)=4
(G)=5
Twierdzenie 16. Dla każdego grafu G,
(G)/2 < ir(G)
(G)
2ir(G)-1.
Twierdzenie 17. Dla każdego grafu G, IR(G)
n -
(G).
Inne rodzaje dominowania.
Oprócz dominowania, rozważa się dodatkowe własności zbiorów
wierzchołków, rozważając własności podgrafów indukowanych
przez te zbiory.
Dominowanie spójne
(Sampathkumar, Walikar, 1979)
Zbiór dominujący D nazywamy zbiorem spójnie dominującym,
jeśli D jest dominujący i G[D] jest spójny.
Moc najmniejszego zbioru spójnie dominującego w G
nazywamy liczbą dominowania spójnego grafu G i oznaczamy
c
(G).
Każdy zbiór spójnie dominujący jest dominujący, więc dla
każdego grafu spójnego G mamy
(G)
c
(G).
Twierdzenie 18. W każdym grafie spójnym G istnieje zbiór
spójnie dominujący S taki, że |S|
2
0
(G) – 1.
Wniosek: Dla każdego grafu spójnego G,
c
(G)
2
0
(G) – 1.
Twierdzenie 19. (Duchet, Meyniel)
Dla każdego grafu spójnego G,
c
(G)
3
(G)-2.
Lemat 20. Jeśli w grafie spójnym G istnieje najmniejszy
maksymalny zbiór nienadmierny, który jest zbiorem niezależnym,
to ir(G) =
(G) = i(G).
Twierdzenie 21. Jeśli G jest spójny, to ir(G)
c
(G)
3ir (G)- 2.
Wniosek: Jeśli G jest spójny, to
c
(G)
3i (G)- 2.
Nierówności są najlepsze z możliwych. Przedstawimy przykłady,
dla których zachodzą równości.
Twierdzenie 22. Jeśli G jest grafem, który nie zawiera K
1,3
ani
A-L-grafu jako podgrafów indukowanych, to ir(G) =
(G) = i(G).
A-L- graf
Przykład 1. Dla dowolnej liczby naturalnej p rozważmy graf
G=C
3p
. W takim grafie
c
(C
3p
) = 3p-2. Zbiór D, do którego należy
co trzeci wierzchołek cyklu jest niezależnym zbiorem
nienadmiernym i dominującym, |D|=p. Widać, że taki graf nie
zawiera K
1,3
ani A-L-grafu jako podgrafu indukowanego, więc
ir(C
3p
) =
(C
3p
) = i(C
3p
)= p.
Przykład 2. Dla dowolnych liczb naturalnych s i t rozważmy graf H
otrzymany przez utożsamienie ze sobą jednego z wierzchołków
każdego z cykli C
3s
,C
3t .
W takim grafie jest 3(s+t)-1 wierzchołków
oraz
c
(H) = 3(s+t)-5.
W grafie tym znajdziemy najmniejszy maksymalny zbiór
nienadmierny, który jest również zbiorem niezależnym (do zbioru
tego musi należeć wierzchołek powstały przez utożsamienie), wiec
zgodnie z lematem 20 mamy ir(H) =
(H) = i(H) = s + t – 1.
Na rysunku jest przedstawiony graf G, dla którego s = t = 2,
a wierzchołek v z jednego cyklu jest utożsamiony z wierzchołkiem u
z drugiego. Widać, ze ilość wierzchołków w tym grafie
n = 11;
c
(G) =3(2 + 2) - 5 = 7; ir(G) =
(G) = i(G) = 2 + 2 - 1 = 3.
Z łańcucha dominowania oraz z tego, że
c
(G)
2
0
(G) – 1 wynika również, że
c
(G)
2
(G) – 1
oraz
c
(G)
2IR(G) – 1 Ograniczenia te sa
najlepsze z możliwych. Na przykład w cyklu C
5
mamy
0
(C
5
) =
(C
5
) = IR(C
5
) = 2;
c
(C
5
) = 3.
Dla każdego grafu spójnego G istnieje drzewo spinające T grafu G
takie, że
c
(G) =
c
(T) = n(G) – n
1
(T), gdzie n
1
oznacza ilość
wierzchołków końcowych w T. Drzewo to ma największą z możliwych
ilość wierzchołków końcowych.
(Sampathkumar, Walikar) Dla każdego spójnego podgrafu
spinającego H grafu G mamy
c
(H)
c
(G).
Twierdzenie 23. Dla każdego grafu spójnego G z n wierzchołkami
zachodzi równość
c
(G) +
(G) = n, gdzie
(G) oznacza
największą ilość wierzchołków końcowych w drzewie spinającym
grafu G.
Twierdzenie 24. Dla każdego grafu spójnego G z n wierzchołkami
i największym stopniem wierzchołka
(G) zachodzi nierówność
c
(G)
n -
(G).
W roku 1956 E.A. Nordhaus oraz J.W. Gaddum
znaleźli ograniczenia dla sumy i iloczynu liczb
chromatycznych grafu G i jego dopełnienia Gd:
(G)+
(Gd)
n+1, n
(G)
(Gd)
(n+1)(n+1)/4
Podobnych ograniczeń szuka się również dla
różnych liczb dominowania.
Ogólnie zagadnienia typu Nordhausa-Gadduma
polegają na znalezieniu podobnych ograniczeń
dla sumy i iloczynu pewnego niezmiennika grafu
G i tego samego niezmiennika dopełnienia Gd
grafu G. Hedetniemi i Laskar znaleźli górne
ograniczenie dla sumy liczb spójnego
dominowania dla grafu G i jego dopełnienia.
Twierdzenie 25. Jeśli G i jego dopełnienie Gd są spójne, to
c
(G)+
c
(Gd)
n+1.
Twierdzenie 26. Dla każdego drzewa T z co najmniej dwoma
wierzchołkami, różnego od gwiazdy, mamy
c
(T)+
c
(Td)
n.
Dominowanie wypukłe i słabo wypukłe.
(prof. Topp)
Zbiór X
V jest wypukły w G, jeśli wszystkie wierzchołki
każdej najkrótszej (x-y)-ścieżki należą do X dla każdych
x,y należących do zbioru X.
Zbiór X
V nazywamy słabo wypukłym w G, jeśli dla każdych
dwóch wierzchołków x,y należących do zbioru X istnieje
najkrótsza (x-y)-ścieżka, której wierzchołki należą do X.
Liczba dominowania słabo wypukłego w G,
oznaczana
wcon
(G), jest to moc najmniejszego zbioru słabo
wypukłego dominującego w G, natomiast liczba
dominowania wypukłego
w G, oznaczana
con
(G), jest to moc
najmniejszego zbioru
wypukłego w G.
Dominowanie spójne: dla każdych dwóch wierzchołków u,v
należących do zbioru dominującego D, istnieje (u-v)- ścieżka, której
wierzchołki należą do D;
Dominowanie słabo wypukłe: dla każdych dwóch wierzchołków u,v
należących do zbioru dominującego D, istnieje najkrótsza (u-v)- ścieżka,
której wierzchołki należą do D;
Dominowanie wypukłe: dla każdych dwóch wierzchołków u,v
należących do zbioru dominującego D, wierzchołki ze wszystkich
najkrótszych (u-v)- ścieżek należą do D.
Obserwacja 28: Dla każdego grafu spójnego G jest
(G)
c
(G)
wcon
(G)
con
(G).
Twierdzenie29 Dla dowolnych k,r
N, r
3, istnieje graf G taki,
że
c
(G) -
wcon
(G) = r oraz
con
(G) -
c
(G) =
con
(G) -
wcon
(G) =k.
Twierdzenie 30 Każda z różnic
con
(G) -
0
oraz
con
(G) -
może
być dowolnie duża.
Twierdzenie 31 Jeśli G jest spójny, nie posiada wierzchołków
końcowych oraz nie istnieje w G cykl indukowany długości
mniejszej niż 6, to
con
(G) = n.
Lemat 27 Dla każdej liczby naturalnej n
7 i dla każdej
liczby naturalnej k, 7
k
n, istnieje graf G rzędu n
taki, że
con
(G)=
wcon
(G) = k.
Hipoteza Vizinga: Dla każdych dwóch grafów G, H jest
(G)
(H)
(G
H )
Twierdzenie 32 (Canoy, Garces) Zbiór D
V(G
H ) jest
wypukły w G
H wtedy i tylko wtedy, gdy D=D
G
D
H
, gdzie
D
G
jest wypukły w G i D
H
jest wypukły w H.
Twierdzenie 33 Jeśli D jest dominujący w G
H, to D
G
jest
dominujący w G i D
H
jest dominujący w H.
Twierdzenie 34 Dla dowolnych grafów spójnych G i H jest
con
(G)
con
(H)
con
(G
H).
Niech G
H będzie iloczynem kartezjańskim grafów spójnych
G i H. Dla zbioru D
V(G
H ) oznaczmy:
D
G
= {u
V(G): (u,v)
D dla pewnego v
V(H)};
D
H
= {u
V(H): (u,v)
D dla pewnego v
V(G)}.
Dominowanie słabo spójne
(Dunbar, Grossman, Hedetniemi, Hatting, 1997)
Podgraf słabo indukowany przez D
V(G) -
graf G[D]
w
=(N
G
[D],E
w
); e
E
w
jeśli e ma
przynajmniej jeden koniec w D;
D
V(G) – zbiór słabo spójny dominujący, jeśli D jest
dominujący oraz G[D]
w
(<D>
w
) jest spójny;
Liczba dominowania słabo spójnego grafu G, ozn.
w
(G)-
moc najmniejszego zbioru słabo spójnego dominującego w G.
G[D]
w
= (
N
G
[D], E
w
)
Równości między liczbami dominowania.
