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ędz
ma dwa (niekoniecznie różne) wierzchołki jako jej punkty końcowe oraz nie prze-
chodzi ona przez inne wierzchołki. Mówimy, że krawędz
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ędz
ma określoną orientację.
Zorientowana krawędz
 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.
u u u
5 5 5
v v
1 1
u
u
1
1
u
u
v 3
3
1
v
v
4
4 v
5
u
1
u
u 4
u
4
3
v
4
v
v 3
u
3 u
4
u 2
2
v
v 2
2
v
3
u
2
v
2
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.
v v
1 1
u
1
u
6 u
u u
u 1
5 6
7
v
2
u
5
u u
4 3 u
2
u
7
v
4
v
3
u
2
u
u
3
4
v v
3 4
v
2
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 przyporzÄ…dkowano m - wymiarowy wektor
j
T
C [C1 j ,... CMJ ] , gdzie:
j
ąi+ - ai- jeśli krawędz
ui jest  przechodzona Ä…i+ razy w kierunku
Cij = zgodnym z jej orientacjÄ… oraz Ä…i- w przeciwnym
0 jeśli ui nie jest częścią cyklu
Dla grafu z rys. 2 wektor C odpowiadający cyklowi C = [u1, u2, u3, u4, u2, u6]T jest równy
j j
C = [1, -2, -1, 1, 0 , 1, 0]T.
j
Definicja 7
Macierz T [tij] wymiaru N x M nazywamy macierzÄ… incydencji wtedy, gdy:
-1 gdy uj  wychodzi do wierzchołka Vi,
tij = +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 2 3 4 5
1
3
4
w 1 -1 0 1 0 0
4
Ä™ 1 1 0 0 0
2
3
2
z
3 0 -1 -1 1 0
2
Å‚
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) b)
1
2
5
1
2
2
2
4
3 3
1 1
3
4
3
4
6
a) graf podstawowy: linie grube - krawędzie pierwszego rodzaju
linie cienkie - krawędzie drugiego rodzaju
b) graf uproszczony
Macierze incydencji są następujące:
a) b)
p r Ä™ t y p r Ä™ t y
w 1 2 3 4 5 6 w 1 2 3
Ä™ Ä™
1 1 1 1 1 1 1
z z
2 -1 1 1 2 -1 1
Å‚ Å‚
3 -1 -1 1 3 -1
y y
4 -1 -1 -1 4 -1
 Na podstawie zdefiniowanej macierzy incydencji T określona jest uogólniona macierz
incydencji H, zwana dalej macierzÄ… incydencji.
Elementy macierzy H ustalane są następująco:
element H(i,j) jako macierz jednostkowa:
I1dla T(i,j) = 1
s
- I1 dla T(i,j) = -1
s
o
Is dla T(i,j) = 0
s - wskaz
nik oznaczający stopień macierzy:
s = 2 - kratownica 2D s = 3  rama 2D
s = 3 - kratownica 3D s = 6 - rama 3D
Postaci macierzy I są następujące:
1 1 0 1 0 0
0 1 0 1 0
0 0 1
s=1 s=2 s=3
Ogólnie:
f+ dla T (i,j) = 1
H(i,j) = f dla T (i,j) = -1
fo dla T (i,j) = 0
o o o o
f+ = [I1 ; Is ], f- = [Is ; I1], fo = [Is ; Is ]
s s
gdzie: I1 - jest macierzÄ… jednostkowÄ… stopnia s,
s
o
Is - jest macierzÄ… zerowÄ… stopnia s o wymiarze s x s,
gdzie s - stopień swobody węzła konstrukcji.