Matematyka Dyskretna 膰w. 5
Grafy: wprowadzenie, macierze s膮siedztwa, drogi i cykle Eulera
佛 Grafem (nieskierowanym) G nazywamy uporz膮dkowan膮 tr贸jk臋 G = (V(G), E(G), (G)), gdzie V(G)
jest niepustym zbiorem wierzcho艂k贸w grafu G, zbi贸r E(G) niepustym zbiorem kraw臋dzi grafu, za艣
jest funkcj膮 incydencji grafu G. Elementy V(G)
nazywamy wierzcho艂kami, za艣 elementy E(G) kraw臋dziami
佛 Grafem skierowanym (digrafem) G nazywamy uporz膮dkowan膮 tr贸jk臋 G = (V(G), E(G), (G)), gdzie
V(G) jest niepustym zbiorem wierzcho艂k贸w grafu G, zbi贸r E(G) niepustym zbiorem kraw臋dzi
grafu, za艣 jest funkcj膮 incydencji grafu G
佛 W grafie G, o kraw臋dzi e takiej, 偶e m贸wimy, 偶e 艂膮czy wierzcho艂ki p i q. Dodatkowo
wierzcho艂ki p i q nazywamy ko艅cami kraw臋dzi e, za艣 kraw臋dz e incydentn膮 do wierzcho艂k贸w p i q
佛 W digrafie G, o kraw臋dzi e takiej, 偶e m贸wimy, 偶e jest kraw臋dzi膮 od wierzcho艂ka p do
wierzcho艂ka q. Dodatkowo wierzcho艂ek p nazywamy pocz膮tkiem kraw臋dzi e, za艣 q nazywamy ko艅cem
kraw臋dzi e
佛 Je偶eli to e nazywamy kraw臋dzi膮 zwyk艂膮, w przeciwnym przypadku: p臋tl膮
佛 Kraw臋dzie i nazywamy kraw臋dziami wielokrotnymi je艣li
佛 Graf G nazywamy prostym je艣li nie posiada p臋tli i kraw臋dzi wielokrotnych
佛 Wierzcho艂kiem izolowanym nazwiemy wierzcho艂ek, kt贸ry nie jest ko艅cem 偶adnej kraw臋dzi
Dalej b臋dziemy rozwa偶a膰 tylko grafy sko艅czone:
佛 Drog膮 grafu G nazywamy dowolny ci膮g kraw臋dzi spe艂niaj膮cy zale偶no艣膰:
. M贸wimy, 偶e droga ta ma d艂ugo艣膰 n. Je艣li to droga ta jest zamkni臋ta
佛 Drog臋 nazywamy drog膮 prost膮, je艣li wszystkie kraw臋dzie j膮 tworz膮ce s膮 r贸偶ne
佛 Drog臋 zamkni臋t膮 o ci膮gu wierzcho艂k贸w o d艂ugo艣ci co najmniej jeden nazywamy cyklem,
je艣li wszystkie wierzcho艂ki s膮 r贸偶ne
佛 Stopniem wierzcho艂ka v (oznaczanym symbolem deg(v)) grafu G nazywamy liczb臋
dwuwierzcho艂kowych kraw臋dzi z v jako jednym z wierzcho艂k贸w plus podwojon膮 liczb臋 p臋tli o
wierzcho艂ku v. Liczb膮 b臋dziemy oznacza膰 liczb臋 wierzcho艂k贸w grafu G stopnia x
Zad. 1. Niech dany b臋dzie graf G:
. Narysuj ten graf. Wska偶 w nim:
(a) p臋tle,
(b) trzy drogi zamkni臋te o d艂ugo艣ciach 2,4,8,
(c) trzy drogi proste o d艂ugo艣ciach 3,4,6,
(d) trzy drogi proste zamkni臋te,
(e) trzy cykle
oraz policz stopnie wierzcho艂k贸w.
佛 W grafie G m贸wimy, 偶e wierzcho艂ki p i q s膮 s膮siednie je偶eli dla pewnej kraw臋dzi e:
佛 Macierz膮 s膮siedztwa digrafu G o n wierzcho艂kach v1, v2, & , vn nazwiemy macierz M wymiaru ,
kt贸rej ka偶dy wyraz jest liczb膮 kraw臋dzi od wierzcho艂ka vi do wierzcho艂ka vj
佛 Dla dowolnego digrafu G o n wierzcho艂kach v1, v2, & , vn liczba dr贸g o d艂ugo艣ci p z wierzcho艂ka vi do
wierzcho艂ka vj jest r贸wna elementowi macierzy , gdzie M jest macierz膮 s膮siedztwa digrafu G
Matematyka dyskretna dr Marcin Raniszewski
Zad. 2. Podaj ile jest dr贸g o d艂ugo艣ci 3 z wierzcho艂ka v2 do v1 oraz z v3 do v4 digrafu, je偶eli
macierz s膮siedztwa digrafu ma posta膰: . Narysuj ten digraf.
佛 Drog膮 Eulera w grafie G nazywamy ka偶d膮 drog臋 prost膮, zawieraj膮c膮 wszystkie kraw臋dzie grafu G
佛 Cyklem Eulera w grafie G nazywamy ka偶d膮 drog臋 prost膮 i zamkni臋t膮, zawieraj膮c膮 wszystkie
kraw臋dzie grafu G
佛 Graf G nazywamy sp贸jnym, je艣li ka偶da para r贸偶nych wierzcho艂k贸w jest po艂膮czona drog膮 w tym grafie
佛 Graf H nazwiemy podgrafem grafu G, je偶eli oraz
佛 Sp贸jny podgraf, kt贸ry nie jest zawarty w wi臋kszym sp贸jnym podgrafie grafu G, nazywamy sk艂adow膮
grafu G
佛 Twierdzenie Eulera: Graf jest sp贸jny i ma ka偶dy wierzcho艂ek stopnia parzystego ma cykl Eulera
佛 Wniosek z twierdzenia Eulera: Graf jest sp贸jny i ma dok艂adnie dwa wierzcho艂ki stopnia
nieparzystego lub nie ma wierzcho艂k贸w stopnia nieparzystego ma drog臋 Eulera
Zad. 3. Podaj:
(a) przyk艂ad grafu sp贸jnego, kt贸ry nie ma cyklu Eulera,
(b) przyk艂ad grafu o wierzcho艂kach parzystego stopnia, kt贸ry ma cykl Eulera,
(c) przyk艂ad grafu o wierzcho艂kach parzystego stopnia, kt贸ry nie ma cyklu Eulera.
Zad. 4. Czy jest mo偶liwe, aby owad poruszaj膮cy si臋 wzd艂u偶 kraw臋dzi sze艣cianu przeszed艂
ka偶d膮 kraw臋dz dok艂adnie raz? Odpowiedz poprzyj odpowiednim rysunkiem grafu.
Zad. 5. Kt贸re z graf贸w maj膮 cykle Eulera, a kt贸re nie maj膮 i dlaczego? Podaj przyk艂adowy
cykl Eulera dla graf贸w, kt贸re je posiadaj膮.
Matematyka dyskretna dr Marcin Raniszewski
Zad. 6. Kt贸re z graf贸w maj膮 drogi Eulera, a kt贸re nie maj膮 i dlaczego? Podaj tak膮 drog臋 dla
graf贸w, kt贸re j膮 posiadaj膮.
Zad. 7. Zbuduj graf maj膮cy zbi贸r wierzcho艂k贸w , w kt贸rym wierzcho艂ki
v i w s膮 po艂膮czone kraw臋dzi膮, je艣li ci膮gi v i w r贸偶ni膮 si臋 na dok艂adnie dw贸ch wsp贸艂rz臋dnych.
(a) Ile sk艂adowych ma ten graf?
(b) Ile wierzcho艂k贸w danego stopnia ma ten graf?
(c) Czy ten graf ma cykl Eulera? Czy ten graf ma drog臋 Eulera?
Zad. 8. Czy mo偶na tak przej艣膰 dany dom aby przez ka偶de drzwi przej艣膰 dok艂adnie raz?
Odpowiedz uzasadnij. Jak zmieni si臋 odpowiedz, je艣li drzwi mi臋dzy dwoma du偶ymi pokojami
b臋d膮 zamkni臋te?
Matematyka dyskretna dr Marcin Raniszewski
Wyszukiwarka
Podobne podstrony:
MD cwMD cwMD cw 4MD cwMD cwMD cwMD cwMD cwMD cwMD cw 3MATLAB cw Skryptycad2 cw 5 6cw formularzCw 2 zespol2 HIPSCw 9 Wzmacniacz mocyCw 1metrologia cw 1 protokolwi臋cej podobnych podstron