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 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.

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.

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
przyporządkowano m - wymiarowy wektor

, gdzie:

jeśli krawędź u_i jest „przechodzona”
razy w kierunku

C_ij = zgodnym z jej orientacją oraz
w przeciwnym

0 jeśli u_i nie jest częścią cyklu

Dla grafu z rys. 2 wektor odpowiadający cyklowi = [u₁, u₂, u₃, u₄, u₂, u₆]^T jest równy
= [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.

			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)

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:

dla T(i,j) = 1

- dla T(i,j) = -1

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⁺ = , f^- = , f^o =

gdzie: - jest macierzą jednostkową stopnia s,

- jest macierzą zerową stopnia s o wymiarze s x s,

gdzie s - stopień swobody węzła konstrukcji.

---