WYKŁAD 7.

Spójność i rozpięte drzewa

• Graf jest

spójny,

gdy dla każdego podziału

V na dwa rozłączne podzbiory A i B istnieje
krawędź z A do B.

• Definicja równoważna:

Graf jest

spójny

, gdy

każde dwa wierzchołki są połączone ścieżką
(będącą podgrafem danego grafu). (

ćw

)

• Ścieżka

to graf postaci: V={v_1,...v_k},

E={v_1v_2,...,v_{k-1}v_k}. Wierzchołki v_1
i v_k to

końce

ścieżki.

Składowe spójności

• Relacja ,,być połączonymi ścieżką”

(tzn. być końcami ścieżki) jest

relacją równoważności

(zwrotna,

symetryczna, przechodnia). (

ćw

)

• Klasy abstrakcji tej relacji indukują

składowe spójności

grafu.

• Inaczej, składowe spójności to

maksymalne podgrafy spójne.

Wierzchołki i krawędzie

cięcia

• 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.

Wniosek:

Krawędź e jest krawędzią cięcia

grafu G, wgdy nie leży na żadnym cyklu

w G. (

ćw

)

Minimalne grafy spójne

• Ile najmniej krawędzi ma graf spójny G?

• Jeśli G ma cykl, to można z niego usunąć

dowolną krawędź bez rozspójniania G.

• Wiemy, że jeśli e(G)>n-1, to G zawiera cykl

(

ćw

).

• Stąd, G ma co najwyżej n-1 krawędzi.

• Wiemy też, że istnieje ciąg v_1,...,v_n taki,

że dla każdego i istnieje j>i takie, że v_iv_j

jest krawędzią (patrz: algorytm zachłanny).

•

Zatem e(G)=n-1

.

Drzewa, lasy, liście

• Drzewo

to graf spójny bez cykli (a więc,

minimalny graf spójny).

• Las

to graf acykliczny (a więc, rozłączna

suma drzew).

• Liść

to wierzchołek wiszący drzewa.

Fakt:

Każde drzewo ma co najmniej dwa

liście.

Dowód: Spójrz na końce najdłuższej

ścieżki.

Własności drzew

Tw

. Dla spójnego grafu G, następujące

warunki są równoważne:

(i) T jest drzewem

;

(ii) e(T)=n-1;

(iii) każde 2 wierzchołki są połączone

dokładnie 1 ścieżką;

(iv) każda krawędź jest krawędzią cięcia;

(v) dla dowolnej krawędzi e nie należącej

do G, graf G+e ma dokładnie 1 cykl.

Drzewa rozpięte

• Drzewo rozpięte

w grafie G, to

podgraf T taki, że V(T)=V(G) i T
jest drzewem.

• Każdy graf spójny zawiera

przynajmniej 1 rozpięte drzewo.

• Graf pełny K_n ma ich n^{n-2}

(

Cayley, 1889)

Rozłączne rozpięte

drzewa

• Lepszą miarą spójności grafu jest

maksymalna liczba

rozłącznych

rozpiętych drzew (RRD).

• Jeśli G ma k RRD, to

)

1

)

(

(

)

(





G

v

k

G

e

•

Nie jest to jednak warunek dostateczny !

Ilustracja 1

v=5
e=8
k=2

Ilustracja 2

v=7
e=12
k=2 ?

A

A

v=3
e=3
k=1

Dziel i ściągaj !

Dla danego podziału Π

l

V

V

V

G

V









...

)

(

2

1

definiujemy

multigraf G(Π)=(W,F),

gdzie W={1,2...,l},

)},

(

:

,

:

{

G

E

uv

V

v

V

u

ij

F

j

i











a krotność krawędzi ij jest liczbą
e(V_i,V_j) wszystkich krawędzi z V_i

do V_j

Ilustracja

a

b

c

d

e

Π: {{a,d},{b,e},{c}}

c

ad

be

G(Π)

G

Tw. Nash-Williamsa

• Jeśli G jest spójny, to G(Π) też. (

ćw

)

• Stąd, jeśli G ma k RRD T_1,...,T_k, to

)

1

|

(|

))

(

(

))

(

(

1

















k

T

e

G

e

k

i

i

Tw. (Nash-Williams, 1961)

G ma co

najmniej k RRD wgdy powyższa
nierówność zachodzi dla
wszystkich podziałów Π zbioru
V(G) na niepuste podzbiory.

(Bez

dowodu)

Odległości w grafie

• Odległość

d_G(u,v) między wierzchołkami

u i v w spójnym grafie G to długość

najkrótszej ścieżki łączącej u i v.

• Odległość wierzchołków jest metryką

(ćw)

• Średnicą

diam(G) grafu G nazywamy

największą odległość w G.

• Np. diam(K_n)=1, diam(C_{2n})=n,

diam(P_n)=n-1

• Ale diam(K_n-e)=diam(K_{1,n})=2

Zastosowanie średnicy

grafu

• W pewnym kraju n miast ma lotniska.

• Każde lotnisko może mieć nie więcej niż k

bezpośrednich połączeń z innymi, a
przynajmniej jedno ma ich mieć dokładnie k

.

• Chcemy optymalnie zaprojektować siatkę

połączeń, by żadna podróż nie wymagała
więcej niż d-1 przesiadek.

• Jest to więc pytanie o

}

)

(

,

)

(

,

)

(

:

)

(

min{

)

,

(

d

G

diam

k

G

n

G

v

G

e

k

n

e

d











Przypadek d=2, k>n-6

e_2(n,n-1)=n-1 (weź G=K_{1,n-1})

Tw.

Dla n>12

e_2(n,n-2)=e_2(n,n-5)=2n-4
e_2(n,n-3)=e_2(n,n-4)=2n-5

Dowód (k=n-2):

Graf K_{2,n-2} daje

oszacowanie z góry. Oszacowanie
z dołu na

ćwiczeniach.