W3.PDF

(105 KB) Pobierz
Microsoft Word - 8course-03.doc
Przykład 5 .
Wszystkie cztery grafy na Rysunku 7 maj 8 wierzchołków stopnia 3 i nie
maj adnych innych wierzchołków, tzn.
(
0
2 jest ci giem liczb
wierzchołków kolejnych stopni.
Okazuje si , e
H @
1
H
2
, ale
aden z tych grafów nie jest
izomorficzny z grafem
H .
3
H 1
H 2
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.
K 1
K 2
K 3
K 4
K 5
Rysunek 8
10
)
3247204.003.png 3247204.004.png
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
m
K dla
j
=
1
2
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
np. graf
K zawiera
Å
Æ
5
Õ
Ö
=
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
1
(
G
)
+
2
×
D
2
(
G
)
+
3
×
D
3
(
G
)
+
3
=
2
×
|
E
(
G
)
|
.
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
2
¼
).
Oczywi cie
1
+
1
+
3
+
3
+
3
+
3
+
3
+
3
+
4
=
2
×
12
=
2
+
2
×
0
+
3
×
6
+
4
×
1
.
11
j
Ä
Ô
3247204.005.png
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
3247204.006.png
Dowód.
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 = to droga jest zamkni ta i twierdzenie Eulera
w
mówi, e wszystkie wierzchołki maj stopie parzysty. Je li
u ¹ , 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
}
=
G
stopnia nieparzystego.
13
w
}
e
3247204.001.png
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
a
e
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
3247204.002.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin