疎グラフと密グラフ
グラフはノードとエッジという２つのパラメータを持つ点が、グラフ構造に関するアルゴリズムの検討に影響する。ノードとエッジの数をそれぞれV,Eとすると、EがVに比べ比較的少ないグラフを疎グラフ(sparse graph)、EがVに比べ比較的多いグラフを密グラフ(dense graph)と呼ぶ。グラフに適用するアルゴリズムのステップ数が、疎グラフとステップ数がEとVの関数で表せたとすると、疎グラフと密グラフでその効率の評価が分かれることがある。グラフの疎密の基準として、 を疎グラフ、
を密グラフとすれば、たとえば、
ステップのアルゴリズムと
ステップのアルゴリズムがあるとき、疎グラフには
が早いが、密グラフでは
が早い。
隣接行列表現,グラフの
- V個のノードを持つグラフにおいて、V行V列の行列によってエッジのありなしを表現する方法。エッジに重み(距離など)がない場合にはブール値。無向グラフの場合は
、有向グラフの場合は、
。対角成分は、trueで統一するかfalseで統一するか、用途により使い分ける。
のメモリを要求し、エッジの読み込み→隣接行列化に
隣接リスト表現,グラフの
- V個のノードについて、それが隣接するノードをリストに列挙する方法。無向グラフの場合には、隣接ノードの種類は１つであり、１エッジの読み込みにつき、２つの端ノードの両方について、隣接ノードを追加し、有向グラフの場合には、隣接ノードの種類は２種類(上流か下流か)であり、１エッジの読み込みにつき、２つの端ノードの両方について、かたや、上流ノードをかたや下流ノードを追加する。１エッジが２ノードに登録されることによって、探索が効率的に行える。出来上がる隣接リストはエッジ情報の入力情報に依存する。したがって、入力順序は処理論理の効率に影響を与える。また、解が複数存在する場合には、最初に得られる解が、入力順序によって異なることもありえる。
- ノードとその連結エッジの除去処理は、隣接リスト表現ではステップ数が多くなる。煩雑さを回避するためには、登録された隣接ノード同士にリンクを張る方法があるが、こうすることで、すばやく処理できるが、体系自体は煩雑になる。
深さ優先探索
- グラフ上のあるノードからスタートし、隣接するノードを『訪問』する。『訪問中』のノードからさらに訪問可能なノードを『訪問』し、『訪問先』がなくなるまで続け、なくなったら、『訪問先』探索をまだ済ませていない『訪問中』のノードについて同様の処理を繰り返す
- 連結か
- 『訪問できる』ノードがなくなったときに、すべてのノードが訪問されていれば、『連結』であることがわかる
- 閉路があるか
- 『訪問先』探索中に、『すでに訪問したノード』に『再度訪問しそう』になったら、閉路を見出したことになる
- 連結か
- このアルゴリズムでは、すべてのノードとエッジが調べつくされる
- 隣接リスト表現での深さ優先探索
に比例：疎グラフで効率的
- 隣接行列表現での深さ優先探索
最小木(minimum spanning tree,最小極大木とも)
- 重みつきグラフにおいて、すべてのノードを結ぶエッジの集合で、辺の重みの総和が最小のもの
- 疎グラフの場合
- 大きくわけてアプローチは２つ
- １つのノードからスタートし、そのノードを含む木を成長させ、すべてのノードが結ばれるまで続ける(順位優先探索、
ステップ)
- すべてのノードからスタートし、それぞれのノードを個別の木としてとらえ、それらをつないで行き、すべてのノードがつながるまで続ける(クラスカル法、
ステップ)
- １つのノードからスタートし、そのノードを含む木を成長させ、すべてのノードが結ばれるまで続ける(順位優先探索、
- まだ整理できていない疑問
- 今、連結なグラフが与えられており、そのノード集合を複数の部分集合に分割し、部分集合同士には共通のノードが存在しないときに、その部分集合の最小木を作成するとする。複数の最小木ができるが、その最小木に共通して含まれるエッジと、ある最小木に特異的に含まれるエッジと、いずれの最小木にも含まれないエッジとでは、どういう意味があるのだろうか？
- 大きくわけてアプローチは２つ
- 密グラフの場合
- 全ノードについて優先度値を与え、その優先度リストの更新と優先度の最小値を見つける
- 全ノードについて優先度値を与え、その優先度リストの更新と優先度の最小値を見つける
推移閉包(transitive closure)、または、到達可能性全網羅
(有向)グラフにおいて、あるノードからあるノードへ到達可能であるときに、その２ノード間にエッジを加えて作成したグラフを、そのグラフの推移閉包と言う。一度この推移閉包を作成すれば、(有向)グラフにおける径路の有無の情報はすぐに得られる。密なグラフができるので、推移閉包は隣接行列で表現する方が適当なことが多い。推移閉包を計算するプログラムは極めて簡単であり、推移閉包の計算時間は疎グラフの場合に、密グラフの場合に
である
今、あるグラフが隣接行列表現してあるとし、それがV個のノードからなるグラフがの行列N[i][j], 0<=i<=V-1,0<=j<=V-1,とする。隣接グラフにはエッジが存在するノード間は１、そうでない場合には０が記載されている。ノード数Vに関する３重ループにて次のようにして、推移閉包の隣接行列が得られる
//本ソースは未検証です
for(i=0;i<V;i++){
for(j=0;j<V;j++){
if(N[i][j]==1){
for(k=1;k<V;k++){
if(N[i][k]==1){
N[j][k]=1;
}
}
}
}
}
ウォーシャルの方法と呼ばれる
最短径路全網羅、または、最短径路探索のウォーシャルの方法的拡張(フロイドの方法)
前項の推移閉包は、グラフにおける到達可能性(到達可能か否か)の情報を全ノードペアについて求める方法である『ウォーシャルの方法』についてであった。これは、到達可能性を全ノードペアについて行うことに他ならないが、同様に、任意の２ノード間の最短径路計算を全ノードペアについて行い、その情報を保管することが必要な場合もあり、その場合には、ウォーシャルの方法のアナロジーを２ノード間最短径路問題にあてはめることに通じる。この方法にフロイドの方法という。
今、あるグラフが行列表現してあるとし、エッジの長さが正の数値で記録されている。それがV個のノードからなるグラフがの行列N[i][j], 0<=i<=V-1,0<=j<=V-1,とする。隣接グラフにはエッジがない場合には、未定義である。ノード数Vに関する３重ループにて次のようにして、全ノードペア間の最短距離を情報として有するの行列が得られる。ウォーシャルの方法と同じくノード数による３重ループで
である
//本ソースは未検証です
for(i=0;i<V;i++){
for(j=0;j<V;j++){
if(N[i][j]==1){
for(k=1;k<V;k++){
/*
*到達可能判断(ウォーシャルの方法)のときには、%の判断が"==1"であったが
*">0"という判断(到達可能な距離が定められている)に入れ替えられている
*/
if(N[i][k]>0){//%
/*
*#の判断で
*ノード間距離が未定義(N[j][k]!=null)か、
*より短い径路が示唆される(N[j][i]+N[i][k] < N[j][k])かしたら
*/
if(N[j][k]!=null || (N[j][i]+N[i][k] < N[j][k])){//#
/*
*$において『到達可能である(N[j][k]=1)』と更新するかわりに
*距離を更新する
*/
N[j][k]=N[j][i]+N[i][k];//$
}
}
}
}
}
深さ優先探索と幅優先探索、再帰表現・非再帰表現との親和性
深さ優先探索は再帰表現がしやすく、幅優先探索は非再帰表現がしやすいと言う。その理由は次のようになる。
深さ優先探索では、探索過程において、多段階の保留状態を生み、その多段階の保留状態は、『当該段階』『当該段階より１つ上の段階』『当該段階より１つ下の段階』の３段階で構成され、この『３段階構成』は、多段階のそれぞれの段階で発生するものであるから、この『３段階構成』を多段階に発生させる部分を『再帰表現』すると、探索構造全体が「上下の『３段階構成』と『上下の数列』の２規則」で表現しきれるからである。
他方、幅優先探索では、探索過程において、『３段階構成』を生むが、その構成要素を増やすことで網羅的探索に対応している。探索構造は、「上下の『３段階構成』」のみになっているわけである。ただし、深さ優先探索が２構造規則で表現されていたのに対して、幅優先探索で１構造規則になっているのには、理由があり、それは、『３段階構成』を利用した幅優先探索においては、探索を進める順序に、「古いものから先に処理する」という別の規則を定めているからである。
深さ優先探索でも『再帰表現』をしないのであれば、処理順規則という形の別規則を持ち込む必要があるだろう。
処理順規則は、キュー・スタックに任せるのが便利だろうが、それは各論に過ぎるので、こちらで。
無閉路有向グラフ(Directed acyclic graph)
グラフ中の有向閉路とは、エッジの向きに進んだときに、ぐるぐると回れてしまうような閉路を言う。今、有向グラフのうち、有向閉路を持たないグラフを無閉路有向グラフと呼ぶ。無閉路有向グラフにおいては、エッジの向きを無視すれば閉路は存在するものの、エッジの向きを考慮するとぐるぐる回れないようなグラフを含む。木はグラフの中の特殊型であるが、無閉路有向グラフは木よりも制約が弱く、一般的なグラフと木の中間的要素を有し、その特徴を用いた処理が可能である。
ＡＲＧは無閉路有向グラフである。
無閉路有向グラフにはトポロジカルソートが適用できる
連結
- 連結
- グラフを連結成分に分けるには、グラフ探索法により、連結・非連結の判定が必要で、網羅探索をする必要がある。工夫の余地は、連結情報の表現方法であろう。例としては以下のようなものが考えられる
- 単純に連結成分ごとに保管する方法
- ノードに値を与え、その値が連続しているノード同士は連結であることとし、値が非連続であるノードとノードとの間で非連結であることを表現する方法
- ２重連結
- ある連結なグラフがあって、そのグラフから１つのノードを取り去る場合、取り去るノードとしてどのノードを選んでも、グラフが連結なままであるとき、そのグラフは２重連結(biconnected)であるという
- ある連結なグラフがあって、そのグラフから１つのノードを取り去ったときに、グラフが連結でなくなる場合、その取り去られたノードを元の連結グラフの関節点(articulation point)と呼ぶ
- あるシステムにおけるリスク回避のためには、そのシステムがグラフ表現できたとすると、そのグラフが２重連結になっていることが必要であろう。遺伝統計学的な発想から言えば、すべての２倍体(多倍体)生物の遺伝が組換えを介して多くのサイクルを有する２重連結なARGを形成していうことは、リスク回避の１表現ともいえるだろう。また、遺伝子の長さが長い(ときとして冗長配列を含みながら)ということは、その遺伝子領域内に組換えが起きる確率を高くすることであり、より短い時間経過の間に２重連結ARGを構成させる、という意味もあるかもしれない。ただし、長さが長いことは、変異の発生も線形に増加させるから、リスク回避の側面からのみ捉えるべきではない。また、遺伝子の伝達のみならず、遺伝子・遺伝子ネットワークから考えた場合、たいていの機能は２重連結性によりその機能の安定性を確保しているものと予想される。また、グラフ理論を応用して解析するにあたっては、大きな連結グラフを２重連結成分ごとに分割解析することで処理の効率化を図ることも念頭においてよい事項と予想される
- 関節点の判定アルゴリズムにおいては、深さ優先探索の応用が適当である。なぜなら、深さ優先探索においては、着目ノードよりも『深い』部分を網羅的に探索することができ、２重連結性の確認には、『深い』部分が、着目ノードよりも『浅い』部分と連結するか否かで判断できるからである
- 処理ステップ数
である
- 合併･発見アルゴリズム
- グラフ上の２ノード間に道が存在するかいなかの判断をする
- グラフの全構造を知らずとも、ノード間の道の存在だけを知るための方法である
- グラフのエッジ情報から出発し、木の親を記録していくことで実現する。このようにして作成する木を『合併・発見木(union-find tree)』と称する
- このアルゴリズムでは、着目２ノード間をつなぐ木構造(合併・発見木)を作りつつ進むが、その出来上がる木構造がどうなるかは、処理するエッジ情報の順番と、その情報を元に記録する親情報の決め方に依存する。平均すると、
な処理時間であるが、最悪の場合には、
かかる
ネットワーク流
ネットワーク流のグラフでのモデル化には、いくつかの要素を付加する必要がある。ソース(湧出点)とシンク(吸収点)と呼ばれる特殊な２点である(ソースとシンクがそれぞれ１つずつの場合もあれば、これらが複数の場合もある)。また、グラフは重み付き有向グラフであるが、エッジには容量と流量が設定される。エッジには流量の上限が存在し、それが容量である。グラフ全体が表現しているネットワーク全体については、総流量という値が存在する。その総流量の最大値を求めるのが、ネットワーク流問題と呼ばれる問題である。エッジに容量・流量以外の値(長さやコスト)を持たせることも可能である。ＡＲＧで言えば、個々の染色体が作るＡＲＧでなく、ハプロタイプで表現される染色体集合についてのＡＲＧを考えた場合、流量の概念が発生する。
- マッチング(ノードが２グループに分けられるときに、それぞれのグループに属するノードの間にペアをつくる)は、補助ノードの追加によりネットワーク流の問題に変換できる
