グラフ理論について

ジル･スティングレイ @katrbe_

経営工学概論3回目、小林の最後の授業です。

ジル･スティングレイ @katrbe_

ノード集合とアーク集合(エッジ集合)、エッジ:無向でアーク:有向

ジル･スティングレイ @katrbe_

ノード集合は点、無向グラフ(地点を結ぶ経路のようなもの)、有向グラフ(相関図のようなもの(矢印付き))

ジル･スティングレイ @katrbe_

グラフ(有向、無向)またはネットワークと呼ぶ。語感としてはネットワークのほうが分かりやすいか？

ジル･スティングレイ @katrbe_

有向グラフは順序対で(V,A)でVは集合、A≦V*VはVの順序対の集合。であるもののこと。V:ノード集合、A:アーク集合。

ジル･スティングレイ @katrbe_

V＝{1,2,3}とするとV*Vは{1,2,3}*{1,2,3}と表せる。またそれ＝{(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)}と表せる。(組み合わせていく感じ)9個からなる 。 ≦:(左辺は右辺の部分集合)

ジル･スティングレイ @katrbe_

Vはノードの集合、の中からいくつかとってきたものをアーク集合という。順序対とは？←説明を聞いたが少しよくわからない。有向グラフでは(2,3)と(3,2)の意味は違う。矢印の向きが違うため

ジル･スティングレイ @katrbe_

V＝{1,2,3} A＝{(1,2),(1,3),(2,3),(3,1)} こちらのほうを「グラフ」と呼ぶ

ジル･スティングレイ @katrbe_

①→→②→→③　 ↓↑　　　　　↓↑　 　　←← 　　→→ 図示したもの

ジル･スティングレイ @katrbe_

Vの要素をノード、頂点、点と呼ぶ Aの要素をアーク、辺と呼ぶ。 (スライドが進んだためAについては曖昧まいんちゃん)

ジル･スティングレイ @katrbe_

無向グラフとは順序対(V,E)でVは集合、E∈2^VはVの要素数2の部分集合であるもののこと。 2^V:Vのべき集合という V＝{1,2,3} 2^V＝{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} 8個＝2^3となる

ジル･スティングレイ @katrbe_

なぜ3乗か？ １をとる/とらない＊２をとる/とらない＊３をとる/とらない

ジル･スティングレイ @katrbe_

無向グラフを図示すると。 E＝{{1,2},{2,3}} ①→②→③ と書ける。有向グラフと違い向きがないので{1,3}と{3,1}の意味は同じ

ジル･スティングレイ @katrbe_

無向グラフ(Eの要素を辺と呼ぶ) 辺(u,v)∈Eに対して、u,vを端点と呼ぶ。 ⓤ─ⓥ 頂点vが辺Eの端点であるとき、vはEに接続する、という。uとvが辺eをなすときuとvは隣接する。という。(街と街が隣接する、という言い方？離れていても空路で繋がっていたら隣接であるのか)

ジル･スティングレイ @katrbe_

グラフを図示する際は用途によっていろいろな書き方がある。ちゃんと見やすいように書こう。

ジル･スティングレイ @katrbe_

休憩をはさみました、続きます。

ジル･スティングレイ @katrbe_

次数とは(無向グラフ)、G＝(V,E)、頂点v∈V vの次数とはvに接続する辺の数のこと。数式で書くと deg_g(v)=|{e∈E|u∈E(e={u,v})}| |①|②|:①は②を満たすEの中のもの？という認識でよいのだろうが？ 図示したものから考えたほうが圧倒的に良い。

ジル･スティングレイ @katrbe_

点(ノード)から何本の線が出ているか？で見る

ジル･スティングレイ @katrbe_

有向グラフ、G＝(V,A),頂点v∈V vの入次数とは、vを終点とする弧の数のこと deg_g(v)=|{a∈A|u∈V(a=(u,v))| ①→②←③ ↑ ④ deg(1)=1 deg(2)=2

ジル･スティングレイ @katrbe_

出次数というものも存在する。 vを始点とするもの deg_g(v)=|{a∈A|u∈V(a=(v,u))| 上記と同様の図で deg(1)=1 deg(3)=1 deg(2)=0

ジル･スティングレイ @katrbe_

握手補題　無向グラフG=(V,E) 握手補題　Σdeg_g(v)=2|E| (ちょっと自分で調べて) 次数をすべて足して、2で割ったら辺の数と同じになるよ？見たいいな感じ

ジル･スティングレイ @katrbe_

pic.twitter.com/Jxahw8r34p

拡大

ジル･スティングレイ @katrbe_

ゆるして

ジル･スティングレイ @katrbe_

最後は握手補題の証明でした。最短経路問題等の根底にあるのは離散数学。