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

íåé ñìåæíà âåðøèíà 1. Ñëåäîâàòåëüíî, ïåðâàÿ öèôðà êîäà
Ïðþôåðà ðàâíà 1. Óäàëÿÿ âåðøèíó 2, ïîëó÷èì ãðàô, èçîáðà-
æåííûé íà ðèñ. 3.7,á.  ýòîì ãðàôå ñðåäè âåðøèí åäèíè÷íîé
ñòåïåíè ìèíèìàëüíûé íîìåð ó âåøèíû 3, ïîýòîìó âòîðàÿ öèô-
ðà êîäà  4. Âûïîëíèâ åùå òðè èòåðàöèè, êîòîðûì ñîîòâåò-
ñòâóò ãðàôû, èçîáðàæåííûå íà ðèñ. 3.7,â,ã,ä, ïîëó÷èì äåðåâî,
ñîñòîÿùåå èç åäèíñòâåííîãî ðåáðà {7; 6} . Ïðîöåññ çàâåðøåí.
   Ðåçóëüòàòû ïðîäåëàííûõ øàãîâ ïðåäñòàâëåíû â òàáë. 3.1,
ïîñëåäíÿÿ ñòðîêà êîòîðîé ñîäåðæèò èñêîìûé êîä  14166.
                                                     Òàáëèöà 3.1
 Èòåðàöèÿ                     1       2       3       4       5
 Ãðàô íà ðèñ. 3.7              à       á       â       ã       ä
 Ìèíèìàëüíûé íîìåð âåðøèíû     2       3       4       1       5
 Óäàëÿåìîå ðåáðî             {1;2}   {4;3}   {1;4}   {6;1}   {6;5}
 Ýëåìåíò êîäà Ïðþôåðà          1       4       1       6       6

   Àëãîðèòì âîññòàíîâëåíèÿ äåðåâà, ïðåäñòàâëåííîãî êîäîì
Ïðþôåðà, ïîçâîëÿåò ïîëó÷èòü ñîîòâåòñòâóþùåé ñïèñîê ðåáåð.
   Íàçîâåì àíòèêîäîì óïîðÿäî÷åííóþ ïî âîçðàñòàíèþ ïîñëå-
äîâàòåëüíîñòü íîìåðîâ âåðøèí, íå âîøåäøèõ â êîä Ïðþôåðà.
Äëÿ ðàññìîòðåííîãî ïðèìåðà àíòèêîä ðàâåí 2357.
   Äåðåâî ñòðîèòñÿ ïóòåì ïîñëåäîâàòåëüíîãî äîáàâëåíèÿ ðå-
áåð. Î÷åðåäíîå äîáàâëÿåìîå ðåáðî, íà÷èíàÿ ñ ïåðâîãî, îáðàçó-
åòñÿ ïàðîé âåðøèí, íîìåðà êîòîðûõ ñòîÿò ïåðâûìè â ñòðîêå
êîäà è â ñòðîêå àíòèêîäà. Ïîñëå ýòîãî èñïîëüçîâàííûå ýëåìåí-
òû ñòðîê âû÷åðêèâàþòñÿ. Åñëè íîìåð, âû÷åðêíóòûé èç ñòðî-
êè êîäà, íå ñîäåðæèòñÿ ñðåäè îñòàâøèõñÿ â íåé ýëåìåíòîâ,
åãî ñëåäóåò äîáàâèòü ê ñòðîêå àíòèêîäà, íå íàðóøàÿ åå óïîðÿ-
äî÷åííîñòü. Îïèñàííûå äåéñòâèÿ ïîâòîðÿþòñÿ ñ "îñòàòêàìè"
ñòðîê êîäà è àíòèêîäà, ïîêà íå áóäóò âû÷åðêíóòû âñå ýëåìåí-
òû ïåðâîé èç íèõ. Ïðè ýòîì ñòðîêà àíòèêîäà áóäåò ñîäåðæàòü
äâà ýëåìåíòà, îïðåäåëÿþùèõ ïîñëåäíåå ðåáðî, êîòîðîå ñëåäó-
åò äîáàâèòü ê ôîðìèðóåìîìó ñïèñêó.  ðåçóëüòàòå ïîëó÷àåì
ñïèñîê èç n−1 ðåáåð, ñîîòâåòñòâóþùèé äåðåâó, çàäàííîìó êî-
äîì Ïðþôåðà.



                             49