Дискретная математика: Основы теории графов и алгоритмизация задач. Прокушев Л.А. - 11 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

11
îáîçíà÷àòü G=(V,
U
). Ïðè òàêîì îïðåäåëåíèè ãðàôà îòíîøåíèå èíöè-
äåíòíîñòè âåðøèí è ðåáåð çàäàåòñÿ íå ÿâíî. Íàïðèìåð, äëÿ ãåîìåòðè-
÷åñêîãî ãðàôà (ðèñ.1.2) ñîîòâåòñòâóþùèé àáñòðàêòíûé ãðàô ìîæíî îïè-
ñàòü êàê ìíîæåñòâà:
âåðøèí V={v
1
, v
2
, v
3
, v
4
} è
ðåáåð
U
={[v
1
, v
2
], [v
2
, v
3
], [v
3
, v
4
], [v
4
, v
2
], [v
4
, v
1
]}.
Ìîæíî ââåñòè îòîáðàæåíèå èíöèäåíòíîñòè (èëè èíöèäåíöèè) Ã
ãðàôà G. Åñëè âåðøèíû v, w∈V ÿâëÿþòñÿ ãðàíè÷íûìè (êîíöåâûìè) òî÷-
êàìè ðåáðà
u
∈
U
, òî ýòî ìîæíî îáîçíà÷èòü
u
~[v, w] (÷èòàåòñÿ
u
ñîåäèíÿåò âåðøèíû v è w) è ââåñòè îòîáðàæåíèå Ã(
u
)=[v, w] ýòî
îçíà÷àåò, ÷òî ðåáðî
u
èíöèäåíòíî êàæäîé èç âåðøèí v è w è íàîáîðîò
âåðøèíû èíöèäåíòíû ðåáðó.
Òîãäà ãðàô G ìîæíî îïèñàòü êàê ìàòåìàòè÷åñêóþ ñèñòåìó G=(V,
U
,
Ã), ñîñòîÿùóþ èç äâóõ ìíîæåñòâ V (âåðøèí) è
U
(ðåáåð) è îòîáðàæåíèÿ
à èíöèäåíòíîñòè ìíîæåñòâà
U
â V&V (ìíîæåñòâî íåóïîðÿäî÷åííûõ
ïàð ýëåìåíòîâ âèäà [v, w]∈V).
Íàïðèìåð, äëÿ ãåîìåòðè÷åñêîãî ãðàôà (ðèñ.1.3) ñîîòâåòñòâóþùèé
àáñòðàêòíûé ãðàô ìîæíî îïèñàòü êàê ìíîæåñòâà:
V={v
1
, v
2
, v
3
, v
4
},
U
={
u
1
,
u
2
,
u
3
,
u
4
,
u
5
} è îòîáðàæåíèÿ èíöèäåíòíîñòè
Ã={
u
1
~[v
1
, v
2
],
u
2
~[v
2
, v
3
],
u
3
~[v
3
, v
4
],
u
4
~[v
4
, v
1
],
u
5
~[v
4
, v
2
]}.
Ïîñêîëüêó îòîáðàæåíèå èíöèäåíòíîñòè ãðàôà à âêëþ÷àåò ìíîæå-
ñòâî ðåáåð ãðàôà
U
, ïîñòîëüêó îïèñàíèå ãðàôà êàê ñîâîêóïíîñòè ìíî-
æåñòâà âåðøèí V è îòîáðàæåíèÿ Ã ìíîæåñòâà
U
â V&V âèäà G=(V, Ã)
ïîëíîñòüþ îïðåäåëÿåò ãðàô.
L
L
L
"
L
!
L
L
L
"
L
!
1
u
2
u
3
u
4
u
5
u
Ðèñ. 1.2. Ãåîìåòðè÷åñêèé ãðàô
áåç îáîçíà÷åíèÿ ðåáåð
Ðèñ. 1.3. Ãåîìåòðè÷åñêèé ãðàô
ñ îáîçíà÷åíèåì ðåáåð

Страницы