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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

S,
S S
1
− S
6
.
s s s
s s s
e
1
e
2
e
3
e
4
e
5
e
6
e
7
S
µ ´
S
²
s s s
s s s
e
1
e
2
e
3
e
4
e
5
e
6
e
7
!
S
1
±°
S
2
"
S
3
Ã
S
4
#
S
5
²¯
S
6
S
1
= {e
1
, e
3
} , S
2
= {e
1
, e
2
, e
4
} , S
3
= {e
2
, e
5
} ,
S
4
= {e
3
, e
6
} , S
5
= {e
4
, e
6
, e
7
} , S
6
= {e
5
, e
7
} .
S={e
1
, e
5
, e
6
, e
7
}
{e
1
, e
6
} {e
5
, e
7
}
m
j
e
j
S
1
− S
6
S
1
= 1010000 , S
2
= 1101000 , S
3
= 0100100 ,
S
4
= 0010010 , S
5
= 0001011 , S
6
= 0000101 .
S
1
−S
6
S
S=S
2
⊕S
3
⊕S
5
.
   Ñ ïîíÿòèåì öèêëà òåñíî ñâÿçàíî ïîíÿòèå ðàçðåçà  ìíîæå-
ñòâà ðåáåð S, óäàëåíèå êîòîðûõ ïðèâîäèò ê íåñâÿçíîìó ãðà-
ôó. Ïðèìåðû ðàçðåçîâ äàíû íà ðèñ. 5.4,a,á  ýòî ìíîæåñòâà
ðåáåð, ïåðåñåêàåìûõ ëèíèÿìè S , S1 − S6 .
         s   e1 S s    e2   s                  s  e1 S2s e2 s
                                                  !  ±°"
                                            S1                  S3
    e3            e4   e5                    e3      e4       e5
                      ² S                   S4    à  ²¯#        S
         s       s     s                        s       s    s 6
             e6    e7                             e6 S    e7
                µ     ´                                5
                 à                                         á
                                 Ðèñ. 5.4
   Ðàçðåç íàçûâàåòñÿ ïðîñòûì èëè ïðàâèëüíûì, åñëè íèêàêîå
åãî ñîáñòâåííîå ïîäìíîæåñòâî íå ÿâëÿåòñÿ ðàçðåçîì. Èíûìè
ñëîâàìè, ïðîñòîé ðàçðåç ÿâëÿåòñÿ ìèíèìàëüíûì ðàçðåçîì è
âñåãäà ðàçáèâàåò ãðàô íà äâå êîìïîíåíòû. Íåêîòîðîå ìíîæå-
ñòâî ïðîñòûõ ðàçðåçîâ ãðàôà ïîêàçàíî íà ðèñ. 5.4,á :
             S1 = {e1 , e3 } ,    S2 = {e1 , e2 , e4 } ,       S3 = {e2 , e5 } ,
             S4 = {e3 , e6 } ,    S5 = {e4 , e6 , e7 } ,       S6 = {e5 , e7 } .
Ðàçðåç S={e1 , e5 , e6 , e7 } íà ðèñ. 5.4,à ïðîñòûì íå ÿâëÿåòñÿ,
òàê êàê ñîñòîèò èç äâóõ ïðîñòûõ {e1 , e6 } è {e5 , e7 } .
   Ïî àíàëîãèè ñ öèêëàìè áóäåì îïèñûâàòü ðàçðåçû m-ðàç-
ðÿäíûìè äâîè÷íûìè êîäàìè, â êîòîðûõ ðàçðÿä j ðàâåí 1,
åñëè ðåáðî ej ïðèíàäëåæèò ðàçðåçó, è 0, åñëè íå ïðèíàäëåæèò.
 ýòîì ñëó÷àå îïèñàíèå ðàçðåçîâ S1 − S6 èìååò âèä:
             S1 = 1010000 ,        S2 = 1101000 ,          S3 = 0100100 ,
             S4 = 0010010 ,        S5 = 0001011 ,          S6 = 0000101 .
Ëåãêî çàìåòèòü, ÷òî êîä ëþáîãî èç ýòèõ øåñòè ðàçðåçîâ ìîæåò
áûòü ïîëó÷åí êàê ñóììà îñòàëüíûõ ïÿòè ïî ìîäóëþ 2, ò. å. ðàç-
ðåçû S1 −S6 çàâèñèìû. Åñëè æå îãðàíè÷èòüñÿ ëþáûìè ïÿòüþ
èç íèõ, òî ïîëó÷èì ìíîæåñòâî ïðîñòûõ íåçàâèñèìûõ ðàçðå-
çîâ, ñ ïîìîùüþ êîòîðûõ ìîæíî ñôîðìèðîâàòü ëþáîé ðàçðåç
â ãðàôå. Òàê, ðàçðåç S íà ðèñ. 5.4,a ìîæíî ðàññìàòðèâàòü êàê
ñóììó S=S2 ⊕S3 ⊕S5 .
    Ñðåäè ìíîæåñòâ íåçàâèñèìûõ ðàçðåçîâ âûäåëÿþò ìíîæå-
ñòâà ôóíäàìåíòàëüíûõ (áàçèñíûõ) ðàçðåçîâ.



                                      100

Страницы