WYKŁAD 8. Siła spójności
• Wierzchołek v nazywamy
wierzchołkiem
cięcia
grafu G, gdy podgraf G-v ma więcej
składowych spójności niż G.
• Krawędź e nazywamy
krawędzią cięcia
grafu G, gdy podgraf G-e ma więcej
składowych spójności niż G.
WYKŁAD 8. Siła spójności
• Wierzchołek v nazywamy
wierzchołkiem
cięcia
grafu G, gdy podgraf G-v ma więcej
składowych spójności niż G.
• Krawędź e nazywamy
krawędzią cięcia
grafu G, gdy podgraf G-e ma więcej
składowych spójności niż G.
Cięcia
• Mówimy, że zbiór X
wierzchołków
(
krawędzi
) grafu G jest cięciem
wierzchołkowym
(
krawędziowym
)
grafu G, gdy podgraf G-X jest
niespójny.
• Jeśli wierzchołki u i v należą do
różnych składowych spójności
podgrafu G-X, to mówimy, że
cięcie X
rozspójnia u i v w G
.
Wierzchołki i krawędzie
cięcia
• Jeśli X={v} rozspójnia dwa wierzchołki
tej samej składowej grafu G, to v jest
wierzchołkiem cięcia
.
• Krawędź, która rozspójnia swoje końce,
to
krawędź cięcia
.
• Wierzchołek
(
krawędź
) cięcia stanowi
1-elementowe cięcie
wierzchołkowe
(
krawędziowe
), ale odwrotnie być nie
musi (
podać kontrprzykład
).
k-Spójność
• Dla k
0, graf G jest
k-spójny
, gdy |
V(G)|>k i G nie ma cięcia
wierzchołkowego mocy mniejszej niż
k.
• Każdy graf jest 0-spójny.
• Każdy spójny graf oprócz K_1 jest 1-
spójny.
• Spójny graf G jest
2-spójny
, gdy |
V(G)|>2 i G nie ma wierzchołka
cięcia.
Charakteryzacja grafów 2-
spójnych
Tw
. Graf G jest 2-spójny
wgdy
można go
otrzymać z cyklu przez sukcesywne
dodawanie ścieżek zaczepionych
obydwoma końcami w
dotychczasowym grafie,
tzn.
istnieje ciąg grafów H_1,...,H_l, gdzie
H_1 jest cyklem, H_l=G i dla każdego
i=2,...,l graf H_i jest sumą H_{i-1} i
ścieżki P_i o końcach u_i i v_i takiej, że
}
,
{
)
(
)
(
1
i
i
i
i
v
u
H
V
P
V
Dowód na ćw.
Ilustracja
H_{i-1}
P_i
Stopień spójności
• Dla k
0, graf G jest
k-spójny
, gdy |V(G)|
>k i G nie ma cięcia
wierzchołkowego mocy mniejszej niż k.
• Stopień spójności κ(G)
to
największa
liczba całkowita k taka, że G jest k-spójny.
• Np. κ(G)=0 gdy G jest niespójny;
κ(K_n)=n-1 dla n=1,2,…
• Jeśli G nie jest grafem pełnym, to
κ(G)
jest mocą
najmniejszego
cięcia
wierzchołkowego w G.
Krawędziowa k-spójność
• Graf G jest
k-krawędziowo-spójny
,
gdy |V(G)|>1 i G nie ma cięcia
krawędziowego mocy mniejszej niż k.
• Stopień spójności krawędziowej κ’(G)
to największa liczba całkowita k taka,
że G jest k- krawędziowo-spójny.
• Równoważnie,
κ’(G)
to moc
najmniejszego cięcia krawędziowego
w G.
Krawędziowa k-spójność a
RRD
• Jeśli G ma k RRD
(rozłącznych,
rozpiętych drzew),
to G jest k-
krawędziowo-spójny
(oczywiste).
• Jeśli G jest 2k-krawędziowo-spójny, to
G ma k RRD
(dowód na ćwiczeniach)
κ(G), κ’(G), δ(G)
Twierdzenie (Whitney, 1932)
)
(
'
G
(G)
κ
κ(G)
Dowód:
Prawa nierówność:
Krawędzie incydentne z dowolnym
wierzchołkiem stanowią cięcie
krawędziowe.
Lewa nierówność
:
Jeśli G=K_n, to κ(G)=κ’(G)=n-1.
Lewa nierówność – c.d.
• W grafie G nie będącym grafem pełnym niech
X będzie najmniejszym cięciem krawędziowym.
• X można traktować jako zbiór krawędzi
dwudzielnego podgrafu grafu G z 2-podziałem
V_1, V_2=V(G)-V_1.
• Każda krawędź grafu G pomiędzy V_1 i V_2
należy do X.
V_1
V_2
X
Lewa nierówność –
dokończenie
• Ponieważ
G
nie jest pełny a
|X| =
κ’(G)
δ(G)
, to istnieją
u
w
V_1
i
v
w
V_2
takie, że
uv
nie jest krawędzią w
G
.
(ćw.)
• Biorąc po 1 końcu każdej krawędzi
zbioru X, ale tak by ominąć u i v,
otrzymujemy cięcie wierzchołkowe
(rozspójniające u i v) mocy nie większej
niż |X|.
Ilustracja
v
u
d(u)=δ
V_1
V_2
X
Niezależne ścieżki
• Dwie u-v ścieżki (czyli ścieżki z u do
v) nazywamy
niezależnymi
, gdy ich
jedynymi wspólnymi wierzchołkami
są ich końce u i v.
• Jeśli istnieje k parami niezależnych
u-v ścieżek, to każde cięcie
wierzchołkowe rozspójniające u i v
musi mieć moc co najmniej k.
Tw. Mengera dla pary
wierzchołków
Tw.1 (Menger, 1927).
Niech a i b będą
wierzchołkami grafu G.
(i) Jeśli a i b
nie są połączone krawędzią
,
to moc
najmniejszego
cięcia
wierzchołkowego, rozspójniającego a
i b, jest równa mocy
największego
zbioru niezależnych a-b ścieżek.
(ii) Moc
najmniejszego
cięcia
krawędziowego rozspójniającego a i b
jest równa mocy
największego
zbioru
krawędziowo rozłącznych a-b ścieżek.
Globalne Tw. Mengera
Tw 2. (Menger, 1927)
(i) Graf jest k-spójny
(tzn.|V(G)|>k i G nie ma
cięcia wierzchołkowego mocy mniejszej niż k)
wgdy zawiera co najmniej k parami
niezależnych
ścieżek pomiędzy każdą parą
wierzchołków.
(ii) Graf jest k-krawędziowo-spójny
(tzn. |V(G)|
>1 i G nie ma cięcia krawędziowego mocy
mniejszej niż k)
wgdy zawiera co najmniej k
parami
krawędziowo rozłącznych
ścieżek
pomiędzy każdą parą wierzchołków.
Dowód Tw. 2(i)
Jeśli G ma k niezależnych ścieżek między
każdą parą wierzchołków, to |V(G)|>k i G nie
może mieć cięcia wierzchołkowego mocy
mniejszej niż k.
Zatem G jest k-spójny
.
Przypuśćmy, że k-spójny graf G zawiera
wierzchołki a i b nie połączone k
niezależnymi ścieżkami.
.
Dowód Tw. 2(i) c.d.
• Z Twierdzenia 1(i), ab jest krawędzią.
• Podgraf G’:=G-ab ma co najwyżej k-2
niezależne a-b ścieżki
.
• Ponownie z
Twierdzenia 1(i),
istnieje
cięcie wierzchołkowe X mocy |X|
k-
2 rozspójniające a i b w G’.
• Ponieważ |V(G)|
k+1, to istnieje w
G wierzchołek v taki, że
}
,
{ b
a
X
v
Dowód Tw. 2(i)
dokończenie
• X rozspójnia w G’ wierzchołki v i a
lub b (powiedzmy a).
• Wtedy zbiór X powiększony o b
rozspójnia w G v i a, co przeczy k-
spójności G.
Dowód Tw. 2 (ii) – ćwiczenia!
Ilustracja
a
b
X
v
A-B ścieżki
i zbiory
rozdzielające
• A,B – dowolne podzbiory V(G)
• Ścieżkę P w grafie G o końcach a i b
nazywamy
A-B ścieżką
, gdy
}
{
)
(
},
{
)
(
b
B
P
V
a
A
P
V
• Mówimy, że zbiór wierzchołków X
grafu G
rozdziela A i B
, gdy każda A-B
ścieżka zawiera wierzchołek z X.
Ilustracja
A
B
X
Tw. Mengera (1927)
Tw 3.
Niech A,B będą dowolnymi
podzbiorami V(G). Wtedy moc
najmniejszego
zbioru
rozdzielającego A i B równa się mocy
największego
zbioru rozłącznych A-B
ścieżek.
Bez dowodu
.
Ilustracja
V_1
V_2
Tw. Mengera dla pary
wierzchołków
Tw.1 (Menger, 1927).
Niech a i b będą
wierzchołkami grafu G.
(i) Jeśli a i b
nie są połączone krawędzią
,
to moc
najmniejszego
cięcia
wierzchołkowego, rozspójniającego a
i b, jest równa mocy
największego
zbioru niezależnych a-b ścieżek.
(ii) Moc
najmniejszego
cięcia
krawędziowego rozspójniającego a i b
jest równa mocy
największego
zbioru
krawędziowo rozłącznych a-b ścieżek.
Dowód Tw. 1
(ćw.)
(i) Zastosuj Tw. 3 do A=N(a) i B=N(b)
(ii)
Zastosuj Tw. 3 do grafu krawędziowego
L(G), A=E(a), B=E(b)
a
b
A
B
Tw. Königa raz jeszcze
Wniosek 1 : Tw. Königa
Dowód:
Niech G będzie grafem 2-dzielnym
o 2-podziale (A,B). Zbiór rozdzielający to
pokrycie wierzchołkowe. Rozłączne A-B
ścieżki to skojarzenie.
A
B