ALG 0

250 RozdziaMO. Elementy algorytmiki gratów

(

z-O;

while(l) // pętla nieskończona

I

if(z==n) broak;

if((ql|x][zl==l)4&(g?(z][y)==1)) (

g3[x]ly]=l; break:

1

z + + ;

)

I

• potęga grafu

Potęga G¹' jest zdefiniowana w sposób rekurencyjny:

G° = D,

V p > 1. G‘‘ = G¹'-' oG = C»G'^M.

D oznacza tzw. graf diagonalny, czyli laki. w którym istnieją wyłącznie „krawędzie” typu Z potęgą grafu jest związane dość ciekawe twierdzenie: (x,y) należy do (/' wtedy i tylko wtedy, jeśli w G istnieje droga o długości p, która prowadzi od węzła x do węzła y.

Graf jest dość ciekawym wytworem z punktu widzenia matematyki, gdyż zupełnie naturalnie pozwala on przez samą swoją konstrukcję wyrazić relacje binarne zdefiniowane na zbiorze swoich wierzchołków X.

Elementarnym przykładem niech będzie pojęcie symetrii: jeśli istnienie krawędzi (x, y) implikuje istnienie krawędzi (y, x), to możemy powiedzieć o grafie, że jest on symetryczny. W podobny sposób można zdefiniować całkiem sporo innych relacji binarnych. z których większość... nie ma żadnego praktycznego zastosowania. Wyjątkiem jest relacja przechodniości, która oznacza, że każda droga grafu G o długości większej lub równej I jest „podtrzymywana'’ przez jakąś krawędź.

Dlaczego relacja przechodniości jest taka ważna? Otóż przechodniość sama w sobie dość paradoksalnie nic nic oznacza. Jest ona po prostu dość wygodnym środkiem do zdefiniowania tzw . domknięcia przechodniego grafu, oznaczanego typowo przez G =(X. E J, gdzie:

G ={(x, y) 1 istnieje droga od v do y w grafie G}