隣接行列
𝑉 = {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5}
𝐸 = {(𝑣1, 𝑣1), (𝑣1, 𝑣4),
(𝑣2, 𝑣1), (𝑣2, 𝑣3),
𝑣 3 , 𝑣2 , 𝑣3 , 𝑣5 ,
𝑣 4 , 𝑣1 , 𝑣4 , 𝑣4 ,
(𝑣5, 𝑣3)}
(a) 集合表現
1 0 0 1 0
1 0 1 0 0
0 1 0 0 1
1 0 0 1 0
0 0 1 0 0
1: 辺が有る
0: 辺が無い
(b) 隣接行列
隣接行列のブール積
グラフ 𝐺 = (𝑉, 𝐸)の隣接行列 𝐺のブール積𝐺2
ブール積 ブール和
(𝑖, 𝑗)成分 𝑔2 𝑖𝑗 = 𝑔𝑖1 𝑔1𝑗 + 𝑔𝑖2 𝑔2𝑗 + ⋯ … + 𝑔𝑖|𝑉| 𝑔|𝑉|𝑗
𝐺に辺(𝑖, 1)と辺(1, 𝑗)があるか?
径路「𝑖 → 1 → 𝑗」の有無
𝐺に辺(𝑖, 2)と辺(2, 𝑗)があるか?
径路「𝑖 → 2 → 𝑗」の有無
𝐺に辺(𝑖, 𝑉 )と辺( 𝑉 , 𝑗)があるか?
径路「𝑖 → |𝑉| → 𝑗」の有無
それらの論理和： 𝑖 から 𝑗への長さ２の径路の有無
多重グラフの隣接行列の積
グラフ 𝐺 = (𝑉, 𝐸)の隣接行列 𝐺の算術積𝐺2
算術積
算術和
(𝑖, 𝑗)成分 𝑔2 𝑖𝑗 = 𝑔𝑖1 𝑔1𝑗 + 𝑔𝑖2 𝑔2𝑗 + ⋯ … + 𝑔𝑖|𝑉| 𝑔|𝑉|𝑗
𝐺で 𝑖 から1への辺の数と
1から 𝑗 への辺の数の積
𝐺で 𝑖 から|𝑉|への辺の数と
|𝑉|から 𝑗 への辺の数の積
径路「𝑖 → 1 → 𝑗」の数
径路「𝑖 → |𝑉| → 𝑗)」の数
算術和： 𝑖 から 𝑗への長さ２の径路の数
ケーニヒスベルクの橋
ケーニヒスベルクを流れるプレーゲル川には、市の中心地で大
聖堂の建っている中州クナイプホーフ島ともう一つの大きな中洲が
あり、それらを中心に両岸へ以下のように7つの橋が架かっている。
この7つの橋を各1度ずつ通って、元の場所に戻ってくることができ
るかどうか? ただし、同じ橋を2度以上通ってはならない。
Wikipediaより
オイラーの定理の必要条件の証明
必要性： オイラーグラフ ⇒ 連結かつすべてが偶節点
𝐺 をオイラーグラフとし，そのオイラー閉路を 𝐿 とする
「𝐺が連結グラフであること」の証明
𝐺 に孤立点はないので，𝐺中の各節点はいずれかの辺に接続し
ており、その辺はオイラー閉路𝐿に含まれる。
すなわち、𝐺中の任意の2節点間に𝐿に沿った径路（小道）がある。
「𝐺の節点はすべて偶節点であること」の証明
任意の節点 𝑣 を考える。
𝐿は𝐺中の辺をそれぞれ1回ずつ含んでいるので、 𝑣に接続された
辺もそれぞれ𝐿に1回ずつ含まれる。
𝐿は閉路なので、𝐿 中で𝑣 に入る辺の数と、𝑣 から出る辺の数は等
しいので、それらの和は偶数となり 𝑣 は偶節点となる。
オイラーの定理の十分条件の証明
以下によりオイラー閉路を（再帰的に）構成できる
(1) 任意の節点を通る小道の閉路 𝐿 を構成
「すべて偶節点」なので、適当な節点から出発しても必ず閉路
は見つかる
(2) 𝐿 がすべての辺を通るならば終了
(3) そうでなければ 𝐺 から 𝐿 を除いたグラフ 𝐺1 もすべてが偶節
点であり、かつ𝐺1 と 𝐿 は少なくとも一つの節点𝐴を共有
(4) 𝐺1中の𝐴を含む閉路 𝐿’ をみつけ、𝐿 とつなげたものを新た
な 𝐿 として(2)へ
𝐺1 𝐿’
𝐴
𝐿
オイラー閉路の再帰的構成
オイラー閉路の再帰的構成
オイラー閉路の再帰的構成
無向木
端点
A
D
E
分岐節点
C
H
B
G
F
無向木の定義4種
𝑇 = (𝑉, 𝐸)が木であるとは
(A) 𝑉中の任意の2節点間に順路（径路）がただ一つ存在する
(B) 𝑇は連結かつ無閉路
(C) 𝑇は連結かつ 𝐸 = 𝑉 − 1
(D) 𝑇は無閉路かつ 𝐸 = 𝑉 − 1
無向木の定義4種の同値性
𝐴 ⇒ 𝐵 : 任意の2節点間に順路がただ一つ存在⇒連結∧無閉路
対偶「~(𝐵) ⇒ ~(𝐴)」を示す
~𝐵 = ~(連結∧無閉路)= ~連結 ∨ ~無閉路
𝑇が連結でない ⇒ 順路の存在しない節点対が存在
𝑇が閉路を持つ ⇒ 2つ以上の順路をもつ節点対が存在
Q.E.D.
無向木の定義4種の同値性（続き）
(B)⇒(C): 𝑇 = (𝑉, 𝐸)が連結、無閉路 ⇒
𝐸 = 𝑉 −1
数（自然数）の話になるので数学的帰納法を使うことを考える
|𝑉| = 1のとき 𝐸 = ∅なので成立
|𝑉| = 𝑘なる任意の連結無閉路なグラフ𝑇 = (𝑉, 𝐸)について、
𝐸 = 𝑘 − 1が成り立つとする
𝑉 = 𝑘 + 1なる連結無閉路なグラフ 𝑇 = (𝑉, 𝐸) を考える
𝑇は閉路を持たないので最長の順路𝑃を考えると、その始点は 次
数１である
𝑇から順路𝑃の始点とそれに接続する辺一つを除いた𝑇’ = (𝑉 ′ , 𝐸 ′ )
を考えると、𝑇′は連結かつ無閉路で、 𝑉 ′ = 𝑘となり、帰納法仮定よ
り 𝐸 ′ = 𝑘 − 1なので、 𝐸 = 𝐸 ′ + 1 = 𝑘 = 𝑉 − 1となる。
以上より任意の節点数 𝑛 について題意が成立する。
Q.E.D.
無向木の定義4種の同値性（続き）
(C)⇒(D): 𝐸 = 𝑉 − 1かつ連結⇒無閉路
背理法による証明
𝑇 = 𝑉, 𝐸 が 𝐸 = 𝑉 − 1かつ連結で閉路をもつと仮定する。
このとき、𝑇中の閉路上の辺を一つ除去した𝑇 −1 = 𝑉, 𝐸 −1 は連結
であり、 𝐸 −1 = 𝑉 − 2である。
同様の操作を𝑇 −𝑚 = (𝑉, 𝐸 −𝑚 )が無閉路になるまで続けると𝑇 −𝑚
（𝑚 ≥ 1）は連結かつ無閉路で 𝐸 −𝑚 = 𝑉 − (𝑚 + 1)となる。
直前に示した「(B)⇒(C)」に反する。
すなわち当初の仮定が誤っており、 𝑇 = 𝑉, 𝐸 が 𝐸 = 𝑉 − 1
かつ連結であれば、𝑇は閉路を持たない。
Q.E.D.
無向木の定義4種の同値性（続き）
(D)⇒(A): 𝑇 = (𝑉, 𝐸)が無閉路かつ 𝐸 = 𝑉 − 1なら、
任意の節点間に順路がちょうど一つ
(remark)
𝑇は閉路を持たないので、
任意の節点間の順路は高々一つ(0か1)
（背理法） ある2つの節点間に順路がない、すなわち𝑇が非連結と
する。
このとき𝑇は𝑘（≥ 2）個の連結成分 𝑇1, … , 𝑇𝑘 (𝑇𝑖 = 𝑉𝑖 , 𝐸𝑖 )に分割
することができ、 𝑉, 𝐸 はそれぞれ 𝑉𝑖 , 𝐸𝑖 (1 ≤ 𝑖 ≤ 𝑘)の直和になる。
既に示した「(B)⇒(C)」より 𝐸𝑖 = 𝑉𝑖 − 1であることと𝑉, 𝐸がそれ
ぞれ 𝑉𝑖 , 𝐸𝑖 の直和であることより、 𝐸 = 𝑉 − 𝑘 (𝑘 ≥ 2)ということに
なり、 𝐸 = 𝑉 − 1という前提に矛盾する。
すなわち、ある2つの節点間に順路がないとの仮定が誤りであり、
𝑇のすべての節点間にちょうど一つ順路が存在することになる。
Q.E.D.
有向木
根
分岐
節点
葉
辺が上から下に向くよう節点を配置し辺の向きを省略する
© Copyright 2024 ExpyDoc
