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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

v
1
. C
1
. C
1
G,
G
1
(V, E−EC
1
),
G C
1
.
G
C
1
. G
C
1
G
1
v
2
G
1
C
1
,
G
1
. G
1
C
2
.
C
1
C
2
,
s
v
1
s
s
v
2
s
s
sss
-
@
@R
@
@R
@
@I
6
C
1
C
2
C
1
= v
1
→ . . . →v
2
→ . . . →v
1
C
2
= v
2
→ . . . →v
2
C
1
∪C
2
= v
1
→ . . . →v
2
| {z }
C
0
1
→ . . . → v
2
→ . . . →v
1
| {z }
C
00
1
C
2
z }| {
C
1
∪C
2
G
2
(V, E−EC
1
−EC
2
),
C
3
, C
1
C
2
¢
deg
+
v = deg
−
v ∀v ∈ V
deg
+
v = deg
−
v ∀v 6= (u w)
deg
+
u = deg
−
u+1, deg
−
w = deg
+
w+1
u w
èñïîëüçîâàííîå. Áóäåì ïîâòîðÿòü ýòó îïåðàöèþ, êàæäûé ðàç
âûáèðàÿ íîâîå ðåáðî, ïîêà íå îêàæåìñÿ â èñõîäíîé âåðøèíå
v1 . Îáîçíà÷èì íàéäåííûé öèêë êàê C1 . Åñëè C1 âêëþ÷àåò
âñå ðåáðà ãðàôà G, òî ýòî è áóäåò òðåáóåìûé ýéëåðîâ öèêë.
 ïðîòèâíîì ñëó÷àå ðàññìîòðèì ãðàô G1 (V, E−EC1 ), ïîëó-
÷àþùèéñÿ ïðè óäàëåíèè èç G âñåõ ðåáåð, îòíîñÿùèõñÿ ê C1 .
Ýòîò ãðàô ìîæåò áûòü êàê ñâÿçíûì, òàê è íåñâÿçíûì, íî ëþ-
áàÿ åãî êîìïîíåíòà â ñèëó ñâÿçíîñòè G èìååò õîòÿ áû îäíó
îáùóþ âåðøèíó ñ ãðàôîì C1 . Òàê êàê êàæäàÿ âåðøèíà â G
è C1 èìååò ÷åòíóþ ñòåïåíü, òî è â G1 ñòåïåíè âñåõ âåðøèí
äîëæíû áûòü ÷åòíûìè. Ïóñòü v2 îáùàÿ âåðøèíà G1 è C1 , íå
ÿâëÿþùàÿñÿ èçîëèðîâàííîé â ãðàôå G1 . Íàéäåì â G1 öèêë,
ñîäåðæàùèé ýòó âåðøèíó, è îáîçíà÷èì åãî êàê C2 . Îáúåäè-
íèì öèêëû C1 è C2 , êàê ïîêàçàíî íà ðèñ. 5.8. Åñëè öèêë
 vs1 -s       s      C1 = v1 → . . . →v2 → . . . →v1
  6    @ v2  @
    C1 @ Rs C @
               2
                Rs   C2 = v2 → . . . →v2         C2
          @
          I                               z    }|      {
 s    s    @s       C1 ∪C2 = v1 → . . . →v2 → . . . → v2 → . . . →v1
                              |    {z      }           |    {z      }
                                     C10                    C100
                        Ðèñ. 5.8
C1 ∪C2 ýéëåðîâ, òî ïðîöåññ çàâåðøåí.  ïðîòèâíîì ñëó÷àå
ñëåäóåò ïåðåéòè ê ðàññìîòðåíèþ ãðàôà G2 (V, E−EC1 −EC2 ),
îòûñêàòü â íåì öèêë C3 , êîòîðûé ñëåäóåò îáúåäèíèòü ñ C1 è
C2 è ò. ä. Òàê êàê êàæäûé ðàç êîëè÷åñòâî íåèñïîëüçîâàííûõ
ðåáåð óìåíüøàåòñÿ, òî îïèñàííûé ïðîöåññ êîíå÷åí è äîëæåí
çàêîí÷èòüñÿ ïîñòðîåíèåì ýéëåðîâà öèêëà. ¢
   Àíàëîãè÷íàÿ òåîðåìà äëÿ îðãðàôîâ ôîðìóëèðóåòñÿ òàê:
   Òåîðåìà 5.2 Ñâÿçíûé îðèåíòèðîâàííûé ãðàô ñîäåðæèò
ýéëåðîâ îðöèêë (îðöåïü) òîãäà è òîëüêî òîãäà, êîãäà ïîëó-
ñòåïåíè èñõîäà è ïîëóñòåïåíè çàõîäà âñåõ âåðøèí óäîâëå-
òâîðÿþò óñëîâèÿì:
deg+ v = deg− v ∀v ∈ V  â ñëó÷àå îðöèêëà;
deg+ v = deg− v ∀v 6= (u èëè w) è
deg+ u = deg− u+1, deg− w = deg+ w+1  â ñëó÷àå îðöåïè,
ãäå u  íà÷àëüíàÿ, w  êîíå÷íàÿ âåðøèíû öåïè.



                              104

Страницы