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
]
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
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