Wszystkie cztery grafy na Rysunku 7 maj 8 wierzchołków stopnia 3 i nie maj adnych innych wierzchołków, tzn. (
,
8
,
0
,
0
,
0
) jest ci giem liczb
wierzchołków kolejnych stopni.
Okazuje si , e H ≅ H , ale
1
2
aden z tych grafów nie jest
izomorficzny z grafem H .
3
H
2
H1
Rysunek 7
H
3
To, e dwa grafy maj ten sam ci g liczb wierzchołków kolejnych stopni nie gwarantuje, e s one izomorficzne.
Graf regularny: graf w których wszystkie wierzchołki maj ten sam stopie .
Przykładem grafów regularnych s grafy na Rysunku 7. Wida , e grafy regularne o tej samej liczbie wierzchołków nie musz by izomorficzne.
Graf pełny: graf bez p tli i kraw dzi wielokrotnych, w którym ka dy wierzchołek jest poł czony kraw dzi z ka dym innym wierzchołkiem.
K1
K2
K3
K4
K5
Rysunek 8
10
Graf pełny o n wierzchołkach ma wszystkie wierzchołki stopnia n-1, wi c taki graf jest grafem regularnym. Wszystkie grafy pełne o n − 1 wierzchołkach s ze sob izomorficzne. Oznacza si je symbolem K . Rysunek 8 przedstawia pi pierwszych m
grafów pełnych. Graf pełny K zawiera podgrafy izomorficzne z grafami K dla m
j
j = ,
1 ,
2
, .
m Taki podgraf mo na otrzyma , wybieraj c dowolnych j spo ród m wierzchołków i bior c wszystkie kraw dzie grafu K ł cz ce te wierzchołki. Zatem m
5
np. graf K zawiera
=10 podgrafów izomorficznych z K .
5
2
2
Istnieje zale no pomi dzy stopniami wierzchołków i liczb kraw dzi.
Twierdzenie.
a) Suma stopni wierzchołków grafu jest dwa razy wi ksza od liczby kraw dzi.
deg( v) = 2⋅ | E( G) ,|
∈
v V ( G)
b) D G + ⋅ D G + ⋅ D G +
= ⋅ E G
1 (
) 2
2 (
) 3
3 (
)
2 | ( ) |.
Dowód jest natychmiastowy. Ka da kraw d niezale nie czy jest p tl czy nie dodaje 2 do sumy stopni.
Przykład 6.
Graf przedstawiony na Rysunku
6 (powtórzenie obok) ma wierzchołki
stopni 1,1,3,3,3,3,3,3 oraz 4 i ma 12
kraw dzi. Ci giem liczb wierzchołków
kolejnych stopni jest ( ,
0
,
0
,
1
,
6
,
0
,
2
)
… .
Oczywi cie 1 + 1 + 3 + 3 + 3 + 3 + 3 + 3 + 4 = 2 ⋅12 = 2 + 2 ⋅ 0 + 3 ⋅ 6 + 4 ⋅1.
11
Zagadnienia zwi zane z poruszanie si po kraw dziach grafu.
Jednym z najstarszych problemów dotycz cych grafów jest problem mostów w Królewcu. Czy mo na przej po mie cie pokazanym na Rysunku 8a przechodz c przez ka dy most dokładnie jeden raz.
ziemia
wyspa
wyspa
rzeka
Rysunek (8a)
(8 b)
Szwajcarski matematyk Leonhard Euler rozwi zał ten problem w 1736 roku.
Zbudował on graf pokazany na Rysunku 8b zast puj c obszary l du wierzchołkami a mosty kraw dziami. Powstało pytanie: czy istnieje w tym grafie
Cykl Eulera:
droga zamkni ta przechodz ca przez ka d kraw d dokładnie jeden raz.
Ogólniej mówi c droga prosta zawieraj ca wszystkie kraw dzie grafu G jest nazywana drog Eulera w G.
Euler pokazał, e nie ma cyklu Eulera dla grafu mostów królewieckich, w którym wszystkie wierzchołki s stopnia nieparzystego. Euler udowodnił
Twierdzenie.
Graf, który ma cykl Eulera, musi mie wszystkie wierzchołki stopnia parzystego.
12
Wychodz c z dowolnego wierzchołka na cyklu Eulera, poruszamy si po tym cyklu, przechodz c od wierzchołka do wierzchołka i wycieraj c ka d kraw d po której przeszli my. Kiedy przechodzimy przez wierzchołek, wycieramy jedn kraw d dochodz c do wierzchołka
i jedn wychodz c z niego lub
wycieramy
p tl .
W
ka dym
przypadku to wycieranie spowoduje
zmniejszenie stopnia wierzchołka o 2.
Ostatecznie ka da kraw d zostanie
usuni ta.
Zatem
wszystkie
wierzchołki musiały mie stopie
parzysty.
Z powy szego twierdzenia nasuwa si nast puj cy wniosek:
Graf G maj cy drog Eulera ma albo dwa wierzchołki stopnia nieparzystego albo nie ma w ogóle wierzchołków stopnia nieparzystego.
Wniosek ten jest oparty na nast puj cym rozumowaniu:
Przypu my, e graf G ma drog Eulera zaczynaj c si w wierzchołku u i ko cz c w wierzchołku w. Je li u = w to droga jest zamkni ta i twierdzenie Eulera mówi, e wszystkie wierzchołki maj stopie parzysty. Je li u ≠ w , to tworzymy now kraw d e ł cz c u i w. Nowy graf G ∪{ }
e ma cykl Eulera składaj cy si z
drogi Eulera w G i kraw dzi e, wi c wszystkie wierzchołki grafu G ∪{ }
e maj
stopie parzysty. Usuwamy kraw d .
e Wtedy u i w s jedynymi wierzchołkami grafu G
( ∪ e
{ }) \ e
{ } = G stopnia nieparzystego.
13
Przeanalizujmy graf przedstawiony na Rysunku 9a. Graf ten nie ma cyklu Eulera, poniewa wierzchołki u i v maj stopie nieparzysty, ale droga bacdgfe jest drog Eulera.
b
u
v
e
a
c
d
g
w
f
x
Rys. 9a
Rys. 9b
Graf pokazany na Rysunku 9b ma wszystkie wierzchołki stopnia parzystego ale nie ma cyklu Eulera z tego powodu, e składa si z dwóch podgrafów nie poł czonych ze sob . Ka dy z tych podgrafów ma jednak swój własny cykl Eulera.
Twierdzenie Eulera, mówi e warunek parzysto ci stopni wierzchołków jest warunkiem koniecznym istnienia cyklu Eulera. Warunek ten jest równie warunkiem wystarczaj cym je li nie b dziemy rozwa ali takich grafów jak z Rysunku 9b.
Koniecznym jest tu wprowadzenie charakterystyki grafów zwanej spójno ci grafu.
Graf jest spójny, je li ka da para wierzchołków jest poł czona drog na tym grafie.
Graf na Rysunku 9a jest spójny a ten na Rysunku 9b jest niespójny. Spójny podgraf grafu G, który nie jest zawarty w wi kszym spójnym podgrafie grafu G nazywa si składow grafu. Np. graf na rysunku 9b ma dwie składowe. Korzystaj c z poj cia spójno ci grafu mo emy powiedzie , e
Sko czony graf spójny, którego ka dy wierzchołek jest stopnia parzystego ma cykl Eulera.
14