Matematyka dyskretna 2004 - 09 ...

Matematyka dyskretna 2004 - 09 Grafy nieskierowane, Studia - informatyka, Matematyka dyskretna

[ Pobierz całość w formacie PDF ]
Matematyka Dyskretna
Andrzej Szepietowski
25 marca 2004 roku
Rozdział 1
Grafy (nieskierowane)
Najpierw podamy podstawowe definicje i fakty, czesc z nich była juz przedstawiona w
rozdziale pierwszym.
Definicja 1.1
Graf (nieskierowany)
G = (V; E)
jest to para składaj aca sie ze sko nczo-
nego zbioru wierzchołków
V
oraz ze zbioru krawedzi
E
, gdzie krawedzie to pary wierz-
chołków
Effu; vgju; v2V; u 6= vg:
Rysunek 1.1: Przykład grafu
a
b
c
d
e
f
g
Stopie n wierzchołka
v
, oznaczany przez
d(v)
, jest to liczba krawedzi wychodz acych z
v
.
W rozdziale o kombinatoryce udowodnilismy nastepuj acy lemat.
Lemat 1.2
W dowolnym grafie
G = (V; E)
z
m =jEj
krawedziami zachodzi
P
v2V
d(v) = 2m:
Liczba wierzchołków o nieparzystych stopniach jest parzysta.
3
4
Rozdział 1. Grafy (nieskierowane)
Graf
H = (V
H
; E
H
)
nazywamy
podgrafem
grafu
G = (V
G
; E
G
)
, jezeli
V
H
V
G
oraz
E
H
E
G
.
Graf pełny
o
n
wierzchołkach, oznaczany przez
K
n
, jest to graf z
n
wierzchołkami, w którym kazde dwa wierzchołki poł aczone s a krawedzi a.
Rysunek 1.2: Graf pełny dwudzielny
K
3;3
a
b
c
d
e
f
Graf
G = (V; E)
jest
dwudzielny
, jezeli zbior jego wierzchołków mozna rozbi c na
dwie czesci
V = V
1
[V
2
,
V
1
\V
2
=;
, tak, ze kazda krawedz
e2E
ma ko nce w
obu zbiorach
V
1
i
V
2
.
Pełny graf dwudzielny
K
m;n
ma zbior wierzchołków rozbity na
dwa podzbiory:
V
1
=fv
1
; : : : ; v
m
g
i
V
2
=fw
1
; : : : ; w
n
g
, a krawedzie ł acz a kazdy
wierzchołek z
V
1
z kazdym wierzchołkiem z
V
2
, czyli
E =ffv
i
; w
j
gj1im; 1
jng
.
1.1 Izomorfizm grafów
Izomorfizmem grafu
G = (V
G
; E
G
)
na graf
H = (V
H
; E
H
)
nazywamy funkcje wza-
jemnie jednoznaczn a
h : V
G
!V
H
spełniaj ac a warunek:
fu; vg2E
G
wtedy i tylko
wtedy, gdy
fh(u); h(v)g2E
H
. Jezeli taka funkcja istnieje, to mówimy, ze grafy
G
i
H
s a izomorficzne. Łatwo sprawdzic, ze izomorfizm grafów jest relacj a równowaznosci.
Przykład 1.3
Rysunki 1.3a i 1.3b przedstawiaj a ten sam graf
G
4
= (V
4
; E
4
)
ze zbiorem
wierzchołków
V
4
=fa; b; c; dg
oraz zbiorem krawedzi
E
4
=ffa; bg;fa; cg;fa; dg;fb; cgg
Graf
G
5
= (V
5
; E
5
)
z rysunku 1.4a jest izomorficzny z grafem
G
4
. Izomorfizmem z
G
5
na
G
4
jest funkcja
h : V
5
!V
4
okreslona nastepuj aco:
h(a) = c
,
h(b) = b
,
h(c) = a
,
h(d) = d
.
Graf
G
6
z rysunku 1.4b nie jest izomorficzny z grafami
G
4
i
G
5
. Graf
G
4
zawiera
wierzchołek
d
stopnia jeden, a w grafie
G
6
takiego wierzchołka nie ma.
Jezeli mamy izomorfizm grafu
G = (V
G
; E
G
)
na graf
H = (V
H
; E
H
)
, to mozemy
powiedziec, ze
H
jest takim samym grafem co
G
tylko ze zmienionymi nazwami wierz-
chołków.
Twierdzenie 1.4
Jezeli grafy
G = (V
G
; E
G
)
i
H = (V
H
; E
H
)
s a izomorficzne, to:
(a)
G
i
H
maj a tyle samo wierzchołków,
jV
G
j=jV
H
j
,
1.2. Drogi i cykle
5
Rysunek 1.3: Rysunki a) i b) przedstawiaj a ten sam graf
G
4
a
a
d
b
c
b
c
a)
b)
Rysunek 1.4: a) Graf
G
5
izomorficzny z
G
4
. b) Graf
G
6
nieizomorficzny z
G
4
a
b
a
b
c
d
c
d
a)
b)
(b)
G
i
H
maj a tyle samo krawedzi,
jE
G
j=jE
H
j
,
(c) Dla kazdego
k
,
G
i
H
maj a tyle samo wierzchołków stopnia
k
.
Dowód:
(a) wynika bezposrednio z definicji.
(b) Niech
h
bedzie izomorfizmem z
V
G
na
V
H
. Ale
h
okresla takze wzajemn a jednoznacz-
nosc pomiedzy zbiorem krawedzi
h(fu; vg) =fh(u); h(v)g
.
(c) Udowodnimy, ze jezeli
v2V
G
jest stopnia
k
, to i
h(v)2V
H
jest stopnia
k
. Niech
v
1
, ... ,
v
k
bed a wszystkimi wierzchołkami z
V
G
poł aczonymi krawedziami z
v
. Wtedy
h(v
1
)
, ... ,
h(v
k
)
s a wszystkimi wierzchołkami z
V
H
poł aczonymi krawedziami z
h(v)
.
Pokazalismy wiec, ze
h
odwzorowuje wierzchołki stopnia
k
na wierzchołki stopnia
k
.
2
Nalezy zwrócic uwage, ze warunki (a), (b) oraz (c) nie s a wystarczaj ace do izomorfi-
zmu grafów. Istniej a pary grafów
G
i
H
, które spełniaj a wszystkie trzy warunki, ale nie
s a izomorficzne.
1.2 Drogi i cykle
Droga
lub
sciezka
w grafie jest to ci ag wierzchołków
v
0
; v
1
; : : : ; v
k
, taki, ze dla kazdego
i; 1ik
, wierzchołki
v
i1
,
v
i
s a poł aczone krawedzi a, czyli
fv
i1
; v
i
g2E
G
. O
[ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

mement.xlx.pl