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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

ν=m−n+1.
e
5
, e
6
, e
7
, e
8
, e
9
s
s s
s s s
J
J
J
J
e
5
J
J
J
J
e
5
e
6
e
6
e
7
e
7
e
8
e
8
e
9
e
9
e
1
e
2
J
J
J
J
e
3
J
J
J
J
e
4
Φ
2
¹¸
º·
Φ
1
µ´
¶³
Φ
3
¹¸
º·
Φ
4
s
s s
s s s
J
J
J
J
e
5
e
6
e
7
e
8
e
9
e
1
e
2
J
J
J
J
e
3
J
J
J
J
e
4
¹¸
º·
C
1
¹¸
º·
C
2
¹¸
º·
C
3
¹¸
º·
C
4
Φ = [φ
ij
],
φ
ij
e
j
Φ
i
,
e
1
e
2
e
3
e
4
e
5
e
6
e
7
e
8
e
9
Φ =
Φ
1
Φ
2
Φ
3
Φ
4
1 0 0 0 1 1 0 0 0
0 1 0 0 0 1 1 1 0
0 0 1 0 0 1 1 0 0
0 0 0 1 0 0 1 0 1
Φ=(I
ν
|Φ
0
), I
ν
ν, Φ
0
ν×(n−1),
C
3
C
1
, C
2
, C
4
,
ãäà ðàâíà ν=m−n+1. Ýòî öèêëîìàòè÷åñêîå ÷èñëî  îäíà èç
âàæíåéøèõ õàðàêòåðèñòèê ãðàôà. ßñíî òàêæå, ÷òî âñå öèê-
ëû òàêîãî ìíîæåñòâà íåçàâèñèìû, ïîñêîëüêó êàæäûé èç íèõ
ñîäåðæèò ðåáðî, ïðèíàäëåæàùåå òîëüêî ýòîìó öèêëó.
    êà÷åñòâå ïðèìåðà íà ðèñ. 5.2 ïðåäñòàâëåíû âñå ôóíäà-
ìåíòàëüíûå öèêëû ãðàôà îòíîñèòåëüíî îñòîâà, îáðàçîâàííî-
ãî ðåáðàìè e5 , e6 , e7 , e8 , e9 (âûäåëåíû æèðíûìè ëèíèÿìè). Íà
ðèñ. 5.3 ïîêàçàíî ïîëíîå ìíîæåñòâî íåçàâèñèìûõ öèêëîâ òîãî
                    s                                        s
                   ­
                  º·J                                    º·­ J
               e1 ­ J e5                              e1 ­     J e5
                ­ Φ1 J                                 ­    C 1 J
              s e6¹¸
              ­   ¶³     Js                          s e6º·
                                                     ­   ¹¸       Js
            ­J         º·  J                       ­
                                                  º· J            ­J
                                                                 º·
           ­
       e2 ­ eJ     Φ   ­                                   C
                3 µ´ J e4                      e2 ­ J           ­ J e4
                     3                                       3
        ­­­ Φ2 J ­­e7 Φ4 J                      ­ C2 eJ  ¹¸    ­  C4 J
                                                          3    e7¹¸
      ­
      s            Js ¹¸     Js               ­
                                              s   ¹¸       Js­        Js
             e8           e9                        e8             e9
             Ðèñ. 5.2                                     Ðèñ. 5.3
æå ãðàôà, êîòîðîå íå ÿâëÿåòñÿ ìíîæåñòâîì ôóíäàìåíòàëüíûõ
öèêëîâ, òàê êàê íåò ñîîòâåòñòâóþùåãî îñòîâà17 .
   Îïèñàíèå ôóíäàìåíòàëüíûõ öèêëîâ óäîáíî âûïîëíÿòü â
âèäå ìàòðèöû Φ = [φij ], ñòðîêè êîòîðîé ñîîòâåòñòâóþò öèê-
ëàì, à ñòîëáöû  ðåáðàì, ïðè÷åì φij ðàâíî 1, åñëè ej ïðèíàä-
ëåæèò öèêëó Φi , èëè 0, åñëè íå ïðèíàäëåæèò. Êàíîíè÷åñêàÿ
ôîðìà çàïèñè ìàòðèöû ïîëó÷àåòñÿ, åñëè ïðåäâàðèòåëüíî ïðî-
íóìåðîâàòü ñíà÷àëà âñå íåîñòîâíûå ðåáðà, à çàòåì îñòîâíûå,
êàê íà ðèñ 5.2.  ýòîì ñëó÷àå ìàòðèöà âûãëÿäèò òàê:
                            e1 e2 e3 e4 e5 e6 e7 e8 e9
                                                           
                 Φ1 1 0           0   0   1   1   0   0   0
                 Φ 0 1           0   0   0   1   1   1   0 
             Φ = Φ2  0 0
                  3               1   0   0   1   1   0   0 ,
                 Φ4 0 0           0   1   0   0   1   0   1

èëè ñîêðàùåííî Φ=(Iν |Φ0 ), ãäå Iν  åäèíè÷íàÿ ìàòðèöà ïî-
ðÿäêà ν, à Φ0  ìàòðèöà ðàçìåðà ν×(n−1), îïðåäåëÿþùàÿ,
êàêèå ðåáðà îñòîâà ïðèíàäëåæàò ñîîòâåòñòâóþùåìó öèêëó.
 17 Öèêë C3 íå ìîæåò áûòü ïîëó÷åí ïóòåì ñóïåðïîçèöèè C1 , C2 , C4 , è
ïîýòîìó íåçàâèñèì.


                                      99

Страницы