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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

(B )
−7
,
B .
B
B ,
(B )
−1
, B ,
−1.
+1
−1, n−1
n
n−2
n.
s
3
s
4
s s s
5
s
7
s
6
A
A
A
s s
4
s
1
s
5
s
7
s
6
A
A
A
s
s
1
s
5
s
7
s
6
A
A
A
s s
5
s
7
s
6
A
A
A
s
s
7
s
6
    Òåïåðü ðàññìîòðèì êâàäðàòíóþ ìàòðèöó (Bá )−7 , êîòîðàÿ
ïîëó÷àåòñÿ, åñëè óäàëèòü ñåäüìóþ ñòðîêó ìàòðèöû Bá . Îïðå-
äåëèòåëü ýòîé ìàòðèöû ðàâåí 1. Ñåäüìàÿ ñòðîêà Bá ñîîò-
âåòñòâóåò ïåðâîé ñòðîêå Bà , ïîýòîìó îðåäåëèòåëü ìàòðèöû
(Bà )−1 , ïîëó÷åííîé ïðè âû÷åðêèâàíèè ïåðâîé ñòðîêè â Bà ,
(ñ ó÷åòîì ÷èñëà ïåðåñòàíîâîê ñòðîê è ñòîëáöîâ) ðàâåí −1.
    ßñíî, ÷òî âûøåîïèñàííàÿ ïîöåäóðà ïîçâîëÿåò, âûáðàâ íåêî-
òîðóþ âåðøèíó, ïîëó÷èòü òàêîé âàðèàíò íóìåðàöèè, êîãäà ýòà
âåðøèíà èìååò ìàêñèìàëüíûé íîìåð, à ìàòðèöà èíöèäåíòíî-
ñòè ãðàôà (ïîñëå óäàëåíèÿ ïîñëåäíåé ñòðîêè, ñîîòâåòñòâóþ-
ùåé âûáðàííîé âåðøèíå) îêàçûâàåòñÿ òðåóãîëüíîé ñ åäèíè-
öàìè íà ãëàâíîé äèàãîíàëè è îïðåäåëèòåëåì ðàâíûì 1. Ïî-
ýòîìó óäàëåíèå ëþáîé ñòðîêè ìàòðèöû èíöèäåíòíîñòè äåðåâà
ïîðîæäàåò êâàäðàòíóþ ìàòðèöó ñ îïðåäåëèòåëåì ðàâíûì +1
èëè −1, à ýòî çíà÷èò, ÷òî ëþáîé ìèíîð ïîðÿäêà n−1 ìàòðè-
öû èíöèäåíòíîñòè äåðåâà ïî àáñîëþòíîé âåëè÷èíå ðàâåí 1.
    Êîä Ïðþôåðà. Êàæäîå äåðåâî, èìåþùåå n âåðøèí,
ìîæåò áûòü îäíîçíà÷íî îïèñàíî ÷èñëîâûì êîäîì, ñîäåðæà-
ùèì n−2 ýëåìåíòîâ è íàçûâàåìûì êîäîì Ïðþôåðà.
    Àëãîðèòì ïîëó÷åíèÿ êîäà ñîñòîèò â ñëåäóþùåì. Ïóñòü âåð-
øèíû äåðåâà ïîìå÷åíû (ïðîíóìåðîâàíû) ÷èñëàìè îò 1 äî n.
Îòûñêèâàåì âåðøèíó ñòåïåíè 1 ñ íàèìåíüøèì íîìåðîì è âêëþ-
÷àåì â êîä íîìåð ñìåæíîé ñ íåé âåðøèíû, ïîñëå ÷åãî óäàëÿåì
íàéäåííóþ âåðøèíó (âìåñòå ñ ðåáðîì). Ñ ïîëó÷èâøèìñÿ ïîä-
ãðàôîì âûïîëíÿåì òó æå îïåðàöèþ, ïîâòîðÿÿ åå, ïîêà íå îñ-
   3s    4s    3s    4s          4s
                              
2s    s1 s5      s1 s5      s1 s5      s1 s5                s5
       A          A          A         A                
   s As       s As       s As       s As      s       s
   7     6     7     6     7     6     7    6     7       6
     a           á           â           ã            ä
                           Ðèñ. 3.7
òàíåòñÿ òîëüêî îäíî ðåáðî. Ïðîöåññ ôîðìèðîâàíèÿ êîäà îòðà-
æàåò ðèñ. 3.7. Íîìåð âåðøèíû, óäàëÿåìîé íà î÷åðåäíîì øàãå,
çàêëþ÷åí â ðàìêó.  çàäàííîì ãðàôå (ðèñ. 3.7,à) ñðåäè âåð-
øèí åäèíè÷íîé ñòåïåíè ìèíèìàëüíûé íîìåð ó âåðøèíû 2. Ñ


                             48

Страницы