ALG$9

10.2. Sposoby reprezentacji grafów 249

10.2. Sposoby reprezentacji grafów 249

Rys. 10- 5.

a)    b)

A	B	A	NULL
1)	C.D	D	A
C	C.F,	C	B.C
1)	E.F	D	B
E	F	E	C.D
V	NULL	1	D.E

10.3.Podstawowe operacje na grafach

Wiele algorytmów dotyczących grafów daje się łatwo wyrazić przy użyciu specjalnej notacji matematycznej, którą poznamy właśnie w tym paragrafie¹.

Mając dane dwa grafy GJ=(X. TI) i G2=fX. V2), możemy na nich zdefiniować następujące operacje:

• suma grafów

G3=G1+G2= (X, r,₍r₂).

Graf wynikowy G3 zawiera wszystkie krawędzie grafów G1 i G2.

• kompozycja grafów

G₃=G,°G\- (X,r₃ = {(Ar,>-)|32G,V:(x-,z)Gr_i oraz (z,y)<=r,}).

Krawędzie <x. y) grafu wynikowego G3 spełniają warunek, że istnieje pewien węzeł z, taki, że (x, z) należy do Gl, a (z, y) należy do G2.

Kompozycja grafów może być dość łatwo zrealizowana programowo, np. tak jak na listingu znajdującym się poniżej (dla uproszczenia ograniczymy się tylko do reprezentacji tablicowej):

kompoz-cpp

void kompozycja(int gl[n][n), int ę2[n][n), int g3[n](n])

I

int z;

for(int x=0:x<n;x++) for(int y-0;y<n;yiM

Warto w tym miejscu „odświeżyć” oznaczenia matematyczne poznane w rozdziale 3.