Kuratowskiで平面にかこう
このワークシートはMath by Codeの一部です。
平面グラフは辺と辺が交差せずかいた平面にかいたグラフです。
平面グラフにかけるグラフを平面的グラフといいます。
完全グラフをおぼえてますか？頂点の数|V|=ｎで、辺はすべての頂点をつないでいるので、
|E|=nC2=n(n-1)/2でしたね。
＜完全グラフは平面的か＞
たとえば、完全グラフK1は１点,K2は線分,K3は三角形,K4は四角形と２本の対角線です。
K4はふつうにかくと辺と辺が交差してしまいますね。
しかし、グラフの線は直線でなくてもいいので１本だけ曲線にすれば、K４は平面的グラフです。
完全グラフK1,K2,K3,K4は平面的です。
質問：K4をどうしても直線で平面グラフにしたかったらどうかいたらよいでしょうか。
K3の三角形の内部に１点をとり他の３点と結ぶとK4は平面グラフになりますね。
ファーリという人は、「平面的グラフは辺をまっすぐな線分の平面グラフにかける」という定理を見つけたそうです。
立体図形で面の数が大切だったように平面グラフでも面が大事です。
平面では、「領域」という言葉を使います。
K3は頂点数も辺数も３ですから、|V|=|E|=3です。
領域数をrとします。領域は辺にかこまれた平面の部分ですが、内部の１つ以外に、外の無限の領域も１つと数えます。だから、r=2になりますね。|V|-|E|+r=2になってます。
K4は三角形の内部を３つに分けますから、領域数は3-1＝2増えてr=2+2=4になります。
|V|は1増えて3+1=4、|E|=3+3=6です。|V|-|E|+r=4-6+4=2になりました。
平面グラフでは|V|-|E|+r=2になります。これは有名なオイラーの定理というものだね。
K5は平面的ではありません。
五角形の中に星型五角形があるグラフですね。
K5はどうがんばっても平面的ではないでしょう。ではなぜダメなのでしょうか。
オイラーの定理「連結平面グラフG（V,E)では|V| - |E| + r = 2」が成り立ちますね。
４点がかこむと凸４角形だけでなく、辺が交差する蝶ネクタイになる領域になりますので要注意、平面化すると、領域に変えられるからです。
・|V|≧３で、閉路のある平面グラフGでは、|E| ≦ 3|V| - 6
（理由）
どの領域も３本以上の辺でかこまれて、どの辺も最高で２つの領域の境にある。
ということは領域数を３倍しても辺数の２倍を超えることはないね。
3r ≦ 2|E|
オイラーの定理から3r=6-3|V|+3|E|だから、
6 - 3|V| +3|E| ≦ 2|E|
|E| ≦ 3|V| - 6
この不等式で不等号が＝になるとき極大平面的グラフという。
どの領域も三角形になっていて、これ以上、辺数が最大になっている状態のグラフだ。
たとえば、K4がそうだね。だからこそ、K5は平面的ではないともいえる。
もちろん、K5では|E|=10,|V|=5だから、不等式10≦15-6が成り立たないから平面的ではないとも言える。
＜完全２部グラフは平面的か＞
完全２部グラフK2,1, K2,2, K2,3を考えて見ましょう。
K2,1はVの字ですから平面的です。
K2,2は蝶ネクタイがたの四角形ですが、辺が交差しないように開くとひし形のようにかけて平面的です。
K2,3はWの字のはしの４点をX字で結んだ形です。２点の部に対してVの字を３つ重ならずにかけるので
平面的です。
K2,nは２点の部に対してVの字をｎ個重ならずにかけるので平面的です。
完全２部グラフK2,nは平面的です。
しかし、K3,3は３点の部に対して重ならないようにのこりの点への３本線をずらしてかいても
どうしても辺が交差してしまいます。
完全２部グラフK3,3は非平面的です。
・|V|≧３で、単純な2部の平面グラフGでは、|E| ≦ 2|V| - 4
（理由）
ケーニヒの定理「Gに連結成分のある2部グラフであることと、長さ奇数のサイクルを含まないことは
同値」。（Gにサイクル、つまり多辺形があるとすると、2部を交互につなぐ点になる。同じ部に属する点が隣接すると2部ではなくなるから、サイクルの長さは偶数に限らられるね。）から、
どの領域は４本以上の偶数辺でかこまれている。もちろん、どの辺も最大で２つの領域の境目だ。
ということは領域数を４倍しても辺数の２倍を超えることはないね。
4r ≦ 2|E|
オイラーの定理から4r=8-4|V|+4|E|だから、
8 - 4|V| +4|E| ≦ 2|E|
2|E| ≦ 4|V| - 8
|E| ≦ 2|V| - 4
質問：平面的かどうかを完全グラフをいくつかかいてたしかめてみましょう。
#Python
#===================================================
# 完全グラフをかく関数Kn
import networkx as nx
import itertools
import matplotlib.pyplot as plt
n=6
G = nx.Graph()
G.add_node(1)
plt.subplot(2,3,1)
nx.draw_networkx(G)
def K(n):
V = list(range(1,n+1))
E = list(itertools.combinations(V,2))
G = nx.Graph()
G.add_edges_from(E)
return G
for i in range(2,n+1):
G=K(i)
plt.subplot(2,3,i)
nx.draw_networkx(G)
#===================================================
#2部グラフKp,qを色分けして、平面的かどうかを確認しよう。
import networkx as nx
import itertools
import matplotlib.pyplot as plt
def K(p,q,pos_num):
Vp = list(range(1,1+p)) #第１部の頂点は１からpまでのｐ個
Vq = list(range(p+1,p+1+q)) #第２部の頂点はp+1からp+qまでのｑ個
E = list(itertools.product(Vp,Vq)) #VpとVqの直積のリスト
G = nx.Graph()
V=Vp+Vq
colorList = ['Red']*p + ['Green']*q #色名は頭文字を大文字にする
G.add_nodes_from(V)
G.add_edges_from(E)
plt.subplot(2,2,pos_num)
nx.draw_networkx(G,node_color=colorList)
K(2,1,1)
K(2,2,2)
K(2,3,3)
K(3,3,4)
完全グラフK1からK6は平面的？
完全2部グラフK2,nとK3,3は平面的？
２．クラトウスキーの定理
クラトウスキーは、「グラフGが平面的であることは、K5とK3,3と位相同相な部分を含まないということと同値だ。」を見つけた。
位相同型というのは、次数が２の点と辺が交互に連続している部分があれば、1本の辺になおす単純化をしても位相の上では同型とするということだ。辺上に点を打って辺を細切れにするので、細分と言ったりすることもあるね。
質問：適当なグラフをかいてそれが平面的かどうかを判断するにはどうしたらよいでしょうか。
networkxの中に2部グラフかどうかを判定する関数is_bipartiteがある。
また、平面的かどうかを判定する関数is_planarがあるからそれが使えるね。
頂点の数だけ与えてグラフを作る関数を使っていろいろ確認してみよう。
これらをぜんぶまとめてkuratowski関数を作り、
連続的にグラフをかいて観察してみよう。
#[IN]Python
#===================================================================================
from matplotlib import pyplot as plt
import networkx as nx
import numpy as np
from networkx.algorithms import bipartite
def kuratowski(pos_num):
while True:
G = nx.fast_gnp_random_graph(6, 0.7)
if nx.is_connected(G):
break
#グラフの属性を得て表示する。
V=len(G.nodes())
E=len(G.edges())
isPlanar = nx.is_planar(G)
isBipartite = bipartite.is_bipartite(G)
resB =True if E <= 2 *V -4 else False
resP =True if E <= 3 *V -6 else False
print('|V|=',V,',|E|=',E,',E≦2V-4 ?',resB,',E≦3V-6 ?',resP,',2部グラフか?',isBipartite,',平面的か?',isPlanar)
#Gが平面的グラフなら平面グラフをかき、そうでないなら普通にグラフをかく。
plt.subplot(2,3,pos_num)
if isPlanar:
nx.draw(G, pos=nx.planar_layout(G))
else:
nx.draw(G)
for item in range(1,7):
kuratowski(item)
#===================================================================================
[OUT]
