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

UptoLike

ВУЗ: 

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

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

Рубрика: 

77
d
(d ∨ e) ∨ d
e
=
d
e ∨ d
e
,
e
(d ∨ e) ∨ e
d
= d
e
∨
d
e.
Ô
N
= (
a
b ∨
a
e ∨ a
b
e
) (
b
a ∨
b
c ∨
b
d) c (
d
e ∨ d
e
) =
= (
a
b ∨
a
e ∨ a
b
e
)(
b
c) (
d
e∨d
e
) =
= (
a
b
ce ∨ a
b
c
e
) (
d
e ∨ d
e
) =
a
b
c
d
e ∨ a
b
cd
e
= 1,
ò. å. Ô
N
=
a
b
c
d
e ∨ a
b
cd
e
= 1.
Òàêèì îáðàçîì, ãðàô îáëàäàåò äâóìÿ ÿäðàìè : N
1
={C,E} è N
2
={A,C,D},
êîòîðûå âûäåëåíû íà ðèñ. 4.10.
Èç ðèñ. 4.10 âèäíî, ÷òî ìåæäó âåðøèíàìè ÿäðà ïðîèçâîëüíîãî
ãðàôà ìîæåò íàðóøàòüñÿ îòíîøåíèå ïðåâîñõîäñòâà : (v,v')∈U, åñëè
(v,v')∈P
f
, ò. å. åñëè v' ïðåâîñõîäèò v, òî ñóùåñòâóåò äóãà (v,v')∈U. Ýòî
ïðîèñõîäèò âñëåäñòâèå ïðèñóòñòâèÿ êîíòóðîâ â ãðàôå, íàïðèìåð âåð-
øèíû êîíòóðà {E,D}, ïðèíàäëåæàò ðàçíûì ÿäðàì, à òàêæå èç-çà íà-
ðóøåíèÿ îòíîøåíèÿ òðàíçèòèâíîñòè ìåæäó âåðøèíàìè ÿäåð, íàïðè-
ìåð ìåæäó âåðøèíàìè A è C åñòü ïóòü (À,Â,Ñ). Ïîýòîìó ïîèñê ïðåä-
ïî÷òèòåëüíûõ îáúåêòîâ ñ èñïîëüçîâàíèåì ÿäåð ãðàôà ìîæíî ðàçáèòü
íà äâà ýòàïà.
1 ýòàï. Â èñõîäíîì ãðàôå îñóùåñòâëÿåòñÿ ïîèñê êëàññîâ ýêâèâà-
ëåíòíîñòåé âåðøèí (ò. å. êîíòóðîâ) â ñîîòâåòñòâèè ñ àëãîðèòìîì ï.
4.5.2 è òðàíñôîðìàöèÿ èñõîäíîãî ãðàôà â ãðàô êëàññîâ ýêâèâàëåíò-
íîñòåé, êîòîðûé ÿâëÿåòñÿ ãðàôîì áåç êîíòóðîâ, ò. å. àöèêëè÷åñêèì.
2 ýòàï. Â òåîðèè ãðàôîâ äîêàçàíà ñëåäóþùàÿ òåîðåìà : ãðàô áåç
êîíòóðîâ âñåãäà îáëàäàåò ÿäðîì. Íà îñíîâå ýòîé òåîðåìû îñóùåñòâ-
ëÿåòñÿ ïîèñê ÿäåð àöèêëè÷åñêîãî ãðàôà è âûäåëåíèå ñðåäè íèõ âèñÿ-
Ðèñ. 4.10. Ãðàô ñ âûäåëåííûìè ÿäðàìè
E
A
D
CB
N
N

Страницы