To tylko jedna z 4 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
PODSTAWOWE DEFINICJE TEORII GRAFÓW
Definicja 1
Grafem skończonym G nazywamy skończony zbiór punktów Vi, i = l, N, zwanych
wierzchołkami i skończony zbiór linii ui, i = l, M, zwanych krawędziami takimi, że każda
krawędź ma dwa (niekoniecznie różne) wierzchołki jako jej punkty końcowe oraz nie przechodzi ona przez inne wierzchołki. Mówimy, że krawędź jest incydentna (powiązana) z
wierzchołkiem, jeśli jest on jednym z jej końców.
Definicja 2
Graf G nazywamy skierowanym, jeśli każda jego krawędź ma określoną orientację.
Zorientowana krawędź „wychodzi” z wierzchołka, który jest jej początkiem i „wchodzi” do
wierzchołka, która jest jej końcem lub inaczej - jest względem obu wierzchołków dodatnio i
ujemnie incydentna.
Definicja 3
Graf G jest grafem spójnym, jeśli nie ma wierzchołków izolowanych, tzn. wierzchołków, z których nie można przejść po krawędziach grafu do dowolnego innego wierzchołka.
Na rys. 1 przedstawiono graf spójny, niespójny oraz graf spójny skierowany.
u5
u5
v1
u1
u3
u5
v1
u1
v1
v4
u1
u4
u3
v4
v5
u4
u3
v4
v2
u2
v3
u4
v2
u2
v2
u2
v3
Definicja 4
Dwa grafy są izomorficzne jeśli:
1. jest wzajemnie jednoznaczna odpowiedniość między zbiorami wierzchołków,
2. jest wzajemnie jednoznaczna odpowiedniość między ich zbiorami krawędzi,
3. zachowana jest orientacja krawędzi dla grafów zorientowanych.
v3
v1
v1
u1
u5
u6
u7
u1
u6
v2
u4
u5
u3
u2
v4
v3
u2
v3
u7
u3
u4
v4
v2
Definicja 5
Ścieżką nazywamy ciąg różnych krawędzi takich, że dwie kolejne krawędzie w ciągu
są incydentne względem tego samego wierzchołka.
Definicja 6
Cyklem nazywamy ścieżkę, której początkowy wierzchołek zbiega się z końcowym
wierzchołkiem pierwszej i ostatniej krawędzi.
W grafie spójnym skierowanym mającym N wierzchołków i M krawędzi, każdemu
cyklowi C j przyporządkowano m - wymiarowy wektor
[
C j C1 j ,... C MJ
]
T
, gdzie:
α i+ − ai−
jeśli krawędź ui jest „przechodzona” α i+ razy w kierunku
zgodnym z jej orientacją oraz α i− w przeciwnym
Cij =
0
jeśli ui nie jest częścią cyklu
Dla grafu z rys. 2 wektor C j odpowiadający cyklowi C j = [u1, u2, u3, u4, u2, u6]T jest równy
C j = [1, -2, -1, 1, 0 , 1, 0]T.
Definicja 7
Macierz T [tij] wymiaru N x M nazywamy macierzą incydencji wtedy, gdy:
-1
tij =
gdy uj „wychodzi” do wierzchołka Vi,
+1
gdy uj „wychodzi” z wierzchołka Vi,
0
gdy uj nie ma końca w wierzchołku Vi.
5
k r a w ę d z i e
1
1
1
3
4
2
3
4
5
w
-1
0
1
0
0
2
1
1
0
0
0
z
3
0
-1
-1
1
0
ł
3
2
2
1
ę
4
4
0
0
0
-1
0
y
Definicja 8
Grafem planarnym nazywamy graf, którego żadna dwie krawędzie nie przecinają się z
wyjątkiem punktów końcowych.
Macierz incydencji = macierz podstawowych przekrojów grafu, zawiera informacje o
sposobie połączeń wzdłuż i prętów oraz o zwrocie prętów konstrukcji.
Np. dla ramy portalowej:
a)
5
b)
1
1
2
2
2
2
4
3
1
3
3
1
3
4
4
6
a) graf podstawowy: linie grube - krawędzie pierwszego rodzaju
linie cienkie - krawędzie drugiego rodzaju
b) graf
... zobacz całą notatkę
Komentarze użytkowników (0)