離散構造とアルゴリズム


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

次数:グラフ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の点数最大の独立点集合を求めよ

オーダーの話