Document

アルゴリズムイントロダクション輪講
5章
D3照山順一
5章：集合
•
•
•
•
離散数学における基本的なもの
集合、関係、関数、グラフ、木
簡単に説明・・・
23章～27章：グラフアルゴリズムなので分か
らない用語が出てきたらここに戻るように。
5章：集合
• 集合：要素の集まり
• 空集合：
• 部分集合：
• 真部分集合：
• 積集合、和集合、差集合：
• 補集合：
• ド・モルガンの法則：
5章：集合
• 分割：
•
•
•
•
•
サイズ(要素数、基数)：
加算無限：自然数と1対1対応
非加算無限：自然数と1対1対応しない
べき集合：
直積：
5章：集合
• 包除原理(inclusion-exclusion)(問題5.1-3)
• 和集合のサイズ
5章：関係
• 2項関係：直積の部分集合
• 反射的(reflexive)：
• 対称的(symmetric)：
• 推移的(transitive)：
• ３つの性質を持つ関係を同値関係という。
5章：関係：同値関係
• 同値関係の例：
偶奇が同じ
Nで割ったあまりが同じ：mod N
• 集合を同値関係毎に分割してみる
同値類：
同値類の性質：
1：同値類は分割をなす
2：任意の分割は同値関係を表す
5章：関係：同値関係
1：同値類は分割をなす
Ⅰ：
反射性・推移性から、
よって、
Ⅱ：同値類の和集合はA
反射的なので、
5章：関係：同値関係
2：任意の分割は同値関係を表す
A上の分割：
次のような関係を考え、同値関係であることを示す：
反射性：aRa は自明
対称性：aRb : a, bは同じ集合の要素 ⇒ bRa
推移性： aRb かつ bRc ⇒ aRc
5章：関係：他の用語
• 反対称的： aRb かつ bRa の時、a=b
例）
• 反順序関係：反射的かつ反対称的
• 反順序集合：反順序関係が定義された集合
• 全順序：すべてのペアに対して反順序関係が成立
5章：関数
• 関数：
Aの要素すべてに対して、Bの要素が唯一に対応
• 単射、全射、全単射：
• 置換：
• 逆関数：
なる全単射
5章：グラフ
• 有向グラフ：
V：頂点集合
E：辺集合
1
2
3
4
5章：グラフ
• 無向グラフ：
V：頂点集合
E：辺集合
1
2
3
4
5章：グラフ
• 有向グラフと無向グラフで用語が少し変わる
頂点の次数
• 経路、閉路：
有向グラフ
無向グラフ
uからvに接続
uから出る、vに入る
uとv上に接続
uとvは隣接
出次数、入次数
次数＝出次数+入次数
隣接頂点の数
5章：グラフ
• 有向グラフ：
V：頂点集合
E：辺集合
1
2
3
4
5章：グラフ
• 有向グラフと無向グラフで用語が少し変わる
頂点の次数
有向グラフ
無向グラフ
uからvに接続
uから出る、vに入る
uとv上に接続
uとvは隣接
出次数、入次数
次数＝出次数+入次数
隣接頂点の数
• 経路、閉路：
• 連結：全頂点間に経路がある (有向：強連結)
• 同型：グラフが等価になる頂点間の全単射が存在
5章：グラフ
• 部分グラフ：
• 誘導グラフ：
1
2
3
4
5章：グラフ
• 部分グラフ：
• 誘導グラフ：
• 完全グラフ：全頂点間に辺がある
• ２部グラフ：頂点集合をV1とV2に分割した時、
辺がV1-V2間のみである
• 森：閉路がない無向グラフ
• 木：閉路がなく連結な無向グラフ
• ダグ(DAG)：閉路がない有向グラフ
5章：木
木：閉路のない連結な無向グラフ
＊以下の命題はすべて等価である
1：Gは木
2：任意の2頂点は唯一の単純経路で連結
3：Gは連結で、どの辺を除いても非連結となる
4：Gは連結で、|E| = |V|-1
5：Gは閉路を持たず、|E| = |V|-1
6： Gは閉路を持たず、一つでも辺を増やせば、閉路ができる
5章：木
1：Gは木
2：任意の2頂点は唯一の単純経路で連結
3：Gは連結で、どの辺を除いても非連結となる
4：Gは連結で、|E| = |V|-1
5：Gは閉路を持たず、|E| = |V|-1
6： Gは閉路を持たず、一つでも辺を増やせば、閉路ができる
(1)→(2)：経路が2つあると閉路があり矛盾
(2)→(3)：ほぼ自明
(3)→(4)：帰納法
5章：木
1：Gは木
2：任意の2頂点は唯一の単純経路で連結
3：Gは連結で、どの辺を除いても非連結となる
4：Gは連結で、|E| = |V|-1
5：Gは閉路を持たず、|E| = |V|-1
6： Gは閉路を持たず、一つでも辺を増やせば、閉路ができる
(4)→(5)：閉路を持つと連結でなくなる
(5)→(6)：閉路がない⇒森、森かつ辺の数→(1)、(1)→(2)
(6)→(1)：Gは連結
5章：いろいろな木
•
•
•
•
根付き木：先祖・子孫、親・子の関係
順序木： k番目の子かも区別
２分木 (k分木) ：子が高々２つ(k個)
位置木：何番目の子かラベルが付いている
根（root）
深さ（depth）

Download Report