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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Φ S,
ΦS
T
=(I
ν
|Φ
0
)(S
0
|I
ρ
)
T
=(I
ν
|Φ
0
)
Ã
S
0
T
I
ρ
T
!
=I
ν
S
0
T
+Φ
0
I
ρ
=S
0
T
+Φ
0
,
I
ν
I
ρ
ν ρ
ΦS
T
≡ 0 (mod 2), S
0
T
+Φ
0
=0,
S
0
T
=Φ
0
,
r
v
1
r
v
2
r
v
6
r
v
5
r
v
4
r
v
3
@
@
@
@
@
@
@
G
1
r
v
1
r
v
2
r
v
5
r
v
4
r
v
3
@
@
@
@
@
G
2
r
v
1
r
v
2
r
v
4
r
v
3
@
@
@
G
3
G
1
(v
1
, v
2
, v
3
, v
4
, v
1
, v
3
, v
5
, v
2
, v
4
, v
6
, v
1
);
G
2
(v
1
, v
2
, v
3
, v
4
, v
1
, v
3
, v
5
, v
2
, v
4
), G
2
G
3
ñòðóêòóðó Φ è S, òî, ïî ïðàâèëàì óìíîæåíèÿ áëî÷íûõ ìàò-
ðèö, ìîæíî çàïèñàòü                 Ã      !
                                        0T
                                      S
ΦST =(Iν |Φ0 )(S0 |Iρ )T =(Iν |Φ0 )      T
                                             =Iν S0 T +Φ0 Iρ =S0 T +Φ0 ,
                                      Iρ
ãäå Iν è Iρ  åäèíè÷íûå ìàòðèöû ïîðÿäêà ν è ρ ñîîòâåò-
ñòâåííî, à îïåðàöèè âûïîëíÿþòñÿ ïî ìîäóëþ 2. Ó÷èòûâàÿ,
÷òî ΦST ≡ 0 (mod 2), èìååì S0 T +Φ0 =0, îòêóäà ñëåäóåò,
÷òî S0 T =Φ0 , òàê êàê ñëîæåíèå âåäåòñÿ ïî ìîäóëþ 2.

    5.2. Ýéëåðîâû öèêëû
    5.2.1. Îïðåäåëåíèå è óñëîâèÿ ñóùåñòâîâàíèÿ
  Ýéëåðîâ öèêë ýòî ïðîñòîé öèêë, ñîäåðæàùèé âñå ðåáðà ñâÿç-
íîãî íåîðèåíòèðîâàííîãî ìóëüòèãðàôà. Ïðîñòóþ öåïü, ïðîõî-
äÿùóþ ÷åðåç âñå ðåáðà, íàçûâàþò ýéëåðîâîé öåïüþ. Ãðàô, â
êîòîðîì åñòü ýéëåðîâ öèêë, íàçûâàåòñÿ ýéëåðîâûì, à ãðàô,
ñîäåðæàùèé ýéëåðîâó öåïü  ïîëóýéëåðîâûì.
           vr1    vr2            vr1     vr2             vr1    vr2
            @      @@r v 5        @       @@r             @
     v6 r      @                    @           v5          @
        @ @r    @r               r   @r                  r   @r
           v4 G v3               v4 G v3                 v4 G v3
                1                     2                      3
                                 Ðèñ. 5.6

    Ñðåäè ãðàôîâ, ïðåäñòàâëåííûõ íà ðèñ. 5.6, ãðàô G1 ÿâ-
ëÿåòñÿ ýéëåðîâûì, òàê êàê â íåì åñòü öèêë, ñîäåðæàùèé âñå
ðåáðà, íàïðèìåð, (v1 , v2 , v3 , v4 , v1 , v3 , v5 , v2 , v4 , v6 , v1 ); â ãðàôå
G2 ïîäîáíûé öèêë îòñóòñòâóåò, íî åñòü ýéëåðîâà öåïü, íàïðè-
ìåð (v1 , v2 , v3 , v4 , v1 , v3 , v5 , v2 , v4 ), ïîýòîìó ãðàô G2 ïîëóýéëå-
ðîâ; íàêîíåö, ãðàô G3 íå ýéëåðîâ è íå ïîëóýéëåðîâ: â íåì íåò
ñîîòâåòñòâóþùåãî öèêëà èëè öåïè.
    Ñâîèì íàçâàíèåì ðàñìàòðèâàåìûå çäåñü öèêëû îáÿçàíû
Ýéëåðó, êîòîðûé óñòàíîâèë ïðîñòîé ïðèçíàê ñóùåñòâîâàíèÿ
òàêèõ öèêëîâ â ãðàôå, ðåøèâ çíàìåíèòóþ â ñâîå âðåìÿ çàäà÷ó
î êåíèãñáåðãñêèõ ìîñòàõ. Ñàìà çàäà÷à ñîñòîèò â ñëåäóþùåì.
Ñåìü ìîñòîâ â òîãäàøíåì Êåíèãñáåðãå (íûíå Êàëèíèíãðàä)


                                       102

Страницы