RODZAJE GAŁĘZI W GRAFIE
1. Gałąź u taką, że dla x≠y <x,u,y>∈P i <y,u,x> ∈P. nazywamy krawędzią.
2. Gałąź u taką, że dla x≠y <x,u,y>∈ P i <y,u,x> ∉ P, nazywamy łukiem.
3. Gałąź u taką, że <x,u,x> ∈P nazywamy pętlą.
Definicje grafu skończonego
Graf nazywa się grafem skończonym, gdy |W| + |U| < ∝, a więc jeśli suma mocy zbiorów wierzchołków i gałęzi jest skończona.
Przykład
Rozważmy graf G=<W,U,P>, w którym W={1,2,3,4,5), U={a,b,c,d,e,f,g,h,i,j}.
Zbiór elementów relacji P: WxW → U jest przedstawiony w tabl. 1.1 zawierającej trójki uporządkowane <x,u,y> ∈ P. gdzie x,y ∈W, a u∈U.
Analizując poszczególne elementy relacji P można zauważyć, że w grafie tym występują wszystkie rodzaje gałęzi.
Gałęzie: b, i - są krawędziami;
Gałęzie: a, e, f, g, h - są łukami;
Gałęzie: c, d, j- są pętlami.
Zbiór elementów relacji P
x |
1 |
1 |
2 |
2 |
2 |
2 |
3 |
3 |
3 |
3 |
4 |
4 |
u |
a |
b |
b |
c |
d |
e |
f |
g |
h |
i |
i |
j |
y |
3 |
2 |
1 |
2 |
2 |
3 |
2 |
4 |
4 |
4 |
3 |
4 |