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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

G
r
A
r
B
r
C
r
D
P
P
P
P
P
P
P
P
³
³
³
³
³
³
³
³
®
©
ª
®
©
ª
A, B, C, D,
G,
G
¤
G(V,E)
v
1
.
ñîåäèíÿëè áåðåãà ðåêè Ïðåãåëü, à òàêæå äâà îñòðîâà íà íåé,
â ñîîòâåòñòâèè ñî ñõåìîé, èçîáðàæåííîé íà ðèñ. 5.6,a. Ñïðà-
øèâàåòñÿ, ìîæíî ëè, âûéäÿ èç íåêîòîðîãî ïóíêòà â ãîðîäå,
âåðíóòüñÿ îáðàòíî, ïðîéäÿ îäèí ðàç ïî êàæäîìó ìîñòó?

           A                             r
                                       A P PPG
       ®            ©®       ©                PP
                                                  PP
           B             D             B r
                                                  ³
                                                    P
                                                    ³r D
                                                    ³
       ­            ª­       ª                  ³
                                           ³ ³³
           C                           C ³
                                         r
                à                             á
                             Ðèñ. 5.7
   Äàäèì ãðàôîâîå ïðåäñòàâëåíèå ñõåìû íà ðèñ. 5.7,à, îòîá-
ðàçèâ ÷åòûðå ó÷àñòêà ñóøè A,B,C,D, ðàçäåëåííûå ðåêîé, ÷å-
òûðüìÿ âåðøèíàìè A, B, C, D, à ñåìü ìîñòîâ, ñâÿçûâàþùèõ
ýòè ó÷àñòêè, ñåìüþ ðåáðàìè ìóëüòèãðàôà G, êàê ïîêàçàíî íà
ðèñ. 5.7,á. Ïðè òàêîì ïðåäñòàâëåíèè çàäà÷ó î êåíèãñáåðãñêèõ
ìîñòàõ ìîæíî ñôîðìóëèðîâàòü èíà÷å: åñòü ëè â ãðàôå G öèêë,
ñîäåðæàùèé âñå åãî ðåáðà?  äàííîì ñëó÷àå îòâåò îòðèöàòå-
ëåí â ñîîòâåòñòâèè ñî ñëåäóþùåé òåîðåìîé, íîñÿùåé òàêæå
èìÿ Ýéëåðà.
   Òåîðåìà 5.1 Ñâÿçíûé íåîðèåíòèðîâàííûé ãðàô ñîäåð
æèò ýéëåðîâ öèêë òîãäà è òîëüêî òîãäà, êîãäà ñòåïåíè âñåõ
åãî âåðøèí ÷åòíû.
    ¤ Íåîáõîäèìîñòü. Ïóñòü ãðàô ñîäåæèò ýéëåðîâ öèêë. Ïî-
ñòàâèì â ñîîòâåòñòâèå êàæäîé âåðøèíå ñ÷åò÷èê ñ íóëåâûì
íà÷àëüíûì çíà÷åíèåì. Îáîéäåì öèêë, íà÷èíàÿ ñ ïðîèçâîëü-
íîãî ðåáðà è óâåëè÷èâàÿ íà 2 ñîäåðæèìîå ñ÷åò÷èêà âåðøèíû
ïðè êàæäîì åå ïðîõîæäåíèè, ÷òî ñîîòâåòñòâóåò èñïîëüçîâà-
íèþ äâóõ î÷åðåäíûõ èíöèäåíòíûõ âåðøèíå ðåáåð. Î÷åâèäíî,
÷òî ïî îêîí÷àíèè îáõîäà, êîãäà âñå ðåáðà èñïîëüçîâàíû, ñ÷åò-
÷èêè áóäóò ñîäåðæàòü ñòåïåíè âåðøèí, êîòîðûå ïðè âûøåóêà-
çàííîì ïðèðàùåíèè ìîãóò èìåòü òîëüêî ÷åòíûå çíà÷åíèÿ.
   Äîñòàòî÷íîñòü. Ïóñòü ñòåïåíè âñåõ âåðøèí ãðàôà G(V,E)
÷åòíû. Òàêîé ãðàô ÿâëÿåòñÿ, ïî êðàéíåé ìåðå, äâóñâÿçíûì è,
ñëåäîâàòåëüíî, ñîäåðæèò öèêë. Äëÿ ïîñòðîåíèÿ öèêëà ïðîèç-
âîëüíî âûáåðåì îäíó èç âåðøèí. Ïóñòü ýòî áóäåò v1 . Ïåðåéäåì
ïî íåêîòîðîìó ðåáðó â ñìåæíóþ âåðøèíó, ïîìåòèâ ðåáðî êàê


                                 103

Страницы