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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

G
1
G
1
r
r
rr
r
r
r
rr
r
r
r
r
r
r
r
r
r
r
r
G
2
r
r r r
r r r
J
J
J
J
J
J
J
J
J
J
J
J
G
3
r r
r
r
r
r
r
@
@
G
2
,
G
3
n v
i
,
n
n
   Ñëîâî "ãàìèëüòîíîâ" â ýòèõ îïðåäåëåíèÿõ ÿâëÿåòñÿ ïðîèç-
âîäíûì îò èìåíè Ó. Ãàìèëüòîíà , ïðåäëîæèâøåãî ñëåäóþùóþ
èãðó ïîä íàçâàíèåì "Êðóãîñâåòíîå ïóòåøåñòâèå". Êàæäîé èç
äâàäöàòè âåðøèí äîäåêàýäðà ïðèïèñàíî íàçâàíèå îäíîãî èç
ãîðîäîâ ìèðà. Òðåáóåòñÿ, ïåðåõîäÿ ïî ðåáðàì äîäåêàýäðà îò
îäíîãî ãîðîäà ê äðóãîìó è ïîñåòèâ êàæäûé èç íèõ òîëüêî
îäèí ðàç, îêàçàòüñÿ â èñõîäíîé òî÷êå. Î÷åâèäíî, ÷òî çàäà-
÷à ñâîäèòñÿ ê îòûñêàíèþ â ãðàôå äîäåêàýäðà (ãðàô G1 íà
ðèñ. 5.13) ïðîñòîãî öèêëà, ïðîõîäÿùåãî ÷åðåç âñå âåðøèíû.
         r                  r
         r                  J
   r r rr rr r r              J               r         r
                         r r Jr
       r rrr r           J      J       r r          r
        r r r                                      r @
                          J      J                     @r
     r         r     r     Jr     Jr
          G1                G2                    G3
                         Ðèñ. 5.13
   Â ãðàôå G2 , èçîáðàæåííîì íà ðèñ. 5.13, ãàìèëüòîíîâ öèêë
îòñóòñòâóåò, íî èìååòñÿ ïðîñòàÿ öåïü, âêëþ÷àþùàÿ âñå âåðøè-
íû. Òàêóþ öåïü íàçûâàþò ãàìèëüòîíîâîé öåïüþ, à ñîäåðæà-
ùèé åå ãðàô  ïîëóãàìèëüòîíîâûì. Íàêîíåö, â ãðàôå G3 íà
òîì æå ðèñóíêå íå ñóùåñòâóåò íè ãàìèëüòîíîâîé öåïè, íè òåì
áîëåå, ãàìèëüòîíîâà öèêëà.  òàêîì ñëó÷àå ãîâîðÿò, ÷òî ãðàô
íåãàìèëüòîíîâ.
   Ðàññìîòðèì ñëåäóþùóþ çàäà÷ó ïëàíèðîâàíèÿ, õàðàêòåð-
íóþ äëÿ õèìè÷åñêîé ïðîìûøëåííîñòè. Èìååòñÿ åäèíñòâåííûé
êîìïëåêñ àïïàðàòóðû èëè ðåàêòîð, íà êîòîðîì ìîæíî ïðîèç-
âîäèòü n ðàçëè÷íûõ âèäîâ ïðîäóêöèè vi , ïðè÷åì â ëþáîé
ìîìåíò âðåìåíè ïðîèçâîäèòñÿ òîëüêî îäèí âèä. Ïðè ïåðåõî-
äå ê ïðîèçâîäñòâó äðóãîãî âèäà â çàâèñèìîñòè îò êîíêðåòíî-
ãî ñî÷åòàíèÿ ïðåäøåñòâóþùåãî è ïîñëåäóþùåãî âèäîâ ëèáî
òðåáóåòñÿ ïîäãîòîâêà àïïàðàòóðû (íàñòðîéêà, î÷èñòêà, îõëà-
æäåíèå è ò. ï.), ëèáî íå òðåáóåòñÿ. Ïðîäóêòû ïðîèçâîäÿòñÿ â
íåïðåðûâíîì öèêëå, òàê ÷òî ïîñëå ïðîèçâîäñòâà â çàäàííûõ
êîëè÷åñòâàõ âñåõ n âèäîâ ïðîöåññ ïîâòîðÿåòñÿ. Åñòåñòâåííî
âîçíèêàåò âîïðîñ î òîì, ñóùåñòâóåò ëè öèêëè÷åñêàÿ ïîñëåäî-
âàòåëüíîñòü ïðîèçâîäñòâà n ïðîäóêòîâ, âîîáùå íå òðåáóþùàÿ
îñòàíîâîê äëÿ ïîäãîòîâêè àïïàðàòóðû.


                             113

Страницы