6

Liczba dróg pomi dzy wierzchołkami.

Je eli

M jest macierz grafu G (macierz s siedztwa) to element

]

,

[ j

i

M

tej macierzy

reprezentuje liczb kraw dzi wychodz cych z wierzchołka i do wierzchołka j. Ta
liczba kraw dzi jest zarazem liczb dróg o

długo ci 1 od wierzchołka v

1

do

v

2

.

Przykład

4.

Rozwa my graf z Rysunku

4. Jego macierz

s siedztwa ma posta :

Łatwo zauwa y , e drogami o długo ci 2 z
wierzchołka

v

1

do wierzchołka

v

2

s drogi

ab, ac, bd, be, cd, ce i hj. Jest ich 7. W
podobny sposób mo na wyznaczy liczb
dróg o długo ci n pomi dzy wybranymi
wierzchołkami.
Metoda zliczania „na wprost” jest jednak mudna i łatwo o bł dy, szczególnie gdy
analizujemy grafy o du ej liczbie w złów i kraw dzi.
Zauwa my, e np. ka da droga o długo ci 2 z wierzchołka

v

1

do

v

2

w mi dzyczasie

przechodzi przez wierzchołki

v

1

,

v

2

,

v

3

oraz

v

4

. Tak wi c mo emy policzy drogi z v1

do

v

1

przechodz ce przez

v

1

, przez

v

2

itd. a nast pnie je doda . Je li np. chcemy

policzy drogi maj ce ci g wierzchołków

v

1

v

2

v

1

, zliczamy kraw dzie z

v

1

do

v

1

(p tle) i kraw dzie z

v

1

do

v

2

i otrzymane liczby mno ymy przez siebie:

2

2

1

=

⋅

.

Tymi drogami s

ab i ac. Liczby, które mno ymy, tzn. M[1,1] i M[1,2] s wzi te z

macierzy M. Podobnie jest z drogami maj cymi ci g wierzchołków

v

1

v

2

v

2

. Zliczamy

kraw dzie od

v

1

do

v

2

oraz od

v

2

do

v

2

a nast pnie te liczby mno ymy przez siebie:

4

2

2

]

2

,

2

[

]

2

,

1

[

=

⋅

=

⋅ M

M

. Tymi drogami s : bd, be, cd oraz ce. Liczba wszystkich

dróg od

v

1

do

v

2

o długo ci 2 wynosi:

=

0

0

1

0

1

0

0

1

0

0

2

0

1

1

2

1

M

d

f

g

h

k

j

v

3

v

4

v

1

v

2

a

b

c

e

Rysunek 4

7

.

7

1

0

4

2

]

2

,

4

[

]

4

,

1

[

]

2

,

3

[

]

3

,

1

[

]

2

,

2

[

]

2

,

1

[

]

1

,

1

[

]

1

,

1

[

=

+

+

+

=

⋅

+

⋅

+

⋅

+

⋅

M

M

M

M

M

M

M

M

Liczba, któr otrzymali my jest elementem [1,2] macierzy M

2

. Wyraz

]

,

[

2

j

i

M

jest

liczb dróg od

v

i

do

v

j

o długo ci k

Ogólnie:

=

]

,

[ j

i

M

k

liczba dróg

v

i

do

v

j

o długo ci

k.

Dla grafu z Rysunku 4 mamy:

Czyli, np. jest 3 drogi długo ci 3 od

v

3

do

v

2

.

Znajomo liczby dróg ró nej długo ci dla danego grafu jest wa na gdy analizujemy
relacj osi galno ci w zbiorze V(G) wierzchołków grafu G.

Dwa

wierzchołki v, w s osi galne je li istnieje w G droga od v do w

długo ci co najmniej 1.

Np. dla grafu z Rys. 4 wida , e chocia nie ma kraw dzi od

v

3

do

v

2

,

,

0

]

2

,

3

[

=

M

to

jednak

,

3

]

2

,

3

[

2

=

M

a zatem istniej 3 drogi o długo ci 2 od

v

3

do

v

2

, i wierzchołki te

s w relacji osi galno ci.

,

0

0

2

0

1

1

3

1

0

0

4

0

2

1

7

2

2

=

M

8

Izomorfizm grafów.

Cz sto zdarza si , e dwa grafy s „wła ciwie takie same”, pomimo, e ró ni si
nazwami wierzchołków i kraw dzi. Wa nym jest czy podobie stwo jest tylko
wizualne czy te strukturalnie dwa grafy s identyczne.

Ogólnie dwa zbiory wyposa one w pewne struktury matematyczne nazywamy
izomorficznymi, je li istnieje przekształcenie wzajemnie jednoznaczne pomi dzy
tymi zbiorami zachowuj ce ich struktury.

Izomorfizmem grafu G na graf H nazywamy przekształcenie wzajemnie jednoznaczne

)

(

)

(

:

H

V

G

V

→

α

takie, e

}

,

{ w

u

jest kraw dzi grafu G wtedy i tylko wtedy, gdy

)}

(

),

(

{

w

u

α

α

jest kraw dzi w grafie H. Zapisujemy to jako

.

H

G

≅

Uwaga:

powy sze okre lenie jest poprawne dla grafów bez kraw dzi

wielokrotnych. Je li graf ma jednak kraw dzie wielokrotne to sytuacja si komplikuje
w tym sensie, e wymagana jest jeszcze wzajemna jednoznaczno dodatkowego
przekształcenia

)

(

)

(

:

H

E

G

E

→

β

pomi dzy zbiorami kraw dzi grafów.

Czy grafy przedstawione na Rys. 5 s izomorficzne?

Istniej pewne cechy grafów, zwane

niezmiennikami izomorfizmu, które pozwalaj

oceni czy dwa grafy s to same w sensie strukturalnym.
Przykładami niezmienników izomorfizmu grafów s liczby: wierzchołków, kraw dzi,
p tli czy liczba dróg prostych o danej długo ci.

Rysunek 5

9

Innym przydatnym niezmiennikiem jest

stopie wierzchołka.

Stopie wierzchołka, oznaczany jako deg(w), jest to liczba dwuwierzchołkowych
kraw dzi z

w jako jednym z wierzchołków, plus podwojona liczba p tli o

wierzchołku

w.

Na przykład wierzchołek w na grafie z
Rysunku 6 ma stopie 4, gdy s dwie
kraw dzie

wychodz ce

z

tego

wierzchołka oraz jedna p tla,

Natomiast wierzchołek v ma stopie 1:

Niech

)

(G

D

k

oznacza liczb wierzchołków stopnia k w grafie G.

)

(G

D

k

jest

niezmiennikiem izomorfizmu.

Niezmiennikiem jest równie ci g liczb

wierzchołków kolejnych stopni

).

),

(

),

(

(

1

0

G

D

G

D

4

1

2

2

)

deg(

=

⋅

+

=

w

.

1

0

2

1

)

deg(

=

⋅

+

=

v

w

v

Rysunek 6