[b]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/b][br][color=#9900ff][u][b][size=150]質問：Gの各頂点をvとするとGの辺の総数２|E(G)|=Σdeg(v)はどうして言えるでしょうか。[br][/size][/b][/u][/color][br]＜握手補題＞[br]上記の内容は握手補題と呼ばれたりしてるね。当たり前すぎて説明がしにくいかもしれません。[br][br]１辺{u,v}は、辺１つを２頂点u,vのどちらからでも重複して数えられる。[br]これがどの辺についても言える。[br]だから、辺数の合計の２倍は重複を込めた点の総数と等しい。[br]重複をこめた点の総数は頂点の次数の合計で求めることができる。

[br]グラフG=(V,E)の頂点Vをｎ個の集合に分割してみる。[br]たとえば、２つの集合、部VAと部VBに分けたとしよう。[br]部VAのどの２点ｘ，ｙを選んでも[b]辺{x,y}はEにはなく[/b]、[br]部VBのどの２点ｘ，ｙを選んでも[b]辺{x,y}はEにはない[/b]。[br]言い換えると[b][color=#0000ff]Gのどの辺も２つの部にまたがっていて、１つの部に属するものがない[/color][/b]。[br]このとき、2部グラフはG=(VA,VB,E)とかける。[br][br]一般に、[color=#0000ff][b]Gがｎ部グラフ[/b][/color]だということは、[b][color=#0000ff]隣接辺を持たない点集合Vi[/color][/b]のｎ個(V1,....,Vn)に頂点分割ができるということだから、Gのつながり具合を特徴づけていると言えるね。G=（V1,....,Vn,E)とかける。[br]とくに、ｎ個の点集合からどの２つの部X,Yを選んでも、部のどの２点ｘ∈X,　y∈Yでも隣接しているなら、Gは[b][color=#0000ff]完全ｎ部グラフ[/color][/b]と呼ばれる。|Vi|=piのとき、各部の頂点数を並べて、G=K(1,2,3)とか、K1,2,3などと表示することがあるね。[br][br][color=#9900ff][u][b][size=150]質問：要素数ｐ*ｑの完全２部グラフKp,qを作るにはどうしたらよいでしょうか。[br][/size][/b][/u][/color][br]頂点ｐ個の集合Aとｑ個の集合Bを用意し、Aの各点に対してBの全点を結ぶ辺を作ります。[br]頂点と辺をGに加えたものが完全２部グラフG(A,B,E）＝K(p,q)です。[br]つまり、AとBの集合の直積が辺集合になるね。[br]同じ部にある頂点は隣接してないので、部という言葉がピンとこないかもしれない。[br]補グラフを意識してみよう。[br][color=#0000ff][b][size=150]２部グラフの補グラフでは、同じ部にある頂点はどれもつながるので完全グラフになるね。[br][/size][/b][/color][br]#[IN]Python[br]#========================================================[br][color=#0000ff][b][size=150]#完全2部グラフKp,qを色分けして[br][/size][/b][/color]import networkx as nx[br]import itertools[br]import matplotlib.pyplot as plt[br][color=#0000ff]def K(p,q,pos_num):[br] Vp = list(range(1,1+p)) #第１部の頂点は１からpまでのｐ個[br] Vq = list(range(p+1,p+1+q)) #第２部の頂点はp+1からp+qまでのｑ個[br] E = list(itertools.product(Vp,Vq)) #VpとVqの直積のリスト[br] G = nx.Graph()[br] V=Vp+Vq[br] colorList = ['Red']*p + ['Green']*q #色名は頭文字を大文字にする[br] G.add_nodes_from(V)[br] G.add_edges_from(E)[br] plt.subplot(2,2,pos_num)[br] nx.draw_networkx(G,node_color=colorList)[br][/color][br]K(3,1,1)[br]K(3,2,2)[br]K(3,3,3)[br]K(3,4,4)[br]#========================================================[br][OUT][br]

＜不完全な２部グラフ＞[br][br]完全な２部グラフは直積の発想を使ってつくることができた。[br][br]完全でない場合は、２部に頂点をわけておき、[br]部間を結ぶ辺をあとで追加すればよいね。[br]2部用のパッケージを使ってみよう。やっていることは素朴だ。[br]色はグラフそのものの構造データではないからdrawするときに部ごとに指定しよう。[br][br]#[IN]Python[br]#============================================================[br]import networkx as nx[br]from matplotlib import pyplot as plt[br][color=#0000ff][b]from networkx.algorithms import bipartite[br][/b][/color]B = nx.Graph() #部のフラグbipartiteに０，１を立てておこう。[br]B.add_nodes_from([1, 2, 3, 4], bipartite=0)[br]B.add_nodes_from(["a", "b", "c"], bipartite=1)[br]B.add_edges_from([(1, "a"), (1, "b"), (2, "b"), (2, "c"), (3, "c"), (4, "a")]) #部間の連結辺[br]colorList = ['Red']*4 + ['Green']*3 #色名は頭文字を大文字にする　#色分け[br]nx.draw_networkx(B,node_color=colorList)[br]#============================================================[br][OUT]

完全２部グラフを作るのは、直積を使えば簡単でしたね。[br][br][color=#9900ff][b][u][size=150]質問：頂点が４か６のグラフが２部グラフか完全２部グラフかを判定するにはどうしたらよいでしょう。[br][/size][/u][/b][/color][br]完全２部グラフなら、頂点数は２つの部の頂点数の積になる。[br][br]＜頂点４の場合＞[br]完全２部グラフなら4=2+2 4=2*2から、辺が４本だとK2,2の可能性がある。[br]４つの頂点を２組にわけて、どちらも部の中に結ぶ辺がないと２部グラフと判断するのがjudge4(G)関数だ。[br]２部グラフの頂点の２集合VA,VB、辺集合Eから２部グラフを色分けする関数がmakebipatiteだ。[br]judge4の中に、この描画関数を使うと２部グラフの確認が目で見てわかる。[br]#[IN]Python[br]#====================================================================[br]import networkx as nx[br]from matplotlib import pyplot as plt[br]import itertools[br]from networkx.algorithms import bipartite[br][br]pos_num=1[br][color=#0000ff]def makebipatite(VA,VB,E):[br] B = nx.Graph()[br] B.add_nodes_from(VA, bipartite=0)[br] B.add_nodes_from(VB, bipartite=1)[br] B.add_edges_from(E)[br] colorList = ['Red']*len(VA) + ['Green']*len(VB) #色名は頭文字を大文字にする[br] nx.draw_networkx(B,node_color=colorList)[br]def judge4(G):[br] global pos_num[br] V=G.nodes()[br] E=G.edges()[br] V1=list(itertools.combinations(V,2))[br] for Pset in V1:[br] p,q = Pset[0],Pset[1][br] R = list(set(V)-set([p,q]))[br] r,s= R[0],R[1][br] # もし2️部グラフと判断されたら、makebipatite関数で描画する。[br] if not((p,q) in E or (q,p) in E or (r,s) in E or (s,r) in E):[br] VA= [p,q][br] VB= R[br] E= E[br] plt.subplot(2,2,pos_num)[br] makebipatite(VA,VB,E)[br] pos_num +=1[br] return True[br] return False[br][br][/color]V=[1,2,3,4][br][br]E1=[(1,2),(2,3),(3,4),(4,1)] #四角形と4頂点[br]E2=[(1,2),(3,4)] #4頂点と２つの辺[br]G1=nx.Graph()[br]G1.add_nodes_from(V)[br]G1.add_edges_from(E1)[br]G2=nx.Graph()[br]G2.add_edges_from(E2)[br]G2.add_nodes_from(V)[br][br]judge4(G1)[br]judge4(G2)[br]#====================================================================[br][OUT]

・頂点６の場合[br]辺数が７のグラフGがあるとする。[br]6=3+3, 3*3=9, 9-7=2から、２本の辺の追加で完全グラフK3,3に直せるかもしれない。[br]6=2+4, 2*4=8, 8-7=1から、１本の辺の追加で完全グラフK2,4に直せるかもしれない。[br]6=1+5, 1*5=5, 5-7<0から、完全グラフよりも辺が多いので２部グラフには直せない。[br]ということで、[br]２部グラフの頂点の２集合VA,VB、辺集合Eから２部グラフを色分けする関数がmakebipatiteは点数に[br]関係なく使える。judge6の中に、この描画関数を使うと２部グラフの確認が目で見てわかる。[br]judge6の作り方[br]６点から３点選び、３点が連結せず、残り３点も連結していないときか、[br]６点から２点選び、２点が連結せず、残り４点も連結しないとき。[br]このどちらかが言えれば２部グラフと判断するのがjudge6(G)関数だ。[br]#[IN]Python[br]#==================================================================[br]import networkx as nx[br]from matplotlib import pyplot as plt[br]import itertools[br]from networkx.algorithms import bipartite[br][br]pos_num=1[br]def makebipatite(VA,VB,E):[br] B = nx.Graph()[br] B.add_nodes_from(VA, bipartite=0)[br] B.add_nodes_from(VB, bipartite=1)[br] B.add_edges_from(E)[br] colorList = ['Red']*len(VA) + ['Green']*len(VB) #色名は頭文字を大文字にする[br] nx.draw_networkx(B,node_color=colorList)[br][b][color=#1e84cc][size=150]def judge6(G):[br] global pos_num[br] V = G.nodes()[br] E = G.edges()[br] V1 = list(itertools.combinations(V,3))[br] for Pset in V1:[br] p,q,r = Pset[0],Pset[1],Pset[2][br] R = list(set(V)-set([p,q,r]))[br] s,t,u = R[0],R[1],R[2][br] # もし2️部グラフと判断されたら、makebipatite関数で描画する[br] 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[br] 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[br] if not(siki1 or siki2):[br] VA = [p,q,r][br] VB = R[br] E = E [br] print(VA,VB,E)[br] plt.subplot(2,2,pos_num)[br] makebipatite(VA,VB,E)[br] pos_num +=1[br] V1 = list(itertools.combinations(V,2))[br] for Pset in V1:[br] p,q= Pset[0],Pset[1][br] R = list(set(V)-set([p,q]))[br] r,s,t,u = R[0],R[1],R[2],R[3][br] # もし2️部グラフと判断されたら、makebipatite関数で描画する[br] siki1= (p,q) in E or (q,p) in E[br] 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[br] 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[br] if not(siki1 or siki2 or siki3):[br] VA = [p,q][br] VB = R[br] E = E[br] print(VA,VB,E)[br] plt.subplot(2,2,pos_num)[br] makebipatite(VA,VB,E)[br] pos_num +=1[br][br]V=[1,2,3,4,5,6][br]E1=[(1,2),(2,3),(3,4),(4,5),(5,6),(6,1),(2,5)] #日の字型の６点[br]E2=[(1,5),(2,5),(3,5),(4,5),(1,6),(2,6),(3,6)] #１,２,３,４につなぐ５，６。[br][/size][/color][/b][br]G1=nx.Graph()[br]G1.add_nodes_from(V)[br]G1.add_edges_from(E1)[br]judge6(G1)[br][br]G2=nx.Graph()[br]G2.add_nodes_from(V)[br]G2.add_edges_from(E2)[br]judge6(G2)[br]#==================================================================[br][OUT]