次数：グラフGの点vに接続している辺の数
同型：1対1に対応する点があれば、同型
トレイル：全部違う辺を通る
パス：全部違う点を通る
ウォーク⊇トレイル⊇パス
隣接行列
行列の縦横が両方とも点
隣接していたら1
対照的な正方行列になる
接続行列
行列の縦が点、横が辺
点から辺が接続していたら1
縦の合計は2（一つの辺に接続する点は2点）
横の合計はその点の次数
定理
Σ次数(v) = 2|E(G)|
木：任意の2点が一意につながる/閉路を含まない連結
全域部分グラフ：Gの点を全て持った部分グラフ
部分グラフ：Gのある一部分だけを取ったグラフ
全域木：全域部分グラフかつ木である
完全グラフ：すべての2点が辺で結ばれている
2部グラフ：二つの独立点集合に分けられる（二色で塗ることが可能）
完全2部グラフ：二つの独立点集合X, Yに分けられ、全てのXとYが辺で結ばれている
ハミルトングラフ：すべての点を含む閉路が存在する
オイラー閉トレイル：グラフの全ての点と全ての辺を通る閉トレイル（一筆書きが出来る）
単純グラフ：任意の2点のパスが一意に定まるグラフ（ループなどがない）
平面グラフ：辺が交差することなく平面に書くことが出来る
Gが連結：任意の2点がつながる
⇔Gに全域木が存在する
Gが2部グラフ：二つの独立点集合に分けられる
⇔Gが奇閉路を含まない
Gがオイラーグラフ：一筆書きが出来るグラフ
⇔Gのすべての点が偶点
オイラーグラフにはオイラー閉トレイルが存在する
Gにオイラートレイルが存在⇔Gに奇点が2つ以下（始点と終点）
判定問題
質問に対してYesならば、探索問題はその根拠や答えを示すもの。
最適化問題は最大とか最小を入れれば良い。真部分集合としてGと一致すれば良い。
オイラーグラフ判定問題
入力：グラフG
質問：Gはオイラーグラフか
探索問題
入力：グラフG
質問：Gがオイラーグラフならばオイラー閉トレイルを一つ示せ
最適化問題
入力：グラフG
質問：Gの長さが最大である閉トレイルを一つ示せ
ハミルトングラフ判定問題
入力：グラフG
質問：Gはハミルトングラフか
探索問題
入力：グラフG
質問：Gがハミルトングラフならばハミルトン閉路を一つ示せ
最適化問題
入力：グラフG
質問：Gの長さが最大である閉路を一つ示せ
グラフ同型問題
入力：グラフGとH
質問：GとHは同型か
探索問題
入力：グラフGとH
質問：GとHが同型ならば同型写像を一つ示せ
最適化問題
入力：グラフGとH
質問：GとHの同型な部分グラフで点数最大のものを求めよ
連結性判定問題
入力：グラフG
質問：Gは連結か
探索問題
入力：グラフG
質問：Gが連結ならば、全域木を一つ示せ。/Gが連結ならば、すべての2点間のパスを示せ。
最適化問題
入力：グラフG
質問：Gの点数最大の全域部分グラフを示せ
判定問題
入力：グラフG、k
質問：Gに点数k以上の独立点集合があるか
探索問題
入力：グラフG、k
質問：Gに点数k以上の独立点集合があるならば、一つ示せ
最適化問題
入力：グラフG
質問：Gの点数最大の独立点集合を求めよ
オーダーの話
最終更新：2013年05月31日 01:43
