Таран Т.А. Основы дискретной математики
Подождите немного. Документ загружается.
120 121Ãëàâà 8 Ãðàôû
Ïðèìåð.
Ðèñ. 8.8. Ïðèìåðû ãðàôîâ.
Äèàìåòð ãðàôà íà ðèñ. 8.8, a ðàâåí 5, ðàäèóñ 3; â ãðàôå äâà
öåíòðà: âåðøèíû v
3
, v
4
. Äèàìåòð ãðàôà íà ðèñ. 8.8, á ðàâåí 4, ðàäèóñ
2; âåðøèíà v
3
öåíòð ãðàôà.  ãðàôå íà ðèñ. 8.8, â, òîïîëîãè÷åñêè
ýêâèâàëåíòíîì îêðóæíîñòè (âåðíåå, òåëåæíîìó êîëåñó), äèàìåòð
d(G) = 2, ðàäèóñ r(G) = 1, ò.å.äèàìåòð, êàê è â êðóãå, â äâà ðàçà
áîëüøå ðàäèóñà; âåðøèíà v öåíòð. Â ãðàôå íà ðèñ. 8.8, ã d(G)=3,
ðàäèóñ r(G) = 3, è âñå âåðøèíû öåíòðû.
8.5.3. Ýéëåðîâ îáõîä
Îïðåäåëåíèå 8.15. Ýéëåðîâûì îáõîäîì, èëè ýéëåðîâûì öèêëîì, â
íåîðèåíòèðîâàííîì ãðàôå (ìóëüòèãðàôå) íàçûâàåòñÿ öèêë,
êîòîðûé ñîäåðæèò âñå ðåáðà ãðàôà â òî÷íîñòè ïî îäíîìó ðàçó.
Ãðàô íàçûâàåòñÿ ýéëåðîâûì, åñëè â íåì ñóùåñòâóåò ýéëåðîâ îáõîä.
Íå âñÿêèé ãðàô ýéëåðîâ. Ýòî óñòàíîâèë âåëèêèé ìàòåìàòèê
Ë.Ýéëåð, çàíèìàÿñü çàäà÷åé î ê¸íèãñáåðãñêèõ ìîñòàõ.  ãîðîäå
ʸíèãñáåðãå âî âðåìåíà Ýéëåðà áûëî ñåìü ìîñòîâ (ñì. ðèñ. 8.9).
Çàäà÷à çàêëþ÷àåòñÿ â òîì, ÷òîáû, âûéäÿ ñ ëþáîãî ó÷àñòêà ñóøè,
ïðîéòè êàæäûé ìîñò ïî îäíîìó ðàçó è âåðíóòüñÿ â èñõîäíóþ òî÷êó.
Ýéëåð ñâåë ýòó çàäà÷ó ê çàäà÷å íàõîæäåíèÿ îáõîäà ãðàôà íà
ðèñ.8.10è ïîêàçàë, ÷òî îíà íå èìååò ðåøåíèÿ. Íåîáõîäèìûå è äîñ-
òàòî÷íûå óñëîâèÿ ñóùåñòâîâàíèÿ ýéëåðîâà îáõîäà îí ñôîðìóëè-
ðîâàë â ñëåäóþùåé òåîðåìå.
Òåîðåìà 8.3. (Ë.Ýéëåð, 1736ã.). Íåîðèåíòèðîâàííûé ãðàô
ÿâëÿåòñÿ ýéëåðîâûì òîãäà è òîëüêî òîãäà, êîãäà îí ñâÿçåí è âñå
ñòåïåíè åãî âåðøèí ÷åòíû.
Äîêàçàòåëüñòâî.
Íåîáõîäèìîñòü. Ïóñòü G ýéëåðîâ ãðàô. Ýéëåðîâ îáõîä ýòîãî
ãðàôà, ïðîõîäÿ ÷åðåç êàæäóþ åãî âåðøèíó, âõîäèò â íåå ïî îäíîìó
ðåáðó, à âûõîäèò ïî äðóãîìó. Ýòî îçíà÷àåò, ÷òî êàæäàÿ âåðøèíà
èíöèäåíòíà ÷åòíîìó ÷èñëó ðåáåð ýéëåðîâà öèêëà, à ïîñêîëüêó òàêîé
öèêë ñîäåðæèò âñå ðåáðà ãðàôà G, òî îòñþäà ñëåäóåò ÷åòíîñòü
ñòåïåíåé âñåõ âåðøèí.
Äîñòàòî÷íîñòü. Ïðåäïîëîæèì òåïåðü, ÷òî ñòåïåíè âåðøèí
ãðàôà G ÷åòíû. Ïóñòü öåïü P
1
íà÷èíàåòñÿ èç ïðîèçâîëüíîé âåðøèíû
v
1
. Áóäåì ïðîäîëæàòü åå, íàñêîëüêî âîçìîæíî, âûáèðàÿ êàæäûé
ðàç íîâîå ðåáðî. Òàê êàê ñòåïåíè âñåõ âåðøèí ÷åòíû, òî, ïîïàâ â
î÷åðåäíóþ îòëè÷íóþ îò v
1
âåðøèíó, ìû âñåãäà áóäåì èìåòü â
ðàñïîðÿæåíèè åùå íå ïðîéäåííîå ðåáðî. Ïîýòîìó öåïü Ð
1
ìîæíî
ïðîäîëæèòü ïóòåì äîáàâëåíèÿ ýòîãî ðåáðà. Òàêèì îáðàçîì,
ïîñòðîåíèå öåïè Ð
1
çàêîí÷èòñÿ â âåðøèíå v
1
, òî åñòü Ð
1
íåïðåìåííî
áóäåò öèêëîì. Åñëè îêàæåòñÿ, ÷òî Ð
1
ñîäåðæèò âñå ðåáðà ãðàôà G,
òî ýòî áóäåò òðåáóåìûé ýéëåðîâ öèêë.  ïðîòèâíîì ñëó÷àå, óäàëèâ
èç ãðàôà G âñå ðåáðà öèêëà Ð
1
, ðàññìîòðèì ãðàô G
1
, ïîëó÷åííûé â
ðåçóëüòàòå òàêîé îïåðàöèè. Ïîñêîëüêó P
1
è G èìåëè âåðøèíû
òîëüêî ÷åòíûõ ñòåïåíåé, òî, î÷åâèäíî, è G
1
áóäåò îáëàäàòü òåì æå
ñâîéñòâîì. Êðîìå òîãî, â ñèëó ñâÿçíîñòè ãðàôà G, ãðàôû P
1
è
G
1
äîëæíû èìåòü õîòÿ áû îäíó îáùóþ âåðøèíó v
2
. Òåïåðü, íà÷èíàÿ
ñ âåðøèíû v
2
, ïîñòðîèì öèêë P
2
â ãðàôå G
1
ïîäîáíî òîìó, êàê
ñòðîèëè öèêë P
1
. Îáîçíà÷èì ÷åðåç P
1
′, P
1
′′ ÷àñòè öèêëà P
1
îò v
1
äî
v
2
è îò v
2
äî v
1
ñîîòâåòñòâåííî. Ïîëó÷èì íîâûé
öèêë P
3
= P
1
′ ∪ P
2
∪ P
1
′′, êîòîðûé, íà÷èíàÿñü
â v
1
, ïðîõîäèò ïî ðåáðàì öåïè P
1
′ äî v
2
, à çàòåì
îáõîäèò âñå ðåáðà öèêëà P
2
è, íàêîíåö, âîçâðà-
ùàåòñÿ â v
1
ïî ðåáðàì öåïè P
1
′′ (ðèñ.8.11).
Åñëè öèêë P
3
íå ýéëåðîâ, ò.å.ñîäåðæèò åùå
íå âñå ðåáðà ãðàôà, òî, ïðîäåëàâ àíàëîãè÷íûå
ïîñòðîåíèÿ, ïîëó÷èì åùå áîëüøèé öèêë,
èò.ä. Ýòîò ïðîöåññ çàêîí÷èòñÿ ïîñòðîåíèåì
ýéëåðîâà öèêëà.
Ïðèìåðû.
Íà ðèñ. 8.12ïîêàçàí ýéëåðîâ ãðàô. Ïîìèìî çàäà÷è î ê¸íèãñ-
áåðãñêèõ ìîñòàõ, èçâåñòåí ðÿä äðóãèõ ñòàðèííûõ çàíèìàòåëüíûõ
çàäà÷ è ãîëîâîëîìîê, ðåøåíèå êîòîðûõ ñâîäèòñÿ ê âûÿñíåíèþ
âîïðîñà, ÿâëÿåòñÿ ëè ãðàô ýéëåðîâûì. Â îäíîé èç íèõ òðåáóåòñÿ
Ðèñ. 8.9. ʸíèãñáåðãñêèå ìîñòû. Ðèñ. 8.10. Ãðàô ê çàäà÷å
îê¸íèãñáåðãñêèõ ìîñòàõ.
Ðèñ. 8.11. Ãðàô
êäîêàçàòåëüñòâó
òåîðåìû Ýéëåðà.
122 123Ãëàâà 8 Ãðàôû
îáðèñîâàòü ôèãóðó, èìåíóåìóþ ñàáëÿìè (çíàêîì) Ìàãîìåòà
(ðèñ.8.13), íå îòðûâàÿ êàðàíäàøà îò áóìàãè è íå ïîâòîðÿÿ ëèíèé.
8.5.4. Ãàìèëüòîíîâ öèêë
Îïðåäåëåíèå 8.16. Öèêë â íåîðèåíòèðîâàííîì ãðàôå íàçûâàåòñÿ
ãàìèëüòîíîâûì, åñëè îí ñîäåðæèò âñå âåðøèíû ãðàôà â òî÷íîñòè
ïî îäíîìó ðàçó. Ãðàô íàçûâàåòñÿ ãàìèëüòîíîâûì, åñëè â íåì
ñóùåñòâóåò ãàìèëüòîíîâ öèêë.
Çàäà÷à íàõîæäåíèÿ ãàìèëüòîíîâà öèêëà, ïîñòàâëåííàÿ àíãëèé-
ñêèì ìàòåìàòèêîì Ãàìèëüòîíîì, ïðè âñåì ñõîäñòâå åå ôîðìóëè-
ðîâêè ñ çàäà÷åé îá ýéëåðîâîì îáõîäå, îêàçûâàåòñÿ ãîðàçäî áîëåå
ñëîæíîé. Ïðîñòûå êðèòåðèè ñóùåñòâîâàíèÿ ãàìèëüòîíîâà öèêëà
íåèçâåñòíû. Â òî æå âðåìÿ èíòåðåñ ê åå ðåøåíèþ âåëèê, ïîñêîëüêó
îíà èìååò åñòåñòâåííóþ ïðèêëàäíóþ èíòåðïðåòàöèþ. Åñëè ðàññìàò-
ðèâàòü ãðàô êàê òðàíñïîðòíóþ ñåòü, âåðøèíû êîòîðîé ãîðîäà, à
ðåáðà ïóòè ìåæäó ãîðîäàìè, òî çàäà÷à î ãàìèëüòîíîâîì öèêëå
îêàçûâàåòñÿ ÷àñòíûì ñëó÷àåì èçâåñòíîé «çàäà÷è î êîììèâîÿæåðå»:
îáúåõàòü âñå ãîðîäà, ïîáûâàâ â êàæäîì ðîâíî îäèí ðàç è âåðíóòüñÿ
â èñõîäíûé ãîðîä. Áîëåå ñëîæíàÿ ïîñòàíîâêà ýòîé çàäà÷è ñâÿçàíà
ñî ñëó÷àåì, êîãäà ðàçíûå ïóòè èìåþò ðàçíóþ öåíó â ñòîèìîñòè
èëè äëèòåëüíîñòè; òîãäà òðåáóåòñÿ íàéòè îáõîä âñåõ ãîðîäîâ ñ
ìèíèìàëüíîé öåíîé.
8.6. Ïóòè è ñâÿçíîñòü â îðèåíòèðîâàííûõ ãðàôàõ
 îðèåíòèðîâàííûõ ãðàôàõ ðÿä ïîíÿòèé ñîâïàäàåò ñ àíàëîãè÷-
íûìè äëÿ íåîðèåíòèðîâàííûõ ãðàôîâ. Îäíàêî, â ëèòåðàòóðå ÷àñòî
îäíè è òå æå ïîíÿòèÿ èìåþò ðàçëè÷íûå íàçâàíèÿ.  îñíîâíîì ìû
áóäåì ïðèäåðæèâàòüñÿ îäèíàêîâîé òåðìèíîëîãèè êàê äëÿ îðèåíòè-
ðîâàííûõ, òàê è äëÿ íåîðèåíòèðîâàííûõ ãðàôîâ.
Îïðåäåëåíèå 8.17. Ïóòü P
i
â îðèåíòèðîâàííîì ãðàôå ýòî
ïîñëåäîâàòåëüíîñòü äóã (v
i0
, v
i1
), (v
i1
, v
i2
),..., (v
i n1
, v
in
), òàêàÿ, ÷òî
êîíåö ëþáîé äóãè ñîâïàäàåò ñ íà÷àëîì ñëåäóþùåé. Âåðøèíà
v
i0
íàçûâàåòñÿ íà÷àëîì ïóòè, âåðøèíà v
in
êîíöîì ïóòè.
Äðóãîå îáîçíà÷åíèå ïóòè ïîñëåäîâàòåëüíîñòü âåðøèí v
0
, v
1
,...,
v
n1
, v
n
, êîòîðûå ñîåäèíåíû äóãàìè â íàïðàâëåíèè ñòðåëîê. Â
äàëüíåéøåì ìû èìåííî òàê è áóäåì îáîçíà÷àòü ïóòü â îðãðàôå.
Ïîíÿòèÿ öèêëà, öåïè, ïðîñòîé öåïè, äëèíû ïóòè è öèêëà,
ãàìèëüòîíîâà öèêëà áåç èçìåíåíèÿ ïåðåíîñÿòñÿ íà îðãðàôû. (Öèêë
â îðãðàôå íàçûâàþò èíà÷å êîíòóðîì).
Íà ðèñ. 8.14èçîáðàæåíî íåñêîëüêî îðãðàôîâ. Â îðãðàôå D
7
u,v,
w ïðîñòàÿ öåïü, à u,v, y, x, v, w öåïü, íå ÿâëÿþùàÿñÿ ïðîñòîé,
ïîñêîëüêó âåðøèíà v âñòðå÷àåòñÿ â íåé äâàæäû. Ïóòü u,v, y, x, u
ÿâëÿåòñÿ ïðîñòûì öèêëîì, íî íå ÿâëÿåòñÿ ãàìèëüòîíîâûì (ïîëíûì)
öèêëîì. Ïóòü u, v, w, x, u â ãðàôå D
4
ÿâëÿåòñÿ öèêëîì; îí ÿâëÿåòñÿ
òàêæå ïðîñòûì, ãàìèëüòîíîâûì è ýéëåðîâûì öèêëîì. Â ãðàôå
D
6
ïóòü u, v, u ÿâëÿåòñÿ öèêëîì, íî íå ÿâëÿåòñÿ ïîëíûì öèêëîì,
òàê êàê îí ñîäåðæèò íå âñå âåðøèíû ãðàôà.
Ðèñ. 8.14. Ïðèìåðû îðãðàôîâ.
Äðóãèå ïîíÿòèÿ, è, ïðåæäå âñåãî, ñâÿçíîñòü è äîñòèæèìîñòü,
ñóùåñòâåííî èçìåíÿþòñÿ äëÿ îðãðàôîâ.
Îïðåäåëåíèå 8.18. Âåðøèíà v
j
äîñòèæèìà èç âåðøèíû v
i
, åñëè
ñóùåñòâóåò ïóòü ñ íà÷àëîì â v
i
è êîíöîì â v
j
. Ïî îïðåäåëåíèþ
ïîëàãàåì, ÷òî ëþáàÿ âåðøèíà äîñòèæèìà èç ñåáÿ ñàìîé.
Ðèñ. 8.12. Ýéëåðîâ ãðàô. Ðèñ. 8.13. Ñàáëè Ìàãîìåòà.
124 125
Äëÿ îðãðàôîâ âåðíî óòâåðæäåíèå, àíàëîãè÷íîå òåîðåìå 8.1.
Òåîðåìà 8.1′. Åñëè âåðøèíà v
j
äîñòèæèìà èç âåðøèíû v
i
, òî
ñóùåñòâóåò ïðîñòîé ïóòü èç v
i
â v
j
.
Äëÿ ñåòåé êîììóíèêàöèé òåîðåìà 8.1′ èìååò ñëåäóþùóþ ïðîç-
ðà÷íóþ èíòåðïðåòàöèþ: åñëè íåêîòîðîå ëèöî èìååò âîçìîæíîñòü
îòïðàâèòü ñîîáùåíèå äðóãîìó ëèöó ÷åðåç öåïî÷êó ïîñðåäíèêîâ,
òî ñìîæåò ýòî ñäåëàòü òàê, ÷òî íè îäèí ïîñðåäíèê íå ïåðåäàñò ýòî
ñîîáùåíèå äâàæäû.
Îïðåäåëåíèå 8.19. Ïîëóïóòü â îðèåíòèðîâàííîì ãðàôå ýòî ïî-
ñëåäîâàòåëüíîñòü äóã, òàêàÿ, ÷òî ëþáûå äâå ñîñåäíèå äóãè ðàçëè÷íû
è èìåþò îáùóþ èíöèäåíòíóþ èì âåðøèíó. Èíà÷å ãîâîðÿ, ïîëó-
ïóòü ýòî ïóòü, êîòîðûé ïðîõîäèòñÿ áåç ó÷åòà îðèåíòàöèè äóã.
Ãîâîðÿò, ÷òî âåðøèíû u è v â îðãðàôå ñîåäèíèìû, åñëè v ìîæíî
äîñòè÷ü èç u, íå îáÿçàòåëüíî ñëåäóÿ ïî äóãàì â íàïðàâëåíèè èõ
îðèåíòàöèè, ò.å., åñëè ìåæäó íèìè ñóùåñòâóåò ïîëóïóòü.
Îòíîøåíèå äîñòèæèìîñòè ìåæäó âåðøèíàìè â îðãðàôàõ íå-
ñèììåòðè÷íî: åñëè v
j
äîñòèæèìà èç v
i
, òî v
i
íå îáÿçàòåëüíî äîñòè-
æèìà èç v
j
. Îäíàêî ïîëóïóòü èç v
j
â v
i
â ýòîì ñëó÷àå ñóùåñòâóåò
âñåãäà. Âîçìîæåí ñëó÷àé, êîãäà ìåæäó âåðøèíàìè íåò ïóòè íè â
îäíó, íè â äðóãóþ ñòîðîíó, íî åñòü ïîëóïóòü. Íàïðèìåð, íà
ðèñ.8.14â ãðàôå D
3
íå ñóùåñòâóåò ïóòè èç âåðøèíû u â âåðøèíó
x, îäíàêî ñóùåñòâóåò ïîëóïóòü u, v, w, x.
 ñâÿçè ñ íåñèììåòðè÷íîñòüþ îòíîøåíèÿ äîñòèæèìîñòè, ðàñ-
ñòîÿíèå ìåæäó äâóìÿ âåðøèíàìè îðãðàôà d (u, v) íå óäîâëåòâîðÿåò
âñåì àêñèîìàì ìåòðèêè (ñì. îïðåäåëåíèå 8.13).  ÷àñòíîñòè, îíî
íå îáÿçàòåëüíî ñèììåòðè÷íî: â îáùåì ñëó÷àå d (u,v)≠d (v,u). Â
êà÷åñòâå ïðèìåðà ðàññìîòðèì îðãðàô D
7
íà ðèñ.8.14: d (x,v)=1,
d (v,x)=2. Ïðè îòñóòñòâèè ïóòè ìåæäó äâóìÿ âåðøèíàìè
ðàññòîÿíèå ñ÷èòàåòñÿ ëèáî íåîïðåäåëåííûì, ëèáî áåñêîíå÷íûì.
Íàïðèìåð, â ãðàôå D
7
ðàññòîÿíèå d (w,u)íå îïðåäåëåíî. (Èíîãäà
â òàêèõ ñëó÷àÿõ ðàññòîÿíèå ìåæäó äâóìÿ âåðøèíàìè â îðãðàôàõ
îïðåäåëÿåòñÿ êàê äëèíà ïîëóïóòè ìåæäó íèìè.)
Íåðàâåíñòâî òðåóãîëüíèêà èìååò ìåñòî â òîì ñëó÷àå, åñëè
âåðøèíà v äîñòèæèìà èç u è w äîñòèæèìà èç v. Äåéñòâèòåëüíî,
ïóñòü d (u,v)=s, d (v,w)=t è u, u
2
, u
3
,..., u
s
, v êðàò÷àéøèé ïóòü
èç u â v, à v, v
2
, v
3
,..., v
t
, w êðàò÷àéøèé ïóòü èç v â w. Òîãäà u, u
2
,
u
3
,...,u
t
, w ïóòü äëèíû s+t èç u â w, è ìû çàêëþ÷àåì, ÷òî
d(u,v)≤d(u,v)+d(v,w).
8.6.1. Âèäû ñâÿçíîñòè îðãðàôîâ
 îðãðàôàõ ñóùåñòâóþò ðàçëè÷íûå âèäû ñâÿçíîñòè, êîòîðûå
îïèñûâàþòñÿ ñëåäóþùèì îïðåäåëåíèåì.
Îïðåäåëåíèå 8.20.
1.Îðãðàô D=(V,E) íàçûâàåòñÿ ñèëüíî ñâÿçíûì, èëè ñèëüíûì,
åñëè ëþáûå äâå åãî âåðøèíû äîñòèæèìû äðóã èç äðóãà (ò.å.åñëè
ìåæäó íèìè ñóùåñòâóþò ïóòè â îáå ñòîðîíû).
Íàïðèìåð, îðãðàôû D
4
, D
5
íà ðèñ. 8.14ñèëüíî ñâÿçíû, òîãäà
êàê äðóãèå îðãðàôû íåò. Íàïðèìåð, â îðãðàôå D
9
âåðøèíû x, y, z
íå äîñòèæèìû èç âåðøèí u, v, w.
Åñëè ñåòü êîììóíèêàöèé ñèëüíî ñâÿçíà, òî êàæäîå ëèöî ìîæåò
ïåðåäàòü ñîîáùåíèå ëþáîìó äðóãîìó ëèöó.
2.Îðãðàô íàçûâàåòñÿ îäíîñòîðîííå ñâÿçíûì, èëè îäíîñòî-
ðîííèì, åñëè äëÿ ëþáîé ïàðû âåðøèí õîòÿ áû îäíà äîñòèæèìà
èç äðóãîé, ò.å.åñëè ñóùåñòâóåò ïóòü ìåæäó íèìè õîòÿ áû â
îäíó ñòîðîíó.
Íàïðèìåð, îðãðàôû D
1,
D
2
, D
9
íà ðèñ. 8.14îäíîñòîðîííå ñâÿçíû.
Îðãðàô D
3
íå îäíîñòîðîííèé, òàê êàê âåðøèíû u è x íåäîñòèæè-
ìû äðóã äëÿ äðóãà.
Ñåòü êîììóíèêàöèé ÿâëÿåòñÿ îäíîñòîðîííå ñâÿçíîé, åñëè äëÿ
êàæäîé ïàðû åå ÷ëåíîâ ïî êðàéíåé ìåðå îäèí ìîæåò ïîñëàòü
ñîîáùåíèå äðóãîìó.
3.Îðãðàô íàçûâàåòñÿ ñëàáî ñâÿçíûì, èëè ñëàáûì, åñëè êàæäàÿ
ïàðà âåðøèí ñîåäèíèìà, ò.å., åñëè ìåæäó ëþáîé ïàðîé âåðøèí
ñóùåñòâóåò ïîëóïóòü. Íàïðèìåð, îðãðàô D
3
íà ðèñ. 8.14ñëàáî
ñâÿçåí, òîãäà êàê îðãðàô D
8
íåò, òàê êàê âåðøèíû u è x íå
ñîåäèíèìû.
4.Îðãðàô íàçûâàåòñÿ íåñâÿçíûì, åñëè ìåæäó íåêîòîðîé ïàðîé
âåðøèí íåò ïîëóïóòè (ò.å.åñëè îí íå ÿâëÿåòñÿ ñëàáî ñâÿçíûì).
Ïðèìåðû íåñâÿçíûõ ãðàôîâ íà ðèñ. 8.14: D
8
, D
10
, D
11
.
Îòìåòèì, ÷òî ýòè ÷åòûðå ñâîéñòâà óïîðÿäî÷åíû ïî âêëþ÷åíèþ:
ãðàô, îáëàäàþùèé îäíèì èç ýòèõ ñâîéñòâ, îáëàäàåò âñåìè ñâîé-
ñòâàìè, êîòîðûå â ýòîì îïðåäåëåíèè «íèæå» íåãî. Òàê, ñèëüíî ñâÿç-
íûé ãðàô îáëàäàåò ñâîéñòâàìè 2 4èò.ä.
8.6.2. Êðèòåðèè ñâÿçíîñòè
Ïðîâåðêà ñèëüíîé, ñëàáîé èëè îäíîñòîðîííåé ñâÿçíîñòè ïóòåì
íåïîñðåäñòâåííîãî èñïîëüçîâàíèÿ îïðåäåëåíèé ìîæåò îêàçàòüñÿ
î÷åíü òðóäîåìêîé, ïîñêîëüêó â îðãðàôå ñ n âåðøèíàìè èìååòñÿ
n(n1)/2ïàð âåðøèí. Â ýòîì ïàðàãðàôå áóäóò ïðèâåäåíû
êðèòåðèè ïðèíàäëåæíîñòè ê êàæäîìó èç òðåõ êëàññîâ îðãðàôîâ:
ñèëüíûõ, îäíîñòîðîííèõ è ñëàáûõ.
 ñèëüíî ñâÿçíîì ãðàôå ëþáàÿ âåðøèíà v
i
âõîäèò ïî êðàéíåé
ìåðå â îäèí öèêë, îáðàçîâàííûé ïóòÿìè èç v
i
â íåêîòîðóþ äðóãóþ
Ãëàâà 8 Ãðàôû
126 127
âåðøèíó v
j
è îáðàòíî èç v
j
â v
i
. Öèêëû, ïðîõîäÿùèå ÷åðåç v
i
è äðóãèå
âåðøèíû ãðàôà, íå îáÿçàòåëüíî âñå ðàçëè÷íû.  ÷àñòíîñòè, ñèëüíî
ñâÿçíûé ãðàô, ñîäåðæàùèé n âåðøèí, ìîæåò ïðåäñòàâëÿòü ñîáîé
îäèí ïðîñòîé öèêë, ïðîõîäÿùèé ÷åðåç âñå âåðøèíû.
Òåîðåìà 8.4. Îðãðàô ñèëüíî ñâÿçåí òîãäà è òîëüêî òîãäà, êîãäà
â íåì èìååòñÿ ïîëíûé öèêë, ò.å.öèêë, ïðîõîäÿùèé ÷åðåç âñå
âåðøèíû.
Äîêàçàòåëüñòâî. Ïóñòü u
1
, u
2
,..., u
t
, u
1
ïîëíûé öèêë. Òîãäà
ëþáàÿ ïàðà âåðøèí u
i
, u
j
â íåì ñîäåðæèòñÿ. Áóäåì ñ÷èòàòü, ÷òî
i<j. Òîãäà u
i
, u
i+1
,..., u
j
- ïóòü èç u
i
â u
j
, à u
j
, u
j+1
,..., u
t
, u
1
,..., u
i
- ïóòü
èç u
j
â u
i
. Òàêèì îáðàçîì, îðãðàô D ñèëüíî ñâÿçåí.
Îáðàòíî, ïðåäïîëîæèì, ÷òî D ñèëüíî ñâÿçåí. Ïóñòü âåðøèíàìè
â D ÿâëÿþòñÿ u
1
, u
2
,..., u
n
. Òîãäà èìåþòñÿ ïóòè P
1
èç u
1
â u
2
, P
2
èç u
2
â
u
3
,..., P
n1
èç u
n1
â u
n
, P
n
èç u
n
â u
1
. Ïîëíûé öèêë â D ìîæíî ïîñòðîèòü
îáúåäèíåíèåì ýòèõ ïóòåé â ñëåäóþùåì ïîðÿäêå: P
1
, P
2
,..., P
n1
, P
n
.
Äëÿ èëëþñòðàöèè ýòîé òåîðåìû ðàññìîò-
ðèì îðãðàô D íà ðèñ.8.15. Îí ñèëüíî ñâÿçåí,
ïîòîìó ÷òî ïîñëåäîâàòåëüíîñòü v, y, z, u, v, w, x,
v îáðàçóåò ïîëíûé öèêë. ×òîáû èñïîëüçîâàòü
òåîðåìó8.4äëÿ ïðîâåðêè ñèëüíîé ñâÿçíîñòè
îðãðàôà D, ïåðåíóìåðóåì âåðøèíû u
1
, u
2
,..., u
n
.
Çàòåì ïðîâåðèì, ñóùåñòâóåò ëè ïóòü èç u
1
â u
2
,
èç u
2
â u
3
,..., èç u
n1
â u
n
è èç u
n
â u
1
.
 òåðìèíàõ ñåòåé êîììóíèêàöèé òåîðå-
ìà8.4óòâåðæäàåò, ÷òî äëÿ òîãî, ÷òîáû êàæäîå
ëèöî ìîãëî îòïðàâèòü ñîîáùåíèå ëþáîìó äðóãîìó ëèöó, íåîáõîäèìî
(è äîñòàòî÷íî) íàëè÷èå ïîñëåäîâàòåëüíîñòè ëèö ñî ñëåäóþùèìè
ñâîéñòâàìè: 1) êàæäîå èç íèõ ìîæåò ñâÿçàòüñÿ ñî ñëåäóþùèì; 2) â
ïîñëåäîâàòåëüíîñòè ïðåäñòàâëåíû âñå ó÷àñòíèêè ñåòè; 3) ïîñëåäíåå
ëèöî ìîæåò ñâÿçàòüñÿ ñ ïåðâûì.
Òåîðåìà 8.5. Îðãðàô D îäíîñòîðîííå ñâÿçåí òîãäà è òîëüêî
òîãäà, êîãäà â íåì èìååòñÿ ïîëíûé ïóòü.
 êà÷åñòâå èëëþñòðàöèè ýòîé òåîðåìû çàìåòèì, ÷òî îðãðàô D
7
íà
ðèñ. 8.14îäíîñòîðîííå ñâÿçíûé, ïîòîìó ÷òî â íåì èìååòñÿ ïîëíûé
ïóòü x, u, v, y, z, w. Ãðàô D
2
òàêæå îäíîñòîðîííå ñâÿçíûé.
Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà òåîðåìû ïðåäïîëîæèì, ÷òî
u
1
, u
2
,..., u
t
ïîëíûé ïóòü. Òîãäà ëþáûå âåðøèíû u
i
, u
j
â íåì
ñîäåðæàòñÿ. Åñëè i<j, òî u
i
, u
i+1
,..., u
j
ïóòü èç u
i
â u
j
. Òàêèì îáðàçîì,
D îäíîñòîðîííèé îðãðàô.
Îáðàòíî, ïðåäïîëîæèì, ÷òî D îäíîñòîðîííèé îðãðàô. Ñíà÷àëà
äîêàæåì ïðåäâàðèòåëüíûé ðåçóëüòàò.
Ãëàâà 8 Ãðàôû
Ëåììà 8.1. Â ëþáîì ïîäìíîæåñòâå âåðøèí îäíîñòîðîííåãî
ãðàôà D ñóùåñòâóåò âåðøèíà, èç êîòîðîé äîñòèæèìû (ïóòåì
èñïîëüçîâàíèÿ äóã D) âñå äðóãèå âåðøèíû â ýòîì ìíîæåñòâå.
Îðãðàô D
9
íà ðèñ.8.14èëëþñòðèðóåò ëåììó. Îí ÿâëÿåòñÿ îäíî-
ñòîðîííå ñâÿçíûì. Âî ìíîæåñòâå {u, v, x} èç âåðøèíû u äîñòèæèìû
âñå äðóãèå. Â ìíîæåñòâå {x, y} òàêèì ñâîéñòâîì îáëàäàåò âåðøèíà
x, à â ìíîæåñòâå {u, v, w, x, y, z} - âåðøèíà u èò.ä.
Äîêàçàòåëüñòâî ëåììû ïðîâåäåì èíäóêöèåé ïî ÷èñëó âåðøèí
k â ïðîèçâîëüíîì ìíîæåñòâå U.Ïðè k=1ëåììà âåðíà, òàê êàê
êàæäàÿ âåðøèíà äîñòèæèìà ñàìà èç ñåáÿ. Ïðåäïîëîæèì, ÷òî îíà
âåðíà äëÿ âñåõ ìíîæåñòâ ñ k âåðøèíàìè, è âûáåðåì íåêîòîðîå
ìíîæåñòâî U, ñîäåðæàùåå k+1âåðøèíó. Îáîçíà÷èì ýëåìåíòû U
÷åðåç v
1
, v
2
,..., v
k+1
. Ïî ïðåäïîëîæåíèþ èíäóêöèè â U\{v
k+1
}
ñóùåñòâóåò âåðøèíà v
i
, èç êîòîðîé äîñòèæèìû âñå v
j
ïðè j<k+1.
Òåïåðü, ïîñêîëüêó îðãðàô D îäíîñòîðîííèé, ëèáî v
i
äîñòèæèìà èç
v
k+1
, ëèáî v
k+1
äîñòèæèìà èç v
i
. Åñëè v
k+1
äîñòèæèìà èç v
i
, òî èç v
i
äîñòèæèìû âñå âåðøèíû â U.Åñëè v
i
äîñòèæèìà èç v
k+1
, òî èç
v
k+1
äîñòèæèìû âñå âåðøèíû â U.Ýòî äîêàçûâàåò ëåììó.
Òåïåðü, èñïîëüçóÿ ëåììó, ïðîäîëæèì äîêàçàòåëüñòâî òåîðåìû.
Âûáåðåì â ìíîæåñòâå âåðøèí V îðãðàôà D âåðøèíó u
1
, èç êîòîðîé
äîñòèæèìû âñå äðóãèå âåðøèíû â V.Âûáåðåì â V\{u
1
} âåðøèíó u
2
,
èç êîòîðîé äîñòèæèìû âñå äðóãèå âåðøèíû â V\{u
1
}. Âûáåðåì â
V\{u
1
, u
2
} âåðøèíó u
3
, èç êîòîðîé äîñòèæèìû âñå äðóãèå âåðøèíû
â V\{u
1
, u
2
}, èò.ä. Äàëåå, u
2
äîñòèæèìà èç u
1
ïî ïóòè P
1
, u
3
äîñòèæèìà
èç u
2
ïî ïóòè P
2
èò.ä. Îáúåäèíåíèå ýòèõ ïóòåé äàåò ïîëíûé ïóòü
îðãðàôàD.
Îðãðàô D
7
íà ðèñ. 8.14èëëþñòðèðóåò äîêàçàòåëüñòâî òåîðå-
ìû8.4. Âîçüìåì u
1
=y, u
2
=x, u
3
=u, u
4
=v, u
5
=z, u
6
=w. Òîãäà
P
1
={y,x}, P
2
={x, u}, P
3
={u,v}, P
4
={v,y,z}, P
5
={z,w}. Ïîëíûé
ïóòü çàäàåòñÿ âåðøèíàìè y, x, u, v, y, z, w. (Â ýòîì îðãðàôå ñóùåñòâóåò
äàæå ïîëíûé ïðîñòîé ïóòü. Èìååòñÿ ëè òàêîé ïóòü äëÿ êàæäîãî
îäíîñòîðîííåãî îðãðàôà?)
Òåîðåìà 8.6. Îðãðàô D ñëàáî ñâÿçåí òîãäà è òîëüêî òîãäà, êîãäà
â íåì èìååòñÿ ïîëíûé ïîëóïóòü.
Äîêàçàòü ñàìîñòîÿòåëüíî.
Äëÿ èëëþñòðàöèè ýòîé òåîðåìû çàìåòèì, ÷òî îðãðàô D
3
íà
ðèñ.8.14 ñëàáî ñâÿçíûé, ïîñêîëüêó ïîñëåäîâàòåëüíîñòü âåðøèí
u, v, w, x îáðàçóåò ïîëíûé ïîëóïóòü. Ïðè ýòîì îí íå ÿâëÿåòñÿ îäíî-
ñòîðîííèì, òàê êàê â íåì íå ñóùåñòâóåò ïîëíîãî ïóòè. Ãðàô
D
9
ÿâëÿåòñÿ ñëàáî ñâÿçíûì è îäíîñòîðîííèì.
Ðèñ. 8.15. Ïðèìåð
êòåîðåìå 8.4.
128 129Ãëàâà 8 Ãðàôû
8.7. Èññëåäîâàíèå îðãðàôîâ ñ ïîìîùüþ ìàòðèö
Çíà÷èòåëüíóþ ÷àñòü èíôîðìàöèè îòíîñèòåëüíî îðãðàôà D ìîæ-
íî ïðåäñòàâèòü â óäîáíîé ôîðìå, èñïîëüçóÿ ìàòðèöû, ñîîòâåòñòâó-
þùèå îðãðàôó D.Îïðåäåëèì ñëåäóþùèå îïåðàöèè íàä ìàòðèöàìè.
Ïóñòü A=(a
ij
) è B=(b
ij
) äâå ìàòðèöû n × n. Òîãäà
A + B=(a
ij
+ b
ij
) ïîýëåìåíòíîå ñëîæåíèå ìàòðèö A, B,
A × B=(a
ij
× b
ij
) ïîýëåìåíòíîå ïðîèçâåäåíèå A è B,
AB=(c
ij
), ãäå
1
ij ik kj
n
cab
k
=
=
∑
, ïðîèçâåäåíèå A èB.
Òðàíñïîíèðîâàííîé ìàòðèöåé A′ ê ìàòðèöå A ÿâëÿåòñÿ ìàòðèöà
(a′
ij
), â êîòîðîé a′
ij
=a
ji
.
Îïðåäåëèì áóëåâî ïðåîáðàçîâàíèå B: N → {0,1} ñëåäóþùèì
îáðàçîì:
0, åñëè 0,
()
1, åñëè 0.
x
Bx
x
=
=
>
Òîãäà ïðåîáðàçîâàíèå Â (À) äëÿ ìàòðèöû À=(a
ij
) îçíà÷àåò, ÷òî
ýëåìåíò (i, j) â B (A) ðàâåí B (a
ij
). Íàïðèìåð:
185 111
020 010
110 110
B
=
.
 ðåçóëüòàòå ïîëó÷àåì áèíàðíóþ ìàòðèöó.
Áóäåì îáîçíà÷àòü ÷åðåç I äèàãîíàëüíóþ åäèíè÷íóþ ìàòðèöó
(ìàòðèöó, â êîòîðîé íà ãëàâíîé äèàãîíàëè ñòîÿò åäèíèöû, à âñå
îñòàëüíûå ýëåìåíòû ðàâíû íóëþ), è ÷åðåç J åäèíè÷íóþ ìàòðèöó,
â êîòîðîé âñå ýëåìåíòû ðàâíû åäèíèöå.
8.7.1. Ìàòðèöû îðãðàôîâ è èõ ñâÿçü ñ ïóòÿìè
Ìàòðèöó ñìåæíîñòè A (D) îðãðàôà D ìîæíî èñïîëüçîâàòü äëÿ
ïîäñ÷åòà ÷èñëà ðàçëè÷íûõ ïóòåé â D.Ñàìà ìàòðèöà A çàäàåò äóãè
D, ò.å.ïóòè äëèíû 1. Îêàçûâàåòñÿ, ÷òî ìàòðèöà A
l
(l-ÿ ñòåïåíü A)
çàäàåò ÷èñëî ïóòåé äëèíû l.
Òåîðåìà 8.7. Ýëåìåíò (i, j)=
()
l
ij
c
ìàòðèöû A
l
îðãðàôà D ðàâåí
÷èñëó ïóòåé äëèíû l èç v
i
â v
j
.
Äîêàçàòåëüñòâî òåîðåìû ïðîâåäåì èíäóêöèåé ïî l. Äëÿ
l=1òåîðåìà î÷åâèäíà: ìàòðèöà ñìåæíîñòè çàäàåò ïóòè äëèíîé 1.
Ïóñòü äëÿ íåêîòîðîãî l òåîðåìà âåðíà, ò.å.ýëåìåíò
()
l
ij
c
ìàòðèöû
A
l
ðàâåí ÷èñëó ïóòåé äëèíû l èç v
i
â v
j
. Äîêàæåì åå äëÿ l+1. Ëþáîé
ïóòü äëèíû l+1èç v
i
â v
j
ñîñòîèò èç äóãè, âåäóùåé èç v
i
â ñìåæíóþ
ñ íåé âåðøèíó v
k
, è çàòåì ïóòè äëèíû l èç v
k
â v
j
. ×èñëî ïóòåé
äëèíû l+1èç v
i
â v
j
, ïðîõîäÿùèõ íà ïåðâîì øàãå ÷åðåç âåðøèíó
v
k
, ðàâíî a
ik
()
l
kj
c
(åñëè äóãè èç v
i
â v
k
íåò, òî a
ik
= 0, è a
ik
()
l
kj
c
=0,
à åñëè òàêàÿ äóãà åñòü, òî a
ik
()
l
kj
c
=
()
l
kj
c
, òàê êàê a
ik
=1). Îáùåå
÷èñëî ïóòåé äëèíû l+1èç v
i
â v
j
ïîëó÷èì, åñëè ïðîñóììèðóåì ýòó
âåëè÷èíó ïî âñåì k:
()
1
n
l
ik k
j
k
cc
=
∑
. Ýòà ñóììà ðàâíà ýëåìåíòó (i, j)
ïðîèçâåäåíèÿ ìàòðèö A è A
l
, ò.å.ýëåìåíòó (i,j) ìàòðèöû A
l+1
, ÷òî
è äîêàçûâàåò òåîðåìó.
Ñëåäñòâèå. Ýëåìåíò (i, j) ìàòðèöû A+A
2
+...+ A
l
îðãðàôà D
ðàâåí ÷èñëó âñåõ ïóòåé äëèíû ≤ l èç v
i
â v
j
.
Ïðèìåð. Íà ðèñ. 8.16ïðèâåäåíû ìàòðèöû ñìåæíîñòè A, A
2
, A
3
è
A
4
, ñîîòâåòñòâóþùèå îðãðàôó D.Ìàòðèöà A
2
ïîêàçûâàåò ÷èñëî
ïóòåé äëèíû äâà: ïîñêîëüêó ýëåìåíò a
11
â A
2
ðàâåí 1, â D ñóùåñòâóåò
ïóòü äëèíû 2èç u
1
â u
1
. Äåéñòâèòåëüíî, ýòî öèêë u
1
, u
2
, u
1
. Ýëåìåíò
a
13
= 1, ò.å.â D ñóùåñòâóåò ïóòü äëèíû 2èç u
1
â u
3
: u
1
, u
2
, u
3
, èò.ä.
Ýëåìåíò a
21
= 2â A
3
, ñëåäîâàòåëüíî, ñóùåñòâóåò äâà ïóòè äëèíû3
èçu
2
â u
1
. Ýòè ïóòè u
2
, u
1
, u
2
, u
1
è u
2
, u
3
, u
4
, u
1
. Àíàëîãè÷íî
èíòåðïðåòèðóþòñÿ äðóãèå ýëåìåíòû ìàòðèö A
2
, A
3
, A
4
èò.ä.
Íåòðóäíî çàìåòèòü, ÷òî åñëè â ãðàôå íåò öèêëîâ, ìàòðèöà A
n
ñòàíåò íóëåâîé ÷åðåç îïðåäåëåííîå (êàêîå?) ÷èñëî øàãîâ.
Ðèñ. 8.16. Ñòåïåíè ìàòðèöû ñìåæíîñòè îðãðàôàD.
8.7.2. Ìàòðèöà ðàññòîÿíèé
Íîâàÿ ìàòðèöà, êîòîðàÿ îêàçûâàåòñÿ ïîëåçíîé ïðè ðàññìîòðå-
íèè îðãðàôîâ, ìàòðèöà ðàññòîÿíèé (d
ij
), ãäå d
ij
ðàññòîÿíèå îò u
i
1234
1 0100
2 1010
3 0001
4 1000
A
=
2
1234
1 1010
2 0101
3 1000
4 0100
A
=
3
1234
1 0101
2 2010
3 0100
4 1010
A
=
4
1234
12010
20201
31010
40101
A
=
130 131Ãëàâà 8 Ãðàôû
äî u
j
, îïðåäåëÿåìîå êàê äëèíà êðàò÷àéøåãî ïóòè èç u
i
â u
j
. (Íàïîì-
íèì, ÷òî âåëè÷èíà d
ij
íå îïðåäåëåíà, åñëè ïóòè èç u
i
â u
j
íåò.)
Òåîðåìà 8.8. Ïóñòü îðãðàô D èìååò ìàòðèöó ñìåæíîñòè À è
ìàòðèöó ðàññòîÿíèé (d
ij
). Òîãäà, åñëè âåëè÷èíà d
ij
, i≠j îïðå-
äåëåíà, òî îíà ðàâíà íàèìåíüøåìó k, äëÿ êîòîðîãî ýëåìåíò (i,j)
â A
k
íå ðàâåí 0.
Äîêàçàòü òåîðåìó ïðåäîñòàâëÿåòñÿ ÷èòàòåëþ ñàìîñòîÿòåëüíî.
Ñëåäóÿ ýòîé òåîðåìå, ìîæíî ïîñòðîèòü ìàòðèöó ðàññòîÿíèé,
ïîñëåäîâàòåëüíî âîçâîäÿ â ñòåïåíü ìàòðèöó ñìåæíîñòè îðãðàôà.
Íà ðèñ. 8.16ïðèâåäåíû ñòåïåíè ìàòðèöû ñìåæíîñòè îðãðàôà
D.Èñïîëüçóåì èõ äëÿ ïîëó÷åíèÿ ìàòðèöû ðàññòîÿíèé ýòîãî ãðàôà
(ñì. ðèñ. 8.17).
1. Ìàòðèöà ðàññòîÿíèé èìååò íóëè íà ãëàâíîé äèàãîíàëè è âíà-
÷àëå ñîâïàäàåò ñ ìàòðèöåé ñìåæíîñòè, ò.å.îíà ñîäåðæèò âñå ïóòè
äëèíû 1. Îñòàëüíûå ýëåìåíòû ìàòðèöû ðàññòîÿíèé ïîêà íå
îïðåäåëåíû.
2. Ìàòðèöà A
2
óêàçûâàåò âñå ïóòè äëèíû 2. Íåîïðåäåëåííûì
ýëåìåíòàì ìàòðèöû ðàññòîÿíèé d
ik
ïðèñâàèâàåì çíà÷åíèå 2, åñëè
a
ik
(2)
≠0.
3. Òåì ýëåìåíòàì d
ik
, êîòîðûå åùå íå îïðåäåëåíû, ïðèñâàèâàåì
çíà÷åíèå 3, åñëè ýëåìåíòû A
3
a
ik
(3)
≠ 0.
Òåïåðü ìàòðèöà ðàññòîÿíèé ïîëíîñòüþ îïðåäåëåíà.
1).d(D)=
01
101
01
10
xx
x
xx
xx
2).d(D)=
012
1012
201
12 0
x
x
x
3).d(D)=
0123
1012
2301
1230
Ðèñ. 8.17. Âû÷èñëåíèå ìàòðèöû ðàññòîÿíèé îðãðàôàD.
Òåîðåìà 8.9. Äëÿ òîãî, ÷òîáû n-âåðøèííûé îðãðàô ñ ìàòðèöåé
ñìåæíîñòè A èìåë õîòÿ áû îäèí öèêë, íåîáõîäèìî è äîñòàòî÷íî,
÷òîáû ìàòðèöà K=A
2
+ A
3
+...+ A
n
èìåëà õîòÿ áû îäèí íå
íóëåâîé äèàãîíàëüíûé ýëåìåíò.
Èñïîëüçîâàíèå ìàòðèö ïîçâîëÿåò ïîëó÷èòü è ïåðå÷èñëåíèå êîí-
êðåòíûõ ïóòåé. Äëÿ ýòîãî âñåì äóãàì ãðàôà D ïðèñâîèì êîíêðåòíûå
èìåíà (íàïðèìåð, e
1
,..., e
m
), è â ìàòðèöå A çàìåíèì åäèíèöû èìåíàìè
ñîîòâåòñòâóþùèõ äóã, ò.å.ýëåìåíò a
ij
=1çàìåíèì èìåíåì äóãè,
êîòîðàÿ ñîåäèíÿåò âåðøèíó v
i
ñ âåðøèíîé
v
j
. Ïîëó÷åííóþ ìàòðèöó
îáîçíà÷èì ÷åðåç H (D). Äëÿ òîãî, ÷òîáû îïðåäåëèòü ïðîèçâåäåíèå
ìàòðèö ýòîãî âèäà, ââåäåì àëãåáðó íà ìíîæåñòâàõ ïóòåé.
Ïóòü áóäåì ðàññìàòðèâàòü êàê ñëîâî (ïîñëåäîâàòåëüíîñòü ñèì-
âîëîâ) â àëôàâèòå {e
1
,..., e
m
}. Ïóñòü äàíû äâà ìíîæåñòâà ïóòåé M
1
è
M
2
. Ñóììà M
1
è M
2
îïðåäåëÿåòñÿ êàê èõ îáû÷íîå òåîðåòèêî-
ìíîæåñòâåííîå îáúåäèíåíèå: M
1
∪M
2
, ïðîèçâåäåíèå M
1
⋅M
2
êàê
ìíîæåñòâî, ïîëó÷àåìîå ïðèïèñûâàíèåì ñïðàâà ê êàæäîìó ñëîâó
èç M
1
âñåõ ñëîâ èç M
2
. Íàïðèìåð, åñëè M
1
={e
2
e
4
e
2
, e
3
e
1
, e
1
},
M
2
={e
3
e
1
e
4
, e
2
}, òî M
1
⋅M
2
= {e
2
e
4
e
2
e
3
e
1
e
4
, e
2
e
4
e
2
e
2
, e
3
e
1
e
3
e
1
e
4
,
e
3
e
1
e
2
, e
1
e
3
e
1
e
4
,
e
1
e
2
}. (Òàêóþ îïåðàöèþ íàçûâàþò êîíêàòåíàöèåé.) Ïóñòîå ìíîæå-
ñòâî ∅ èãðàåò çäåñü ðîëü íóëÿ: M
1
⋅∅ = ∅⋅M
2
= ∅. Ïîýòîìó âìåñòî
∅ áóäåì, êàê è â ìàòðèöå A, ïèñàòü 0. Î÷åâèäíî, ÷òî îïåðàöèÿ
êîíêàòåíàöèè íåêîììóòàòèâíà. Îíà èìååò ïðîñòîé ñìûñë: åñëè M
1
ìíîæåñòâî âñåõ ïóòåé, âåäóùèõ èç v
i
â v
j
, à M
2
ìíîæåñòâî âñåõ
ïóòåé, âåäóùèõ èç v
j
â v
k
, òî M
1
⋅M
2
ýòî ìíîæåñòâî âñåõ ïóòåé,
âåäóùèõ èç v
i
â v
k
è ïðîõîäÿùèõ ÷åðåç v
j
.
Ñ ïîìîùüþ ýòèõ îïåðàöèé îïðåäåëèì ïðîèçâåäåíèå Z=X⋅Y êâàä-
ðàòíûõ ìàòðèö X è Y îäèíàêîâîé ðàçìåðíîñòè n, ýëåìåíòàìè êîòîðûõ
ÿâëÿþòñÿ ìíîæåñòâà ñëîâ (òàêèå ìàòðèöû íàçîâåì ñëîâàðíûìè):
z
ij
=
1
n
ik k
j
k
x
y
=
⋅
U
.
 ýòîé ôîðìóëå ðîëü ñóììû ýëåìåíòîâ èãðàåò òåîðåòèêî-
ìíîæåñòâåííîå îáúåäèíåíèå, à ïðîèçâåäåíèÿ îïðåäåëåííàÿ âûøå
êîíêàòåíàöèÿ. Ñòåïåíü ìàòðèöû H îïðåäåëÿåòñÿ ïî èíäóêöèè
ôîðìóëîé H
l+1
= H⋅H
l
.
Òåîðåìà 8.10. Ýëåìåíò (i, j) =
()
l
ij
h
ìàòðèöû H
l
îðãðàôà D
ïðåäñòàâëÿåò ñîáîé ìíîæåñòâî âñåõ ïóòåé äëèíû l èç v
i
â v
j
.
Äîêàçàòåëüñòâî ïî÷òè äîñëîâíî ñîâïàäàåò ñ äîêàçàòåëüñòâîì
òåîðåìû 8.7.
Ñëåäñòâèå. Ýëåìåíò (i, j) ìàòðèöû H∪H
2
∪... ∪H
l
îðãðàôà D
ðàâåí ìíîæåñòâó âñåõ ïóòåé äëèíû ≤ l èç v
i
â v
j
.
Ïðèìåð.
Ðèñ. 8.18. Ìàòðèöà ïóòåé â îðãðàôå.
000
00
000
000
b
cd
H
e
a
=
2
00
00
000
000
bc bd
cb de
H
ea
ab
=
3
00
00
000
00
bcb bde
cbc dea cbd
H
eab
abc abd
∪
=
132 133
8.7.3. Ìàòðèöà äîñòèæèìîñòè
Ìàòðèöà äîñòèæèìîñòè R (D)=(r
ij
) îïðåäåëÿåòñÿ ñëåäóþùèì
îáðàçîì:
1, åñëè äîñòèæèìà èç ,
0, åñëè íå äîñòèæèìà èç .
ji
ij
ji
uu
r
uu
=
Âñÿêàÿ âåðøèíà äîñòèæèìà ñàìà èç ñåáÿ, ïîýòîìó r
ii
=1äëÿ
âñåõ i. Íà ðèñ.8.19ïðåäñòàâëåíû ìàòðèöû ñìåæíîñòè, ðàññòîÿíèé
è äîñòèæèìîñòè äëÿ íåêîòîðûõ îðãðàôîâ.
Ìàòðèöà äîñòèæèìîñòè ìîæåò áûòü ïîëó÷åíà ïðè ïîìîùè
ìàòðèöû ñìåæíîñòè.
Òåîðåìà 8.11. Ïóñòü À ìàòðèöà ñìåæíîñòè è R ìàòðèöà
äîñòèæèìîñòè îðãðàôà D ñ n âåðøèíàìè. Òîãäà
R=B (I + A + A
2
+...+ A
n1
)=B [(I + A)
n1
],
ãäå B áóëåâî ïðåîáðàçîâàíèå, à I åäèíè÷íàÿ äèàãîíàëüíàÿ
ìàòðèöà.
Äîêàçàòåëüñòâî. Äåéñòâèòåëüíî, ïî òåîðåìå 8.1′, åñëè v
j
äîñòèæèìà èç v
i
, òî ñóùåñòâóåò ïðîñòàÿ öåïü èç v
i
â v
j
. Äëèíà ýòîãî
ïóòè íå ïðåâîñõîäèò n1, ïîñêîëüêó â ïðîñòîé öåïè âåðøèíû íå
ïîâòîðÿþòñÿ. Ñîãëàñíî ñëåäñòâèþ èç òåîðåìû 8.5, â ýòîì ñëó÷àå
ýëåìåíò (i, j) ìàòðèöû I+A+A
2
+...+A
n1
áóäåò íåíóëåâûì,
îòêóäà è ñëåäóåò íàøà òåîðåìà.
 ñëåäóþùåé òåîðåìå áóäåò ïîêàçàíî ïðèìåíåíèå ìàòðèöû
äîñòèæèìîñòè êàê ìåòîäà îïðåäåëåíèÿ ñâÿçíîñòè îðãðàôà.
Òåîðåìà 8.12. Ïóñòü îðãðàô D èìååò ìàòðèöó äîñòèæèìîñòè R
è ìàòðèöó ñìåæíîñòè À.Òîãäà
1) D ñèëüíî ñâÿçåí òîãäà è òîëüêî òîãäà, êîãäà R=J;
2) D îäíîñòîðîííå ñâÿçåí òîãäà è òîëüêî òîãäà, êîãäà
B(R + R′)=J;
3) D ñëàáî ñâÿçåí òîãäà è òîëüêî òîãäà, êîãäà
B [(I + A + A′)
n1
]=J, ãäå J åäèíè÷íàÿ ìàòðèöà.
8.8. Âåðøèííûå áàçû è ñåòè êîììóíèêàöèé
8.8.1. Ñèëüíûå êîìïîíåíòû è âåðøèííàÿ áàçà
Ïðåäïîëîæèì, ìû õîòèì ïåðåäàòü ñîîáùåíèå ïî ñåòè êîììóíè-
êàöèé òàê, ÷òîáû îíî ìîãëî äîñòèãíóòü âñåõ åå ó÷àñòíèêîâ. Åñëè ñåòü
ñèëüíî ñâÿçíà, äîñòàòî÷íî ïåðåäàòü ñîîáùåíèå ëþáîìó îäíîìó ëèöó.
( äåéñòâèòåëüíîñòè, ïî òåîðåìå 8.4, äîñòàòî÷íî îäíîñòîðîííåé
ñâÿçíîñòè ñåòè, íî â ýòîì ñëó÷àå íàäî áóäåò ïåðåäàòü ñîîáùåíèå îïðåäå-
ëåííîìó ëèöó.) Îäíàêî, åñëè ãðàô íå ÿâëÿåòñÿ ñèëüíî ñâÿçíûì, òî
Ãëàâà 8 Ãðàôû
1
1234
10100
()
20010
3 0001
40000
AD
=
1
1234
11111
()
20111
3 0011
40001
RD
=
12 34
10123
()
2012
301
40
i
j
d
x
xx
xxx
=
2
12345
1 01000
2 00100
()
3 00010
4 00001
5 10000
AD
=
1234
1 0123
()
2 3012
32301
41230
i
j
d
=
3
1234
1 1111
()
2 1111
3 1111
4 1111
RD
=
3
1234
1 0100
()
2 1010
3 0001
4 1000
AD
=
2
12345
1 11111
2 11111
()
3 11111
4 11111
5 11111
RD
=
12345
1 01234
2 40123
()
3 34012
423401
512340
i
j
d
=
Ðèñ. 8.19. Ìàòðèöû ðàññòîÿíèé è äîñòèæèìîñòè äëÿ îðãðàôîâ.
ñîîáùåíèå, ïåðåäàííîå îäíîìó ëèöó, íå âñåãäà äîñòèãíåò âñåõ ó÷àñò-
íèêîâ.  òàêîì ñëó÷àå âîçíèêàåò çàäà÷à íàõîæäåíèÿ ìíîæåñòâà âåð-
øèí, èç êîòîðûõ äîñòèæèìû âñå äðóãèå âåðøèíû, ïðè÷åì æåëàòåëüíî,
÷òîáû ýòî ìíîæåñòâî ñîäåðæàëî íàèìåíüøåå ÷èñëî âåðøèí.
134 135
Îïðåäåëåíèå 8.21. Ñîâîêóïíîñòü âåðøèí B îðãðàôà D
íàçûâàåòñÿ åãî âåðøèííîé áàçîé (èëè áàçîé âåðøèí), åñëè êàæäàÿ
âåðøèíà, íå âõîäÿùàÿ â Â, äîñòèæèìà èç íåêîòîðîé âåðøèíû â
Â, è ìíîæåñòâî Â ìèíèìàëüíî. Çäåñü ìèíèìàëüíîñòü Â îçíà-
÷àåò, ÷òî íè èç êàêîãî ñîáñòâåííîãî ïîäìíîæåñòâà  íåëüçÿ äîñ-
òè÷ü âñåõ îñòàâøèõñÿ âåðøèíD.
Äëÿ ïðèìåðà ðàññìîòðèì îðãðàô, èçîáðàæåííûé íà ðèñ. 8.20.
Íàéäåì âåðøèííóþ áàçó ñ íàèìåíüøèì ÷èñëîì ýëåìåíòîâ, èñõîäÿ
èç åå îïðåäåëåíèÿ. Âåðøèíà t íå èìååò âõîäÿùèõ äóã, ïîýòîìó ìû
äîëæíû âêëþ÷èòü åå â âåðøèííóþ áàçó. Âåðøèíû u, v, w íåäîñòè-
æèìû èç p, q, r, s, íî êàæäàÿ èç íèõ äîñòèæèìà äðóã äëÿ äðóãà,
ïîýòîìó îäíà èç íèõ äîëæíà âõîäèòü â ëþáóþ èç âåðøèííûõ áàç.
Ñëåäîâàòåëüíî, âåðøèííóþ áàçó ìîæíî ïîëó÷èòü äîáàâëåíèåì ê t
ëèáî u, ëèáî v, ëèáî w. Èç ìíîæåñòâà {t, u, q} òàêæå ìîæíî äîñòè÷ü
âñå îñòàëüíûå âåðøèíû, íî îíî íå ÿâëÿåòñÿ âåðøèííîé áàçîé,
ïîñêîëüêó ïîäìíîæåñòâî {t, u} óæå
îáëàäàåò òðåáóåìûì ñâîéñòâîì. Â
äåéñòâèòåëüíîñòè ìíîæåñòâà {t, u},
{t, v} è {t, w} îáðàçóþò âñå âåðøèí-
íûå áàçû. Êàê âèäíî, âñå îíè èìåþò
îäèíàêîâîå ÷èñëî âåðøèí, è ýòî íå
ñëó÷àéíî. Òàêèì îáðàçîì, ïîèñê
âåðøèííîé áàçû ñ íàèìåíüøèì
÷èñëîì ýëåìåíòîâ çàêàí÷èâàåòñÿ
ñðàçó, êàê òîëüêî íàõîäèòñÿ ïðîèç-
âîëüíàÿ âåðøèííàÿ áàçà.
 ýòîì ïàðàãðàôå áóäåò ïðèâåäåíà ïðîöåäóðà íàõîæäåíèÿ âñåõ
âåðøèííûõ áàç äàííîãî îðãðàôà. Áîëüøèíñòâî ðåçóëüòàòîâ ïðèíàä-
ëåæèò ʸíèãó. ×òîáû îïèñàòü ïðîöåäóðó ʸíèãà, ââåäåì íåêîòîðûå
ïðåäâàðèòåëüíûå îïðåäåëåíèÿ.
Îïðåäåëåíèå 8.22. Ìàêñèìàëüíûé ñèëüíî ñâÿçíûé ïîäãðàô
îðãðàôà D íàçûâàåòñÿ ñèëüíî ñâÿçíîé êîìïîíåíòîé D (ñèëüíîé
êîìïîíåíòîé ñâÿçíîñòè).
Íàïðèìåð, íà ðèñ. 8.20ïîäãðàô, ïîðîæäåííûé âåðøèíàìè v, w,
ÿâëÿåòñÿ ñèëüíî ñâÿçíûì, îäíàêî îí íå ÿâëÿåòñÿ ñèëüíîé êîìïî-
íåíòîé, òàê êàê âõîäèò â ñèëüíûé ïîäãðàô, ïîðîæäåííûé âåðøè-
íàìè u, v, w, ò.å.íå ÿâëÿåòñÿ ìàêñèìàëüíûì ïî ñâîéñòâó ñèëüíîé
ñâÿçíîñòè. Äðóãîé ñèëüíîé êîìïîíåíòîé ÿâëÿåòñÿ ïîäãðàô, ïîðîæ-
äåííûé âåðøèíàìè p, q, r, s, âñå îíè äîñòèæèìû äðóã äëÿ äðóãà,
òàê êàê âõîäÿò â îäèí öèêë. Îäíà âåðøèíà t òàêæå ÿâëÿåòñÿ ñèëüíîé
êîìïîíåíòîé. Ñèëüíûå êîìïîíåíòû îáëàäàþò ñëåäóþùèìè ñâîé-
ñòâàìè.
Òåîðåìà 8.13. Â îðãðàôå D=(V,E) êàæäàÿ âåðøèíà u âõîäèò â
îäíó è òîëüêî îäíó ñèëüíóþ êîìïîíåíòó.
Äîêàçàòåëüñòâî. Âåðøèíà u âõîäèò ïî ìåíüøåé ìåðå â îäíó
ñèëüíóþ êîìïîíåíòó. Â ñàìîì äåëå, ïîäãðàô, ïîðîæäåííûé u, ÿâëÿ-
åòñÿ ñèëüíûì (òàê êàê êàæäàÿ âåðøèíà äîñòèæèìà ñàìà äëÿ ñåáÿ).
Áóäåì äîáàâëÿòü âåðøèíû äî òåõ ïîð, ïîêà áóäóò âñå åùå ïîëó-
÷àòüñÿ ñèëüíî ñâÿçíûå ïîäãðàôû. Òàêàÿ ïðîöåäóðà ïðèâîäèò ê ñèëü-
íî ñâÿçíîé êîìïîíåíòå, ñîäåðæàùåé u. Ïðåäïîëîæèì òåïåðü, ÷òî
u âõîäèò â ñèëüíûå êîìïîíåíòû K è L.Ðàññìîòðèì ïîäãðàô, ïîðîæ-
äåííûé âåðøèíàìè èç K è L.Ýòîò ïîäãðàô ñèëüíî ñâÿçåí, òàê êàê,
åñëè a âõîäèò â K, à b âõîäèò â L, òî èç a ìîæíî ïîïàñòü â b ÷åðåç
âåðøèíû èç K ∪ L, ïîñêîëüêó èç a ìîæíî äîñòè÷ü u ÷åðåç âåðøèíû
K è èç u ìîæíî äîñòè÷ü b ÷åðåç âåðøèíû L.Àíàëîãè÷íî, èç b ìîæíî
ïîïàñòü â a ÷åðåç âåðøèíû K∪L.Èç ìàêñèìàëüíîñòè K è L èìååì,
÷òî K ∪ L=K è K ∪ L=L, ïîýòîìó K=L.
Ýòà òåîðåìà äàåò òîò æå ñàìûé ðåçóëüòàò, ÷òî è ëåììà îá
óïîðÿäî÷åíèè êâàçèóïîðÿäî÷åííîãî ìíîæåñòâà. Äåéñòâèòåëüíî, âñå
âåðøèíû ñèëüíî ñâÿçíîãî ïîäãðàôà äîñòèæèìû äðóã äëÿ äðóãà,
ò.å.íàõîäÿòñÿ â îòíîøåíèè ñèëüíîé ñâÿçíîñòè, êîòîðîå ÿâëÿåòñÿ
ñèììåòðè÷íûì, ðåôëåêñèâíûì è òðàíçèòèâíûì. Ñëåäîâàòåëüíî,
ìíîæåñòâî âåðøèí ñèëüíî ñâÿçíîé êîìïîíåíòû îáðàçóþò îäèí
êëàññ ýêâèâàëåíòíîñòè. Ýòè êëàññû ýêâèâàëåíòíîñòè ñâÿçàíû ìåæäó
ñîáîé è îáðàçóþò íîâûé ãðàô D*, âåðøèíû êîòîðîãî ñîîòâåòñòâóþò
ñèëüíûì êîìïîíåíòàì ãðàôàD.
Îðãðàô D*, íàçûâàåìûé êîíäåíñàöèåé ãðàôà D, ñòðîèòñÿ ñëå-
äóþùèì îáðàçîì. Ïóñòü K
1
, K
2
,..., K
p
ñèëüíûå êîìïîíåíòû D.Òîãäà
âûáèðàåì ìíîæåñòâî âåðøèí V (D*)={K
1
, K
2
,..., K
p
}, è ïðîâîäèì
äóãó îò K
i
ê K
j
òîãäà è òîëüêî òîãäà, êîãäà i≠j è äëÿ íåêîòîðûõ
âåðøèí u∈K
i
è v ∈ K
j
â D èìååòñÿ õîòÿ áû îäíà äóãà èç u â v.
Êîíäåíñàöèÿ D* îðãðàôà D íå èìååò öèêëîâ. Äåéñòâèòåëüíî,
ïóñòü â D* ñóùåñòâóåò öèêë
12 1
, ,..., ,
t
ii ii
KK KK
è u íåêîòîðàÿ
âåðøèíà â
1
i
K
, v íåêîòîðàÿ âåðøèíà â
2
i
K
. Èñïîëüçóÿ öèêë
12 1
, ,..., ,
t
ii ii
KK KK
, ëåãêî äîêàçàòü, ÷òî u äîñòèæèìà èç v è v äîñòè-
æèìà èç u. Òàêèì îáðàçîì, îêàçûâàåòñÿ, ÷òî u è v âõîäÿò â îäíó
ñèëüíóþ êîìïîíåíòó è, ñëåäîâàòåëüíî,
1
i
K
=
2
i
K
(òàêîé âûâîä
îñíîâàí íà òåîðåìå 8.6), à ýòî ïðîòèâîðå÷èò îïðåäåëåíèþ öèêëà.
Ïîñêîëüêó íîâûé îðãðàô D*, ÿâëÿþùèéñÿ êîíäåíñàöèåé èñõîä-
íîãî îðãðàôà D, íå ñîäåðæèò öèêëîâ, îí áóäåò èìåòü ëåãêî îïðåäåëÿ-
åìóþ åäèíñòâåííóþ âåðøèííóþ áàçó B* è èç íåå áóäåò ëåãêî ïîëó-
÷èòü âñå âåðøèííûå áàçû îðãðàôà D.Ýòî ñâîéñòâî êîíäåíñàöèè
ãðàôà îñíîâàíî íà ñëåäóþùåé òåîðåìå.
Ãëàâà 8 Ãðàôû
Ðèñ. 8.20. Ñèëüíûå
êîìïîíåíòû îðãðàôà.
136 137Ãëàâà 8 Ãðàôû
Òåîðåìà 8.14. Â îðãðàôå áåç öèêëîâ D åñòü åäèíñòâåííàÿ
âåðøèííàÿ áàçà, ñîñòîÿùàÿ èç âñåõ âåðøèí, íå èìåþùèõ
âõîäÿùèõ äóã.
Äîêàçàòåëüñòâî. Ïóñòü Â ìíîæåñòâî âñåõ âåðøèí, íå èìåþùèõ
âõîäÿùèõ äóã. ßñíî, ÷òî ëþáàÿ âåðøèíà u èç Â äîëæíà ïðèñóò-
ñòâîâàòü â êàæäîé âåðøèííîé áàçå. Äîñòàòî÷íî äîêàçàòü, ÷òî âñÿêàÿ
âåðøèíà v, íå ïðèíàäëåæàùàÿ Â, äîñòèæèìà èç íåêîòîðîé âåðøèíû
ìíîæåñòâà Â.×òîáû ïîêàçàòü ýòî, ïðåäïîëîæèì, ÷òî v∉B.Ïóñòü
v=v
0
. Ïîñêîëüêó v
0
∉B, èìååòñÿ âõîäÿùàÿ â v
0
äóãà (v
1
, v
0
), ïðè÷åì
v
1
≠v
0
. Åñëè v
1
∈B, âñå äîêàçàíî. Åñëè íåò, òî çíà÷èò åñòü âõîäÿùàÿ
â v
1
äóãà (v
2
, v
1
), ïðè÷åì v
2
≠v
1
. Ïðîäîëæàÿ ýòîò ïðîöåññ, ïîñòðîèì
ïóòü v
t
, v
t1
,..., v
1
, v
0
, íå ñîäåðæàùèé âåðøèí èç B.Âñå âåðøèíû
ýòîãî ïóòè ðàçëè÷íû, ïîñêîëüêó, åñëè v
i
=v
j
, i > j è v
i
, v
i1
,..., v
j+1
ðàçëè÷íû, òî v
i
, v
i1
,..., v
j+1
, v
j
öèêë, ÷òî ïðîòèâîðå÷èò äîïóùåíèþ
îá îòñóòñòâèè öèêëîâ â îðãðàôå D.Òàê êàê D èìååò êîíå÷íîå ÷èñëî
âåðøèí, òî ïîñòðîåíèå ïóòè v
t
, v
t1
,..., v
1
, v
0
íå ìîæåò ïðîäîëæàòüñÿ
áåñêîíå÷íî.  êîíöå êîíöîâ ìû äîëæíû äîñòè÷ü íåêîòîðóþ âåðøèíó
v
t
, âõîäÿùóþ â Â.Òàêèì îáðàçîì, âåðøèíà v=v
0
äîñòèæèìà èçv
t
.
Ñëåäñòâèå. Â îðãðàôå áåç öèêëîâ ñóùåñòâóåò âåðøèíà, â
êîòîðóþ íå âõîäèò íè îäíà äóãà.
Òåîðåìà 8.15. Ïóñòü B* åäèíñòâåííàÿ âåðøèííàÿ áàçà
êîíäåíñàöèè D* îðãðàôà D.Òîãäà âåðøèííûìè áàçàìè â D,
ñëóæàò òàêèå ìíîæåñòâà Â, êîòîðûå ñîäåðæàò ïî îäíîé âåðøèíå
èç êàæäîé ñèëüíîé êîìïîíåíòû D, ïðèíàäëåæàùåé B*.
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî B* åäèíñòâåííàÿ
âåðøèííàÿ áàçà â D* è Â ñîäåðæèò ïî îäíîé âåðøèíå èç êàæäîé
ñèëüíîé êîìïîíåíòû B*. ßñíî, ÷òî êàæäàÿ âåðøèíà â D äîñòèæèìà
èç Â.Íóæíî ïîêàçàòü, ÷òî Â ÿâëÿåòñÿ ìèíèìàëüíûì ìíîæåñòâîì,
îáëàäàþùèì òåì ñâîéñòâîì, ÷òî êàæäàÿ âåðøèíà â D äîñòèæèìà
èç Â.Äëÿ äîêàçàòåëüñòâà ìèíèìàëüíîñòè äîñòàòî÷íî ïîêàçàòü, ÷òî
íå íàéäåòñÿ âåðøèíû v∈B, äîñòèæèìîé èç äðóãîé âåðøèíû
u∈B.Åñëè áû ýòî áûëî âîçìîæíî, òî ñèëüíàÿ êîìïîíåíòà, ñî-
äåðæàùàÿ v, áûëà áû äîñòèæèìà â D* èç ñèëüíîé êîìïîíåíòû,
ñîäåðæàùåé u, ÷òî ïðîòèâîðå÷èëî áû ìèíèìàëüíîñòè B*. ×òîáû
çàâåðøèòü äîêàçàòåëüñòâî, ïîêàæåì, ÷òî åñëè Â ñëóæèò ïðîèçâîëü-
íîé âåðøèííîé áàçîé, òî îíà ñîäåðæèò òî÷íî ïî îäíîé âåðøèíå èç
êàæäîé ñèëüíîé êîìïîíåíòû D, ïðèíàäëåæàùåé B*. Êîíå÷íî, áàçà
 äîëæíà ñîäåðæàòü ïî êðàéíåé ìåðå ïî îäíîé âåðøèíå èç êàæäîé
òàêîé ñèëüíîé êîìïîíåíòû, à òàêæå, âîçìîæíî, è äðóãèå âåðøèíû.
Èç óñëîâèÿ ìèíèìàëüíîñòè ñëåäóåò, ÷òî íèêàêèå äðóãèå âåðøèíû
íå òðåáóþòñÿ.
Ñëåäñòâèåì èç òåîðåìû 8.15ÿâëÿåòñÿ òåîðåìà 8.16.
Òåîðåìà 8.16. Ëþáûå äâå âåðøèííûå áàçû îðãðàôà ñîäåðæàò
îäèíàêîâîå ÷èñëî âåðøèí.
Èç ýòèõ òåîðåì ñëåäóåò ïðîöåäóðà (ʸíèãà) íàõîæäåíèÿ ìíîæå-
ñòâà âåðøèííûõ áàç îðãðàôà.
1. Íàõîäÿòñÿ âñå ñèëüíûå êîìïîíåíòû îðãðàôàD.
2. Ñòðîèòñÿ êîíäåíñàöèÿ D* îðãðàôàD.
3.Íàõîäèòñÿ ìíîæåñòâî âåðøèí ãðàôà êîíäåíñàöèè B*, â
êîòîðûå íå âõîäèò íè îäíà äóãà (âåðøèííàÿ áàçà B* êîíäåíñàöèè
ãðàôà D*).
4.Èç êàæäîé ñèëüíîé êîìïîíåíòû, âõîäÿùåé â B*, âûáèðàåòñÿ
ïî îäíîé âåðøèíå. Ýòî ìíîæåñòâî åñòü âåðøèííàÿ áàçà B îðãðàôàD.
Ðàññìîòðèì ýòó ïðîöåäóðó äëÿ îðãðàôà, èçîáðàæåííîãî íà ðèñ.8.21.
Ðèñ. 8. 21. Îðãðàô, åãî êîíäåíñàöèÿ è âåðøèííàÿ áàçà.
Íàéäåì âñå ñèëüíûå êîìïîíåíòû ýòîãî ãðàôà. Îí ñîäåðæèò
øåñòü ñèëüíûõ êîìïîíåíò (ìíîæåñòâà âõîäÿùèõ â íèõ âåðøèí óêà-
çàíû íà ðèñóíêå). Ñòðîèì êîíäåíñàöèþ D* ãðàôàD.  êà÷åñòâå
âåðøèí D* âûáèðàåì âñå ñèëüíûå êîìïîíåíòû K
1
K
6
è ñîåäèíÿåì
èõ äóãàìè. Â êîíäåíñàöèè D* íàéäåòñÿ, íàïðèìåð, äóãà èç K
3
â K
4
,
ïîñêîëüêó â îðãðàôå D èìååòñÿ äóãà (e,f). Àíàëîãè÷íî â D* íàéäåò-
ñÿ äóãà èç K
4
â K
5
, ïîñêîëüêó â D åñòü äóãà èç g â i. Èìååòñÿ è
äðóãàÿ äóãà (h, k) èç âåðøèíû â K
4
ê âåðøèíå â K
5
, îäíàêî â êîí-
äåíñàöèþ ãðàôà âêëþ÷àåòñÿ òîëüêî îäíà èç íèõ.
Òåïåðü íàéäåì âåðøèííóþ áàçó â D*. Êîìïîíåíòû K
1
, K
2
è K
6
íå
èìåþò âõîäÿùèõ äóã; îíè îáðàçóþò ìíîæåñòâî B* ={K
1
,K
2
,K
6
}, èç
êîòîðîãî äîñòèæèìà êàæäàÿ äðóãàÿ âåðøèíà â D*. Òàêèì îáðàçîì,
B* ={K
1
,K
2
,K
6
} ÿâëÿåòñÿ âåðøèííîé áàçîé äëÿ êîíäåíñàöèè D*.
138 139Ãëàâà 8 Ãðàôû
Äàëåå, åñëè âçÿòü ïî îäíîìó ýëåìåíòó èç êàæäîé ñèëüíîé êîìïî-
íåíòû K
1
, K
2
, K
6
, òî ïîëó÷èì âåðøèííóþ áàçó äëÿD.Íàïðèìåð,
ìíîæåñòâî B = {a,d,l} äàåò òàêóþ âåðøèííóþ áàçó. Äðóãàÿ âåð-
øèííàÿ áàçà çàäàåòñÿ ìíîæåñòâîì {a,d,m}. Èç B* ïîëó÷àþòñÿ è
äðóãèå âåðøèííûå áàçû: {b, d,l}, {b,d,m}, {c,d,l}, {c,d,m}.
Ìû âèäèì, ÷òî â D* âñåãäà åñòü åäèíñòâåííàÿ âåðøèííàÿ áàçà
B*, ñîñòîÿùàÿ, êàê â ýòîì ïðèìåðå, èç âñåõ âåðøèí, íå èìåþùèõ
âõîäÿùèõ äóã.  ñâîþ î÷åðåäü, êàæäóþ âåðøèííóþ áàçó â D ìîæíî
ïîëó÷èòü èç áàçû â D*, âûáèðàÿ ïî îäíîé âåðøèíå èç êàæäîé
ñèëüíîé êîìïîíåíòû â D, âõîäÿùåé â B*. Òàêèì îáðàçîì, ïîëó÷åí-
íûå âåðøèííûå áàçû ñîñòàâëÿþò ìíîæåñòâî âñåõ âåðøèííûõ áàç.
8.8.2. Èñïîëüçîâàíèå ìàòðèöû äîñòèæèìîñòè
äëÿíàõîæäåíèÿ ñèëüíûõ êîìïîíåíò îðãðàôà
Òåîðåìà 8.17. Ïóñòü îðãðàô D èìååò ìàòðèöó äîñòèæèìîñòè
R=(r
ij
) è R
2
=(s
ij
). Òîãäà:
1) ñèëüíàÿ êîìïîíåíòà, ñîäåðæàùàÿ âåðøèíó u
i
, îïðåäåëÿåòñÿ
åäèíè÷íûìè ýëåìåíòàìè â i-é ñòðîêå (èëè ñòîëáöå) ïîýëå-
ìåíòíîãî ïðîèçâåäåíèÿ R×R′, ãäå R′ ìàòðèöà, òðàíñïîíè-
ðîâàííàÿ ê R;
2) ÷èñëî âåðøèí â ñèëüíîé êîìïîíåíòå, ñîäåðæàùåé u
i
, ðàâíî s
ii
.
Äîêàçàòåëüñòâî. Âåðøèíà u
j
äîñòèæèìà èç âåðøèíû u
i
òîãäà è
òîëüêî òîãäà, êîãäà r
ij
=1.  ñâîþ î÷åðåäü, u
i
äîñòèæèìà èç u
j
òîãäà
è òîëüêî òîãäà, êîãäà r
ji
=1. Òàêèì îáðàçîì, u
i
è u
j
âçàèìíî äîñòè-
æèìû â òîì è òîëüêî òîì ñëó÷àå, åñëè r
ij
r
ji
=1.
Âåëè÷èíà s
ii
ðàâíà
1
n
rr
i
jj
i
j
=
∑
, ãäå n ÷èñëî âåðøèí. Äàëåå,
r
ij
r
ji
=1òîãäà è òîëüêî òîãäà, êîãäà u
i
è u
j
âçàèìíî äîñòèæèìû. Òàêèì
îáðàçîì, ñóììèðîâàíèå ýòèõ ÷èñåë ïî âñåì j äàåò ÷èñëî âåðøèí u
j
,
âçàèìíî äîñòèæèìûõ äëÿ âåðøèí u
i
.
Íà ðèñ. 8.22ïðèâåäåíû ìàòðèöû R, R × R′ è R
2
äëÿ èçîáðà-
æåííîãî òàì æå îðãðàôà D.Ïîýëåìåíòíîå ïðîèçâåäåíèå R×R′
ïðåäñòàâëÿåò ñîáîé êëåòî÷íî-äèàãîíàëüíóþ ìàòðèöó. Êàæäàÿ
êëåòêà ñîîòâåòñòâóåò îäíîé ñèëüíîé êîìïîíåíòå. Ìû ìîæåì
íàéòè ñèëüíûå êîìïîíåíòû, ïðîñìàòðèâàÿ ìàòðèöó ïî ñòðîêàì.
Íàïðèìåð, ñòðîêà, ñîîòâåòñòâóþùàÿ âåðøèíå u â ìàòðèöå R×R′,
îïðåäåëÿåò ñèëüíóþ êîìïîíåíòó {u, v, w}. Ýëåìåíò (u, u) â
ìàòðèöå R
2
, à èìåííî 3, äàåò ÷èñëî ýëåìåíòîâ â ýòîé ñèëüíîé
êîìïîíåíòå. Àíàëîãè÷íî ìîæíî íàéòè äðóãèå ñèëüíûå êîìïî-
íåíòû.
Ðèñ. 8.22. Ñèëüíûå êîìïîíåíòû îðãðàôà, îïðåäåëÿåìûå
ïîìàòðèöå äîñòèæèìîñòè.
8.9. Àöèêëè÷åñêèå ãðàôû
Îïðåäåëåíèå 8.23. Îðãðàô íàçûâàåòñÿ àöèêëè÷åñêèì, åñëè îí
íå ñîäåðæèò öèêëîâ.
 îáùåì ñëó÷àå îðãðàô ìîæåò ñîäåðæàòü ïóòè ñêîëü óãîäíî
áîëüøîé äëèíû, ïîñêîëüêó êàæäûé ïóòü ìîæåò ïðîõîäèòü ÷åðåç
îäíó âåðøèíó ëþáîå ÷èñëî ðàç. Îäíàêî ýòî âîçìîæíî, òîëüêî åñëè
â ãðàôå åñòü öèêëû.  àöèêëè÷åñêîì ãðàôå äëèíû ïóòåé îãðàíè÷å-
íû, òàê êàê âåðøèíû â åãî ïóòÿõ íå ìîãóò ïîâòîðÿòüñÿ, ò.å.âñå åãî
ïóòè ïðîñòûå öåïè. Ñëåäîâàòåëüíî, â àöèêëè÷åñêîì îðãðàôå èìå-
þòñÿ ïóòè ìàêñèìàëüíîé äëèíû, ò.å.ïóòè, êîòîðûå íå ìîãóò áûòü
ïðîäîëæåíû: íåëüçÿ äîáàâèòü ðåáðî íè ê èõ íà÷àëó, íè ê èõ êîíöó.
Îòñþäà ñëåäóåò, ÷òî â àöèêëè÷åñêîì ãðàôå ñóùåñòâóåò, ïî êðàéíåé
ìåðå, îäíà âåðøèíà, â êîòîðóþ íå âõîäèò íè îäíà äóãà (òàêóþ
âåðøèíó íàçûâàþò èñòîêîì, èëè èñòî÷íèêîì), è, ïî êðàéíåé ìåðå,
îäíà âåðøèíà, èç êîòîðîé íå âûõîäèò íè îäíà äóãà (òàêóþ âåðøèíó
íàçûâàþò ñòîêîì).
11111110
11111110
11111110
()
00011110
00011110
00011110
00011110
00011111
uvwpqrst
u
v
w
RRD
p
q
r
s
t
==
11100000
11100000
11100000
00011110
00011110
00011110
00011110
00000001
uvwpqrst
u
v
w
RR
p
q
r
s
t
′
×=
2
33377770
33377770
33377770
00044440
00044440
00044440
00044440
00055551
uvwpqrst
u
v
w
R
p
q
r
s
t
=
Ñèëüíûå
êîìïîíåíòû
{u, v, w}
{p, q, r, s}
{t}