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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

(n, m) m
j
e
j
E={e
1
, e
2
, . . . , e
10
}, (e
1
, e
2
, e
6
, e
9
, e
8
, e
4
),
C=1101010110
s s s s
s s s s
e
1
e
2
e
3
e
4
e
5
e
6
e
7
e
8
e
9
e
10
²
±
¯
°
C
1
²
±
¯
°
C
2
²
±
¯
°
C
3
º
¹
·
¸
A
A
C
4
µ
³
´
A
A
C
5
Â
Á
¿
À
A
A
C
6
C
1
− C
6
.
C
6
=C
1
⊕C
2
⊕C
3
, C
4
=C
1
⊕C
2
C
5
=C
2
⊕C
3
.
C
1
, C
2
C
3
T
T
T.
    5. Öèêëû
    5.1. Ôóíäàìåíòàëüíûå öèêëû è ðàçðåçû
   Áóäåì ïðåäñòàâëÿòü öèêëû (n, m)-ãðàôà â âèäå m -ðàçðÿä-
íûõ äâîè÷íûõ êîäîâ, â êîòîðûõ ðàçðÿä j ðàâåí 1, åñëè ðåá-
ðî ej ïðèíàäëåæèò öèêëó, è 0, åñëè ðåáðî öèêëó íå ïðèíàä-
ëåæèò. Ïóñòü, íàïðèìåð, ìíîæåñòâî ðåáåð íåêîòîðîãî ãðàôà
E={e1 , e2 , . . . , e10 }, è â ãðàôå åñòü öèêë (e1 , e2 , e6 , e9 , e8 , e4 ), òî-
ãäà ñîîòâåòñòâóþùèé êîä çàïèøåòñÿ êàê C=1101010110 .
    îáùåì ñëó÷àå ãðàô ìîæåò ñîäåðæàòü ìíîæåñòâî öèêëîâ.
Òàê, â ãðàôå, èçîáðàæåííîì íà ðèñ. 5.1, ñóùåñòâóåò øåñòü
                    sÂe1 s e2 s e3 s
                     º              ·        ¿
                     ² ¯¶     ²¯       ²¯    ³
                  e4 C1 e5     C2 e 6 C3 e 7
                     ±
                     ¹    °  µ±     °
                                    ¸  ±°    ´
                    sÁ      s        sA e    À
                                             s
                      e8AA    A e 9    A  10
                           C4 C6         C5
                              Ðèñ. 5.1

öèêëîâ C1 − C6 . Îäíàêî îíè íå ÿâëÿþòñÿ íåçàâèñèìûìè, ïî-
ñêîëüêó ëþáîé èç ýòèõ öèêëîâ ìîæåò áûòü ïðåäñòàâëåí êàê
ñóïåðïîçèöèÿ äðóãèõ (ñ ïîìîùüþ îïåðàöèè ïîðàçðÿäíîãî ñëî-
æåíèÿ ñîîòâåòñòâóþùèõ êîäîâ ïî ìîäóëþ äâà), â ÷àñòíîñòè,
öèêë C6 =C1 ⊕C2 ⊕C3 , öèêë C4 =C1 ⊕C2 è öèêë C5 =C2 ⊕C3 . Â
ýòèõ ïðèìåðàõ öèêëû C1 , C2 è C3 âûñòóïàþò êàê "ïîëíîå"
ìíîæåñòâî íåçàâèñèìûõ öèêëîâ, òàê êàê íà èõ îñíîâå ìîæ-
íî ïîëó÷èòü ëþáîé èç îñòàëüíûõ öèêëîâ ãðàôà. Ñðåäè òàêèõ
ìíîæåñòâ íåçàâèñèìûõ öèêëîâ âûäåëÿþò ìíîæåñòâà ôóíäà-
ìåíòàëüíûõ (áàçèñíûõ) öèêëîâ16 .
   Ìíîæåñòâîì ôóíäàìåíòàëüíûõ öèêëîâ ãðàôà îòíîñèòåëü-
íî îñòîâà T ýòîãî ãðàôà ïðèíÿòî íàçûâàòü ìíîæåñòâî öèê-
ëîâ, êàæäûé èç êîòîðûõ ïîëó÷àåòñÿ ïðè äîáàâëåíèè ê T íåêî-
òîðîãî ðåáðà ãðàôà, íå ïðèíàäëåæàùåãî T.
   Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî ìîùíîñòü ìíîæåñòâà ôóíäà-
ìåíòàëüíûõ öèêëîâ íå çàâèñèò îò âûáðàííîãî îñòîâà è âñå-
  16 Ãîâîðÿò   òàêæå "ôóíäàìåíòàëüíîå (áàçèñíîå) ìíîæåñòâî öèêëîâ".


                                       98

Страницы