Matematyka dyskretna
Dr Marek Zakrzewski
Wykład 07
Teoria grafów
Co zrobić, żeby koniki z pól 1 i 7 przeszły na 3 i 5 i na odwrót?
Każdy konik musi wykonać 4 ruchy w kierunku zgodnym z
ruchem wskazówek zegara.
Zadanie Alcuina o wilku, kozie i kapuście (=sałacie). Należy przeprawić wilka, kozę i sałatę
na drugi brzeg rzeki wiedząc, że w łódce może znajdować się naraz tylko jedno z nich i na
jednym brzegu bez opieki nie mogą zostać równocześnie wilk i koza, ani koza i sałata.
Podstawowe terminy  podstawowe przykłady
G="ąV , Eą G - graf, - wierzchołki (vertices), - krawędzie (edges)
V E
Przyjmiemy umowę, że krawędzie nie mają kierunku, tzn. krawędz
jest parą wierzchołków
(nieuporzÄ…dkowanÄ…).
{V , V }
Zazwyczaj przyjmujemy też, że nie ma pętli, tzn krawędzi typu .
Graf zwykły to graf symetryczny (krawędzie nie mają kierunku), bez pętli i bez krawędzi
wielokrotnych.
Stopień wierzchołka to ilość krawędzi wychodzących z danego wierzchołka.
Lemat o uściskach dłoni
st v1ƒÄ…st v ƒÄ…...ƒÄ…st vk=2#"E#"
2
Graf nazywamy regularnym, jeżeli wszystkie wierzchołki mają ten sam stopień.
K
- graf pełny (Kuratowski)
n
Cn - grafy cykliczne
Grafy platońskie (=szkielety krawędziowe wielościanów foremnych)
Graf Petersena
Mapa Królewca (1736)
Graf nazywamy eulerowskim jeżeli istnieje w nim cykl Eulera, tzn. cykl przechodzący
dokładnie raz przez każdą krawędz
.
Twierdzenie (Eulera-Hierholzera)
Graf spójny jest eulerowski wtedy i tylko wtedy, gdy stopień każdego wierzchołka jest
parzysty.
Dowód (szkic)
Oczywiste, bo jeśli do wierzchołka wchodzimy to musimy z niego wyjść.
Z parzystości stopni wierzchołków wynika, że istnieje jakiś cykl (bez powtórzeń).
Rozważmy najdłuższy cykl. Przypuśćmy, że nie zawiera on wszystkich krawędzi, tzn. istnieje
krawędz
poza cyklem. Ze spójności można przyjąć, że krawędz
ta styka siÄ™ z cyklem. Niech
v punkt cyklu leżący na tej dodatkowej krawędzi. Zaczynając od tej krawędzi zbudujemy
cykl (krawędziowo) rozłączny z cyklem danym. Wyjściowy cykl można uzupełnić tym
nowym cyklem wbrew założeniom maksymalności. Sprzeczność
Graf nazywamy hamiltonowskim, jeśli istnieje w nim cykl Hamiltona,
tzn. cykl przechodzący dokładnie raz przez każdy wierzchołek.
Twierdzenie Diraca (1952)
n
st śąv źąe"
n
Jeżeli ( - liczba wierzchołków grafu), to graf jest hamiltonowski.
2
Dowód
Załóżmy, że twierdzenie jest fałszywe, tzn. istnieje graf spełniający
to założenie, ale niehamiltonowski. Jeśli trzeba dodajemy trochę
krawędzi, tak aby otrzymać maksymalny graf niehamiltonowski. W
u=v1 v2 v3 ... vn=w
takim grafie istnieje droga Hamiltona .
v1 viƒÄ…1
i
Niech A - zbiór tych indeksów , że sąsiaduje z .
vi vn
B
Podobnie - zbiór tych indeksów i , że sąsiaduje z .
n n
#"A#"d" , #"B#"d"
I ={1,2 , ..., n-1}
Niech . Wówczas A"I , B"I , a ponieważ , to
2 2
v1 viƒÄ…1 viƒÄ…2 ... v vi vi-1 ... v1
istnieje i"A)"B . Wówczas jest cyklem hamiltona.
n
Sprzeczność.
"
000 12 1234
{a}
100 21 123 1343
{a,b}
110 132 1423
{b}
010 312 4123
{b,c}
011 321 4132
{a,b,c}
111 231 1432
{a,c}
101 213 1342
{c}
001 123 1324
"
000 3124
3142
...
Ile jest różnych grafów zwykłych o wierzchołkach 1,2,...,n?
n
n
śą źą
2
Krawędzi możliwych jest czyli grafów jest .
śą źą
2
2
Izomorfizm (izo=równe,morf=kształt)
1-1
G2=śąV , E2źą f : V Śą V
Graf oraz są izomorficzne, jeżeli istnieje sąsiednie wtedy i
2 1 2
na
f śąV źą , f śąV źą
tylko wtedy, gdy sÄ…siednie.
1 2
f śą1źą=2
f śą2źą=1
f śą3źą=3