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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Q, i
1
, i
2
, . . . , i
n
h
1 3 −1
−2 0 1
i
·
2 −1
1 1
−1 0
¸
,
|PQ| =
¯
¯
¯
1 3
−2 0
¯
¯
¯
·
¯
¯
¯
2 −1
1 1
¯
¯
¯
+
¯
¯
¯
1 −1
−2 1
¯
¯
¯
·
¯
¯
¯
2 −1
−1 0
¯
¯
¯
+
¯
¯
¯
3 −1
0 1
¯
¯
¯
·
¯
¯
¯
1 1
−1 0
¯
¯
¯
=22.
PQ=
h
1 3 −1
−2 0 1
i
·
·
2 −1
1 1
−1 0
¸
=
h
6 2
−5 2
i
|PQ|=22
Q=P
T
,
|PP
T
|=M
2
1
+M
2
2
+ . . . +M
2
C
n
m
,
n
n×m, n≤m,
n.
n
B
−i
|B
−i
×B
T
−i
|.
¯
¯
¯
B
−1
×B
T
−1
¯
¯
¯
=
¯
¯
¯
¯
¯
¯
¯
·
−1 0 1 1 0
0 0 0 −1 1
0 −1 −1 0 −1
¸
×
−1 0 0
0 0 −1
1 0 −1
1 −1 0
0 1 −1
¯
¯
¯
¯
¯
¯
¯
=
¯
¯
¯
¯
3 −1 −1
−1 2 −1
−1 −1 3
¯
¯
¯
¯
=8
æå ïîðÿäêà ìàòðèöû Q, îáðàçîâàííûé ñòðîêàìè i1 , i2 , . . . , in
ýòîé ìàòðèöû.
                       h         i       · 2 −1 ¸
                         1 3 −1
   Ïóñòü, íàïðèìåð, P = −2 0 1 è Q =        1 1 , òî-
                                                          −1    0
ãäà â ñîîòâåòñòâèè ñ òåîðåìîé Áèíå-Êîøè èìååì:
        ¯     ¯ ¯       ¯ ¯        ¯ ¯        ¯ ¯       ¯ ¯        ¯
        ¯ 1 3 ¯ ¯ 2 −1 ¯ ¯ 1 −1 ¯ ¯ 2 −1 ¯ ¯ 3 −1 ¯ ¯ 1 1 ¯
|PQ| = ¯ −2 0 ¯ · ¯ 1 1 ¯ + ¯ −2 1 ¯ · ¯ −1 0 ¯ + ¯ 0 1 ¯ · ¯ −1 0 ¯ =22.

  Ïåðåìíîæèâ ìàòðèöû íåïîñðåäñòâåííî, ïîëó÷èì:
    h         i · 2 −1 ¸ h      i
       1 3 −1               6 2
PQ= −2 0 1 ·               −5 2 è, çíà÷èò, |PQ|=22 .
                  1 1 =
                         −1    0

   Åñëè Q=PT , òî â ñèëó ðàâåíñòâà ñîîòâåòñòâóþùèõ ìèíî-
ðîâ ìàòðèö-ñîìíîæèòåëåé èìååì:

                   |PPT |=M21 +M22 + . . . +M2Cmn ,

ãäå ñïðàâà îò çíàêà ðàâåíñòâà ñòîèò ñóììà êâàäðàòîâ âñåõ
ìèíîðîâ ïîðÿäêà n ìàòðèöû P. Ýòî ïîçâîëÿåò óòâåðæäàòü,
÷òî îïðåäåëèòåëü êâàäðàòà ìàòðèöû ïîðÿäêà n×m, ãäå n≤m,
ðàâåí ñóììå êâàäðàòîâ âñåõ åå ìèíîðîâ ïîðÿäêà n. Ñëåäîâà-
òåëüíî, â òîì ñëó÷àå, êîãäà ëþáîé ìèíîð ïîðÿäêà n â ìàòðèöå
ïðèíèìàåò îäíî èç òðåõ çíà÷åíèé: 1, 0 èëè 1, îïðåäåëèòåëü
êâàäðàòà ìàòðèöû îêàçûâàåòñÿ ðàâíûì ÷èñëó íåíóëåâûõ ìè-
íîðîâ. Èç ýòîãî, â ñâîþ î÷åðåäü, ñëåäóåò, ÷òî âìåñòî ïåðåáîðà
ìèíîðîâ ìàòðèöû B−i äëÿ ïîëó÷åíèÿ ÷èñëà îñòîâîâ ãðàôà
                                               T
äîñòàòî÷íî ïîäñ÷èòàòü îïðåäåëèòåëü |B−i ×B−i |.
   Íàïðèìåð, äëÿ ãðàôà, èçîáðàæåííîãî íà ðèñ. 3.8, èìååì:
             ¯                   −1 0 0 ¯
             ¯·                              ¯ ¯
¯          ¯ ¯ −1 0 1 1 0 ¸        0  0 −1   ¯ ¯ 3 −1 −1 ¯¯
¯       T  ¯ ¯                            ¯
¯B−1×B−1 ¯=¯ 0 0 0 −1 1 × 1 0 −1 ¯=¯¯ −1 2 −1 ¯¯ =8 ,
             ¯ 0 −1 −1 0 −1        1 −1 0 ¯ −1 −1 3
             ¯                     0 1 −1
                                             ¯

÷òî ñîâïàäàåò ñ êîëè÷åñòâîì îñòîâîâ, íàéäåííûì ðàíåå.



                                   54

Страницы