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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

S
1
, S
2
, . . . , S
k
G(V, E). G
G
∗
(V
∗
, E
∗
), v
∗
i
S
i
G, (v
∗
i
, v
∗
j
)
E
∗
, G
S
i
S
j
. G,
S
1
S
4
, G
∗
G
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
s
v
6
s
v
7
s
v
8
s
v
9
s
v
10
-
?
I
?
@
@
@
@R
@
@
@
@R
-
@
@
@
@R
@
@
@
@R
-
R
6
6
G
∗
s
v
∗
1
S
1
={v
1
,v
2
}
s
v
∗
2
{v
3
}=S
2
s
v
∗
3
S
3
={v
4
,v
5
,v
8
,v
9
}
s
v
∗
4
{v
6
,v
7
,v
10
}=S
4
?
@
@
@
@
@R
?
G
∗
R(v) (n, m)
v. Γ(v)
v
Γ
2
(v) v
Γ
3
(v)
R(v)
R(v) = {v} ∪ Γ(v) ∪ Γ
2
(v) ∪ . . . ∪ Γ
p
(v) .
   2.3. Êîíäåíñàöèÿ îðãðàôà
     Íà îñíîâå ñèëüíûõ êîìïîíåíò îïðåäåëÿåòñÿ åùå îäèí âèä
ãðàôîâ  ãðàô êîíäåíñàöèè. Ïóñòü S1 , S2 , . . . , Sk  ñèëüíûå
êîìïîíåíòû ãðàôà G(V, E). Êîíäåíñàöèåé ãðàôà G íàçûâà-
åòñÿ ãðàô G∗ (V ∗ , E ∗ ), êàæäàÿ âåðøèíà êîòîðîãî vi∗ ïðåäñòàâ-
ëÿåò ìíîæåñòâî âåðøèí ñîîòâåòñòâóþùåé ñèëüíîé êîìïîíåí-
òû Si ãðàôà G, à äóãà (vi∗ , vj∗ ) ÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà
E ∗ , åñëè â ãðàôå G åñòü ïî êðàéíåé ìåðå îäíà äóãà, èäóùàÿ
îò íåêîòîðîé âåðøèíû êîìïîíåíòû Si ê îäíîé èç âåðøèí êîì-
ïîíåíòû Sj . Ïðèìåð îðãðàôà G, èìåþùåãî ÷åòûðå ñèëüíûõ
êîìïîíåíòû S1  S4 , è åãî êîíäåíñàöèè G∗ äàí íà ðèñ. 2.3.
          v1      v2      v3
               s - s     s       S1 ={v1 ,v2 }        {v3 }=S2
               I   @      @             ∗ s              s ∗
                                      v1 @                 v2
                      @      @
                        Rvs6 @ Rvs7          @
      G
             ? - s?
          v4 s       @ @      @
                               -                 @            G∗
             @
             6    v 5     6                         @
               @                      v3∗ s?          R s?v4∗
                                                      @
                @                          
             s @R s R s      S3 ={v4 ,v5 ,v8 ,v9 } {v6 ,v7 ,v10 }=S4
          v8      v9      v10
                                 Ðèñ. 2.3

   ßñíî, ÷òî ãðàô êîíäåíñàöèè G∗ íå ìîæåò ñîäåðæàòü öèê-
ëîâ, òàê êàê âñå âåðøèíû ëþáîãî öèêëà âçàèìíî äîñòèæèìû
è çíà÷èò ïðèíàäëåæàò íåêîòîðîé ñèëüíîé êîìïîíåíòå, à ýòî
ïðîòèâîðå÷èò îïðåäåëåíèþ êîíäåíñàöèè.


   2.4. Îòûñêàíèå ñèëüíûõ êîìïîíåíò
   Ïóñòü R(v)  ìíîæåñòâî âåðøèí (n, m) -ãðàôà, äîñòèæè-
ìûõ èç âåðøèíû v. Òîãäà, ïîñêîëüêó Γ(v) ÿâëÿåòñÿ ìíîæå-
ñòâîì âåðøèí, äîñòèæèìûõ èç v ñ èñïîëüçîâàíèåì ïóòåé äëè-
íû 1, Γ2 (v)  ìíîæåñòâîì âåðøèí, äîñòèæèìûõ èç v ñ èñ-
ïîëüçîâàíèåì ïóòåé äëèíû 2, Γ3 (v)  ñ èñïîëüçîâàíèåì ïóòåé
äëèíû 3 è ò. ä., òî R(v) ìîæíî ïðåäñòàâèòü â âèäå
            R(v) = {v} ∪ Γ(v) ∪ Γ2 (v) ∪ . . . ∪ Γp (v) .


                                   33

Страницы