W2.PDF

(101 KB) Pobierz
Microsoft Word - 8course-02.doc
Liczba dróg pomi dzy wierzchołkami .
Je eli M jest macierz grafu G (macierz s siedztwa) to element
M
[ 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 v 1 do v 2 .
Przykład 4 .
Rozwa my graf z Rysunku 4 . Jego macierz
s siedztwa ma posta :
a
b
d
e
c
Ç
1
2
1
1
×
v 1
È
Ø
v 2
0
2
0
0
È
Ø
M
=
È
1
0
0
1
Ø
h
È
Ø
É
0
1
0
0
Ù
f
g
j
Łatwo zauwa y , e drogami o długo ci 2 z
v 3
wierzchołka v 1 do wierzchołka v 2 s drogi
ab, ac, bd, be, cd, ce i hj . Jest ich 7. W
k
v 4
podobny sposób mo na wyznaczy liczb
dróg o długo ci n pomi dzy wybranymi
Rysunek 4
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:
1 =
2
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
]
× M
[
2
2
]
=
2
×
2
=
. Tymi drogami s : bd, be, cd oraz ce . Liczba wszystkich
dróg od v 1 do v 2 o długo ci 2 wynosi:
6
i
× .
Tymi drogami s ab i ac . Liczby, które mno ymy, tzn. M[1,1] i M[1,2] s wzi te z
M
3247203.001.png
M
Liczba, któr otrzymali my jest elementem [1,2] macierzy M 2 . Wyraz
[
×
M
[
+
M
[
2
]
×
M
[
2
2
]
+
M
[
×
M
[
2
]
+
M
[
4
×
M
[
4
2
=
2
+
4
+
0
+
1
=
7
M
2
[
i
,
j
]
jest
liczb dróg od v i do v j o długo ci k
Ogólnie:
M k
[ j
,
]
=
liczba dróg v i do v j o długo ci k .
Dla grafu z Rysunku 4 mamy:
Ç
2
7
1
2
×
È
Ø
0
4
0
0
È
Ø
M
2
=
,
È
1
3
1
1
Ø
É
0
2
0
0
Ù
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 ,
M
[
2
]
=
0
to
jednak
M
2
[
2
=
3
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.
7
]
]
.
i
3247203.002.png
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
a
:
V
(
G
)
®
V
(
H
)
takie, e
{ w
}
jest kraw dzi grafu G wtedy i tylko wtedy, gdy
a
(
u a
),
(
)}
jest kraw dzi w grafie H. Zapisujemy to jako
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
b
:
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
u
{
w
H
3247203.003.png
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
w
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 k
( G
)
oznacza liczb wierzchołków stopnia k w grafie G.
D k
( G
)
jest
niezmiennikiem izomorfizmu. Niezmiennikiem jest równie ci g liczb
wierzchołków kolejnych stopni
(
D
0
G
),
D
1
(
G
),
3
).
9
(
3247203.004.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin