関係とグラフ
関係
- 関係
- 複数の集合の直積集合の部分集合
- m項関係
- m個の集合の関係
【例】
2つの集合
"学生"={鈴木,田中,山田}
"住所"={大阪,京都,神戸}
の直積
"学生"×"住所"={(鈴木,大阪)(鈴木,京都)(鈴木,神戸),(田中,大阪),...}
の部分集合
{(鈴木,大阪),(田中,京都),(山田,神戸)}
は2項関係である
関係操作
- 射影
- 大きな関係から特定の属性を取り出して必要な部分を抜き出す操作
- 選択
- 一部の組を選ぶ
- 結合
- 小さな関係を合わせて大きな関係にする
- 自然結合
- 二つの関係の等しい属性名の等しい値どうしを結びつけることによってもｔの二つの関係の属性集合をすべてもつような関係を求める
2項関係とグラフ
集合S×Tの部分集合で２項関係Rが定義されるとき、SをRの定義域、TをRの値域という
S,Tが異なる場合、２部グラフを用いて図示できる
特殊なグラフ
- 反射的
- Sの全要素aに対し、(a,a)∈Rを満たすグラフ
- 対称的
- 全(a,b)∈Rに対し、(b,a)∈Rを満たすグラフ（無向グラフ）
- 推移的
- (a,b)∈R,(b,c)∈Rなら(a,c)∈Rを満たすグラフ
- 同値関係
- Rが反射的かつ対称的かつ推移的であるグラフ
ラベル付きグラフ
- ラベル付きグラフ
- 枝にラベルが付いているぐらふ。俗に言う重み付きグラフ
グラフの利用
オイラーグラフ
ハミルトングラフ
- ハミルトングラフ
- 全ての節点を1度しか通らない閉路を持つグラフ
- ハミルトン閉路問題
- 全ての節点を1度しか通らない閉路を探す問題
- ハミルトン経路問題
- 全ての節点を1度しか通らない経路を探す問題
- 巡回セールスマン問題
- ラベル付きグラフで距離最少の閉路を探す
グラフにおける最短問題
- 全域木
- グラフの枝のみを用いてそのグラフの全ての節点を結ぶ木
- 最短全域木問題
- ラベル付き連結無向グラフの全域木の中でコスト最小のものを探す
- 最短距離問題
- ある節点から別の節点に至る最短距離の経路を求める
