ネットワーク流のグラフでのモデル化には、いくつかの要素を付加する必要がある。ソース(湧出点)とシンク(吸収点)と呼ばれる特殊な２点である(ソースとシンクがそれぞれ１つずつの場合もあれば、これらが複数の場合もある)。また、グラフは重み付き有向グラ…

連結な有向グラフで、有向閉路が存在するとき、ノード同士の関係には、相互に到達可能な関係と、片方のノードから到達可能ながらその逆は到達不能であるような関係の２種類が存在する。相互に到達可能なノードの組を強連結成分とすると、連結な有向グラフは…

連結 グラフを連結成分に分けるには、グラフ探索法により、連結・非連結の判定が必要で、網羅探索をする必要がある。工夫の余地は、連結情報の表現方法であろう。例としては以下のようなものが考えられる 単純に連結成分ごとに保管する方法 ノードに値を与え…

『Algorithms in C アルゴリズム 第３巻 グラフ・数理・トピックス』近代科学社 R.セジウィック 著 野下浩平・星守・佐藤創・田口東 共訳 おすすめ度★★★★☆、ただし、新版が出ている模様。 ３分冊の１冊 アルゴリズムC〈第3巻〉グラフ・数理・トピックス 作者…

グラフ中の有向閉路とは、エッジの向きに進んだときに、ぐるぐると回れてしまうような閉路を言う。今、有向グラフのうち、有向閉路を持たないグラフを無閉路有向グラフと呼ぶ。無閉路有向グラフにおいては、エッジの向きを無視すれば閉路は存在するものの、…

深さ優先探索は再帰表現がしやすく、幅優先探索は非再帰表現がしやすいと言う。その理由は次のようになる。 深さ優先探索では、探索過程において、多段階の保留状態を生み、その多段階の保留状態は、『当該段階』『当該段階より１つ上の段階』『当該段階より…

前項の推移閉包は、グラフにおける到達可能性(到達可能か否か)の情報を全ノードペアについて求める方法である『ウォーシャルの方法』についてであった。これは、到達可能性を全ノードペアについて行うことに他ならないが、同様に、任意の２ノード間の最短径…

(有向)グラフにおいて、あるノードからあるノードへ到達可能であるときに、その２ノード間にエッジを加えて作成したグラフを、そのグラフの推移閉包と言う。一度この推移閉包を作成すれば、(有向)グラフにおける径路の有無の情報はすぐに得られる。密なグラ…

グラフアルゴリズムではノードとノードと隣接関係が対象となっているのに対し、幾何学的アルゴリズムでは、物理的な位置とその距離が対象となっている。物理的な位置の情報を利用すると、探索対象を大幅に減らしうる。ＡＲＧにおいては(おそらく)、ランダム…

重みつきグラフにおいて、すべてのノードを結ぶエッジの集合で、辺の重みの総和が最小のもの 疎グラフの場合 大きくわけてアプローチは２つ １つのノードからスタートし、そのノードを含む木を成長させ、すべてのノードが結ばれるまで続ける(順位優先探索、…

深さ優先探索と同様に、ノードは『訪問済み』『訪問中』『未訪問』の３群に振り分けられる。『訪問中』のノードの中から１つを取り出して、『訪問済み』とする手続きを繰り返す点も深さ優先探索と同じである。違いは次の通り。深さ優先探索では、もっとも新…

グラフ上のあるノードからスタートし、隣接するノードを『訪問』する。『訪問中』のノードからさらに訪問可能なノードを『訪問』し、『訪問先』がなくなるまで続け、なくなったら、『訪問先』探索をまだ済ませていない『訪問中』のノードについて同様の処理…

V個のノードについて、それが隣接するノードをリストに列挙する方法。無向グラフの場合には、隣接ノードの種類は１つであり、１エッジの読み込みにつき、２つの端ノードの両方について、隣接ノードを追加し、有向グラフの場合には、隣接ノードの種類は２種類…

V個のノードを持つグラフにおいて、V行V列の行列によってエッジのありなしを表現する方法。エッジに重み(距離など)がない場合にはブール値。無向グラフの場合は、有向グラフの場合は、。対角成分は、trueで統一するかfalseで統一するか、用途により使い分け…

グラフはノードとエッジという２つのパラメータを持つ点が、グラフ構造に関するアルゴリズムの検討に影響する。ノードとエッジの数をそれぞれV,Eとすると、EがVに比べ比較的少ないグラフを疎グラフ(sparse graph)、EがVに比べ比較的多いグラフを密グラフ(den…