Элементы теории графов. Домнин Л.Н. - 23 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

V {v
1
, v
2
, v
3
, v
4
, v
5
}.
V
2
=V ×V.
(v
i
, v
j
), i, j=1, 5
V
2
= {(v
1
, v
1
) (v
1
, v
2
) (v
1
, v
3
) (v
1
, v
4
), (v
1
, v
5
)
(v
2
, v
1
) (v
2
, v
2
) (v
2
, v
3
) (v
2
, v
4
) (v
2
, v
5
)
(v
3
, v
1
) (v
3
, v
2
) (v
3
, v
3
) (v
3
, v
4
) (v
3
, v
5
)
(v
4
, v
1
) (v
4
, v
2
) (v
4
, v
3
) (v
4
, v
4
) (v
4
, v
5
)
(v
5
, v
1
) (v
5
, v
2
) (v
5
, v
3
) (v
5
, v
4
) (v
5
, v
5
)}
A ⊆ V
2
,
A={(v
1
, v
2
), (v
1
, v
3
), (v
2
, v
5
), (v
3
, v
2
), (v
4
, v
1
), (v
4
, v
3
), (v
5
, v
4
)}.
hV, Ai G
V A
V
2
.
hV, Ai
V
A
V,
G(V, A)=h{v
1
, v
2
, v
3
, v
4
, v
5
}, {(v
1
, v
2
), (v
1
, v
3
), (v
2
, v
5
), (v
3
, v
2
),
(v
4
, v
1
), (v
4
, v
3
), (v
5
, v
4
)}i, (v
i
, v
j
)
v
i
v
j
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
Z
Z
Z~
B
B
B
B
BN
-
B
B
BN
hV, Γi, Γ
V.
Γ(v
1
) = {v
2
, v
3
} Γ(v
2
) = {v
5
} Γ(v
3
) = {v
2
}
Γ(v
4
) = {v
1
, v
3
} Γ(v
5
) = {v
4
}
V
2
A
    1.6. Îðèåíòèðîâàííûå ãðàôû
   Íàðÿäó ñ íåîðèåíòèðîâàííûìè â òåîðèè ãðàôîâ ðàññìàò-
ðèâàþòñÿ îðèåíòèðîâàííûå ãðàôû, èëè îðãðàôû.
    Òåîðåòèêî-ìíîæåñòâåííîå îïðåäåëåíèå îðãðàôà.
Ïóñòü V  íåïóñòîå ìíîæåñòâî, íàïðèìåð, {v1 , v2 , v3 , v4 , v5 }. Çà-
ïèøåì åãî äåêàðòîâ êâàäðàò V 2 =V ×V. Äëÿ íàøåãî ïðèìåðà
ýòî ìíîæåñòâî âñåõ óïîðÿäî÷åííûõ ïàð âèäà (vi , vj ), i, j=1, 5 :
         V 2 = {(v1 , v1 ) ,    (v1 , v2 ) ,   (v1 , v3 ) , (v1 , v4 ), (v1 , v5 ) ,
                (v2 , v1 ) ,    (v2 , v2 ) ,   (v2 , v3 ) , (v2 , v4 ) , (v2 , v5 ) ,
                (v3 , v1 ) ,    (v3 , v2 ) ,   (v3 , v3 ) , (v3 , v4 ) , (v3 , v5 ) ,
                (v4 , v1 ) ,    (v4 , v2 ) ,   (v4 , v3 ) , (v4 , v4 ) , (v4 , v5 ) ,
                (v5 , v1 ) ,    (v5 , v2 ) ,   (v5 , v3 ) , (v5 , v4 ) , (v5 , v5 )} .
    Âîçüìåì ïðîèçâîëüíî íåêîòîðîå A ⊆ V 2 , íàïðèìåð,
A={(v1 , v2 ), (v1 , v3 ), (v2 , v5 ), (v3 , v2 ), (v4 , v1 ), (v4 , v3 ), (v5 , v4 )}. 5
    Ïàðó hV, Ai íàçûâàþò îðèåíòèðîâàííûì ãðàôîì G , â êî-
òîðîì V  ìíîæåñòâî âåðøèí, A  ìíîæåñòâî äóã, ÿâëÿþùå-
åñÿ ïîäìíîæåñòâîì V 2 . Îêîí÷àòåëüíî ñôîðìóëèðóåì îïðåäå-
ëåíèå òàê: ïàðà hV, Ai íàçûâàåòñÿ îðèåíòèðîâàííûì ãðàôîì,
åñëè V  íåïóñòîå ìíîæåñòâî ýëåìåíòîâ, íàçûâàåìûõ âåðøè-
íàìè, A  ìíîæåñòâî óïîðÿäî÷åííûõ ïàð ðàçëè÷íûõ ýëåìåí-
òîâ èç V, íàçûâàåìûõ äóãàìè. Òîãäà äëÿ íàøåãî ïðèìåðà èìå-
åì G(V, A)=h{v1 , v2 , v3 , v4 , v5 }, {(v1 , v2 ), (v1 , v3 ), (v2 , v5 ), (v3 , v2 ),
(v4 , v1 ), (v4 , v3 ), (v5 , v4 )}i, ãäå (vi , vj )  äó-                        vs1
ãà, ó êîòîðîé vi  íà÷àëüíàÿ, à vj  êî-                                         BZZ
íå÷íàÿ âåðøèíû. Èçîáðàæåíèå ýòîãî ãðàôà v5 B  B Z                       
                                                                         s             ~ sv2
ïðèâåäåíî íà ðèñ. 1.15. Î÷åâèäíî, ÷òî ìíî-                                           B 
                                                                          BBN        BN
æåñòâî äóã, ñîåäèíÿþùèõ ýëåìåíòû ìíîæå-                                  v4 s - sv3
ñòâà âåðøèí, îòîáðàæàåò ýòî ìíîæåñòâî ñà-
ìî â ñåáÿ. Ïîýòîìó îðãðàô ìîæíî ðàñ-                                      Ðèñ. 1.15
ñìàòðèâàòü êàê ïàðó hV, Γi, ãäå Γ  îòîáðàæåíèå, çàäàííîå
íà ìíîæåñòâå V. Äëÿ ãðàôà íà ðèñ. 1.15 èìååì
      Γ(v1 ) = {v2 , v3 },       Γ(v2 ) = {v5 },           Γ(v3 ) = {v2 },
      Γ(v4 ) = {v1 , v3 },       Γ(v5 ) = {v4 }.
   5   çàïèñè äëÿ V 2 ýëåìåíòû èíîæåñòâà A ïîä÷åðêíóòû.


                                               23

Страницы