10章 離散グラフ （discrete graph）

Presentation on theme: "10章 離散グラフ （discrete graph）"— Presentation transcript:

1 10章 離散グラフ （discrete graph）
情報数学（第11回） 10章　離散グラフ （discrete graph）

2 グラフとは 複数のコンポーネントからなるシステムを点と線でモデル化 交通路線図 組織図 分子構造図 回路図 フローチャート クラス図
教科書p 章 離散グラフ グラフとは 交通路線図 組織図 分子構造図 回路図 フローチャート クラス図 複数のコンポーネントからなるシステムを点と線でモデル化

3 教科書p. 154■離散グラフ 無向グラフ 𝑎 𝑏 𝑐 𝑒 𝑑 節点 無向辺 （2つの節点を結ぶ）

4 無向グラフ（undirected graph）
無向グラフ 𝐺= 𝑉,𝐸 もしくは 𝐺(𝑉,𝐸) 𝑉: 節点（vertex, node）の集合 𝐸⊆𝑉×𝑉: 𝑉上の無向辺（edge）の有限集合 ( 𝑣 1 , 𝑣 2 ) と ( 𝑣 2 , 𝑣 1 ) は 同じとみなす 「非順序対」とも言う ・𝐺= 𝑉,𝐸 , 𝑣 1 , 𝑣 2 ∈𝐸 であるとき, 「𝐺 において 𝑣 1 と 𝑣 2 は隣接する」という ・節点は頂点と呼ぶ場合も多い ・必要に応じて、𝑉, 𝐸 を無限集合とする場合もある

5 無向グラフ 𝑎 𝑏 𝑐 𝑒 𝑑 節点、頂点 (vertex) 無向辺（edge) 2つの節点を結ぶ 「節点𝑎と節点𝑏は隣接」
教科書p. 154■離散グラフ 無向グラフ 𝑎 𝑏 𝑐 𝑒 𝑑 節点、頂点 (vertex) 無向辺（edge) 2つの節点を結ぶ 「節点𝑎と節点𝑏は隣接」 　𝑉={𝑎, 𝑏, 𝑐, 𝑑, 𝑒} 　𝐸={(𝑎,𝑏), (𝑎,𝑐), (𝑏,𝑒), (𝑐,𝑑), (𝑐,𝑒), (𝑑,𝑒)} 　𝑉={𝑎, 𝑏, 𝑐, 𝑑, 𝑒} 　𝐸={(𝑏,𝑎), (𝑎,𝑐), (𝑏,𝑒), (𝑐,𝑑), (𝑐,𝑒), (𝑑,𝑒)}

6 演習1 次の無向グラフ 𝐺=(𝑉,𝐸) の図を描け。また、連結かどうか、 カットポイント、ブリッジがあればそれを示せ。
教科書p. 164■演習問題 演習1 次の無向グラフ 𝐺=(𝑉,𝐸) の図を描け。また、連結かどうか、 カットポイント、ブリッジがあればそれを示せ。 (1) 𝑉= 𝑝,𝑞,𝑟,𝑠,𝑡 , 𝐸={ 𝑝,𝑞 , 𝑝,𝑟 , 𝑝,𝑡 , 𝑞,𝑟 , 𝑞,𝑠 , 𝑞,𝑡 , 𝑟,𝑠 } (2) 𝑉= 𝑝,𝑞,𝑟,𝑠,𝑡 , 𝐸={ 𝑝,𝑞 , 𝑝,𝑠 , 𝑞,𝑠 , 𝑟,𝑡 } (3) 𝑉= 𝑝,𝑞,𝑟,𝑠,𝑡 , 𝐸={ 𝑝,𝑞 , 𝑝,𝑟 , 𝑝,𝑠 , 𝑞,𝑡 , 𝑟,𝑠 }

7 論理回路の無向グラフ表現 𝐽 𝐶 𝐾 𝑄 𝑔1 𝑔4 𝑔2 𝑔3

8 教科書p. 154■離散グラフ 有向グラフ 節点 𝑎 𝑏 𝑐 𝑑 𝑒 有向辺 ループ辺

9 有向グラフ（directed graph or digraph）
有向グラフ 𝐺=(𝑁,𝐴) 𝑁: 節点（vertex, node）の集合 𝐴⊆𝑁×𝑁:　𝑁上の有向辺（arc）の有限集合 ( 𝑛 1 , 𝑛 2 ) と ( 𝑛 2 , 𝑛 1 ) は異なる 「順序対」とも言う 𝑛 1 , 𝑛 2 : 始節点 𝑛 1 , 終節点 𝑛 2 ・ループ辺 𝑛 1 , 𝑛 1 ∈𝐴 を許す場合が多い e.g. 反射的関係の関係グラフ

10 有向グラフ 節点（node) 𝑏 𝑎 有向辺（arc) 始節点𝑎, 終節点𝑏 ループ辺（loop) 𝑐 𝑒 𝑑
　𝑉={𝑎, 𝑏, 𝑐, 𝑑, 𝑒} 　𝐸={ 𝑎,𝑏 , 𝑎,𝑐 , 𝑏,𝑒 , 𝑐,𝑒 , 𝑒,𝑐 , 𝑑,𝑐 , 𝑑,𝑒 ,(𝑒,𝑒)}

11 道路網の有向グラフ表現 右折 禁止 Uターン 一方通行が表現できる 右折/Uターン禁止を表現するには、少し工夫が必要

12 右折/Uターン禁止の交差点 Uターン 禁止 右折 禁止 Uターン 禁止

13 多重グラフと辺ラベル 阪急 阪神 辺ラベルにより区別 辺はラベルを加えた3項組で表現 e.g.(梅田，三宮, 阪急) 三宮 多重辺 梅田
教科書p. 154■離散グラフ 多重グラフと辺ラベル 三宮 梅田 阪急 阪神 多重辺 辺ラベルにより区別 辺はラベルを加えた3項組で表現 e.g.(梅田，三宮, 阪急)

14 重みつきグラフ（weighted graph）
4 3 2 2 2 1 ・重みはコスト（小さい方がよい）や 　容量（大きい方がよい）を表す ・負の重みを許す場合もある

15 以降は主に 多重辺、ループ、辺の重みを持たない 　　　　　　　　「単純無向グラフ」 で話を進めるが、ほとんどは、 有向グラフや 多重辺、ループを許す場合 重みつきグラフ でも、ほぼ同様の議論ができる

16 部分グラフ（subgraph） 𝐺=(𝑉,𝐸)に対して 𝑉 ′ ⊆𝑉 𝐸 ′ ⊆𝐸 𝐸 ′ ⊆ 𝑉 ′ ×𝑉′
教科書にはない 部分グラフ（subgraph） 𝐺=(𝑉,𝐸)に対して 𝑉 ′ ⊆𝑉 𝐸 ′ ⊆𝐸 𝐸 ′ ⊆ 𝑉 ′ ×𝑉′ であるとき、 𝐺 ′ =( 𝑉 ′ , 𝐸 ′ ) は𝐺 の部分グラフであるという 𝐺 𝐺′ 𝑏 𝑎 𝑐 𝑒 𝑑 𝑎 𝑐 𝑒 𝑑 𝑉= 𝑎,𝑏,𝑐,𝑑,𝑒 𝐸={ 𝑎,𝑏 , 𝑎,𝑐 , 𝑏.𝑒 , 𝑐,𝑑 , 𝑐,𝑒 ,(𝑑,𝑒)} 𝑉= 𝑎,𝑏,𝑐,𝑑,𝑒 𝐸={ 𝑎,𝑏 , 𝑎,𝑐 , 𝑏.𝑒 , 𝑐,𝑑 , 𝑐,𝑒 ,(𝑑,𝑒)}

17 部分グラフ 𝐺′ 𝐸 ′ ⊆𝐸でない 𝐺 𝐺′′ 𝑉′= 𝑎,𝑐,𝑑,𝑒 𝐸′={ 𝑎,𝑒 , 𝑎,𝑐 ,
𝑐,𝑑 , 𝑐,𝑒 ,(𝑑,𝑒)} 𝐸 ′ ⊆𝐸でない 𝐺 𝑏 𝑎 𝑐 𝑒 𝑑 𝑉= 𝑎,𝑏,𝑐,𝑑,𝑒 𝐸={ 𝑎,𝑏 , 𝑎,𝑐 , 𝑏.𝑒 , 𝑐,𝑑 , 𝑐,𝑒 ,(𝑑,𝑒)} 𝐺′′ 𝑏 𝑎 𝑐 𝑒 𝐸 ′ ⊆𝑉′×𝑉′でない

18 教科書p. 155■同型グラフ 同型グラフ 𝐺 1 = 𝑉 1 , 𝐸 1 , 𝐺 2 =( 𝑉 2 , 𝐸 2 ) について、隣接関係を保存する 𝑉 1 から 𝑉 2 への全単射 𝑓 が存在するとき、 𝐺 1 と 𝐺 2 は同型である（isomorphic）という 𝑣 𝑖 , 𝑣 𝑗 ∈ 𝐸 1 iff 𝑓 𝑣 𝑖 ,𝑓 𝑣 𝑗 ∈ 𝐸 2 𝑎 𝑏 𝑐 𝑑 𝑒 𝑎 𝑏 𝑐 𝑑 𝑒 𝑝 𝑞 𝑟 𝑠 𝑡 𝑓 𝑝 𝑞 𝑟 𝑠 𝑡

19 同型グラフ 𝑎 𝑏 𝑐 𝑑 𝑝 𝑞 𝑟 𝑠 クイズ 𝐺 1 = 𝑉 1 , 𝐸 1 , 𝐺 2 = 𝑉 2 , 𝐸 2 に対して、
教科書p. 155■同型グラフ 同型グラフ 𝑎 𝑏 𝑐 𝑑 𝑝 𝑞 𝑟 𝑠 𝑎 𝑏 𝑐 𝑑 𝑝 𝑞 𝑟 𝑠 クイズ 𝐺 1 = 𝑉 1 , 𝐸 1 , 𝐺 2 = 𝑉 2 , 𝐸 2 に対して、 𝑉 1 = 𝑉 2 かつ 𝐸 1 = 𝐸 2 であることは 𝐺 1 と 𝐺 2 が同型であるための　　　条件

20 節点の次数 節点の次数（degree）：その節点に接続している辺の数 次数: 0 孤立点 偶節点 奇節点 次数：4 次数：1
教科書p. 156■離散グラフの特徴 節点の次数 節点の次数（degree）：その節点に接続している辺の数 次数: 0 孤立点 偶節点 奇節点 次数：4 次数：1

21 節点の次数（有向グラフの場合） 入口 節点の出次数（out degree）：その節点を始節点とする辺の数
教科書p. 156■離散グラフの特徴 節点の次数（有向グラフの場合） 節点の出次数（out degree）：その節点を始節点とする辺の数 節点の入次数（in degree）：その節点を終節点とする辺の数 𝑝 入口 出口 𝑟 𝑞 入次数=0 出次数=0 𝑠 𝑡 入次数=2 出次数=1

22 径路（walk） グラフをたどる節点（もしくは辺）の列を径路とよぶ 始点（initial vertex） 終点 （final vertex）
教科書p. 156■離散グラフの特徴 径路（walk） グラフをたどる節点（もしくは辺）の列を径路とよぶ 始点（initial vertex） 終点 （final vertex） 径路 [𝑎,𝑑,𝑏,𝑎,𝑑,𝑒] または [ 𝑎,𝑑 , 𝑑,𝑏 , 𝑏,𝑎 , 𝑎,𝑑 ,(𝑑,𝑒)] 𝑎 𝑒 𝑏 𝑑 𝑐 径路の長さ：　(辺の数)=(節点の数)−1=5

23 小道（trail） 径路の概念はモデル化の対象によっては一般的過ぎるので 辺に重複のない径路を「小道」と呼んで区別する 小道
教科書p. 156■離散グラフの特徴 小道（trail） 径路の概念はモデル化の対象によっては一般的過ぎるので 辺に重複のない径路を「小道」と呼んで区別する 小道

24 順路（path） さらに（始点と終点を除き）節点に重複の無い径路（小道）を 「順路」と呼んで区別する 順路

25 閉路（cycle, circuit）と単純閉路
教科書p. 156■離散グラフの特徴 閉路（cycle, circuit）と単純閉路 閉路：　両端（始点と終点）が同じ小道（または径路） 単純閉路：　順路の条件を満たす閉路 単純閉路

26 径路、小道、順路の包含関係 径路（walk） 小道（trail） 順路（path） 閉路 単純閉路 （cycle）
（simple cycle）

27 教科書p. 156■離散グラフの特徴 有向グラフの径路 有向径路： 有向辺の向きに沿った径路 有向小道： 有向辺の向きに沿った小道 有向順路： 有向辺の向きに沿った順路 有向閉路： 有向辺の向きに沿った閉路 逆有向辺： 逆向きの辺 𝑎,𝑏 に対して(𝑏,𝑎) 径路：　有向辺の向きを無視した径路

28 演習2 次の無向グラフについて以下の問いに答えよ (1) 𝑎 から 𝑓 への順路は何通りあるか (2) 𝑒 を含む単純閉路はいくつあるか
教科書p. 164■演習問題 演習2 次の無向グラフについて以下の問いに答えよ (1)　𝑎 から 𝑓 への順路は何通りあるか (2)　𝑒 を含む単純閉路はいくつあるか (3)　𝑎 と 𝑓 の間の距離を求めよ (4)　グラフの直径を求めよ (5)　カットポイントはどれか、すべて示せ (6)　ブリッジはどれか、すべて示せ 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑔 ℎ 𝑖

29 無向グラフの連結性 無向グラフで、任意の2節点間に経路が存在するグラフを連結である（connected）といい、そのグラフを連結グラフという
教科書p. 156■離散グラフの特徴 無向グラフの連結性 無向グラフで、任意の2節点間に経路が存在するグラフを連結である（connected）といい、そのグラフを連結グラフという 非連結 連結

30 教科書p. 156■離散グラフの特徴 節点間の距離とグラフの直径 連結グラフ𝐺で、2節点 𝑣 1 , 𝑣 2 間の最短の順路の長さを 𝑣 1 , 𝑣 2 間の距離（distance）といい、2節点間の距離の最大値をグラフ𝐺の直径（diameter）という。 1 3 4 2 重み付きグラフ 𝑎 𝑎, 𝑏間の距離: 𝑑𝑖𝑠𝑡 𝑎,𝑏 =2 グラフの直径： max 𝑥,𝑦∈𝑉 𝑑𝑖𝑠𝑡(𝑥,𝑦) =𝑑𝑖𝑠𝑡 𝑎,𝑐 =5 𝑏 𝑐

31 教科書p. 156■離散グラフの特徴 切断点、橋 連結グラフ 𝐺 で、ある節点 𝑣 と 𝑣 に連結する辺を除くと非連結になるとき、𝑣 は 𝐺 の切断点（cut point）であるといい、ある辺 𝑒 除くと非連結になるとき、𝑒 は 𝐺 の橋（bridge）であるという 橋 切断点

32 演習1 次の無向グラフ 𝐺=(𝑉,𝐸) の図を描け また、連結かどうか、 カットポイント、ブリッジがあればそれを示せ
教科書p. 164■演習問題 演習1 次の無向グラフ 𝐺=(𝑉,𝐸) の図を描け　また、連結かどうか、 カットポイント、ブリッジがあればそれを示せ (1) 𝑉= 𝑝,𝑞,𝑟,𝑠,𝑡 , 𝐸={ 𝑝,𝑞 , 𝑝,𝑟 , 𝑝,𝑡 , 𝑞,𝑟 , 𝑞,𝑠 , 𝑞,𝑡 , 𝑟,𝑠 } (2) 𝑉= 𝑝,𝑞,𝑟,𝑠,𝑡 , 𝐸={ 𝑝,𝑞 , 𝑝,𝑠 , 𝑞,𝑠 , 𝑟,𝑡 } (3) 𝑉= 𝑝,𝑞,𝑟,𝑠,𝑡 , 𝐸={ 𝑝,𝑞 , 𝑝,𝑟 , 𝑝,𝑠 , 𝑞,𝑡 , 𝑟,𝑠 } 解答がおかしい

33 演習2 次の無向グラフについて以下の問いに答えよ (1) 𝑎 から 𝑓 への順路は何通りあるか (2) 𝑒 を含む単純閉路はいくつあるか
教科書p. 164■演習問題 演習2 次の無向グラフについて以下の問いに答えよ (1)　𝑎 から 𝑓 への順路は何通りあるか (2)　𝑒 を含む単純閉路はいくつあるか (3)　𝑎 と 𝑓 の間の距離を求めよ (4)　グラフの直径を求めよ (5)　カットポイントはどれか、すべて示せ (6)　ブリッジはどれか、すべて示せ 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑔 ℎ 𝑖

34 教科書p. 156■離散グラフの特徴 有向グラフの連結性 有向グラフで、任意の2節点間に双方向に有向順路が存在するものを強連結（strongly connected）グラフといい、辺の向きを無視すると順路が存在するものを弱連結（weakly connected）グラフという 強連結グラフ （辺を一つ除去すると弱連結になる）

35 完全グラフ、正則グラフ 教科書p. 157■離散無向グラフ 任意の2節点間に辺がある無向グラフを完全（complete）グラフといい、節点数 𝑛 の完全グラフを 𝐾 𝑛 と表記する すべての節点の次数が等しい（𝑛とする）無向グラフを正則（regular）グラフといい、𝑛 をどの正則グラフの次数という 完全グラフ 𝐾 5 次数3の正則グラフ

36 演習4 次の正則グラフで同型でないものを2つ以上描け (1) 節点数6、3次の正則グラフ (2) 節点数6、4次の正則グラフ
教科書p. 164■演習問題 演習4 次の正則グラフで同型でないものを2つ以上描け (1)　節点数6、3次の正則グラフ (2)　節点数6、4次の正則グラフ (3)　節点数7、4次の正則グラフ

37 2部（bipartite）グラフ 無向グラフ 𝐺=(𝑉,𝐸) において 𝑉= 𝑉 1 + 𝑉 2 （ + は直和） 𝐸⊆ 𝑉 1 × 𝑉 2
𝑉= 𝑉 1 + 𝑉 2 （ + は直和） 𝐸⊆ 𝑉 1 × 𝑉 2 なる 𝑉 1 , 𝑉 2 が存在するとき、𝐺 は2部グラフであるという。特に、 𝑉 1 中のすべての節点と 𝑉 2 中のすべての節点間に辺が存在するものを完全2部グラフといい、 𝐾 𝑉 1 ,| 𝑉 2 | と表記する 完全2部グラフ 𝐾 3,2 2部グラフ

38 論理回路の2部グラフ表現 𝐽 𝐶 𝐾 𝑄 𝑔1 𝑔4 𝑔2 𝑔3

39 無向木（undirected tree） 教科書p. 157■離散無向グラフ 無向グラフ 𝐺=(𝑉,𝐸) において、任意の2節点間にちょうど1つだけ順路が存在するとき、𝐺 は（無向）木であるという。 いくつかの無向木が集まった非連結グラフを林あるいは森（forest）ということがある （無向）木 森 無閉路かつ連結 無閉路

40 補（complement）グラフ 教科書p. 157■離散無向グラフ 無向グラフ 𝐺=(𝑉,𝐸) に対して、同じ節点集合からなる完全グラフを 𝐺 𝑉 =(𝑉, 𝐸 𝐾 )として、 𝐺 ′ =(𝑉, 𝐸 𝐾 −𝐸) を 𝐺 の補グラフという a b e c d a b e c d グラフ 𝐺 𝐺 の補グラフ 𝐺’ 完全グラフ 𝐾 5

41 自己補（self complement）グラフ
𝐺 の補グラフ 𝐺′ が 𝐺 と同型であるとき、𝐺 は自己補グラフであるという a b d c e a b d c e 補グラフ 一致 同型 a e d b c

42 隣接行列 𝐺=(𝑉,𝐸) の節点間の隣接関係を 𝑉 ×|𝑉| 行列で表現したものを𝐺 の隣接行列という
教科書p. 158■隣接行列 隣接行列 𝐺=(𝑉,𝐸) の節点間の隣接関係を 𝑉 ×|𝑉| 行列で表現したものを𝐺 の隣接行列という 𝑉={𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5} 𝐸= {(𝑣1, 𝑣1), (𝑣1, 𝑣4), (𝑣2, 𝑣1), (𝑣2, 𝑣3), 𝑣3, 𝑣2 , 𝑣3, 𝑣5 , 𝑣4, 𝑣1 , 𝑣4, 𝑣4 , (𝑣5, 𝑣3)} (b) 隣接行列表現 1: 辺が有る 0: 辺が無い (a) 有向グラフの集合表現

43 隣接行列のブール積 グラフ 𝐺=(𝑉,𝐸)の隣接行列 𝐺のブール積𝐺2 ブール積 ブール和
教科書p. 159■隣接行列の積 隣接行列のブール積 グラフ 𝐺=(𝑉,𝐸)の隣接行列 𝐺のブール積𝐺2 ブール積 ブール和 (𝑖, 𝑗)成分 𝑔 2 𝑖𝑗 = 𝑔 𝑖1 𝑔 1𝑗 + 𝑔 𝑖2 𝑔 2𝑗 +……+ 𝑔 𝑖|𝑉| 𝑔 |𝑉|𝑗 𝐺に辺(𝑖,1)と辺(1,𝑗)があるか? それらの論理和：　𝑖 から 𝑗への長さ2の径路の有無 径路「𝑖→1→𝑗」の有無 . 𝐺に辺(𝑖, 𝑉 )と辺( 𝑉 ,𝑗)があるか? . 径路「𝑖→|𝑉|→𝑗」の有無 𝐺 𝑘 の(𝑖,𝑗)成分「 𝑔 𝑘 𝑖𝑗 」:　𝑖 から 𝑗への長さ𝑘の径路の有無

44 多重グラフの隣接行列の積 グラフ 𝐺=(𝑉,𝐸)の隣接行列 𝐺の算術積𝐺2 算術和 算術積
教科書p. 160■多重グラフの隣接行列 多重グラフの隣接行列の積 グラフ 𝐺=(𝑉,𝐸)の隣接行列 𝐺の算術積𝐺2 算術和 算術積 (𝑖, 𝑗)成分 𝑔 2 𝑖𝑗 = 𝑔 𝑖1 𝑔 1𝑗 + 𝑔 𝑖2 𝑔 2𝑗 +……+ 𝑔 𝑖|𝑉| 𝑔 |𝑉|𝑗 それらの算術和：　𝑖 から 𝑗への長さ2の径路の数 径路「𝑖→1→𝑗」の数 . 径路「𝑖→|𝑉|→𝑗」の数 𝐺 𝑘 の(𝑖,𝑗)成分「 𝑔 𝑘 𝑖𝑗 」:　𝑖 から 𝑗への長さ𝑘の径路の数

45 まとめ 離散グラフのその諸概念 ・無向グラフ、有向グラフ、多重グラフ、重みつきグラフ ・部分グラフ、同型グラフ ・節点の次数
・径路、小道、順路、閉路と単純閉路 ・無向グラフの連結性、節点間の距離、グラフの直径 ・切断点と橋 ・有向グラフの強連結と弱連結 ・完全グラフ、正則グラフ、2部グラフ、 完全2部グラフ、無向木 ・補グラフ、自己補グラフ ・グラフの隣接行列