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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

(v
3
, v
6
, v
8
, v
7
).
G
0
,
G
0
: (v
1
, v
2
, v
3
, v
6
, v
3
, v
5
, v
2
, v
4
, v
1
, v
5
, v
4
, v
7
,
v
8
, v
7
, v
5
, v
6
, v
9
, v
8
, v
6
, v
8
, v
5
, v
9
, v
5
, v
1
),
G {v
1
,v
5
},{v
5
,v
9
},{v
3
,v
6
},{v
6
,v
8
},
{v
7
, v
8
}
k=6, C
2
6
=15
k=8,
3·5·7. . .(k−1), k
(v3 , v6 , v8 , v7 ). Ïîñëå äóáëèðîâàíèÿ ïÿòè âõîäÿùèõ â íèõ ðåáåð
ïîëó÷àåì ýéëåðîâ ìóëüòèãðàô G0 , èçîáðàæåííûé íà ðèñ. 5.12.
Èñïîëüçóÿ, àëãîðèòì Ôëåðè, íàõîäèì ñëåäóþùèé âàðèàíò ýé-
ëåðîâà öèêëà â ãðàôå G0 : (v1 , v2 , v3 , v6 , v3 , v5 , v2 , v4 , v1 , v5 , v4 , v7 ,
v8 , v7 , v5 , v6 , v9 , v8 , v6 , v8 , v5 , v9 , v5 , v1), êîòîðûé îäíîâðåìåííî ÿâ-
ëÿåòñÿ è êðàò÷àéøèì çàìêíóòûì ìàðøðóòîì ïî÷òàëüîíà â
ãðàôå G ïðè óñëîâèè, ÷òî ðåáðà {v1 ,v5 },{v5 ,v9 },{v3 ,v6 },{v6 ,v8 },
{v7 , v8 } îáõîäÿòñÿ äâàæäû.
      ðàññìîòðåííîì ïðèìåðå ãðàô ñîäåðæàë òîëüêî ÷åòûðå
âåðøèíû íå÷åòíîé ñòåïåíè. Ïîýòîìó ïîèñê îïòèìóìà ïîòðå-
áîâàë àíàëèçà âñåãî òðåõ âàðèàíòîâ ðåøåíèÿ. Ïðè áîëüøåì
÷èñëå âåðøèí êîëè÷åñòâî âàðèàíòîâ áûñòðî âîçðàñòàåò. Òàê,
åñëè k=6, òî ñóùåñòâóåò C62 =15 ðàçëè÷íûõ êðàò÷àéøèõ öå-
ïåé, ñâÿçûâàþùèõ ïàðû âåðøèí íå÷åòíîé ñòåïåíè. Ïðè ýòîì
÷èñëî âîçìîæíûõ êîìáèíàöèé ïî òðè öåïè ñ ðàçëè÷íûìè êîí-
öåâûìè âåðøèíàìè ðàâíî 15. Åñëè k=8, òî ÷èñëî âîçìîæ-
íûõ êîìáèíàöèé ñîñòàâëÿåò 105, ïðè÷åì êàæäàÿ âêëþ÷àåò
â ñåáÿ ïî ÷åòûðå öåïè.  îáùåì æå ñëó÷àå êîëè÷åñòâî êîì-
áèíàöèé, êîòîðûå ïðèäåòñÿ àíàëèçèðîâàòü, îïðåäåëÿåòñÿ êàê
3·5·7. . .(k−1), ãäå k  ÷èñëî âåðøèí íå÷åòíîé ñòåïåíè. Òàêèì
îáðàçîì, ôàêòè÷åñêè ïðèõîäèòñÿ ðåøàòü ñàìîñòîÿòåëüíóþ çà-
äà÷ó, ýêâèâàëåíòíóþ çàäà÷å îòûñêàíèÿ íàèáîëüøåãî ïàðîñî÷å-
òàíèÿ20 ìèíèìàëüíîãî âåñà â ïîëíîì ãðàôå ñ ÷åòíûì ÷èñëîì
âåðøèí.


    5.3. Ãàìèëüòîíîâû öèêëû
    5.3.1. Îïðåäåëåíèå è óñëîâèÿ ñóùåñòâîâàíèÿ
   Ãàìèëüòîíîâûì íàçûâàþò ïðîñòîé öèêë, âêëþ÷àþùèé
âñå âåðøèíû ñâÿçíîãî íåîðèåíòèðîâàííîãî ãðàôà. Àíàëîãè÷-
íî îïðåäåëÿåòñÿ ãàìèëüòîíîâ êîíòóð äëÿ îðãðàôà. Ãðàô (îð-
ãðàô), â êîòîðîì åñòü ãàìèëüòîíîâ öèêë (êîíòóð), íîñèò íà-
çûâàíèå ãàìèëüòîíîâà.
  20 Ïàðîñî÷åòàíèåì íàçûâàåòñÿ ìíîæåñòâî ðåáåð ãðàôà, âûáðàííûõ òàê,
÷òî íèêàêèå äâà èç íèõ íå ÿâëÿþòñÿ ñìåæíûìè.




                                        112

Страницы