アルゴリズムイントロダクション輪講 5章 D3照山順一 5章:集合 • • • • 離散数学における基本的なもの 集合、関係、関数、グラフ、木 簡単に説明・・・ 23章~27章:グラフアルゴリズムなので分か らない用語が出てきたらここに戻るように。 5章:集合 • 集合:要素の集まり • 空集合: • 部分集合: • 真部分集合: • 積集合、 和集合、 差集合: • 補集合: • ド・モルガンの法則: 5章:集合 • 分割: • • • • • サイズ(要素数、基数): 加算無限:自然数と1対1対応 非加算無限:自然数と1対1対応しない べき集合: 直積: 5章:集合 • 包除原理(inclusion-exclusion)(問題5.1-3) • 和集合のサイズ 5章:関係 • 2項関係:直積の部分集合 • 反射的(reflexive): • 対称的(symmetric): • 推移的(transitive): • 3つの性質を持つ関係を同値関係という。 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章:グラフ • 部分グラフ: • 誘導グラフ: • 完全グラフ:全頂点間に辺がある • 2部グラフ:頂点集合を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番目の子かも区別 2分木 (k分木) :子が高々2つ(k個) 位置木:何番目の子かラベルが付いている 根(root) 深さ(depth)
© Copyright 2025 ExpyDoc