グラフ
グラフ中の有向閉路とは、エッジの向きに進んだときに、ぐるぐると回れてしまうような閉路を言う。今、有向グラフのうち、有向閉路を持たないグラフを無閉路有向グラフと呼ぶ。無閉路有向グラフにおいては、エッジの向きを無視すれば閉路は存在するものの、…
深さ優先探索は再帰表現がしやすく、幅優先探索は非再帰表現がしやすいと言う。その理由は次のようになる。 深さ優先探索では、探索過程において、多段階の保留状態を生み、その多段階の保留状態は、『当該段階』『当該段階より１つ上の段階』『当該段階より…
前項の推移閉包は、グラフにおける到達可能性(到達可能か否か)の情報を全ノードペアについて求める方法である『ウォーシャルの方法』についてであった。これは、到達可能性を全ノードペアについて行うことに他ならないが、同様に、任意の２ノード間の最短径…
(有向)グラフにおいて、あるノードからあるノードへ到達可能であるときに、その２ノード間にエッジを加えて作成したグラフを、そのグラフの推移閉包と言う。一度この推移閉包を作成すれば、(有向)グラフにおける径路の有無の情報はすぐに得られる。密なグラ…
グラフアルゴリズムではノードとノードと隣接関係が対象となっているのに対し、幾何学的アルゴリズムでは、物理的な位置とその距離が対象となっている。物理的な位置の情報を利用すると、探索対象を大幅に減らしうる。ＡＲＧにおいては(おそらく)、ランダム…
重みつきグラフにおいて、すべてのノードを結ぶエッジの集合で、辺の重みの総和が最小のもの 疎グラフの場合 大きくわけてアプローチは２つ １つのノードからスタートし、そのノードを含む木を成長させ、すべてのノードが結ばれるまで続ける(順位優先探索、…
深さ優先探索と同様に、ノードは『訪問済み』『訪問中』『未訪問』の３群に振り分けられる。『訪問中』のノードの中から１つを取り出して、『訪問済み』とする手続きを繰り返す点も深さ優先探索と同じである。違いは次の通り。深さ優先探索では、もっとも新…
グラフ上のあるノードからスタートし、隣接するノードを『訪問』する。『訪問中』のノードからさらに訪問可能なノードを『訪問』し、『訪問先』がなくなるまで続け、なくなったら、『訪問先』探索をまだ済ませていない『訪問中』のノードについて同様の処理…
グラフはノードとエッジという２つのパラメータを持つ点が、グラフ構造に関するアルゴリズムの検討に影響する。ノードとエッジの数をそれぞれV,Eとすると、EがVに比べ比較的少ないグラフを疎グラフ(sparse graph)、EがVに比べ比較的多いグラフを密グラフ(den…
グラフ理論系 GISシステム関係 ネットワーク・社会系 ベイズ Rのパッケージ deal
参考サイト 説明 Connected graphを考える Eccentricityは個々のノードに定義される あるノードについて、以外のすべてのノードについて、グラフ上の最短距離を求める(グラフ上の最短距離は、エッジに長さが与えられていなければ、エッジ数に同じ) 今、この…
参考PDF これはウェブネットワーク状態の可視化についての記載 座標決定法 線形手法 古典的多次元尺度法(Classical Multi-Dimensional Scaling (MDS)) ばねモデル すべてのノード間距離を可視化空間に実現することは無理である ノード間距離を「(ノードを結…
はじめに 参考PDF グラフの同形性評価(graph isomorphism)と類似性評価 Graph isomorphismはグラフ構成要素であるノードの1対1対応とエッジの1対1対応によって定義されている。それに対して、類似性評価は同形性からのはずれの程度の評価であり、その尺度は…
記号表 G=(V,E):グラフ V(G):グラフGの頂点集合 E(G):グラフGの辺集合 Kn:n頂点の完全グラフ Km,n:完全2部グラフ Q3:立方体グラフ Cn:長さnのサイクル Pn:長さnの道 Wn:車輪グラフ Sg:種類gの向き付け可能な閉曲面 χ(G):グラフGの彩色数 s(G) :グラフGの全域…
定理 定理1.1.1 グラフGの頂点をv1,v2,...,vpとし、d1,d2,...dpをそれぞれ頂点の次数とする。qをGの辺の個数とすると、次が成り立つ： d1+d2+...+dp=2q. 定理1.1.2 Havel, Hakimi 次の2つの非負整数列を考え、数列(1)は大きいものから順に並んでいるものとす…
10 曲面上のグラフ 10.1 グラフの循環 黒頂点に到達したときに、左方向に方向転換、白頂点に到達したときには右方向に方向転換する、という規則で、頂点が白黒に塗られたグラフを移動するようにしてやると、白黒の塗り方は、回路(circuit)を定義していること…
８ グラフの図 8.1 平面的グラフ 単純曲線(simple curve) 単純閉曲線(simple closed curve) ジョルダンの曲線定理(Jordan Curve Theorem):どんな単純閉曲線も平面を2つの領域、内部と外部とに分割する。 平面的グラフ(planar graph) 辺を交差させることなく…
７ 応用とアルゴリズム 7.1 全域木アルゴリズム グラフ理論のテキストで言うところのアルゴリズム 直観や実験によってはとくことができないほど複雑なグラフ(頂点数1000以上など）についての問題を解こうとしたときに、いつでも作動できることが保証されてい…
６ ラベル付きグラフ 6.1 魔法グラフと優美な木 マジック(magic, super-magicとも) q辺のグラフにおいて、その各辺を1,2,...,qの値でラベル付けしたとき、各頂点に接続する辺のラベルの総和がすべて同じにできるとき、そのグラフをマジックと呼ぶ。 反マジッ…
５ 数え上げ 5.1 1-因子の数え上げ 数え上げ問題(counting problem) ある数学的な対象が幾つ存在し得るのかを調べること。 nの階乗(n factorial, n!) 道は向きを無考慮の順列 組み合わせ 錯乱(derangements) 5.2 ケーリーの全域木公式 プリューファーによる…
４ 極値問題 4.1 テュランの定理 極値問題 ある特別な性質を持つ最大または最小のグラフは何かを問う問題のこと。 ここで言う、「最大」とは、通常、与えられた頂点数に対して、もっとも多い辺を有するグラフを指す。 位数(order) グラフGの頂点の個数のこと…
３ 回路とサイクル 3.1 オイラー回路 グラフ・多重グラフ・準回路を対象とする。 準グラフの用語 歩道(walk) 準グラフGの歩道とは、Gの頂点と辺の交互列。頂点も辺も繰り返し登場してよい。 開歩道と閉歩道 歩道の開始頂点と終了頂点が同じ場合を開歩道(open…
２ グラフの彩色(coloring) グラフの彩色には、頂点彩色と辺彩色とがある。 2.1 頂点彩色 頂点彩色 グラフにあって、隣接するどの2頂点も同色にならないように、全頂点に色を対応させることを、頂点の彩色という。 (頂点)彩色数(chromatic number,χ(G)) グラ…
１ グラフ理論の基礎 1.1 グラフと頂点の次数 グラフ(graph,G)の定義 頂点集合(verices, vertex set, V)と辺集合(edges, edge set, E)との「集合の対」である Vは空集合ではなく、Eは空集合であってもよい グラフで表現される「事象」の例 道路地図 分子化学…
遺伝統計学への応用を念頭に駆け足で読んで、メモにする テキスト：Library of Mathematical Science 2 『グラフ理論入門 Peals in Graph Theory』N.ハーツフィールド・G.リンゲル 著 鈴木晋一 訳 サイエンス社 おすすめ度★★★★★ グラフ理論入門 (数理科学ラ…
Javaソースはこちら
関係のある事象はグラフにできる。グラフにすると、グラフ理論特有の分岐探索の方法などに応用が利く。参考になったのは、SOFT BANK社『C MAGAZINE 2005年2月号』の特集2 問題を図式化して解く グラフ理論入門C MAGAZINE 2005年2月号 引用 http://d.hatena.n…
参考 URL Graph realization 定義 Graph realization problem: "Given subsets P1,..Pn of {0,..,m-1}, find a tree T=(V,E) with E={0,..,m-1} such that every Pi is a path in T, or determine that no such tree exists. " 日本語訳(一部意訳) 0からm-1…
参照文献：Mary Ann Liebert, Inc. - Journal of Computational Biology - 10(3-4):323 論理説明に用いられる用語の定義 PPH問題(Perfect Phylogeny Haplotyping Problem) Unphased data(SNPのdiploid genotype data)が与えられたときに、そこから、「組換え…
Diploidのジェノタイプデータから、ハプロタイプを推定する方法はいくつか(も)知られているが、そのようにして推定されたハプロタイプが、「ARG(Ancestral Recombination Graph)を描けるか＝祖先ハプロタイプからのCoalescenceとRecombinationとからできてき…
