Teoria grafow i sieci - temat nr 1

[ Pobierz całość w formacie PDF ]
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 1:
Definicja grafu. Rodzaje i części grafów
GRAFY
„
Podstawą budowania modelu formalnego danego
obiektu zainteresowań powinien być zawsze
określony
cel modelowania
, tzn. cel tworzenia
modelu matematycznego tego obiektu. Zależnie od
celu modelowania danego obiektu, model może
przyjąć różne formy. Najczęściej przy modelowaniu
obiektów istnieje potrzeba i konieczność – z punktu
widzenia celu modelowania – wyróżnienia w obiekcie
pewnego zbioru elementów
X
(np. operacji
wykonywanych w trakcie procesu produkcyjnego,
stanowisk obróbki, itp.). Z chwilą wyróżnienia tych
elementów modelowany obiekt proponuje się
traktować jako
system,
a uzyskany w następstwie
model nazywać będziemy
modelem systemu
.
”
STRUKTURA SYSTEMU
gdzie R
m
– m-ta relacja wiążąca elementy zbioru X;
Modelem systemowym
obiektu nazywa się bądź samą
strukturę, bądź strukturę opisaną ilościowo.
Jeżeli przy modelowaniu obiektu wystarczające jest
uwzględnienie tylko relacji dwuczłonowych, to model
systemowy może być formalnie zapisany bądź
grafem
(struktura S), bądź
siecią
(graf opisany ilościowo).
W przeciwnym przypadku wykorzystuje się
hipergrafy
i/lub
hipersieci
.
2
S =
〈
X, {R
m
}
〉
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 1:
Definicja grafu. Rodzaje i części grafów
DEFINICJA GRAFU
G
= 〈
W, U, P
〉
gałęzie
wierzchołki
W, U
– zbiory
P
⊂
W × U × W
1.
uUxyW
∈∈
∧∨
,
xu y P
,,
∈
u
∧
U
x
,
y
,
v
∧
,
z
∈
W
[ ]
x
,
u
,
y
∈
P
∧
v
,
u
,
z
∈
P
⇒
2.
⇒
(
x
=
v
∧
y
=
z
) (
x
=
z
∧
y
=
v
)
Ad. 1.
Ad. 2.
a
a
Rodzaje gałęzi grafu
U
~
–krawędzie:
〈
x, u, y
〉
∈
P
∧
〈
y, u, x
〉
∈
P
∧
x
≠
y
U
G
–łuki:
〈
x, u, y
〉
∈
P
∧
〈
y, u, x
〉
∉
P
o
U
– pętle:
〈
x, u, y
〉
∈
P
∧
x = y
U
=
U
~
∪
U
G
∪
o
U
3
∨
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 1:
Definicja grafu. Rodzaje i części grafów
PRZYKŁAD GRAFU
Oznaczenia:
-wierzchołki
-krawędzie
- łuki
- pętle
1
c
2
d
j
5
a
b
f
e
g
k
3
4
6
h
i
W
=
{
1, 2, 3, 4, 5, 6
}
U
=
{
a, b, c, d, e, f, g, h, i, j, k
}
=
U
∪
~
∪
G
U
o
U
U
~
={
d, e, f
}
U
G
={
a, b, c, g, h, j
}
o
U
={
i, k
}
P
=
{
〈
3,
a
, 1
〉
,
〈
1,
b
, 3
〉
,
〈
1,
c
, 2
〉
,
〈
1,
d
, 2
〉
,
〈
2,
d
, 1
〉
,
〈
2,
e
, 4
〉
,
〈
4,
e
, 2
〉
,
〈
2,
f
, 4
〉
,
〈
4,
f
, 2
〉
,
〈
3,
g
, 4
〉
,
〈
3,
h
, 4
〉
,
〈
4,
i
, 4
〉
,
〈
5,
j
, 2
〉
,
〈
6,
k
, 6
〉}
Grafy skończone:
W
<
U
∞
∧
<
∞
4
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 1:
Definicja grafu. Rodzaje i części grafów
Za pomocą grafu możemy opisywać (modelować)
wszelkiego rodzaju obiekty rzeczywiste (obiekty
fizyczne, zjawiska, procesy itp.), które posiadają
pewne cechy (wierzchołki grafu)
i pewne relacje między cechami (łuki grafu).
Typowe reprezentacje obiektów rzeczywistych za
pomocą grafów:
•
Struktura sieci dróg (wierzchołki - miasta lub
skrzyżowania, łuki – odcinki dróg);
•
Struktura dowolnego systemu (wierzchołki –
elementy systemu, łuki – powiązania między
elementami systemu);
•
Mapa polityczna świata (wierzchołki – państwa,
łuki/krawędzie – sąsiedztwo między państwami);
•
Struktura przedsięwzięcia (wierzchołki – zdarzenia,
łuki - czynności);
•
Problem przydziału, np. pracowników do zadań
(wierzchołki – pracownicy i zadania do wykonania,
łuki – zdolność pracownika do wykonania zadania);
•
Drzewo genealogiczne (wierzchołki – osoby, łuki –
relacja typu „rodzic-dziecko”).
5
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 1:
Definicja grafu. Rodzaje i części grafów
MACIERZOWE REPREZENTACJE GRAFU
Macierz incydencji:
A
()
Ga
×
=  
 
xu
WU

ξ
x
u


η
x
u

a
=

ϑ
x
u
x
,
u



ϕ
x
u


0

w przeciwnym przypadku
Incydencja:
wierzchołek
x
jest incydentny z gałęzią
u
(i na odwrót) jeśli:
y
∨
W
x
,
u
,
y
∈
P
∨
y
,
u
,
x
∈
P
Binarna macierz incydencji
A
b
()
G
:
ξ
=
η
=
ϑ
=
ϕ
=
1
Macierz przyległości wierzchołków
R
()
Gr
=


xy
,
WW
×
r
xy
,
=∈ ∈∨ ∈
{
u U x u y P y ux P
:, ,
, ,
}
6

[ Pobierz całość w formacie PDF ]