2部グラフのjudge関数
このワークシートはMath by Codeの一部です。
質問：Gの各頂点をvとするとGの辺の総数２|E(G)|=Σdeg(v)はどうして言えるでしょうか。
＜握手補題＞
上記の内容は握手補題と呼ばれたりしてるね。当たり前すぎて説明がしにくいかもしれません。
１辺{u,v}は、辺１つを２頂点u,vのどちらからでも重複して数えられる。
これがどの辺についても言える。
だから、辺数の合計の２倍は重複を込めた点の総数と等しい。
重複をこめた点の総数は頂点の次数の合計で求めることができる。
１．完全２部グラフ
グラフG=(V,E)の頂点Vをｎ個の集合に分割してみる。
たとえば、２つの集合、部VAと部VBに分けたとしよう。
部VAのどの２点ｘ，ｙを選んでも辺{x,y}はEにはなく、
部VBのどの２点ｘ，ｙを選んでも辺{x,y}はEにはない。
言い換えるとGのどの辺も２つの部にまたがっていて、１つの部に属するものがない。
このとき、2部グラフはG=(VA,VB,E)とかける。
一般に、Gがｎ部グラフだということは、隣接辺を持たない点集合Viのｎ個(V1,....,Vn)に頂点分割ができるということだから、Gのつながり具合を特徴づけていると言えるね。G=（V1,....,Vn,E)とかける。
とくに、ｎ個の点集合からどの２つの部X,Yを選んでも、部のどの２点ｘ∈X, y∈Yでも隣接しているなら、Gは完全ｎ部グラフと呼ばれる。|Vi|=piのとき、各部の頂点数を並べて、G=K(1,2,3)とか、K1,2,3などと表示することがあるね。
質問：要素数ｐ*ｑの完全２部グラフKp,qを作るにはどうしたらよいでしょうか。
頂点ｐ個の集合Aとｑ個の集合Bを用意し、Aの各点に対してBの全点を結ぶ辺を作ります。
頂点と辺をGに加えたものが完全２部グラフG(A,B,E）＝K(p,q)です。
つまり、AとBの集合の直積が辺集合になるね。
同じ部にある頂点は隣接してないので、部という言葉がピンとこないかもしれない。
補グラフを意識してみよう。
２部グラフの補グラフでは、同じ部にある頂点はどれもつながるので完全グラフになるね。
#[IN]Python
#========================================================
#完全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(3,1,1)
K(3,2,2)
K(3,3,3)
K(3,4,4)
#========================================================
[OUT]
完全２部グラフの色分け
＜不完全な２部グラフ＞
完全な２部グラフは直積の発想を使ってつくることができた。
完全でない場合は、２部に頂点をわけておき、
部間を結ぶ辺をあとで追加すればよいね。
2部用のパッケージを使ってみよう。やっていることは素朴だ。
色はグラフそのものの構造データではないからdrawするときに部ごとに指定しよう。
#[IN]Python
#============================================================
import networkx as nx
from matplotlib import pyplot as plt
from networkx.algorithms import bipartite
B = nx.Graph() #部のフラグbipartiteに０，１を立てておこう。
B.add_nodes_from([1, 2, 3, 4], bipartite=0)
B.add_nodes_from(["a", "b", "c"], bipartite=1)
B.add_edges_from([(1, "a"), (1, "b"), (2, "b"), (2, "c"), (3, "c"), (4, "a")]) #部間の連結辺
colorList = ['Red']*4 + ['Green']*3 #色名は頭文字を大文字にする #色分け
nx.draw_networkx(B,node_color=colorList)
#============================================================
[OUT]
２部グラフの１例
２．２部グラフの判定
完全２部グラフを作るのは、直積を使えば簡単でしたね。
質問：頂点が４か６のグラフが２部グラフか完全２部グラフかを判定するにはどうしたらよいでしょう。
完全２部グラフなら、頂点数は２つの部の頂点数の積になる。
＜頂点４の場合＞
完全２部グラフなら4=2+2 4=2*2から、辺が４本だとK2,2の可能性がある。
４つの頂点を２組にわけて、どちらも部の中に結ぶ辺がないと２部グラフと判断するのがjudge4(G)関数だ。
２部グラフの頂点の２集合VA,VB、辺集合Eから２部グラフを色分けする関数がmakebipatiteだ。
judge4の中に、この描画関数を使うと２部グラフの確認が目で見てわかる。
#[IN]Python
#====================================================================
import networkx as nx
from matplotlib import pyplot as plt
import itertools
from networkx.algorithms import bipartite
pos_num=1
def makebipatite(VA,VB,E):
B = nx.Graph()
B.add_nodes_from(VA, bipartite=0)
B.add_nodes_from(VB, bipartite=1)
B.add_edges_from(E)
colorList = ['Red']*len(VA) + ['Green']*len(VB) #色名は頭文字を大文字にする
nx.draw_networkx(B,node_color=colorList)
def judge4(G):
global pos_num
V=G.nodes()
E=G.edges()
V1=list(itertools.combinations(V,2))
for Pset in V1:
p,q = Pset[0],Pset[1]
R = list(set(V)-set([p,q]))
r,s= R[0],R[1]
# もし2️部グラフと判断されたら、makebipatite関数で描画する。
if not((p,q) in E or (q,p) in E or (r,s) in E or (s,r) in E):
VA= [p,q]
VB= R
E= E
plt.subplot(2,2,pos_num)
makebipatite(VA,VB,E)
pos_num +=1
return True
return False
V=[1,2,3,4]
E1=[(1,2),(2,3),(3,4),(4,1)] #四角形と4頂点
E2=[(1,2),(3,4)] #4頂点と２つの辺
G1=nx.Graph()
G1.add_nodes_from(V)
G1.add_edges_from(E1)
G2=nx.Graph()
G2.add_edges_from(E2)
G2.add_nodes_from(V)
judge4(G1)
judge4(G2)
#====================================================================
[OUT]
4点の２部グラフ
・頂点６の場合
辺数が７のグラフGがあるとする。
6=3+3, 3*3=9, 9-7=2から、２本の辺の追加で完全グラフK3,3に直せるかもしれない。
6=2+4, 2*4=8, 8-7=1から、１本の辺の追加で完全グラフK2,4に直せるかもしれない。
6=1+5, 1*5=5, 5-7<0から、完全グラフよりも辺が多いので２部グラフには直せない。
ということで、
２部グラフの頂点の２集合VA,VB、辺集合Eから２部グラフを色分けする関数がmakebipatiteは点数に
関係なく使える。judge6の中に、この描画関数を使うと２部グラフの確認が目で見てわかる。
judge6の作り方
６点から３点選び、３点が連結せず、残り３点も連結していないときか、
６点から２点選び、２点が連結せず、残り４点も連結しないとき。
このどちらかが言えれば２部グラフと判断するのがjudge6(G)関数だ。
#[IN]Python
#==================================================================
import networkx as nx
from matplotlib import pyplot as plt
import itertools
from networkx.algorithms import bipartite
pos_num=1
def makebipatite(VA,VB,E):
B = nx.Graph()
B.add_nodes_from(VA, bipartite=0)
B.add_nodes_from(VB, bipartite=1)
B.add_edges_from(E)
colorList = ['Red']*len(VA) + ['Green']*len(VB) #色名は頭文字を大文字にする
nx.draw_networkx(B,node_color=colorList)
def judge6(G):
global pos_num
V = G.nodes()
E = G.edges()
V1 = list(itertools.combinations(V,3))
for Pset in V1:
p,q,r = Pset[0],Pset[1],Pset[2]
R = list(set(V)-set([p,q,r]))
s,t,u = R[0],R[1],R[2]
# もし2️部グラフと判断されたら、makebipatite関数で描画する
siki1= (p,q) in E or (q,p) in E or (q,r) in E or (r,q) in E or (r,p) in E or (p,r) in E
siki2= (s,t) in E or (t,s) in E or (t,u) in E or (u,t) in E or (u,s) in E or (s,u) in E
if not(siki1 or siki2):
VA = [p,q,r]
VB = R
E = E
print(VA,VB,E)
plt.subplot(2,2,pos_num)
makebipatite(VA,VB,E)
pos_num +=1
V1 = list(itertools.combinations(V,2))
for Pset in V1:
p,q= Pset[0],Pset[1]
R = list(set(V)-set([p,q]))
r,s,t,u = R[0],R[1],R[2],R[3]
# もし2️部グラフと判断されたら、makebipatite関数で描画する
siki1= (p,q) in E or (q,p) in E
siki2= (r,s) in E or (r,t) in E or (r,u) in E or (s,r) in E or (s,t) in E or (s,u) in E
siki3= (t,r) in E or (t,s) in E or (t,u) in E or (u,r) in E or (u,s) in E or (u,t) in E
if not(siki1 or siki2 or siki3):
VA = [p,q]
VB = R
E = E
print(VA,VB,E)
plt.subplot(2,2,pos_num)
makebipatite(VA,VB,E)
pos_num +=1
V=[1,2,3,4,5,6]
E1=[(1,2),(2,3),(3,4),(4,5),(5,6),(6,1),(2,5)] #日の字型の６点
E2=[(1,5),(2,5),(3,5),(4,5),(1,6),(2,6),(3,6)] #１,２,３,４につなぐ５，６。
G1=nx.Graph()
G1.add_nodes_from(V)
G1.add_edges_from(E1)
judge6(G1)
G2=nx.Graph()
G2.add_nodes_from(V)
G2.add_edges_from(E2)
judge6(G2)
#==================================================================
[OUT]
6点の2部グラフ
