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

UptoLike

ВУЗ: 

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

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

Рубрика: 

24
ñèììåòðè÷íûõ âåðøèí. Íàïðèìåð, â ñèñòåìå ãîðîäñêèõ óëèö íåîáõîäè-
ìî èçîáðàçèòü óëèöû ñ îäíîñòîðîííèì äâèæåíèåì. Âî-âòîðûõ, ââåäå-
íèå îðèåíòàöèè íåîáõîäèìî äëÿ óñòàíîâëåíèÿ ñèñòåìû êîîðäèíàò è óñ-
òðàíåíèÿ íåîäíîçíà÷íîñòåé. Íàïðèìåð, ïðè ñîåäèíåíèè ýëåêòðè÷åñêèõ
ïðèáîðîâ îäíî íàïðàâëåíèå íåîáõîäèìî îáîçíà÷èòü êàê ïîëîæèòåëü-
íîå äëÿ òîãî, ÷òîáû îäíîçíà÷íî îïèñàòü ðàñïðåäåëåíèå ýëåêòðè÷åñêî-
ãî òîêà.
Ïðåäñòàâèì ôîðìàëüíîå îïèñàíèå îðãðàôà, îïèðàÿñü íà ñòðóêòóð-
íûå òåðìèíû, ââåäåííûå äëÿ íåîðèåíòèðîâàííûõ ãðàôîâ.
Îðãðàô G ìîæíî îïðåäåëèòü êàê ñîâîêóïíîñòü G=(V, U), ãäå
V={v
1
, , v
n
} ìíîæåñòâî âåðøèí ãðàôà, à U⊂V×V êîíå÷íîå ïîä-
ìíîæåñòâî óïîðÿäî÷åííîãî (äåêàðòîâà) ïðîèçâåäåíèÿ V×V, îáðàçóþùåå
ìíîæåñòâî äóã ãðàôà.
Äóãó (ñòðåëêó), ñîåäèíÿþùóþ âåðøèíû v
i
, v
j
, îáîçíà÷àþò (v
i
, v
j
), ãäå
v
i
íà÷àëî äóãè, à v
j
êîíåö äóãè. Ãîâîðÿò, ÷òî äóãà íàïðàâëåíà îò
âåðøèíû v
i
ê âåðøèíå v
j
, èëè, ÷òî äóãà èñõîäèò èç âåðøèíû v
i
è âõîäèò â
âåðøèíó v
j
. Äëÿ óäîáñòâà äóãè òàêæå îáîçíà÷àþò îäíîé áóêâîé: u
ij
=(v
i
, v
j
),
u
k
=(v
i
, v
j
) èëè u=(v
i
, v
j
). Ïðèìåð îðãðàôà ïðèâåäåí íà ðèñ. 1.15.
Îðãðàô íà ðèñ. 1.15 ñîñòîèò èç ìíîæåñòâà âåðøèí V={v
1
,v
2
,v
3
,v
4,
v
5
}
è ìíîæåñòâà äóã U={u
1
=(v
1
, v
2
), u
2
=(v
2
, v
1
), u
3
=(v
2
, v
3
), u
4
=(v
2
, v
3
), u
5
=
=(v
3
, v
3
), u
6
=(v
3,
v
4
), u
7
=(v
4
, v
1
), u
8
=(v
5
, v
4
), u
9
=(v
5
, v
5
)}.
Ìàòðèöà ñìåæíîñòè âåðøèí îðãðàôà
Îðãðàô ìîæíî îïèñàòü êâàäðàòíîé ìàòðèöåé ñìåæíîñòè S
n×n
, ãäå
n = | S | êîëè÷åñòâî âåðøèí ãðàôà, à ýëåìåíò s
ij
ðàâåí êîëè÷åñòâó
äóã (v
i
, v
j
), ò. å. ñòðåëîê, èäóùèõ îò âåðøèíû v
i
ê v
j
(ðèñ. 1.15).
Ñìåæíûìè äóãàìè íàçûâàþòñÿ äóãè, èìåþùèå îáùóþ ãðàíè÷íóþ
òî÷êó, íàïðèìåð, äóãè u
1
, u
2
, u
3
, u
4
ñìåæíûå îòíîñèòåëüíî âåðøèíû v
2
(ðèñ. 1.15).
v
v
v
"
v
#
u
%
v
!
u
$
u
!
u
"
u
u
u
#
u
'
u
&
V
Ðèñ. 1.15. Îðèåíòèðîâàííûé ãðàô è åãî ìàòðèöà ñìåæíîñòè
S
5×5
=
L
1
L
2
L
3
L
4
L
5
L
1
01000
L
2
10200
L
3
00110
L
4
10000
L
5
00011

Страницы