To tylko jedna z 6 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Grafy
Denicja 1 Graf prosty G skªada si¦ z niepustego zbioru sko«czonego V (G),
którego elementy b¦dziemy nazywa¢ wierzchoªkami grafu (lub w¦zªami) i z sko«czonego zbiou E(G) ró»nych par nieuporz¡dkowanych ró»nych elementów zbioru
V (G), które nazywamy krew¦dziami. Zbiór V (G) nazywamy zbiorem wierzchoªków, a zbiór E(G) zbiorem kerw¦dzi grafu G.
Denicja 2 Mówimy, »e kraw¦d¹ {u, v} ª¡czy wierzchoªki u i v i b¦dziemy j¡
oznacza¢ uv .
Uwaga 1 W ka»dym grae prostym istnieje co najwy»ej jedna kraw¦d¹ ª¡cz¡ca
dan¡ par¦ wierzchoªków.
Denicja 3 Obiekt, w którym mog¡ wyst¦powa¢ p¦tle i kraw¦dzie wielokrotne
b¦dziemy nazywa¢ grafem ogólnym lub grafem.
Uwaga 2 Graf skªada si¦ z niepustego zbioru sko«czonego V (G), którego el-
ementy nazywamy wierzchoªkami i sko«czonej rodziny E(G) par nieuporz¡dkowanych (mog¡ by¢ równe) nazywanych kraw¦dziami.
Denicja 4 Mówimy, »e grafy G1 i G2 s¡ izomorczne, je±li istnieje wzajemnie
jednoznaczna odpowiednio±¢ mi¦dzy wierzchoªkami grafu G1 i grafu G2 taka, »e
liczba kraw¦dzi ª¡cz¡ca dane dwa wierzchoªki grafu G1 jest równa liczbie kraw¦dzi
ª¡cz¡cych odpowiadaj¡ce im wierzchoªki grafu G2 .
Denicja 5 Je±li wierzchoªki grafu s¡ nazwane np. literami lub cyframi, to graf
nazywamy oznakowanym, je±li nie, to graf nazywamy nieoznakowanym.
Denicja 6 Niech G1 = (V (G1 ), E(G1 )) i G2 = (V (G2 ), E(G2 )), gdzie zbiory
V (G1 ) i V (G2 ) s¡ rozª¡czne. Sum¡ grafów G1 ∪ G2 nazywamy graf, którego
zbiorem wiechoªków jest zbiór V (G1 ) ∪ V (G2 ), a rodzin¡ kraw¦dzi jest E(G1 ) ∪
E(G2 ).
Denicja 7 Graf nazywamy spójnym, je±li nie mo»na go przedstawi¢ w postaci
sumy dwóch grafów, w przeciwnym przypadku graf nazywamy niespójnym.
Denicja 8 Graf niespójny G mo»na przedsta¢ w postaci sumy grafów spójnych,
które nazywamy skªadowymi grafu G.
Denicja 9 Podgrafem grafu G nazywamy graf, którego wszystkie wierzchoªki
nale»¡ do V (G), a kraw¦dzie nale»¡ do E(G).
Denicja 10 Wierzchoªki, które s¡ poª¡czone kraw¦dzi¡ nazywamy s¡siednimi.
Przykªad 1 Niech AB b¦dzie kraw¦dzi¡ grafu G. Wtedy wierzchoªki A i B s¡
s¡siednie.
1
Denicja 11 Niech AB b¦dzie kraw¦dzi¡ grafu G. Mówimy, »e wierzchoªek A
jest incydentny z kraw¦dzi¡ AB .
Przykªad 2 Narysujemy graf, którego macierz s¡siedztwa jest okre±lona nast¦puj¡co:
0
1
1
2
0
1
0
0
0
1
1
0
0
1
1
2
0
1
0
0
0
1
1
0
0
Przykªad 3 Narysujemy graf, którego macierz incydencji jest okre±lona nast¦puj¡co:
0
0
0
1
1
0
1
0
0
1
1
0
0
1
0
1
1
0
0
0
1
0
0
1
0
1
0
0
0
1
1
0
0
1
0
0
1
1
0
0
Przykªad 4 Przykªady grafów:
1. grafy puste;
2. grafy peªne;
3. grafy liniowe;
4. koªa.
Denicja 12 Liczb¦ kraw¦dzi incydentnych z danym wierzchoªkiem A nazywamy stopniem wierzchoªka A i oznaczamy deg (A).
Denicja 13 Graf, w którym ka»dy wierzchoªek ma ten sam stopie«, nazywamy
grafem regularnym. Je±li ka»dy wierzchoªek ma stopie« r, to graf nazywamy
grafem regularnym stopnia r lub grafem r-regularnym.
Denicja 14 k-kostk¡ nazywamy graf, którego
(…)
… ei .
5
Podgraf T grafu G, którego kraw¦dziami s¡ e1 , e2 , . . . , en−1 , jest szukanym grafem.
Digrafy
Denicja 23 Graf skierowany lub digraf skªada si¦ z niepustego zbioru sko«c-
zonego V (D) elemetów nazywanych wierzchoªkami i sko«czonej rodziny A(D)
par uporz¡dkowanych elementów zbioru V nazywanych ªukami. Zbiór V (D)
nazywamy zbiorem wierzchoªków, a rodzin¦ A(D) rodzin¡ ªuków digrafu D.
Denicja…
... zobacz całą notatkę
Komentarze użytkowników (0)