[size=150][size=100][b]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/b][br][br]グラフは[b]頂点(ただの点ではないのでpoint、vertexではなくnodeと呼ぶことが多い)[/b]の集合V[br]と辺(edge)の集合Eからなる。[b]G=（V,E)[/b]とかくことがある。[br]逆に、[b]V（G）、E（G)[/b]のように、Gを主体にかくこともあるね。[br]形はどうであれ、VもEもGと一致しているグラフFをGと[color=#0000ff][b]同型(isomorphic)グラフ[/b][/color]というね。[br]VもEもGもGの部分集合になっているグラフFをGの[b][color=#0000ff]部分グラフ(subgraph)[/color][/b]というのはわかるだろう。[br]特に、Vだけはそのまま全部含む部分グラフを[color=#0000ff][b]全域部分グラフ[/b][/color]という。[br]Vはそのままで、Vの可能なすべての辺の集合をEPとすると、Eの補集合E＝EP-Eに切り替えた[br]グラフを[b][color=#0000ff]補グラフ[/color][/b]という。[br][br][/size][b]＜つながりを表す言葉＞[br][/b][/size]・２頂点ｐ，ｑをつなぐ辺eがあるとき、e={p,q}とかくことがある。[br]　点pに隣接する点をpの[color=#0000ff][b]近傍（neighbors)[/b][/color]ということもある。[br][b]頂点[/b]ｐとｑはeで[b][color=#0000ff]隣接(adjacent)[/color][/b]して、[u][color=#0000ff][b]辺[/b]eはｐとｑに[b]接続[/b][/color][/u]しているという。[br]・２つの辺e、ｆをつなぐ点ｒがあるとき、[br][b]辺[/b]eとｆはｒで[b]隣接[/b]してるという。[br]つまり、[color=#0000ff][b]隣接[/b][/color]は辺と辺または、頂点と頂点のように、同種のものが[br]となりあってつながっているときに使う。[br][color=#0000ff][b]接続[/b][/color]は、種類に関係なく、辺と辺、頂点と頂点、頂点と辺がとなりあってつながっているときに使う。[br]・頂点V(G)の部分集合Uと、それらの要素にGで接続していたE(G)の部分FからなるグラフをUが誘導するグラフという。辺についても、部分集合が[color=#0000ff][b]誘導するグラフ(induced subgraph)[/b][/color]を考えることができるね。[br]・１つの点eがｋ個の辺の端にならば、点eの次数(degree)はｋだという。deg(e)=kとかく。[br]次数０の点を[b]孤立点[/b]といい、次数１の点を[b]端点[/b]というが、これは常識的なことば遣いだ。[br]maximum(各頂点の次数）＝最大次数、Δ（G）とかく。[br]minimum(各頂点の次数）＝最小次数、δ（G)とかく。[br]これも常識的なネーミングだね。[br]ただ、同じデルタを大文字小文字で区別しているのはわかりにくいかも。[br]・[color=#0000ff][size=150]ｎ次の[b]正則グラフ[/b][/size][/color]はどの頂点の次数も等しくｎのグラフで、[br]　特に、[size=150][color=#0000ff][b]完全グラフ(complete graph)[/b] Kn＝(n,n-1)とは[/color][/size][color=#0000ff][b][size=150]頂点数がｎでn-1次の正則グラフだ。[/size][/b][/color][br]　どの点からもn-1辺が出ているので、どの２つの頂点同士も隣接しているといえるね。[br]　K1は１点グラフ。K2は線分。K3は正三角形と同型。K4は対角線のある正方形と同型。[br]　K５は対角線のある正五角形と同型。[br]・グラフGに頂点や辺や頂点を足し引きしたグラフを考えることがある。[br]Gの１頂点をu、vとし、１辺をeとする。また、Gにない１頂点をw，１辺をuv={u,v}とする。[br]G-uは、uに接続するすべての辺を取り除いたグラフ。G-eは辺を１辺を消しただけのグラフだ。[br]G+wは、ｗだけなく、wとGを結ぶ辺を追加したグラフ。G+uvは辺１辺を足しただけのグラフだ。[br][br][color=#9900ff][b][u][size=150]質問：完全グラフKnを順次書き出すコードはどうやって作りますか。[br][/size][/u][/b][/color][br]K1に辺がないのでこれは頂点(node)だけのグラフにする。[br]n=2からは、完全グラフを作って返す関数K(n）を作っておき、あとで順次使おう。[br][br]まず頂点リストVを作り、Vから２つ選んだ組み合わせとして辺の端点リストEをつくる。[br]そのあと、グラフのオブジェクトGを作ってから、GにEのデータを登録する。[br]表示のために、matplotlib.pyplotをpltに変名して、[b]plt.subplot(行数、列数、通し番号）で[br]表示枠をかき[/b]、そのあとに中にGを毎回描けばよいね。[br][br][color=#0000ff]#[IN]Python[br]#========================================[br][/color]import networkx as nx[br]import itertools[br]import matplotlib.pyplot as plt[br]n=6[br]G = nx.Graph()[br]G.add_node(1)[br]plt.subplot(2,3,1)[br]nx.draw_networkx(G)[br][color=#0000ff][br][b]def K(n):[br] V = list(range(1,n+1))[br] E = list(itertools.combinations(V,2))[br] G = nx.Graph()[br] G.add_edges_from(E)[br] return G[br][/b][br][/color]for i in range(2,n+1):[br] G=K(i)[br] plt.subplot(2,3,i)[br] nx.draw_networkx(G)[br][color=#0000ff]#========================================[br][/color][OUT][br][br]

[color=#9900ff][u][b][size=150]質問：グラフの要素のたしひき関数を作って、K５を加工するにはどうしますか？[br][/size][/b][/u][/color][br]頂点p追加はadd_node(p)[br]頂点p削除はremove_node(p)。辺には必ず端点があるので、１点を削除したら接続辺も削除される。[br]辺{p,q}追加はadd_edge(p,q)[br]辺{p,q}削除はremove_edge(p,q)[br]ただし、[color=#0000ff]頂点削除は接続辺も連動して削除されるが、[br]頂点追加add_node(p)は孤立点が追加されるだけなので、既存の頂点と結ぶ辺のデータをGに追加する関数[br]add_node_with_edges(G,n)を作ってみよう[/color]。[br][br][color=#0000ff]#[IN]python[br]#=======================================================[br][/color]import networkx as nx[br]import itertools[br]import matplotlib.pyplot as plt[br]def K(n):[br] V = list(range(1,n+1))[br] E = list(itertools.combinations(V,2))[br] G = nx.Graph()[br] for i in range(len(E)):[br] x,y = E[i][0], E[i][1][br] G.add_edge(x,y)[br] return G[br][b][color=#0000ff]def add_node_with_edges(G,n):[br] V=G.nodes() [br] G.add_node(n)[br] for i in V:[br] G.add_edge(i,n)[br] return G [br][/color][/b]G=K(5)[br]plt.subplot(3,2,1)[br]nx.draw_networkx(G)[br][br]G.remove_node(1) #G-1[br]plt.subplot(3,2,2)[br]nx.draw_networkx(G)[br][br]add_node_with_edges(G,0) #G+0, G.add_node(0)では頂点だけが孤立点でたさせる[br]plt.subplot(3,2,3)[br]nx.draw_networkx(G)[br][br]G.remove_edge(2,3) #G-{2,3}[br]G.remove_edge(3,4) #G-{3,4}[br]G.remove_edge(2,4) #G-{2,4}[br]plt.subplot(3,2,4)[br]nx.draw_networkx(G)[br][br]G.add_edge(3,4) #G-{3,4}[br]plt.subplot(3,2,5)[br]nx.draw_networkx(G)[br][color=#0000ff]#=======================================================[br][OUT][br][/color]

グラフの点が決まっているとき、完全グラフをかくことができた。[br]ということは、完全でないグラフとその補グラフをあわせると完全グラフになるのだから、[br]完全でないグラフは補グラフをかくことで、その特徴を裏側から炙り出せるでしょう。[br][color=#9900ff][b][u][size=150][br]質問：グラフからその補グラフを作るにはどうしたよいでしょうか。[br][/size][/u][/b][/color][br]グラフGの頂点Vから完全グラフの辺集合Eを作る。[br]そして、与えられたグラフの辺集合Fとの差集合Eh=E-Fを作る。[br]そして、G(V,Eh)で補グラフ作成関数comp(G)となるね。[br][br]#[IN]Python[br]#====================================================================[br]# 補グラフをかく。[br]import networkx as nx[br]import itertools[br]import matplotlib.pyplot as plt[br][color=#0000ff][b]def K(n):[br] V = list(range(1,n+1))[br] E = list(itertools.combinations(V,2))[br] G = nx.Graph()[br] G.add_edges_from(E)[br] return G[br]def comp(G):[br] V = G.nodes()[br] E = G.edges()[br] Kom = K(len(V))[br] F = Kom.edges()[br] Eh = list(set(F)-set(E))[br] H = nx.Graph()[br] H.add_nodes_from(V)[br] H.add_edges_from(Eh)[br] return H[br][/b][/color]G=K(5)[br]plt.subplot(1,3,1)[br]nx.draw_networkx(G,node_color='Yellow') #完全グラフ[br][br]G.remove_edge(2,3) #G-{2,3}[br]G.remove_edge(3,4) #G-{3,4}[br]G.remove_edge(2,4) #G-{2,4}[br]plt.subplot(1,3,2)[br]nx.draw_networkx(G) #不完全グラフ[br][br]H=comp(G)[br]plt.subplot(1,3,3)[br]nx.draw_networkx(H,node_color='Red') #補グラフ[br]#====================================================================[br][OUT]