PODSTAWOWE DEFINICJE TEORII GRAFÓW
Definicja 1
Grafem skończonym G nazywamy skończony zbiór punktów V
i
, i = l, N, zwanych
wierzchołkami i skończony zbiór linii u
i
, 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 prze-
chodzi 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.
u
1
v
1
v
2
v
3
v
4
u
2
u
3
u
4
u
5
u
1
v
1
v
2
v
3
v
4
v
5
u
2
u
3
u
4
u
5
u
1
v
1
v
2
v
3
v
4
u
2
u
3
u
4
u
5
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
4
v
3
v
2
v
1
u
1
u
6
u
5
u
7
u
2
u
4
u
3
v
4
v
3
v
2
v
1
u
1
u
6
u
5
u
7
u
2
u
4
u
3
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
j
C
przyporządkowano m - wymiarowy wektor
[
]
T
MJ
j
j
C
C
C
,...
1
, gdzie:
−
+
−
i
i
a
α
jeśli krawędź u
i
jest „przechodzona”
+
i
α
razy w kierunku
C
ij
=
zgodnym z jej orientacją oraz
−
i
α
w przeciwnym
0
jeśli u
i
nie jest częścią cyklu
Dla grafu z rys. 2 wektor
j
C
odpowiadający cyklowi
j
C
=
[
u
1
, u
2
, u
3
, u
4
, u
2
, u
6
]
T
jest równy
j
C
=
[
1, -2, -1, 1, 0 , 1, 0
]
T
.
Definicja 7
Macierz T
[
t
ij
]
wymiaru N x M nazywamy macierzą incydencji wtedy, gdy:
-1
gdy u
j
„wychodzi” do wierzchołka V
i
,
t
ij
=
+1
gdy u
j
„wychodzi” z wierzchołka V
i
,
0
gdy u
j
nie ma końca w wierzchołku V
i
.
1
1
2
3
4
2
3
4
5
k r a w ę d z i e
1
2
3
4
5
w
ę
z
ł
y
1
-1
0
1
0
0
2
1
1
0
0
0
3
0
-1
-1
1
0
4
0
0
0
-1
0
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
1
2
3
4
2
3
4
5
6
1
1
2
3
4
2
3
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
ę
z
ł
y
1 2
3
4
5
6
w
ę
z
ł
y
1
2
3
1 1
1
1
1
1
1
2
-1
1
1
2
-1
1
3 -1
-1
1
3
-1
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:
1
s
I
dla T(i,j) = 1
-
1
s
I
dla T(i,j) = -1
o
s
I
dla T(i,j) = 0
s - wskaź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
f
o
dla T (i,j) = 0
f
+
=
[
]
o
s
s
I
I ;
1
,
f
-
=
[
]
1
;
s
o
s
I
I
,
f
o
=
[
]
o
s
o
s
I
I ;
gdzie:
1
s
I
- jest macierzą jednostkową stopnia s,
o
s
I
- jest macierzą zerową stopnia s o wymiarze s x s,
gdzie s - stopień swobody węzła konstrukcji.