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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

{1; 2}.
{4; 3}
1 2 3 4 5 6
61 64 61 66 66
62 3 5 7
63 5 7
64 5 7
61 5 7
65 7
6 7
G (n, m)
B
G, n−1
B.
n−1 B,
(n, n−1) , G
     êà÷åñòâå ïðèìåðà âûïîëíèì âîññòàíîâëåíèå äåðåâà ïî
êîäó 14166. Ñîîòâåòñòâóþùèé àíòèêîä, êàê óæå áûëî ïîêà-
çàíî âûøå, ðàâåí 2357. Ïîýòîìó ïåðâîå ðåáðî äåðåâà áóäåò
{1; 2}. Âû÷åðêèâàÿ 1 è 2, ïîëó÷àåì 4166 â ñòðîêå êîäà è 357 â
ñòðîêå àíòèêîäà. Íà ñëåäóþùåé èòåðàöèè âû÷åðêèâàåì ïàðó
{4; 3} è âêëþ÷àåì â ñòðîêó àíòèêîäà 4 è ò.ä. Ïîñëåäîâàòåëü-
íîñòü èòåðàöèé ìîæåò áûòü ïðåäñòàâëåíà òàáë. 3.2.
                                               Òàáëèöà 3.2
     Èòåðàöèÿ             1    2    3     4    5     6
     Ñòðîêà êîäà         61    64   61    66   66
                         62    3    5      7
                               63   5     7
    Ñòðîêà àíòèêîäà                 64    5    7
                                          61   5       7
                                               65      7
                                                       6 7
     Äîáàâëÿåìîå ðåáðî {1;2} {4;3} {1;4} {6;1} {6;5} {6;7}

   Àíàëèçèðóÿ ñïèñîê ðåáåð, óáåæäàåìñÿ, ÷òî ïîëó÷åíî èñ-
õîäíîå äåðåâî. Îòìåòèì, ÷òî ïîðÿäîê ñëåäîâàíèÿ ðåáåð òîò
æå, ÷òî è â ïðåäûäóùåé òàáëèöå.


   3.3. Çàäà÷è ñ äåðåâüÿìè
   3.3.1. Ïåðå÷èñëåíèå îñòîâíûõ äåðåâüåâ
   Ïóñòü G ÿâëÿåòñÿ (n, m)-ãðàôîì ñ ìàòðèöåé èíöèäåíòíî-
ñòè B è òðåáóåòñÿ ïåðå÷èñëèòü âñå åãî îñòîâû. Î÷åâèäíî, ÷òî
ìíîæåñòâî îñòîâîâ ýòî  íåêîòîðàÿ ÷àñòü ìíîæåñòâà îñòîâ-
íûõ ïîäãðàôîâ ãðàôà G, èìåþùèõ n−1 ðåáåð. Ìàòðèöû èí-
öèäåíòíîñòè âñåõ ýòèõ ïîäãðàôîâ ëåãêî ìîãóò áûòü ïîëó÷åíû
èç ìàòðèöû B. Äåéñòâèòåëüíî, ëþáàÿ ìàòðèöà, ñîñòàâëåííàÿ
èç n−1 ðàçëè÷íûõ ñòîëáöîâ ìàòðèöû B, îïèñûâàåò íåêîòî-
ðûé (n, n−1)-ãðàô, ÿâëÿþùèéñÿ ïî îòíîøåíèþ ê G îñòîâ-
íûì ïîäãðàôîì. ×òîáû âûÿñíèòü, îñòîâ ýòîò ïîäãðàô èëè íåò,
âîñïîëüçóåìñÿ ñëåäóþùèì êðèòåðèåì.



                              50

Страницы