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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

G
6
G
7
.
G
1
G
2
∼
G
1
t
v
1
t
v
2
t
v
3
t
v
4
d
v
5
d
v
6
d
v
7
d
v
8
A
A
A
A
A
@
@
@
@
@
@
@
@
@
@
A
A
A
A
A
G
2
d
v
5
t
v
1
d
v
7
t
v
3
t
v
2
d
v
6
t
v
4
d
v
8
@
@
@
@
∼
G
3
t
v
1
t
v
2
t
v
3
d
v
4
d
v
5
d
v
6
A
A
A
A
A
@
@
@
@
@
A
A
A
A
A
G
4
t
v
1
t
v
2
t
v
3
d
v
4
d
v
5
d
v
6
J
J
J
J
J
H
H
H
H
G
3
G
4
.
{v
1
, v
2
, v
3
}
{v
4
, v
5
, v
6
}.
K
n
1
,n
2
,
n
1
=|V
1
|, n
2
=|V
2
|. |E(K
n
1
,n
2
)|=n
1
n
2
.
¤
v +
v
v,
íî òîëüêî äëÿ ñâÿçíûõ ãðàôîâ G6 è G7 . Íà ðèñ. 1.9 äàíû
áîëåå íàãëÿäíûå ïðèìåðû äâóäîëüíûõ ãðàôîâ2 . Íåñìîòðÿ íà
î÷åâèäíîå íåñõîäñòâî èçîáðàæåíèé, G1 è G2 èçîìîðôíû, ò. å.
ýòî ôàêòè÷åñêè îäèí è òîò æå ãðàô, ÷òî ëåãêî ïðîâåðèòü.
v1      v2  v3     v4       v5              v1   v1      v2     v3         v1
 t       t   t      t        d               t    t       t       t          t
 A
 @     @    A              @ v       v6         A
                                                  @     A                  J
                              @t2       d                                   dvJ4
   A@ @ A                                        A@ A 
    A @    @ A        ∼         d     t
                                                     A @ A          ∼   vtH J
                                                                                J
    A @      @ A                                   A @    A
 
 d     A d @ d @A d
                            t
                                 v8    v@
                                        4@
                                           d      
                                                  d     A d @A d
                                                                        t2 HH
                                                                       d         Jd
                                                                                  H
v5      v6  v7     v8       v3            v7     v4      v5     v6    v5   v3      v6
         G1                           G2                G3                  G4
                                            Ðèñ. 1.9
Òî æå ñàìîå îòíîñèòñÿ ê ïàðå G3 è G4 . Êðîìå òîãî, çäåñü
êàæäàÿ âåðøèíà îäíîé äîëè {v1 , v2 , v3 } ñìåæíà ñ êàæäîé âåð-
øèíîé äðóãîé äîëè {v4 , v5 , v6 }. Òàêèå ãðàôû íàçûâàþò ïîë-
íûìè äâóäîëüíûìè è îáîçíà÷àþò â îáùåì ñëó÷àå Kn1 ,n2 , ãäå
n1 =|V1 |, n2 =|V2 |. Î÷åâèäíî, ÷òî |E(Kn1 ,n2 )|=n1 n2 .
    Ñóùåñòâóåò ïðîñòîé ñïîñîá ðàñïîçíàâàíèÿ äâóäîëüíîñòè
ãðàôà, îñíîâàííûé íà ñëåäóþùåé òåîðåìå Êåíèãà.
    Òåîðåìà 1.2 Ãðàô ÿâëÿåòñÿ äâóäîëüíûì, òîãäà è òîëüêî
òîãäà, êîãäà îí íå ñîäåðæèò öèêëîâ íå÷åòíîé äëèíû.
    ¤ Â îñíîâó äîêàçàòåëüñòâà (è àëãîðèòìà ðàñïîçíàâàíèÿ)
ìîæåò áûòü ïîëîæåíà ñëåäóþùàÿ ïðîöåäóðà ðàçìåòêè ãðàôà.
Âûáèðàåì íåêîòîðóþ âåðøèíó v è ïîìå÷àåì åå çíàêîì " + ".
Äàëåå äëÿ êàæäîé ïîìå÷åííîé íà ïðåäûäóùåì øàãå âåðøèíû
v îòûñêèâàåì âñå åå ñîñåäíèå âåðøèíû è ïîìå÷àåì èõ ïðîòè-
âîïîëîæíûì çíàêîì. Ïðîäîëæàåì ýòó îïåðàöèþ äî òåõ ïîð,
ïîêà íå áóäåò ïîëó÷åí îäèí èç äâóõ âîçìîæíûõ ðåçóëüòàòîâ:
    à) âñå âåðøèíû ãðàôà îêàæóòñÿ ïîìå÷åííûìè áåç êàêèõ-
ëèáî êîëëèçèé, ò. å. ìåòêè ëþáîé âåðøèíû ñî ñòîðîíû åå ñî-
ñåäåé ñîâïàäàþò. Ýòî îçíà÷àåò, ÷òî âñå öåïè, ñîåäèíÿþùèå
ëþáóþ âåðøèíó ãðàôà ñ v, ñîñòîÿò òîëüêî èç ÷åòíîãî èëè
òîëüêî èç íå÷åòíîãî ÷èñëà äóã è, çíà÷èò, â ñîâîêóïíîñòè îá-
ðàçóþò öèêëû ÷åòíîé äëèíû. Âìåñòå ñ òåì ñîãëàñîâàííîñòü
  2 Âåðøèíû,   îòíîñÿùèåñÿ ê ðàçíûì äîëÿì, èçîáðàæåíû ïî-ðàçíîìó.


                                            16

Страницы