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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

G(V, Γ)
Γ
+
(v
i
) Γ
−
(v
i
)
v
i
∈ V.
v R(v) Q(v).
V S = R(v) ∩ Q(v).
V S G
V −VS
V −VS
r
v
1
r
v
2
r
v
3
r
v
6
r
v
5
r
v
4
R
-
J
J
J
J
J^
-
?
-
6
Γ(v
1
) = {v
2
, v
3
, v
5
} Γ(v
2
) = {v
3
} Γ(v
3
) = {v
4
}
Γ(v
4
) = {v
3
} Γ(v
5
) = {v
4
, v
6
} Γ(v
6
) = {v
1
, v
2
}
Γ
−1
(v
1
) = {v
6
} Γ
−1
(v
2
) = {v
1
, v
6
} Γ
−1
(v
3
) = {v
1
, v
2
, v
4
}
Γ
−1
(v
4
) = {v
3
, v
5
} Γ
−1
(v
5
) = {v
1
} Γ
−1
(v
6
) = {v
5
}
R(v), Q(v) R(v) ∩ Q(v)
v
1
R(v
1
) = {v
1
} ∪ {v
2
, v
3
, v
5
} ∪ {v
3
, v
4
, v
6
} = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
},
Q(v
1
) = {v
1
} ∪ {v
6
} ∪ {v
5
} = {v
1
, v
5
, v
6
},
VS
1
= R(v
1
)∩Q(v
1
) = {v
1
, v
5
, v
6
}
   Ñ ó÷åòîì èçëîæåííîãî, ìîæíî ïðåäëîæèòü ñëåäóþùóþ ïðî-
öåäóðó îòûñêàíèÿ âñåõ ñèëüíûõ êîìïîíåíò ãðàôà G(V, Γ) :
   1. Ôîðìèðóåì îïèñàíèå ãðàôà â âèäå Γ+ (vi ) è Γ− (vi )
      äëÿ âñåõ vi ∈ V.
   2. Âûáèðàåì íåêîòîðóþ âåðøèíó v è íàõîäèì R(v) è Q(v).
   3. Ïîëó÷àåì V S = R(v) ∩ Q(v). Âåðøèííî-ïîðîæäåííûé
      íà ìíîæåñòâå âåðøèí V S ïîäãðàô ãðàôà G ïðåäñòàâ-
      ëÿåò ñèëüíóþ êîìïîíåíòó.
   4. Åñëè ìíîæåñòâî V −VS ïóñòî, òî âñå ñèëüíûå êîìïî-
      íåíòû íàéäåíû, â ïðîòèâíîì ñëó÷àå ñòðîèì âåðøèííî-
      ïîðîæäåííûé ïîäãðàô íà V −VS è ïåðåõîäèì ê ï. 1.
   Ðàçáåðåì ïðèìåð íà èñïîëüçîâàíèå îïèñàííîãî ïîäõîäà.
Íàéäåì ñèëüíûå êîìïîíåíòû ãðàôà, èçîáðàæåííîãî íà ðèñ. 2.4.

                                 v1 r - vr 2 -Rvr 3
                                    J
                                    6        
                                      J
                                       J
                                    r J ^r - ?
                                         J      r
                                    v6    v5    v4
                                        Ðèñ 2.4

   Îïèñàíèÿ ãðàôà ñ èñïîëüçîâàíèåì ïðÿìîãî è îáðàòíîãî
îòîáðàæåíèé âûãëÿäÿò òàê:
Γ(v1 ) = {v2 , v3 , v5 },   Γ(v2 ) = {v3 },            Γ(v3 ) = {v4 },
Γ(v4 ) = {v3 },             Γ(v5 ) = {v4 , v6 },       Γ(v6 ) = {v1 , v2 };
Γ−1 (v1 ) = {v6 },          Γ−1 (v2 ) = {v1 , v6 },    Γ−1 (v3 ) = {v1 , v2 , v4 },
Γ−1 (v4 ) = {v3 , v5 },     Γ−1 (v5 ) = {v1 },         Γ−1 (v6 ) = {v5 }.
   Íàõîäèì ìíîæåñòâà R(v), Q(v) è R(v) ∩ Q(v) äëÿ ïðîèç-
âîëüíî âûáðàííîé âåðøèíû, íàïðèìåð äëÿ v1 :
R(v1 ) = {v1 } ∪ {v2 , v3 , v5 } ∪ {v3 , v4 , v6 } = {v1 , v2 , v3 , v4 , v5 , v6 },
Q(v1 ) = {v1 } ∪ {v6 } ∪ {v5 } = {v1 , v5 , v6 },
VS1 = R(v1 )∩Q(v1 ) = {v1 , v5 , v6 }  ìíîæåñòâî âåðøèí ïåðâîé
ñèëüíîé êîìïîíåíòû ãðàôà.


                                        35

Страницы