SELECT * FROM life;

関係とグラフ

関係

関係

複数の集合の直積集合の部分集合

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度だけ通って同じ節点に戻ってくる枝の選び方

オイラーグラフ

オイラー閉路が存在するグラフ

• 与えられたグラフがオイラーグラフである為の必要十分条件
  • グラフが連結している
  • 各節点の次数が偶数
• 与えられたグラフがオイラー経路を持つ為の必要十分条件
  • グラフが連結している
  • 次数が奇数の接点が0個か2個

ハミルトングラフ

ハミルトングラフ

全ての節点を1度しか通らない閉路を持つグラフ

ハミルトン閉路問題

全ての節点を1度しか通らない閉路を探す問題

ハミルトン経路問題

全ての節点を1度しか通らない経路を探す問題

巡回セールスマン問題

ラベル付きグラフで距離最少の閉路を探す

グラフにおける最短問題

全域木

グラフの枝のみを用いてそのグラフの全ての節点を結ぶ木

最短全域木問題

ラベル付き連結無向グラフの全域木の中でコスト最小のものを探す

最短距離問題

ある節点から別の節点に至る最短距離の経路を求める

ツイートする