Liczba dróg pomi dzy wierzchołkami.

Je eli M jest macierz grafu G (macierz s siedztwa) to element M[ i, j] 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 v1 do v2.

Przykład 4.

Rozwa my graf z Rysunku 4. Jego macierz

s siedztwa ma posta :

a

b

d

e

1 2 1 1

c

v1

0 2 0 0

v2

M = 1 0 0 1

h

0 1 0 0

f

g

j

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

v3

wierzchołka v1 do wierzchołka v2 s drogi

k

v

ab, ac, bd, be, cd, ce i hj. Jest ich 7. W

4

podobny sposób mo na wyznaczy liczb

Rysunek 4

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 v1 do v2 w mi dzyczasie przechodzi przez wierzchołki v1, v2, v3 oraz v4. Tak wi c mo emy policzy drogi z v1

do v1 przechodz ce przez v1, przez v2 itd. a nast pnie je doda . Je li np. chcemy policzy drogi maj ce ci g wierzchołków v1v2v1, zliczamy kraw dzie z v1 do v1

(p tle) i kraw dzie z v1 do v2 i otrzymane liczby mno ymy przez siebie: 1⋅ 2 = 2 .

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 v1v2v2. Zliczamy

kraw dzie od v1 do v2 oraz od v2 do v2 a nast pnie te liczby mno ymy przez siebie: M ,

1

[ 2] ⋅ M[ ,

2 2] = 2 ⋅ 2 = 4 . Tymi drogami s : bd, be, cd oraz ce. Liczba wszystkich dróg od v1 do v2 o długo ci 2 wynosi:

6

M

]

1

,

1

[

⋅ M

]

1

,

1

[

+ M ,

1

[ 2] ⋅ M[ ,

2 2] + M

]

3

,

1

[

⋅ M ,

3

[ 2] + M ,

1

[ 4] ⋅ M[ ,

4 2] = 2 + 4 + 0 + 1 = 7.

Liczba, któr otrzymali my jest elementem [1,2] macierzy M2. Wyraz

2

M [ i, j] jest

liczb dróg od vi do vj o długo ci k

Ogólnie:

M k [ i, j] = liczba dróg vi do vj o długo ci k.

Dla grafu z Rysunku 4 mamy:

2 7 1 2

0 4 0 0

2

M =

,

1 3 1 1

0 2 0 0

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

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 v3 do v2, M , 3

[ 2] = ,

0 to

jednak

2

M

,

3

[

]

2 = ,

3 a zatem istniej 3 drogi o długo ci 2 od v3 do v2, i wierzchołki te

s w relacji osi galno ci.

7

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

α : V ( G) → V ( H ) takie, e { u, }

w jest kraw dzi grafu G wtedy i tylko wtedy, gdy

{α( u),α( )

w }jest kraw dzi w grafie H. Zapisujemy to jako G ≅ H.

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 β : E( G) → E( H ) pomi dzy zbiorami kraw dzi grafów.

Rysunek 5

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.

8

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

w

Rysunku 6 ma stopie 4, gdy s dwie

kraw dzie

wychodz ce

z

tego

v

wierzchołka oraz jedna p tla,

deg( )

w = 2 + 2 ⋅1 = 4

Natomiast wierzchołek v ma stopie 1:

Rysunek 6

deg( v) = 1 + 2 ⋅ 0 = 1.

Niech D

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

jest

k ( G)

k ( G)

niezmiennikiem izomorfizmu. Niezmiennikiem jest równie ci g liczb

wierzchołków kolejnych stopni ( D G D G

0 (

), 1( ), ).

9