Matematyka dyskretna 2004 - 09 Grafy nieskierowane.pdf - Matematyka dyskretna - Minnie_

Matematyka Dyskretna

Andrzej Szepietowski

25 marca 2004 roku

Rozdział 1

Grafy (nieskierowane)

Najpierw podamy podstawowe deﬁnicje i fakty, czesc z nich była juz przedstawiona w

rozdziale pierwszym.

Deﬁnicja 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

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 graﬁe G = (V; E) z m =jEj krawedziami zachodzi

v2V d(v) = 2m:

Liczba wierzchołków o nieparzystych stopniach jest parzysta.

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

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 Izomorﬁzm grafów

Izomorﬁzmem 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 izomorﬁczne. Łatwo sprawdzic, ze izomorﬁzm 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 izomorﬁczny z grafem G 4 . Izomorﬁzmem 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 izomorﬁczny z grafami G 4 i G 5 . Graf G 4 zawiera

wierzchołek d stopnia jeden, a w graﬁe G 6 takiego wierzchołka nie ma.

Jezeli mamy izomorﬁzm 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 izomorﬁczne, to:

(a) G i H maj a tyle samo wierzchołków, jV G j=jV H j ,

1.2. Drogi i cykle

Rysunek 1.3: Rysunki a) i b) przedstawiaj a ten sam graf G 4

Rysunek 1.4: a) Graf G 5 izomorﬁczny z G 4 . b) Graf G 6 nieizomorﬁczny z G 4

(b) G i H maj a tyle samo krawedzi, jE G j=jE H j ,

Dowód:

(a) wynika bezposrednio z deﬁnicji.

(b) Niech h bedzie izomorﬁzmem 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 .

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 izomorﬁ-

zmu grafów. Istniej a pary grafów G i H , które spełniaj a wszystkie trzy warunki, ale nie

s a izomorﬁczne.

1.2 Drogi i cykle

Droga lub sciezka w graﬁe 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

Matematyka dyskretna 2004 - 09 Grafy nieskierowane.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: