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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

|B
−i
×B
T
−i
|
k
i,i
n≥2
K
n
.
n)
n−1)
K(K
n
)=
n−1 −1 . . . −1
−1 n−1 . . . −1
−1 −1 . . . n−1
, A
i,i
=
¯
¯
¯
¯
¯
¯
¯
n−1 −1 . . . −1
−1 n−1 . . . −1
−1 −1 . . . n−1
¯
¯
¯
¯
¯
¯
¯
.
n−2,
A
i,i
=
¯
¯
¯
¯
¯
¯
¯
n−1 −1 . . . −1
−n n . . . 0
−n 0 . . . n
¯
¯
¯
¯
¯
¯
¯
=
¯
¯
¯
¯
¯
¯
¯
1 −1 . . . −1
0 n . . . 0
0 0 . . . n
¯
¯
¯
¯
¯
¯
¯
=n
n−2
.
K
n
n
n−2
,
n
n
n
n−2
.
n n
                                         T
   Ïîñêîëüêó îïðåäåëèòåëü |B−i ×B−i | ðàâåí àëãåáðàè÷åñêî-
ìó äîïîëíåíèþ ýëåìåíòà ki,i ìàòðèöû Êèðõãîôà, òî â ñèëó
ñâîéñòâà ïîñëåäíåé9 ðåøåíèå çàäà÷è î ÷èñëå îñòîâîâ â îêîí÷à-
òåëüíîì âèäå ìîæåò áûòü ñôîðìóëèðîâàíî â âèäå ñëåäóþùåé
òåîðåìû, èçâåñòíîé êàê ìàòðè÷íàÿ òåîðåìà î äåðåâüÿõ, èëè
òåîðåìà Êèðõãîôà.
   Òåîðåìà 3.2 ×èñëî îñòîâíûõ äåðåâüåâ ñâÿçíîãî ãðàôà ïî-
ðÿäêà n≥2 ðàâíî àëãåáðàè÷åñêîìó äîïîëíåíèþ ëþáîãî ýëåìåí-
òà ìàòðèöû Êèðõãîôà.
   Âîñïîëüçóåìñÿ òåîðåìîé äëÿ îïðåäåëåíèÿ ÷èñëà îñòîâîâ
ïîëíîãî ãðàôà Kn .  ýòîì ñëó÷àå ìàòðèöà Êèðõãîôà (ïîðÿä-
êà n) è àëãåáðàè÷åñêîå äîïîëíåíèå ëþáîãî åå äèàãîíàëüíîãî
ýëåìåíòà (ïîðÿäêà n−1) âûãëÿäÿò òàê:
                                        ¯                  ¯
              n−1 −1 . . . −1             ¯ n−1 −1 . . . −1 ¯
                                          ¯ −1 n−1 . . . −1 ¯
             −1 n−1 . . . −1            ¯                  ¯
   K(Kn )=  ..    .. . .   ..  , Ai,i = ¯ ..   .. . .   .. ¯ .
                .   .     . .             ¯ .     .     . . ¯
               −1 −1 . . . n−1            ¯ −1 −1 . . . n−1 ¯
  Âû÷òÿ ïåðâóþ ñòðî÷êó îïðåäåëèòåëÿ èç âñåõ íèæåëåæà-
ùèõ è ïðèáàâèâ ê ïåðâîìó ñòîëáöó îñòàëüíûå n−2, ïîëó÷èì:
          ¯                  ¯ ¯                 ¯
          ¯ n−1 −1 . . . −1 ¯ ¯ 1 −1 . . . −1 ¯
          ¯ −n n . . . 0 ¯ ¯ 0 n . . . 0 ¯
          ¯                  ¯ ¯                 ¯
   Ai,i = ¯ ..   .. ..    .. ¯ = ¯ .. .. ..   .. ¯ =nn−2 .
          ¯ .     .    .   . ¯   ¯ . .      .  . ¯
          ¯ −n 0 . . . n ¯ ¯ 0 0 . . . n ¯
   Òàêèì îáðàçîì, ÷èñëî îñòîâîâ ïîëíîãî ãðàôà Kn ðàâíî
 n−2
n , à ïîñêîëüêó îñòîâû ïîëíîãî ïîìå÷åííîãî ãðàôà ñîñòàâ-
ëÿþò âñå ìíîæåñòâî ïîìå÷åííûõ äåðåâüåâ ñ n âåðøèíàìè, òî
ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà Êýëè.
   Òåîðåìà 3.3 ×èñëî ðàçëè÷íûõ ïîìå÷åííûõ äåðåâüåâ ñ n
âåðøèíàìè ðàâíî nn−2 .
   Ýòîò ðåçóëüòàò ìîæåò áûòü ëåãêî ïîëó÷åí íà îñíîâå êî-
äà Ïðþôåðà. Äåéñòâèòåëüíî, ïîñêîëüêó ëþáîå äåðåâî, èìåþ-
ùåå n âåðøèí, ïîìå÷åííûõ ÷èñëàìè îò 1 äî n , îäíîçíà÷íî
  9 Ðàâåíñòâî   àëãåáðàè÷åñêèõ äîïîëíåíèé ýëåìåíòîâ ìàòðèöû.


                                  55

Страницы