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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

M
2
M
9
,
s
v
1
s
v
2
s
v
3
s
v
4
e
1
e
2
e
3
M
1
=0
s
v
1
s
v
2
s
v
3
s
v
4
e
1
e
2
e
4
M
2
=1
s
v
1
s
v
2
s
v
3
s
v
4
e
1
e
2
e
5
M
3
= − 1
s
v
1
s
v
2
s
v
3
s
v
4
e
1
e
4
e
3
M
4
=1
s
v
1
s
v
2
s
v
3
s
v
4
e
1
e
3
e
5
M
5
= − 1
s
v
1
s
v
2
s
v
3
s
v
4
e
1
e
4
e
5
M
6
= − 1
s
v
1
s
v
2
s
v
3
s
v
4
e
2
e
4
e
3
M
7
=1
s
v
1
s
v
2
s
v
3
s
v
4
e
2
e
3
e
5
M
8
= − 1
s
v
1
s
v
2
s
v
3
s
v
4
e
2
e
4
e
5
M
9
= − 1
s
v
1
s
v
2
s
v
3
s
v
4
e
4
e
3
e
5
M
10
=0
B
−1
.
P n×m, Q
m×n, n≤m,
PQ n
P Q.
n P,
i
1
, i
2
, . . . , i
n
,
íîðàìè M2  M9 ,  îñòîâû. Ýòî íàãëÿäíî ïîäòâåðæäàåò è
ðèñ. 3.9, ãäå ïðåäñòàâëåíû âñå òðåõðåáåðíûå îñòîâíûå ïîäãðà-
ôû ðàññìàòðèâàåìîãî ãðàôà è çíà÷åíèÿ ñîîòâåòñòâóþùèõ èì
v1 s   e1 sv2      v1 s   e1 sv2    v1 s    e1 sv2      v1 s   e1 sv2    v1 s   e1 sv2
e2      e3         e2          e4   e2                         e3 e4            e3
v4 s     sv3       v4 s       sv3   v4 s e5 sv3         v4 s      sv3    v4 s e5 sv3
   M1 =0              M2 =1           M3 = − 1             M4 =1           M5 = − 1
v1 s   e1 sv2      v1 s       sv2   v1 s          sv2   v1 s       sv2   v1 s        sv2
              e4   e2     e3 e4     e2       e3         e2          e4           e3 e4
v4 s e5      sv3   v4 s      sv3    v4 s e5 sv3         v4 s e5    sv3   v4 s  5e sv3
  M6 = − 1            M7 =1           M8 = − 1            M9 = − 1          M10 =0

                                         Ðèñ. 3.9
ìèíîðîâ òðåòüåãî ïîðÿäêà ìàòðèöû B−1 . Òîëüêî âîñåìü èç
äåñÿòè ïîäãðàôîâ ÿâëÿþòñÿ îñòîâàìè, è èìåííî äëÿ íèõ àá-
ñîëþòíàÿ âåëè÷èíà ìèíîðà ðàâíà 1.

       3.3.2. Ïåðåñ÷åò îñòîâíûõ äåðåâüåâ
   Çàäà÷à îïðåäåëåíèÿ ÷èñëà îñòîâíûõ äåðåâüåâ ãðàôà åñòå-
ñòâåííûì îáðàçîì ðåøàåòñÿ â ïðîöåññå ïåðå÷èñëåíèÿ îñòîâîâ.
Îäíàêî, åñëè òðåáóåòñÿ çíàòü òîëüêî êîëè÷åñòâî îñòîâîâ, à
ïîëó÷àòü ñàìè îñòîâû íåò íåîáõîäèìîñòè, èçëîæåííûé âûøå
ïîäõîä íå ðàöèîíàëåí.
   Ýôôåêòèâíîå ðåøåíèå ðàññìàòðèâàåìîé çàäà÷è ìîæíî ïî-
ëó÷èòü íà îñíîâå òåîðåìû ÁèíåÊîøè äëÿ îïðåäåëèòåëÿ ïðî-
èçâåäåíèÿ äâóõ ìàòðèö, êîòîðàÿ ôîðìóëèðóåòñÿ òàê.
       Òåîðåìà 3.1 Åñëè P ìàòðèöà ïîðÿäêà n×m, à Q ìàò-
ðèöà ïîðÿäêà m×n, ãäå n≤m, òî îïðåäåëèòåëü ìàòðèöû
PQ ðàâåí ñóììå ïðîèçâåäåíèé êàæäîãî ìèíîðà ïîðÿäêà n
ìàòðèöû P íà ñîîòâåòñòâóþùèé ìèíîð ìàòðèöû Q.
   Ñîîòâåòñòâóþùèì äëÿ ìèíîðà ïîðÿäêà n ìàòðèöû P, îá-
ðàçîâàííîãî åå ñòîëáöàìè i1 , i2 , . . . , in , ÿâëÿåòñÿ ìèíîð òîãî


                                             53

Страницы