グラフ理論入門 １ 基礎
１ グラフ理論の基礎
1.1 グラフと頂点の次数
- グラフ(graph,G)の定義
- グラフで表現される「事象」の例
- グラフの分類
- 有限グラフと無限グラフ
- 有限グラフ(頂点集合V(G)の要素が有限であるグラフ)
- 無限グラフ(頂点集合V(G)の要素が無限であるグラフ)
- 両者は、各種定理の証明上の扱いがことなることからもわかるように、異なる性質を有する。ただし、遺伝統計学への応用にあたっては、「現実世界」の要素が有限であることから、有限グラフを扱うものと考えられる。ただし、「数多くの要素」をハンドリングするときに「無限とみなす(たとえば、変異の中立仮説のように)」必要も生じるものと想像される。
- グラフ・多重グラフ・準グラフ
- 多重グラフ：2以上の辺によって結ばれた頂点ペアを有するグラフ
- 準グラフ：ただ1頂点にのみ接続する辺を有するグラフ(ループを有する)
- (狭義の)グラフ：多重グラフでも準グラフでもないグラフ
- 有限グラフと無限グラフ
- グラフを表現するための用語
- 隣接(adjacent)：ある２頂点を結ぶ辺が存在するとき、その２頂点は「隣接する」と言う
- 隣(neighbor)：互いに隣接する２頂点があるとき、片方の頂点はもう片方の頂点の「隣」であると呼ぶ。
- 近傍(neighborhood,neighbor set)：ある頂点と隣接する頂点の集合のこと。
- 接続(incident)：ある辺の端がある頂点であるとき、その頂点はその辺に「接続している」と言う。また、逆にその辺はその頂点に「接続している」と言う。
- グラフの表記
- Gp,q:頂点数 p, 辺数 q のグラフ
- 頂点に関する表現
- 次数(degree):頂点に接続する辺の数
- 孤立頂点(isolated vertex):次数=0の頂点
- 端頂点(end vertex):次数=1の頂点
- グラフの頂点次数が作る非負数数列:グラフ的数列
- 道(path, Pn)
- ラベル付けされたn+1個の頂点{x0,x1,x2,...,xn}とそれを結ぶ辺{x0x1,x1x2,...,xn-1xn}から成るグラフを長さnの道と言う。この道の端頂点がx0,xnである。
- サイクル(cycle, Cn)
- ラベル付けされたn個の頂点{x0,x1,...,xn-1}とそれを結ぶ辺{x0x1,x1x2,...,xn-1x0}から成るグラフを長さnのサイクルと言う。n-サイクルとも呼ぶ。頂点数が偶数のサイクルを偶サイクル、奇数のサイクルを奇サイクルと称する。
- サイクルの対角的な道
- サイクル上の異なる２頂点を結ぶ道で、サイクルとの交わりが、その道の2端頂点だけであるものを言う。
- 距離(distance,d(x,y))
- グラフの2頂点を結ぶ最短の道の長さ。ただし、道によって結ばれていない2頂点間の距離は無限大と定義する。
- 直径(diameter)
- グラフGの２頂点間の距離の最大値
- Pnの直径はn
- Wn(n>3)の直径は2
- Knの直径は1
- グラフGの２頂点間の距離の最大値
- 正則(regular)
- グラフGのすべての頂点の次数がkであるとき、Gは次数kの正則(k-regular)と言う。
- Knは次数n-1の正則である。
- r-因子(r-factor)
- グラフGの全域部分グラフHが、次数rの正則であるとき、HはGのr-因子と呼ばれる。
- 頂点個数が奇数のグラフには、1-因子は存在しないが、頂点個数が偶数のグラフであっても1-因子を持つとは限らない。
- 橋(bridge)
- Gの辺で、それをGから取り除くとGが2つの部分グラフに分かれて非連結となるものを言う。
- 辺を持たない場合を除いて、木はすべて橋を持つ。実際、木の任意の辺は橋であり、木はこの性質を持つ、唯一の連結グラフである。
- 堤(bank)
- 橋を取り除いたあとに残された、2つの連結部分グラフを、この橋の堤と呼ぶ。
- 成分(component)
- 非連結グラフの部分グラフであり、連結グラフであり、それよりも大きい連結部分グラフに含まれないものを、成分と呼ぶ。
- 非連結グラフは、成分に分けられ、その分け方は1意である。
- 星(star)または傘(umbrella)
- K1,tのこと。
- 車輪グラフ(Wn)
- n-サイクルとサイクルのn個の頂点のすべてと隣接する１頂点とからなるグラフ。
1.2 部分グラフ、同型なグラフ
- 部分グラフ(subgraph,H)
- あるグラフ G について、次の条件を満たすグラフ H を G の部分グラフと言う。
- V(G)はV(H)の部分集合
- E(H)はE(G)の部分集合
- 真部分グラフ(proper subgraph)
- HがGの部分グラフであって、Gでないとき、HをGの真部分グラフと言う。
- 同型(isomorphic)
- ２つのグラフが同数の頂点を持ち、次のように順列化できるとき、その２グラフは同定であると言う。
- ２つのグラフに作製した順列が作るすべてのラベルペアにつき、その２頂点が隣接しているか否かが２グラフ間で一致する。
- 特別な呼称を有するグラフ
- ペテルセングラフ(Petersen graph)
- 完全グラフ(complete graph, Kn: n個の頂点を持つ完全グラフ)
- n個の頂点を持つグラフで、各頂点は残りの全ての頂点と隣接している。
- n(n-1)/2本の辺を有する。
- 完全2部グラフ(complete bipartite graph,Km,n)
- m+n個の頂点を有し、2色に彩色(coloring)することで、m個とn個の頂点に分けられる。
- また、すべての頂点は隣頂点を有する
- 立体図形に相当するグラフ
- K4:４面体
- Q3:立方体グラフ
- O :8面体グラフ(octahedral graph)
- D :12面体グラフ(dodecahedral graph)
- I :20面体グラフ(isosahedral graph)
1.3 木(tree)
- 連結(connected):木を定義するの必要な概念
- グラフGの任意の2頂点を結ぶ道が存在する場合、Gは連結であると言う。
- 木(tree)
- 連結グラフであり、かつ、その部分グラフの中にサイクルを含まないもの。
- 林(forest)
- サイクルを含まないグラフ
- 木と林の関係
- 林の任意の連結部分は木である。
- 林の部分グラフはすべて林である。
- 木は林であり、木のすべての部分グラフも林である。
- 全域部分グラフ(spanning subgraph)
- Gの部分グラフで、Gのすべての頂点を含むもの。
- 全域木
- 全域部分グラフのうち、木であるもの。
- 木とサイクルについては、グラフ理論上の興味深い課題がある。
- その他
