Matematyka dyskretna
Dr Marek Zakrzewski
Wykład 08
Drzewa i twierdzenia Cayleya
Drzewo=graf spójny bez cykli
df
Wierzchołki stopnia 1 liście lub wierzchołki
=
wiszÄ…ce.
Lemacik (nie zasługuje na miano lematu)
Każde drzewo mające więcej niż jeden wierzchołek
ma przynajmniej dwa liście.
Dowodzik:
uv v u
Rozważmy jakąkolwiek krawędz
. Posuwając się od w stronę inną niż natrafimy
na ślepą uliczkę  tzn. liść (bo nie ma cykli). Podobnie idąc w drugą stronę otrzymamy drugi
liść.
G
Drzewo spinające grafu spójnego to drzewo zawierające wszystkie wierzchołki grafu.
Twierdzenie
Każdy graf spójny ma drzewo spinające.
Dowód:
Jeżeli ten graf nie jest drzewem to zawiera jakiś
cykl. Z tego cyklu możemy usunąć krawędz
bez
naruszania spójności. I dalej podobnie.
Lemat
n
Drzewo o wierzchołkach ma n-1 krawędzi.
Dowód:
1. Dla n=1 oczywiste.
n
2. Załóżmy, że lemat zachodzi dla ustalonego . Pokażemy dla nƒÄ…1 . Rozważmy
drzewo majÄ…ce nƒÄ…1 wierzchoÅ‚ków. Odrzućmy jakiÅ› wierzchoÅ‚ek wiszÄ…cy wraz z
n
krawÄ™dziÄ…. OtrzymaliÅ›my drzewo -wierzchoÅ‚kowe. ZaÅ‚ożenia ma ono nƒÄ…1
n
krawędzi wraz z krawędzią odrzuconą jest krawędzi.
Twierdzenie o charakteryzacji
#"E#"=#"V#"-1
A) Graf spójny w którym jest drzewem.
#"E#"=#"V#"-1
B) Graf acykliczny (tzn. bez cykli), w którym jest drzewem.
Dowód:
A) Wystarczy pokazać, że jest acykliczny. Załóżmy, że zawiera cykl  usuńmy jedną z
n
krawędzi wówczas otrzymamy graf spójny o wierzchołkach i n-2 krawędziach.
n n
Sprzeczność bo graf spójny o wierzchołkach ma przynajmniej krawędzi.
B) Z założenia graf jest acykliczny, więc wystarczy pokazać, że jest spójny. Załóżmy, że nie
jest spójny, tzn. jest lasem mającym więcej niż jedną składową. Składowe są drzewami. Niech
V ,V , ... , V Ei
- ilość wierzchołków w odpowiednich składowych, - ilość krawędzi.
1 2 k
Ei=V -1
Skoro składowe są drzewami to .
i
Zatem:
E=E1ƒÄ… E2ƒÄ…...ƒÄ… Ek=V -1ƒÄ…V -1ƒÄ…... V -1=śąV ƒÄ…V ƒÄ…...ƒÄ…V źą-k=V -k "Ä…V -1
.
1 2 k 1 2 k
#"E#"=#"V#"-1
Sprzeczność z założeniem .
Zadanie:
Cn H
Wykazać, że związki są
2nƒÄ…1
acykliczne.
V =nƒÄ…śą 2nƒÄ…2źą=3nƒÄ…2
2 E=n"4ƒÄ…śą 2nƒÄ…2źą=6nƒÄ…2 Ò! E=3nƒÄ…1
Zatem E=V -1 , a więc pozostaje zauważyć, że graf cząsteczki
jest spójny.
Ile jest drzew spinających o wierzchołkach 1,2 ,... , n ?
Twierdzenia Caleya
Istnieje nn-2 drzew etykietowanych o
wierzchołkach 1,2 ,... ,n .
Dowód:
Zbudujmy kod Prüfera przyporzÄ…dkowujÄ…cy
każdemu drzewu ciąg długości n-2 .
1. Przyjmijmy za kod poczÄ…tkowy ciÄ…g
pusty, a za drzewo poczÄ…tkowe dane
T
drzewo .
2. Wez
liść o minimalnym numerze.
Numer sÄ…siada dodaj na koniec kodu.
3. Zaktualizuj drzewo usuwając liść i
odpowiadającą mu krawędz
.
4. Powróć do 2 jeżeli drzewo ma więcej
niż jedną krawędz
. W przeciwnym razie
stop.
21122  i zostaje na koniec krawędz
2-7
Śą 6611 Śą
2655 Śą Śą 2655
WNIOSEK:
K
Graf pełny ma nn-2 drzew spinających.
n
Dowód:
{1,2 ,... , n }
Każde takie drzewo to drzewo etykietowane na .
Liczba drzew nieetykietowanych
T
n
Niech oznacza liczbę drzew nieetykietowanych o wierzchołkach z twierdzenia
n
nn-2
Caleya mamy: T e" .
n
n !
T
Górne szacowanie na otrzymamy za pomocą odpowiedniego kodowania:
n
0000110111
2 śąn-1źą
Ile jest takich kodów? Tzn. Ile jest ciągów długości 2n-2 ( , bo
tyle jest krawędzi) takich, że liczba zer jest zawsze większa lub równa liczbie
jedynek, a Å‚Ä…cznie jest tyle samo zer co jedynek?
Cn-1
nn -1
d"T d"Cn-1
n
n !
0001101101
00011011 Śą
Macierz sÄ…siedztwa
n
Graf o wierzchołkach kodowany jest za pomocą
5
0 0 1 0 0
macierzy binarnej n×n tzn. zajmuje n2 pamiÄ™ci.
4
0 0 1 0 0
Drzewo nieetykietowane (=kształt drzewa) ma kod
3
0 1 0 1 1
binarny długości 2n-2H"2n
2
1 0 1 0 0
[ ]
1
0 1 0 0 0
1 2 3 4 5
Minimalne drzewo spinajÄ…ce
Załóżmy, że krawędziom przypisane są wagi (np. długość). Jak znalez
ć drzewo o minimalnej
sumie wag?
Algorytm Kruskala
Wez
minimalną krawędz
i dodaj minimalną nie tworzącą cyklu aż otrzymasz n-1
krawędzi.
Algorytm Prima
Wez
dowolny wierzchołek i dodawaj do częściowego drzewa najbliższy niepołączony jeszcze
wierzchołek.