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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

w v,
(v, . . ., w). v
w,
(v
1
, v
4
, v
2
, v
3
, v
5
, v
1
),
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
Z
Z
Z}
Q
Q
Q
Qk
3
>
-
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
+
Z
Z
Z~
B
B
B
B
BN
-
>
-
B
B
BN
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
+
Z
Z
Z~
B
B
B
B
BM
>
-
B
B
BN
(v
1
, v
3
, v
4
, v
1
, v
2
, v
1
),
v
5
v
5
.
v
5
v
3
v
5
,
(v
3
, v
4
) (v
5
, v
4
).
   2. Ñâÿçíîñòü â îðãðàôàõ
   2.1. Îñíîâíûå ïîíÿòèÿ
   Ãîâîðÿò, ÷òî âåðøèíà w äîñòèæèìà èç âåðøèíû v, åñëè
ñóùåñòâóåò ïóòü (v, . . ., w). Åñëè ïðè ýòîì v äîñòèæèìà èç
w, òî î âåðøèíàõ ãîâîðÿò, ÷òî îíè âçàèìíî äîñòèæèìû.
   Îðãðàô íàçûâàåòñÿ ñèëüíî ñâÿçíûì èëè ñèëüíûì, åñëè
ëþáûå äâå âåðøèíû â íåì âçàèìíî äîñòèæèìû. Ïðèìåð ñèëü-
íîãî îðãðàôà ïðèâåäåí íà ðèñ. 2.1,a. Ïîñêîëüêó â ãðàôå èìå-
åòñÿ îðöèêë (v1 , v4 , v2 , v3 , v5 , v1 ), âêëþ÷àþùèé âñå âåðøèíû,
òî ëþáûå äâå èç íèõ âçàèìíî äîñòèæèìû.
               vs1                       vs
                                           1                      vs1
            > Z
               }Z                   
                                     >    Z
                                       B Z                 
                                                              >    Z
                                                                BM Z
      v5 s       -
                   Zsv    v5 
                             s           B Z~
                                             - sv2   v5 
                                                        s         B -  ~ sv2
                                                                        Z
          Q
          k       3 2
                            B             B         B           B     
           Q 
                             B                        B           B 
            QQs
           
           s                    BN s+ -BBN s             BN +
         v
         4         3v        v4               v3        v4 s          Bsv
                                                                             3
             à                           á                        â
                                Ðèñ. 2.1

   Îðãðàô íàçûâàåòñÿ îäíîñòîðîííå ñâÿçíûì èëè îäíîñòî-
ðîííèì, åñëè â ëþáîé ïàðå åãî âåðøèí õîòÿ áû îäíà äîñòèæè-
ìà èç äðóãîé. Ïðèìåð îäíîñòîðîííåãî ãðàôà äàí íà ðèñ. 2.1,á.
 ýòîì ãðàôå åñòü îðöèêë (v1 , v3 , v4 , v1 , v2 , v1 ), âêëþ÷àþùèé
÷åòûðå âåðøèíû. Âñå îíè âçàèìíî äîñòèæèìû.  îòëè÷èå îò
ýòèõ âåðøèí v5 èìååò íóëåâóþ ïîëóñòåïåíü çàõîäà, à ýòî çíà-
÷èò, ÷òî íå ñóùåñòâóåò ïóòåé, âåäóùèõ â v5 . Âìåñòå ñ òåì èç
v5 äîñòèæèìà ëþáàÿ èç ÷åòûðåõ îñòàëüíûõ âåðøèí.
   Îðãðàô íàçûâàåòñÿ ñëàáî ñâÿçíûì èëè ñëàáûì, åñëè â íåì
ëþáûå äâå âåðøèíû ñîåäèíåíû ïîëóïóòåì.  îòëè÷èå îò ïó-
òè, êîãäà âñå äóãè îäèíàêîâî îðèåíòèðîâàíû (îò íà÷àëüíîé
âåðøèíû ïóòè ê êîíå÷íîé) â ïîëóïóòè ìîãóò áûòü è ïðîòèâî-
ïîëîæíî íàïðàâëåííûå äóãè. Ïðèìåð ñëàáî ñâÿçíîãî îðãðàôà
ïðèâåäåí íà ðèñ. 2.1,â. Î÷åâèäíî, ÷òî â ãðàôå íåò ïóòè ìåæäó
âåðøèíàìè v3 è v5 , íî ñóùåñòâóåò ïîëóïóòü, ñîñòîÿùèé èç
äâóõ ïðîòèâîïîëîæíî íàïðàâëåííûõ äóã (v3 , v4 ) è (v5 , v4 ).



                                       31

Страницы