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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

T
T.
ρ=n−1.
S=[s
ij
],
s
ij
e
j
S
i
,
s
s s
s s s
J
J
J
J
e
5
J
J
J
J
e
6
e
7
e
8
e
9
e
1
e
2
J
J
J
J
e
3
J
J
J
J
e
4
ª
º·
©
ª
e
4
S
1
S
2
S
3
S
4
S
5
e
1
e
2
e
3
e
4
e
5
e
6
e
7
e
8
e
9
S =
S
1
S
2
S
3
S
4
S
5
1 0 0 0 1 0 0 0 0
1 1 1 0 0 1 0 0 0
0 1 1 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 1
S=(S
0
|I
ρ
), I
ρ
ρ,
S
0
ρ×ν.
Φ S.
i Φ
j S, ΦS
T
≡ 0 (mod 2).
   Ìíîæåñòâîì ôóíäàìåíòàëüíûõ ðàçðåçîâ ãðàôà îòíîñèòåëü-
íî íåêîòîðîãî îñòîâà T ýòîãî ãðàôà íàçûâàþò ìíîæåñòâî
ïðîñòûõ ðàçðåçîâ, êàæäûé èç êîòîðûõ ñîäåðæèò òîëüêî îä-
íî ðåáðî, ïðèíàäëåæàùåå T.
   Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî ìîùíîñòü ìíîæåñòâà ôóíäà-
ìåíòàëüíûõ ðàçðåçîâ íå çàâèñèò îò âûáðàííîãî îñòîâà è ðàâ-
íà ρ=n−1. Ýòî êîöèêëîìàòè÷åñêîå ÷èñëî ãðàôà. Òàêîå íà-
çâàíèå îáúÿñíÿåòñÿ òåì, ÷òî íàðÿäó ñ òåðìèíîì "ôóíäàìåí-
òàëüíûé ðàçðåç" èñïîëüçóþò è òåðìèí "êîöèêë", ïîä÷åðêèâàÿ
ýòèì ñâÿçü ôóíäàìåíòàëüíûõ öèêëîâ è ðàçðåçîâ.
   Îïèñàíèå ôóíäàìåíòàëüíûõ ðàçðåçîâ óäîáíî âûïîëíÿòü â
âèäå ìàòðèöû S=[sij ], ñòðîêè êîòîðîé ñîîòâåòñòâóþò ðàçðå-
çàì, à ñòîëáöû  ðåáðàì, ïðè÷åì sij ðàâíî 1, åñëè ej ïðèíàä-
ëåæèò ðàçðåçó Si , èëè 0, åñëè íå ïðèíàäëåæèò. Êàíîíè÷åñêàÿ
ôîðìà çàïèñè ìàòðèöû ïîëó÷àåòñÿ, åñëè ïðîíóìåðîâàòü ñíà-
÷àëà âñå íåîñòîâíûå ðåáðà, à çàòåì îñòîâíûå. Òîãäà ìàòðèöà
ôóíäàìåíòàëüíûõ ðàçðåçîâ ãðàôà íà ðèñ. 5.5,à âûãëÿäèò êàê
            S1 s                           e1   e2   e3   e4   e5   e6   e7   e8   e9
              ­
              ­J ª                S1      1    0    0    0    1    0    0    0    0 
         e1­ Je5
      S2 s­ ©                     S2      1    1    1    0    0    1    0    0    0 
          ­ e6 J  Js                                                              0 
                              S = S3      0    1    1    1    0    0    1    0       
   S3 ­ ­J ª       J              S4       0    1    0    0    0    0    0    1    0
    e2 ­· e3J    e7 Jº
                     e4           S5       0    0    0    1    0    0    0    0    1
 S4 ­                   S
    s­       JJs     Js 5
                     J
         e8       e9
            à                                                       á
                            Ðèñ. 5.5

íà ðèñ. 5.5,á, èëè ñîêðàùåííî S=(S0 |Iρ ), ãäå Iρ  åäèíè÷-
íàÿ ìàòðèöà ïîðÿäêà ρ, îïðåäåëÿþùàÿ, êàêîå ðåáðî îñòîâà
ïðèíàäëåæèò ðàçðåçó, à S0  ìàòðèöà ðàçìåðà ρ×ν.
   Óñòàíîâèì ñâÿçü ìàòðèö Φ è S. ×èñëî îáùèõ ðåáåð ëþáî-
ãî öèêëà è ëþáîãî ðàçðåçà ìîæåò áûòü òîëüêî ÷åòíûì (â òîì
÷èñëå è íóëåâûì), à ýòî çíà÷èò, ÷òî êîëè÷åñòâî åäèíèö, ñòîÿ-
ùèõ íà îäèíàêîâûõ ïîçèöèÿõ â ñòðîêå i ìàòðèöû Φ è â ñòðî-
êå j ìàòðèöû S, ÷åòíî. Ñëåäîâàòåëüíî, ΦST ≡ 0 (mod 2).
Ñ äðóãîé ñòîðîíû, åñëè ïðèíÿòü âî âíèìàíèå áëî÷íóþ



                                 101

Страницы