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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

V −VS
1
={v
2
, v
3
, v
4
}.
Γ(v
2
) = {v
3
} Γ(v
3
) = {v
4
} Γ(v
4
) = {v
3
}
Γ
−1
(v
2
) = ∅ Γ
−1
(v
3
) = {v
2
} Γ
−1
(v
4
) = {v
3
}
v
2
R(v
2
) = {v
2
} ∪ {v
3
} ∪ {v
4
} = {v
2
, v
3
, v
4
}, Q(v
2
) = {v
2
},
VS
2
= R(v
2
) ∩ Q(v
2
) = {v
2
}
V −VS
1
−VS
2
={v
3
, v
4
}.
R(v
3
) = {v
3
} ∪ {v
4
} = {v
3
, v
4
}, Q(v
3
) = {v
3
} ∪ {v
4
} = {v
3
, v
4
},
VS
3
= R(v
3
)∩Q(v
3
) = {v
3
, v
4
}
R = [r
ij
]
|G|, r
ij
=1,
v
j
v
i
, r
ij
=0
R
R(v
i
)
r
ij
=1, v
j
∈R(v
i
), r
ij
=0
R(v
1
) = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
},
R(v
2
) = {v
2
, v
3
, v
4
},
R(v
3
) = {v
3
, v
4
},
R(v
4
) = {v
3
, v
4
},
R(v
5
) = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
},
R(v
6
) = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
},
=⇒
   Ìíîæåñòâî âåðøèí, íå îòíîñÿùèõñÿ ê íàéäåííîé ñèëüíîé
êîìïîíåíòå, ðàâíî ðàçíîñòè V −VS1 ={v2 , v3 , v4 }. Îïèñàíèå ñî-
îòâåòñòâóþùåãî âåðøèííî-ïîðîæäåííîãî ïîäãðàôà èìååò âèä:
Γ(v2 ) = {v3 }, Γ(v3 ) = {v4 },       Γ(v4 ) = {v3 };
Γ (v2 ) = ∅, Γ (v3 ) = {v2 }, Γ−1 (v4 ) = {v3 },
  −1               −1

    Äëÿ ïîèñêà ñëåäóþùåé ñèëüíîé êîìïîíåíòû âîçüìåì îäíó
èç åãî âåðøèí, íàïðèìåð v2 .  ðåçóëüòàòå ïîëó÷èì:
R(v2 ) = {v2 } ∪ {v3 } ∪ {v4 } = {v2 , v3 , v4 }, Q(v2 ) = {v2 },
VS2 = R(v2 ) ∩ Q(v2 ) = {v2 }  åäèíñòâåííàÿ âåðøèíà, âõîäÿ-
ùàÿ âî âòîðóþ ñèëüíóþ êîìïîíåíòó.
    Äàëåå âåäåì ïîèñê íà ìíîæåñòâå V −VS1 −VS2 ={v3 , v4 }. Â
ðåçóëüòàòå ïîëó÷àåì:
R(v3 ) = {v3 } ∪ {v4 } = {v3 , v4 }, Q(v3 ) = {v3 } ∪ {v4 } = {v3 , v4 },
VS3 = R(v3 )∩Q(v3 ) = {v3 , v4 }  âåðøèíû òðåòüåé è ïîñëåäíåé
ñèëüíîé êîìïîíåíòû ãðàôà.

   2.5. Ìàòðèöû äîñòèæèìîñòåé
   Îïðåäåëèì ìàòðèöó (ïðÿìûõ) äîñòèæèìîñòåé R = [rij ]
êàê êâàäðàòíóþ (0,1)-ìàòðèöó ïîðÿäêà |G|, â êîòîðîé rij =1,
åñëè âåðøèíà vj äîñòèæèìà èç vi , è rij =0  â ïðîòèâíîì
ñëó÷àå. Ïîñêîëüêó êàæäàÿ âåðøèíà äîñòèæèìà èç ñàìîé ñåáÿ,
äèàãîíàëüíûå ýëåìåíòû â R ðàâíû 1.
   Ìàòðèöà äîñòèæèìîñòåé ìîæåò áûòü ïîëó÷åíà ñëåäóþùèì
ñïîñîáîì. Îòûñêèâàåì ìíîæåñòâà R(vi ) äëÿ âñåõ âåðøèí ãðà-
ôà è ïîëàãàåì rij =1, åñëè vj ∈R(vi ), è rij =0  â ïðîòèâíîì
ñëó÷àå. Äëÿ ïðèìåðà èç ïðåäûäóùåãî ðàçäåëà èìååì:
                                          
 R(v1 ) = {v1 , v2 , v3 , v4 , v5 , v6 },         
                                                     1 1 1 1 1 1
                                                                 
 R(v2 ) = {v2 , v3 , v4 },                
                                          
                                          
                                                  0 1 1 1 0 0 
 R(v3 ) = {v3 , v4 },                              0 0 1 1 0 0 
                                            =⇒ R = 
                                                    0 0 1 1 0 0
                                                                 .
                                                                 
 R(v4 ) = {v3 , v4 },                     
                                                               
 R(v5 ) = {v1 , v2 , v3 , v4 , v5 , v6 }, 
                                          
                                          
                                                     1 1 1 1 1 1
                                                     1 1 1 1 1 1
 R(v6 ) = {v1 , v2 , v3 , v4 , v5 , v6 },




                                  36

Страницы