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

    Ïðîöåññ íà÷èíàåòñÿ ñ ñàìîãî êîðîòêîãî ðåáðà eêð , êîòîðîå
îáÿçàòåëüíî äîëæíî âîéòè â êðàò÷àéøèé îñòîâ. Ïðåäïîëîæèâ
îáðàòíîå, ìû ñðàçó ïðèõîäèì ê ïðîòâîðå÷èþ. Äåéñòâèòåëüíî,
ïóñòü T  êðàò÷àéøèé îñòîâ, íå ñîäåðæàùèé eêð . ßñíî, ÷òî â
ãðàôå T +eêð åñòü öèêë. Óäàëèâ ëþáîå ïðèíàäëåæàùåå öèêëó
ðåáðî, îòëè÷íîå îò eêð , ïîëó÷àåì îñòîâ, áîëåå êîðîòêèé ÷åì T
è ñîäåðæàùèé eêð . Ñëåäîâàòåëüíî ïåðâîå ðåáðî ñïèñêà âñåãäà
âêëþ÷àåòñÿ â îñòîâ, îáðàçóÿ íà÷àëüíûé ôðàãìåíò áóäóùåãî
îñòîâà ïîä íîìåðîì 1.
    Ïîñêîëüêó â ãðàôå íåò ïàðàëëåëüíûõ ðåáåð, ïðèñîåäèíå-
íèå ê îñòîâó âòîðîãî ðåáðà íå ìîæåò ïðèâåñòè ê ïîÿâëåíèþ
öèêëà. Ïîýòîìó âòîðîå ïî äëèíå ðåáðî òàêæå äîëæíî âõîäèòü
â îñòîâ. Îíî ìîæåò ëèáî "ïðèìêíóòü" ê óæå ñóùåñòâóþùå-
ìó ôðàãìåíòó ëèáî äàñò íà÷àëî íîâîìó (ïîêà îäíîðåáåðíîìó)
ôðàãìåíòó ïîä íîìåðîì 2.
    Äëÿ îñòàëüíûõ ðåáåð íåîáõîäèì àíàëèç íà ïðåäìåò âêëþ-
÷åíèÿ èëè íåâêëþ÷åíèÿ â îñòîâ. Ïðè ýòîì âîçìîæíû ñëåäóþ-
ùèå ÷åòûðå âàðèàíòà:
   à) êîíöû ðåáðà íå ïðèíàäëåæàò íè îäíîìó ôðàãìåíòó. Ðåá-
      ðî äîëæíî áûòü âêëþ÷åíî â îñòîâ, îáðàçóÿ ïðè ýòîì íî-
      âûé ôðàãìåíò, êîòîðîìó ñëåäóåò ïðèñâîèòü î÷åðåäíîé
      íîìåð;
   á) òîëüêî îäèí èç êîíöîâ ðåáðà ïðèíàäëåæèò íåêîòîðîìó
      ôðàãìåíòó. Ðåáðî âêëþ÷àåòñÿ â îñòîâ, ïðèñîåäèíÿñü ê
      ýòîìó ôðàãìåíòó;
   â) êîíöû ðåáðà ïðèíàäëåæàò ðàçíûì ôðàãìåíòàì. Ïðè
      âêëþ÷åíèè ðåáðà â îñòîâ ïðîèñõîäèò îáúåäèíåíèå ýòèõ
      ôðàãìåíòîâ. "Íîâûé" ôðàãìåíò ïîëó÷àåò ìåíüøèé èç
      íîìåðîâ îáúåäèíÿåìûõ ôðàãìåíòîâ;
   ã) êîíöû ðåáðà ïðèíàäëåæàò îäíîìó ôðàãìåíòó. Ðåáðî íåëü-
      çÿ âêëþ÷àòü â îñòîâ, òàê êàê ýòî ïðèâîäèò ê ïîÿâëåíèþ
      öèêëà.
    Ïîñòðîåíèå îñòîâà çàâåðøèòñÿ ïîñëå ïðèñîåäèíåíèÿ ê íåìó
n−1 ðåáåð. Ê ýòîìó ìîìåíòó âñå ôðàãìåíòû îáúåäèíÿòñÿ â
îäèí. Åñëè æå ýòîãî íå ïðîèñõîäèò, õîòÿ âñå m ðåáåð ãðàôà
ïðîñìîòðåíû, à îñòîâ ñîäåðæèò ìåíåå ÷åì n−1 ðåáåð, òî ýòî
çíà÷èò, ÷òî ãðàô íåñâÿçíûé.


                            57