[b]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/b][br]いままではのつながりは、となりあう点と点、辺と辺、点と辺についてだった。[br]それが、[color=#0000ff]隣接[/color]や[color=#0000ff]接続[/color]という言葉を使って表されてきた。[br][br]これからは隣接していない点と点をつなぐ道を散歩することで、連結しているかどうかを調べてみよう。[br]グラフGの頂点をｎ個取り出したとき、そこが辺でつながっていることがある。[br][br]始点uから終点vまでのn+1個の点を順にｎ本の辺でつなぐ１本道を[color=#0000ff][b][size=150]長さｎの道uv[/size][/b][/color]といいます。[br]

グラフGの２頂点uvに道uvがあるときuvは連結しているといい、これがGのどの２頂点でも言えるときに[br]Gは連結グラフだという。[br]２点の連結成分は、辺と両端の２点というのは簡単にわかる。[br]３点の連結成分は、もとのグラフの部分グラフなので、L字型か三角形かはもとのグラフによる。[br]４点の連結成分も、もとのグラフの[color=#0000ff]点が誘導する部分グラフ[/color]にする。[br]紛らわしいが、[color=#0000ff][b]孤立点があるときは、１点だけで連結成分[/b][/color]という。[br][br]ということは、連結成分がいくつもあるということはグラフがバラバラになっていることになる。[br]連結成分数が１というのはグラフ全体が連結グラフだということだね。[br][br][b][size=150][color=#9900ff][u]質問：連結グラフかどうかを見た目ではなくデータで判断するにはどうしますか？[br][/u][/color][/size][/b][br][br]頂点数ｖ, 辺数eから適当にグラフを作る関数[b][color=#0000ff]gene_G[/color][/b](v,e)を作ります。[br]隣接行列の０乗からｎー１乗までの和を求める関数[color=#0000ff][b]walkSum[/b][/color](隣接行列)を作ります。[br]これから各頂点数から散歩する道順数の合計がわかるので、０でないなら１に直して連結行列でできる。[br]その行列を１次元にフラット化して、０が１つもないなら連結グラフだと判定しましょう。[br][color=#0000ff][br]#[IN]Python[br]#========================================[br]import networkx as nx[br]import random[br]import numpy as np[br]def walkSum(A):[br] n = len(A)[br] res = np.identity(n) # 道順数行列 (初期化 by 単位行列 ）[br] M = np.identity(n) # 散歩行列[br] for i in range(1,n): # 各点からn-1回散歩する。[br] # 散歩の長さを増やすたびに、散歩行列を更新し、道順数行列に足し込む[br] M= M @ A[br] res = res + M[br] return res [br] [br]def gene_G(v,e):[br] # 頂点数v,辺数eのグラフをデタラメに作り、隣接行列Aと、グラフGを返す[br] A=[[0]*v for i in range(v)] #　v*vの隣接行列 (初期化 by 0 )[br] nodes = [x for x in range(v)] #　0〜v-1のv個の点[br] edges = [] # ランダムにできる辺[br] G = nx.Graph()[br] while len(edges) < e:[br] i,j = random.sample(range(v),2)[br] if i > j: i,j = j,i[br] edges.append((i,j)) #辺の格納[br] A[i][j] = A[j][i]= 1 #隣接行列の更新(by 1)[br] #グラフオブジェクトに辺と点を一括で登録する[br] G.add_edges_from(edges)[br] G.add_nodes_from(nodes)[br] return A,G[br][br]#==========上が関数、下がやりたいこと=======[br]Vs=10[br]Es=15[br]A,G = gene_G(Vs,Es)[br]nx.draw_networkx(G)[br]B = np.where(walkSum(A)>=1,1,0) #道順数が０でないなら1にして連結行列とする。[br]all(B.flatten()) #連結グラフならTrue[br]#=========================================[br][OUT][/color]

連結グラフは、一筆書きができるかもしれない。[br]頂点の次数が[b]どれも偶数（偶点）[/b]ならば、重複なく全辺を通る回路、[color=#0000ff][b]オイラー回路[/b][/color]がある。[br]そのグラフは[b][color=#0000ff]オイラーグラフ[/color][/b]といい、一筆書きができるね。[br][br]また、次数が[b]奇数の点（奇点）がちょうど２個[/b]あるときに[b][color=#0000ff]オイラー小道[/color][/b]（始点と終点が一致するとは限らないが、すべての辺を重複なく通る小道）があるときも、一筆書きができるというよね。[br][br][color=#9900ff][b][u][size=150]質問：データから一筆書きができるかどうかと描き方を答えるコードはどうかきますか。[br][/size][/u][/b][/color][br]たとえば、隣接リストから奇点のリストを出す関数evenPoints（）を作りましょう。[br]連結かどうかを上記と同様に調べ、奇点数に従って、コメントを用意しておきます。[br][br]ちなみに、握手定理[u][size=150]Gの辺の総数２|E(G)|=Σdeg(v)[br][/size][/u]から、グラフの次数の総和は偶数になるので、奇点になる頂点はかならず偶数個とわかるね。[br][br]#[IN]Python[br]#=====================================================================[br]#一筆書き[br]import networkx as nx[br]import random[br]import numpy as np[br]def walkSum(A):[br] n = len(A)[br] res = np.identity(n) # 道順数行列 (初期化 by 単位行列 ）[br] M = np.identity(n) # 散歩行列[br] for i in range(1,n): # 各点からn-1回散歩する。[br] # 散歩の長さを増やすたびに、散歩行列を更新し、道順数行列に足し込む[br] M= M @ A[br] res = res + M[br] return res [br][color=#0000ff]def evenPoints(A):[br] n = len(A)[br] nodes = [x for x in range(n)] #　0〜n-1のn個の点[br] rsum = np.sum(A, axis=1) # 行ごとの合計リストを作る。[br] even_map = list(map(lambda x: x % 2 ==0 , rsum)) #ノードが偶点ならTrue、奇点ならFalse[br] odd_points =[x[0] for x in zip(nodes,even_map) if x[1]==False] #奇点のノードだけ取りしたリスト[br] return odd_points[br][/color] [br]def gene_G(v,e):[br] # 頂点数v,辺数eのグラフをデタラメに作り、隣接行列Aと、グラフGを返す[br] A=[[0]*v for i in range(v)] #　v*vの隣接行列 (初期化 by 0 )[br] nodes = [x for x in range(v)] #　0〜v-1のv個の点[br] edges = [] # ランダムにできる辺[br] G = nx.Graph()[br] while len(edges) < e:[br] i,j = random.sample(range(v),2)[br] if i > j: i,j = j,i[br] edges.append((i,j)) #辺の格納[br] A[i][j] = A[j][i]= 1 #隣接行列の更新(by 1)[br] #グラフオブジェクトに辺と点を一括で登録する[br] G.add_edges_from(edges)[br] G.add_nodes_from(nodes)[br] return A,G[br][br]#==========上が関数、下がやりたいこと=======[br]Vs=6[br]Es=10[br]A,G = gene_G(Vs,Es)[br]Euler = evenPoints(A) #奇点のリスト[br]Connect = all(np.where(walkSum(A)>=1,1,0).flatten()) #連結グラフならTrue[br]nx.draw_networkx(G)[br][color=#0000ff]if Connect == True:[br] if len(Euler)==0:#奇点が0個[br] msg='どこからでも一筆書きできます。'[br] elif len(Euler)==2:#奇点が2個[br] msg=str(Euler)+ 'が始点・終点の一筆書きができます。'[br] else:[br] msg='奇点が' + str(Euler) + 'の' + str(len(Euler))+'個あるため、'[br] msg +='連結グラフですが一筆書きできません'[br]else:[br] msg='グラフが連結ではありません。'[br]print(msg)[/color]

適当なグラフをかくと、オイラーグラフになることは少ないけれど、奇点が２個ある連結グラフができて、一筆書きができることは多い。[br][br][color=#9900ff][u][b][size=150]質問：そこで、その感覚が正しいのか、どのくらいの比率なのか、頂点と辺の数の変化がその比率に影響する傾向があるか。[br][/size][/b][/u][/color][br]連結グラフで奇点が0個、連結グラフで奇数が２個、連結グラフで奇数点が２個より多い、非連結グラフ[br]この４タイプの比率を調べてみよう。[br][br]グラフ作成関数が隣接グラフだけを返すように変更した上で、[br]調査のための関数を作ろう。[br]頂点の数をｖ＝６から１０まで変えてみる。[br]辺の数eは連結可能な最小数v-1から完全グラフになれるv(v-1)/2まで変えてみよう。[br]def gene_G(v,e):[br] # 頂点数v,辺数eのグラフをデタラメに作り、隣接行列Aと、グラフGを返す[br] A=[[0]*v for i in range(v)] #　v*vの隣接行列 (初期化 by 0 )[br] nodes = [x for x in range(v)] #　0〜v-1のv個の点[br] edges = [] # ランダムにできる辺[br] G = nx.Graph()[br] while len(edges) < e:[br] i,j = random.sample(range(v),2)[br] if i > j: i,j = j,i[br] edges.append((i,j)) #辺の格納[br] A[i][j] = A[j][i]= 1 #隣接行列の更新(by 1)[br] #グラフオブジェクトに辺と点を一括で登録する[br] return A[br][br][color=#0000ff]#==========次は調査のための関数=======[br]def statEuler(v,e,trials):[br] res=[0,0,0,0][br] for i in range(trials):[br] A = gene_G([/color][color=#ff0000]v, e[/color][color=#0000ff]) #隣接グラフのみ[br] Euler = evenPoints(A) #奇点のリスト[br] Connect = all(np.where(walkSum(A)>=1,1,0).flatten()) #連結グラフならTrue[br] if Connect == True:[br] if len(Euler)==0:[br] res[0] +=1 [br] elif len(Euler)==2:[br] res[1] +=1 [br] else:[br] res[2] +=1[br] else:[br] res[3] +=1[br] return [ res[0]/trials, res[1]/trials, res[2]/trials, res[3]/trials][br][br]def test1(minV, maxV):[br] trialCount = 100[br] result =[][br] for V in range(minV,maxV):[br] F = int(V*(V-1)/2)[br] for E in range(V-1,F+1):[br] result.append([V, statEuler(V, E, trialCount)])[br] return result[br][br][/color]print("test1の結果==================")[br]test1(6,10)[br]#======================================================[br][OUT][br]test1の結果==================[br][[(6, 5), [0.02, 0.47, 0.37, 0.14]],[br] [(6, 6), [0.03, 0.4, 0.5, 0.07]],[br] [(6, 7), [0.02, 0.39, 0.48, 0.11]],[br] [(6, 8), [0.01, 0.41, 0.51, 0.07]],[br] [(6, 9), [0.03, 0.48, 0.37, 0.12]],[br] [(6, 10), [0.02, 0.43, 0.49, 0.06]],[br] [(6, 11), [0.02, 0.38, 0.5, 0.1]],[br] [(6, 12), [0.03, 0.42, 0.45, 0.1]],[br] [(6, 13), [0.02, 0.49, 0.44, 0.05]],[br] [(6, 14), [0.01, 0.41, 0.42, 0.16]],[br] [(6, 15), [0.05, 0.42, 0.43, 0.1]],[br] [(7, 6), [0.04, 0.41, 0.43, 0.12]],[br] [(7, 7), [0.04, 0.4, 0.45, 0.11]],[br] [(7, 8), [0.01, 0.49, 0.43, 0.07]],[br] [(7, 9), [0.04, 0.42, 0.45, 0.09]],[br] [(7, 10), [0.03, 0.5, 0.34, 0.13]],[br] [(7, 11), [0.03, 0.43, 0.45, 0.09]],[br] [(7, 12), [0.06, 0.38, 0.46, 0.1]],[br] [(7, 13), [0.02, 0.46, 0.43, 0.09]],[br] [(7, 14), [0.0, 0.44, 0.44, 0.12]],[br] [(7, 15), [0.03, 0.38, 0.48, 0.11]],[br] [(7, 16), [0.02, 0.38, 0.43, 0.17]],[br] [(7, 17), [0.02, 0.45, 0.4, 0.13]],[br] [(7, 18), [0.02, 0.44, 0.41, 0.13]],[br] [(7, 19), [0.03, 0.44, 0.44, 0.09]],[br] [(7, 20), [0.02, 0.39, 0.47, 0.12]],[br] [(7, 21), [0.04, 0.34, 0.53, 0.09]],[br] [(8, 7), [0.02, 0.36, 0.52, 0.1]],[br] [(8, 8), [0.02, 0.34, 0.52, 0.12]],[br] [(8, 9), [0.01, 0.47, 0.43, 0.09]],[br] [(8, 10), [0.0, 0.43, 0.41, 0.16]],[br] [(8, 11), [0.03, 0.47, 0.45, 0.05]],[br] [(8, 12), [0.04, 0.4, 0.46, 0.1]],[br] [(8, 13), [0.04, 0.42, 0.4, 0.14]],[br] [(8, 14), [0.03, 0.41, 0.49, 0.07]],[br] [(8, 15), [0.02, 0.45, 0.34, 0.19]],[br] [(8, 16), [0.0, 0.32, 0.55, 0.13]],[br] [(8, 17), [0.01, 0.42, 0.47, 0.1]],[br] [(8, 18), [0.02, 0.48, 0.39, 0.11]],[br] [(8, 19), [0.04, 0.39, 0.5, 0.07]],[br] [(8, 20), [0.02, 0.41, 0.41, 0.16]],[br] [(8, 21), [0.02, 0.35, 0.55, 0.08]],[br] [(8, 22), [0.01, 0.38, 0.53, 0.08]],[br] [(8, 23), [0.02, 0.4, 0.47, 0.11]],[br] [(8, 24), [0.03, 0.41, 0.46, 0.1]],[br] [(8, 25), [0.02, 0.44, 0.49, 0.05]],[br] [(8, 26), [0.03, 0.37, 0.49, 0.11]],[br] [(8, 27), [0.03, 0.41, 0.43, 0.13]],[br] [(8, 28), [0.04, 0.34, 0.51, 0.11]],[br] [(9, 8), [0.01, 0.39, 0.52, 0.08]],[br] [(9, 9), [0.03, 0.38, 0.46, 0.13]],[br] [(9, 10), [0.02, 0.38, 0.52, 0.08]],[br] [(9, 11), [0.01, 0.44, 0.41, 0.14]],[br] [(9, 12), [0.02, 0.49, 0.4, 0.09]],[br] [(9, 13), [0.01, 0.37, 0.51, 0.11]],[br] [(9, 14), [0.02, 0.41, 0.47, 0.1]],[br] [(9, 15), [0.02, 0.31, 0.57, 0.1]],[br] [(9, 16), [0.04, 0.47, 0.39, 0.1]],[br] [(9, 17), [0.01, 0.43, 0.48, 0.08]],[br] [(9, 18), [0.01, 0.51, 0.4, 0.08]],[br] [(9, 19), [0.03, 0.33, 0.56, 0.08]],[br] [(9, 20), [0.0, 0.39, 0.47, 0.14]],[br] [(9, 21), [0.01, 0.38, 0.47, 0.14]],[br] [(9, 22), [0.01, 0.46, 0.46, 0.07]],[br] [(9, 23), [0.04, 0.36, 0.53, 0.07]],[br] [(9, 24), [0.03, 0.42, 0.42, 0.13]],[br] [(9, 25), [0.02, 0.4, 0.51, 0.07]],[br] [(9, 26), [0.01, 0.4, 0.47, 0.12]],[br] [(9, 27), [0.01, 0.28, 0.55, 0.16]],[br] [(9, 28), [0.01, 0.48, 0.38, 0.13]],[br] [(9, 29), [0.03, 0.38, 0.46, 0.13]],[br] [(9, 30), [0.04, 0.44, 0.44, 0.08]],[br] [(9, 31), [0.03, 0.39, 0.45, 0.13]],[br] [(9, 32), [0.05, 0.32, 0.52, 0.11]],[br] [(9, 33), [0.03, 0.41, 0.42, 0.14]],[br] [(9, 34), [0.04, 0.44, 0.39, 0.13]],[br] [(9, 35), [0.01, 0.41, 0.5, 0.08]],[br] [(9, 36), [0.03, 0.3, 0.55, 0.12]]][br]

あまり、V,Eの変動にようる比率の変化は見られない。[br][br]そこで、比率を平均値を求めてみよう。[br]def test2(minV, maxV):[br] trialCount = 100[br] result =[][br] for V in range(minV,maxV):[br] F = int(V*(V-1)/2)[br] for E in range(V-1,F+1):[br] result.append(statEuler(V, E, trialCount))[br] a=sum(list(map(lambda x:x[0], result)))/len(result)[br] b=sum(list(map(lambda x:x[1], result)))/len(result)[br] c=sum(list(map(lambda x:x[2], result)))/len(result)[br] d=sum(list(map(lambda x:x[3], result)))/len(result)[br] return a,b,c,d[br] print("test2の結果==================")[br]test2(6,10)[br][br][b][color=#0000ff]test2の結果==================[br][br][258]:[br](0.02564102564102564,[br] 0.4030769230769231,[br] 0.47038461538461535,[br] 0.1008974358974359)[br][/color][/b][br]一筆書きできるのが約43％、できないのが約57％という比率はおもしろ比率だね。[br]どこからでも一筆書きできるオイラーグラフは2.5％とわりとレアな感じが比率に表れている。