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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

¤ G(n)
n G (n) G(n)
G (n)
G(n−1)
|G (n)|<|G(n−1)|
G (n) G (n)
|G (n)|<|G(n−1)| |G(n)|
|G(n)|=2
C(n,2)
|G(n−1)|=2
C(n−1,2)
|G (n)|/|G(n)| < 2
C(n−1,2)−C(n,2)
C(n−1, 2) − C(n, 2) =
(n−1)!
2!(n−3)!
−
n!
2!(n−2)!
=
(n−1)(n−2)
2
−
n(n−1)
2
=
= −(n−1) |G (n)|/|G(n)| < 2
−(n−1)
n→∞ lim
n→∞
|G (n)|/|G(n)|=0
|G (n)| = o|G(n)| ¢
G k
   Òåîðåìà 5.3 Ïî÷òè âñå ãðàôû íå ÿâëÿþòñÿ ýéëåðîâûìè.
     ¤ Ïóñòü G(n)  ìíîæåñòâî âñåõ ïðîñòûõ ïîìå÷åííûõ ãðà-
ôîâ ïîðÿäêà n , à G÷ (n)  ìíîæåñòâî âñåõ ãðàôîâ èç G(n) , íå
èìåþùèõ âåðøèí íå÷åòíîé ñòåïåíè.
    Ëþáîé ãðàô èç G÷ (n) ìîæíî ïîëó÷èòü, äîáàâëÿÿ ê íåêî-
òîðîìó ãðàôó èç G(n−1) åùå îäíó âåðøèíó è ñîåäèíÿÿ åå
ñî âñåìè âåðøèíàìè íå÷åòíîé ñòåïåíè (åñëè òàêîâûå èìåþò-
ñÿ), ïîýòîìó |G÷ (n)|<|G(n−1)| . Òàê êàê ìíîæåñòâî ýéëåðî-
âûõ ãðàôîâ Gý (n) ÿâëÿåòñÿ ïîäìíîæåñòâîì G÷ (n) , çàïèøåì
|Gý (n)|<|G(n−1)| . Ðàçäåëèâ îáå ÷àñòè íåðàâåíñòâà íà |G(n)|
è ó÷èòûâàÿ, ÷òî |G(n)|=2C(n,2) è |G(n−1)|=2C(n−1,2) , ïîëó÷èì
|Gý (n)|/|G(n)| < 2C(n−1,2)−C(n,2) . Óïðîñòèâ ïîêàçàòåëü ñòåïåíè
                         (n−1)!
C(n−1, 2) − C(n, 2) = 2!(n−3)!        n!
                                − 2!(n−2)! = (n−1)(n−2)
                                                 2
                                                        − n(n−1)
                                                             2
                                                                 =
= −(n−1) , îêî÷àòåëüíî èìååì, ÷òî |Gý (n)|/|G(n)| < 2−(n−1) ,
à ïåðåõîäÿ ê ïðåäåëó ïðè n→∞ , lim |Gý (n)|/|G(n)|=0 . Ýòî
                                         n→∞
çíà÷èò, ÷òî ïðè íåîãðàíè÷åííîì óâåëè÷åíèè ÷èñëà âåðøèí, â
îáùåì ÷èñëå ãðàôîâ äîëÿ ýéëåðîâûõ ñòàíîâèòñÿ èñ÷åçàþùå
ìàëîé, ò. å. |Gý (n)| = o|G(n)| . ¢

   5.2.4. Çàäà÷à ïî÷òàëüîíà
   Ïóñòü G  ñâÿçíûé ãðàô, èìåþùèé k âåðøèí íå÷åòíîé
ñòåïåíè è çàäàííûé ìàòðèöåé âåñîâ ðåáåð. Òðåáóåòñÿ íàéòè
êðàò÷àéøèé çàìêíóòûé ìàðøðóò, ïðîõîäÿùèé ïî âñåì ðåáðàì
ãðàôà.  êà÷åñòâå ïðèëîæåíèé, ãäå ìîæåò ïîòðåáîâàòüñÿ ðå-
øåíèå ýòîé èëè ñõîäíîé çàäà÷è, ìîæíî óêàçàòü êîíòðîëü ðàç-
ëè÷íûõ êîììóíèêàöèîííûõ ñåòåé (äîðîæíûõ, ýëåêòðè÷åñêèõ,
ãàçîâûõ è ò. ï.), êîãäà íåîáõîäèìî ïðîâåðÿòü âñå ïðîòÿæåííûå
êîìïîíåíòû ñåòè. Â ëèòåðàòóðå ïî òåîðèè ãðàôîâ ñôîðìóëè-
ðîâàííàÿ âûøå çàäà÷à íàçûâàåòñÿ çàäà÷åé ïî÷òàëüîíà. Ïî-
ñëåäíåìó äàëåêî íå áåçðàçëè÷íî çíàíèå íàèáîëåå êîðîòêîãî
çàìêíóòîãî ìàðøðóòà îáõîäà âñåõ óëèö ñâîåãî ó÷àñòêà (èëè
íåêîòîðîãî èõ ïîäìíîæåñòâà). Àíàëîãè÷íàÿ çàäà÷à ñòîèò è
ïåðåä êóðüåðîì áîëüøîãî ó÷ðåæäåíèÿ, äîñòàâëÿþùèì äîêó-
ìåíòû îò îäíîãî "èñòî÷íèêà" ê ðàçëè÷íûì ïîëó÷àòåëÿì.



                              109

Страницы