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

îïèñûâàåòñÿ (n−2) -ðàçðÿäíûì êîäîì, êàæäûé ðàçðÿä êîòî-
ðîãî ìîæåò ïðèíèìàòü íåêîòîðîå, âïîëíå îïðåäåëåííîå çíà÷å-
íèå èç ìíîæåñòâà {1, 2, . . ., n}, è íàîáîðîò, êàæäîìó (n−2) -
ðàçðÿäíîìó êîäó, ñîñòàâëåííîìó íà îñíîâå ÷èñåë èç óêàçàí-
íîãî ìíîæåñòâà, ñîîòâåòñòâóåò êîíêðåòíîå äåðåâî, òî îáùåå
÷èñëî äåðåâüåâ äîëæíî áûòü ðàâíî nn−2 .


   3.4. Çàäà÷à î êðàò÷àéøåì îñòîâå ãðàôà
   Ïóñòü G  ñâÿçíûé íåîðèåíòèðîâàííûé ãðàô, êàæäîìó
ðåáðó êîòîðîãî ïðèïèñàí íåêîòîðûé âåñ ci,j > 0 . Òðåáóåòñÿ
ñðåäè âñåõ îñòîâîâ ãðàôà íàéòè ïî êðàéíåé ìåðå îäèí ñ ìè-
íèìàëüíîé ñóììîé âåñîâ ðåáåð. Õîòÿ â ðåàëüíîé ñèñòåìå, êî-
òîðàÿ îïèñûâàåòñÿ ãðàôîì, âåñ ðåáðà ìîæåò ñîîòâåòñòâîâàòü
ñòîèìîñòè, òðóäîåìêîñòè, ïðîïóñêíîé ñïîñîáíîñòè è ò. ï., â
òåîðèè ãðàôîâ ÷àùå èñïîëüçóþò òåðìèí "äëèíà ðåáðà", à ñà-
ìà çàäà÷à òðàêòóåòñÿ êàê çàäà÷à îòûcêàíèÿ îñòîâà ñ íàèìåíü-
øåé ñóììîé äëèí ñîñòàâëÿþùèõ åãî ðåáåð, èëè êðàòêî, îñòîâà
íàèìåíüøåé äëèíû (êðàò÷àéøåãî îñòîâà). Ýòî îäíà èç íàè-
áîëåå ïðîñòûõ êëàññè÷åñêèõ îïòèìèçàöèîííûõ çàäà÷ òåîðèè
ãðàôîâ, êîòîðàÿ ñ÷èòàåòñÿ ïîëíîñòüþ ðåøåííîé.  íàñòîÿùåì
ðàçäåëå ðàññìîòðèì äâà íàèáîëåå èçâåñòíûõ àëãîðèòìà îòûñ-
êàíèÿ êðàò÷àéøåãî îñòîâà.

   3.4.1. Àëãîðèòì Êðàñêàëà
   Îïèñàíèå àëãîðèòìà. Â îñíîâó àëãîðèòìà ïîëîæåíà ïðî-
ñòàÿ è èíòóèòèâíî ÿñíàÿ èäåÿ: ñòðîèòü îñòîâ èç íàèáîëåå "êî-
ðîòêèõ" ðåáåð, íå äîïóñêàÿ ïðè ýòîì îáðàçîâàíèÿ öèêëîâ.
   Ïðè âûïîëíåíèè àëãîðèòìà ôîðìèðóåòñÿ ïîñëåäîâàòåëü-
íîñòü ãðàôîâ G1 , G2 , . . . , Gi , . . . , Gn−1 , ãäå G1  îñòîâíûé ïîä-
ãðàô, ñîäåðæàùèé îäíî (ñàìîå êîðîòêîå) ðåáðî ãðàôà; G2 
îñòîâíûé ïîäãðàô, ñîäåðæàùèé äâà (ñàìûõ êîðîòêèõ) ðåáðà
ãðàôà; Gi  ëåñ, ñîäåðæàùèé i ñàìûõ êîðîòêèõ ðåáåð, íå
îáðàçóþùèõ öèêëîâ; Gn−1  èñêîìûé êðàò÷àéøèé îñòîâ.
   Ïóñòü ãðàô ïðåäñòàâëåí ñïèñêîì ðåáåð, ïðåäâàðèòåëüíî
óïîðÿäî÷åííûì ïî âîçðàñòàíèþ èõ âåñîâ.


                                  56