2005-09-27から1日間の記事一覧

グラフ理論入門 補2 記号集

記号表 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.1 グラフGの頂点をv1,v2,...,vpとし、d1,d2,...dpをそれぞれ頂点の次数とする。qをGの辺の個数とすると、次が成り立つ: d1+d2+...+dp=2q. 定理1.1.2 Havel, Hakimi 次の2つの非負整数列を考え、数列(1)は大きいものから順に並んでいるものとす…

グラフ理論入門 10 曲面上のグラフ

10 曲面上のグラフ 10.1 グラフの循環 黒頂点に到達したときに、左方向に方向転換、白頂点に到達したときには右方向に方向転換する、という規則で、頂点が白黒に塗られたグラフを移動するようにしてやると、白黒の塗り方は、回路(circuit)を定義していること…

グラフ理論入門 8 グラフの図

8 グラフの図 8.1 平面的グラフ 単純曲線(simple curve) 単純閉曲線(simple closed curve) ジョルダンの曲線定理(Jordan Curve Theorem):どんな単純閉曲線も平面を2つの領域、内部と外部とに分割する。 平面的グラフ(planar graph) 辺を交差させることなく…

グラフ理論入門 7 応用とアルゴリズム

7 応用とアルゴリズム 7.1 全域木アルゴリズム グラフ理論のテキストで言うところのアルゴリズム 直観や実験によってはとくことができないほど複雑なグラフ(頂点数1000以上など)についての問題を解こうとしたときに、いつでも作動できることが保証されてい…

グラフ理論入門 6 ラベル付きグラフ

6 ラベル付きグラフ 6.1 魔法グラフと優美な木 マジック(magic, super-magicとも) q辺のグラフにおいて、その各辺を1,2,...,qの値でラベル付けしたとき、各頂点に接続する辺のラベルの総和がすべて同じにできるとき、そのグラフをマジックと呼ぶ。 反マジッ…

グラフ理論入門 5 数え上げ

5 数え上げ 5.1 1-因子の数え上げ 数え上げ問題(counting problem) ある数学的な対象が幾つ存在し得るのかを調べること。 nの階乗(n factorial, n!) 道は向きを無考慮の順列 組み合わせ 錯乱(derangements) 5.2 ケーリーの全域木公式 プリューファーによる…

グラフ理論入門 4 極値問題

4 極値問題 4.1 テュランの定理 極値問題 ある特別な性質を持つ最大または最小のグラフは何かを問う問題のこと。 ここで言う、「最大」とは、通常、与えられた頂点数に対して、もっとも多い辺を有するグラフを指す。 位数(order) グラフGの頂点の個数のこと…

グラフ理論入門 3 回路とサイクル

3 回路とサイクル 3.1 オイラー回路 グラフ・多重グラフ・準回路を対象とする。 準グラフの用語 歩道(walk) 準グラフGの歩道とは、Gの頂点と辺の交互列。頂点も辺も繰り返し登場してよい。 開歩道と閉歩道 歩道の開始頂点と終了頂点が同じ場合を開歩道(open…

グラフ理論入門 2 彩色

2 グラフの彩色(coloring) グラフの彩色には、頂点彩色と辺彩色とがある。 2.1 頂点彩色 頂点彩色 グラフにあって、隣接するどの2頂点も同色にならないように、全頂点に色を対応させることを、頂点の彩色という。 (頂点)彩色数(chromatic number,χ(G)) グラ…

グラフ理論入門 1 基礎

1 グラフ理論の基礎 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.リンゲル 著 鈴木晋一 訳 サイエンス社 おすすめ度★★★★★ グラフ理論入門 (数理科学ラ…