連結
- 連結
- グラフを連結成分に分けるには、グラフ探索法により、連結・非連結の判定が必要で、網羅探索をする必要がある。工夫の余地は、連結情報の表現方法であろう。例としては以下のようなものが考えられる
- 単純に連結成分ごとに保管する方法
- ノードに値を与え、その値が連続しているノード同士は連結であることとし、値が非連続であるノードとノードとの間で非連結であることを表現する方法
- ２重連結
- ある連結なグラフがあって、そのグラフから１つのノードを取り去る場合、取り去るノードとしてどのノードを選んでも、グラフが連結なままであるとき、そのグラフは２重連結(biconnected)であるという
- ある連結なグラフがあって、そのグラフから１つのノードを取り去ったときに、グラフが連結でなくなる場合、その取り去られたノードを元の連結グラフの関節点(articulation point)と呼ぶ
- あるシステムにおけるリスク回避のためには、そのシステムがグラフ表現できたとすると、そのグラフが２重連結になっていることが必要であろう。遺伝統計学的な発想から言えば、すべての２倍体(多倍体)生物の遺伝が組換えを介して多くのサイクルを有する２重連結なARGを形成していうことは、リスク回避の１表現ともいえるだろう。また、遺伝子の長さが長い(ときとして冗長配列を含みながら)ということは、その遺伝子領域内に組換えが起きる確率を高くすることであり、より短い時間経過の間に２重連結ARGを構成させる、という意味もあるかもしれない。ただし、長さが長いことは、変異の発生も線形に増加させるから、リスク回避の側面からのみ捉えるべきではない。また、遺伝子の伝達のみならず、遺伝子・遺伝子ネットワークから考えた場合、たいていの機能は２重連結性によりその機能の安定性を確保しているものと予想される。また、グラフ理論を応用して解析するにあたっては、大きな連結グラフを２重連結成分ごとに分割解析することで処理の効率化を図ることも念頭においてよい事項と予想される
- 関節点の判定アルゴリズムにおいては、深さ優先探索の応用が適当である。なぜなら、深さ優先探索においては、着目ノードよりも『深い』部分を網羅的に探索することができ、２重連結性の確認には、『深い』部分が、着目ノードよりも『浅い』部分と連結するか否かで判断できるからである
- 処理ステップ数
である
- 合併･発見アルゴリズム
- グラフ上の２ノード間に道が存在するかいなかの判断をする
- グラフの全構造を知らずとも、ノード間の道の存在だけを知るための方法である
- グラフのエッジ情報から出発し、木の親を記録していくことで実現する。このようにして作成する木を『合併・発見木(union-find tree)』と称する
- このアルゴリズムでは、着目２ノード間をつなぐ木構造(合併・発見木)を作りつつ進むが、その出来上がる木構造がどうなるかは、処理するエッジ情報の順番と、その情報を元に記録する親情報の決め方に依存する。平均すると、
な処理時間であるが、最悪の場合には、
かかる
