# 単純グラフ ## 定義 単純グラフ(simple graph)`G` は、空でない頂点(vertex、node とも呼ぶ)の集合 `V(G)` と、無向辺(undirected edge、単に「辺」とも呼ぶ)の集合 `E(G)` からなる構造である。無向辺は2元集合 `{u,v}`(`u≠v`)として表され、`⟨u—v⟩` と書く。`⟨u—v⟩` と `⟨v—u⟩` は同じ辺を指す。自己ループ(self-loop、両端点が同じ辺)や、同じ2頂点間の多重辺は単純グラフでは許されない(自己ループや多重辺を許す一般化は多重グラフ(multigraph)と呼ばれ本書では扱わない)。2頂点が同じ辺の端点であるとき隣接(adjacent)、辺はその端点に接続(incident)するという。頂点 `v` の次数(degree)`deg(v)` は `v` に接続する辺の本数(=隣接する頂点の数)。頻出する基本形として、n頂点の全ペアに辺を張る完全グラフ `K_n`(辺数 `n(n-1)/2`)、辺を持たない空グラフ、n頂点を一列に繋ぐ線グラフ `L_n`、`L_n` の両端をさらに結んだ閉路グラフ `C_n` がある。2つのグラフ `G`, `H` は、辺の対応関係を保つ全単射(同型写像、isomorphism)`f: V(G)→V(H)`(`⟨u—v⟩∈E(G)` iff `⟨f(u)—f(v)⟩∈E(H)`)が存在するとき同型(isomorphic)であるといい、頂点数・次数分布などの性質はすべて同型で保存される。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] §11.1, §11.3, §11.4) 任意の単純グラフについて、全頂点の次数の総和は辺数の2倍に等しい(**握手補題**、Handshaking Lemma)。この関係は、二部グラフ(bipartite graph、頂点集合が `L(G)` と `R(G)` に分割され全辺が両側に1端点ずつ持つグラフ)における平均次数の恒等式など、多くの応用的な数え上げ論法の出発点になる。頂点と辺が交互に並ぶ有限列を歩道(walk)、頂点が重複しない歩道を道(path)、始点=終点の歩道を閉歩道(closed walk)、長さ3以上かつ始点=終点以外の頂点が相異なる閉歩道を閉路(cycle)と呼ぶ(有向グラフと異なり、長さ1・長さ2の閉歩道は単純グラフでは存在しない・閉路に数えないという違いがある)。2頂点間に道が存在するとき連結(connected)であるといい、連結な頂点・辺の極大な集まりを連結成分(connected component)と呼ぶ。閉路を持たないグラフを森(forest)、連結な森を木(tree)と呼ぶ。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] §11.2, §11.8, §11.9, §11.10) ## 横断的知見 - 第9章は有向グラフを「頂点集合を定義域・余域とする二項関係」として定義し、単純グラフは直感的には「有向グラフの辺から向きを外したもの」として11章冒頭で導入される。しかし形式的な `Definition 11.1.1` は有向辺の集合を無向化するのではなく、辺を最初から2元集合 `{u,v}` として独立に定義し直している。両章を突き合わせると、単純グラフは有向グラフの派生物(商構造)としてではなく、独立した公理系として扱われていることが分かる——このため、有向グラフのk乗の隣接行列で歩道数を数える手法や、DAG・半順序の理論はそのままでは単純グラフに移植できず、対称な隣接行列(`A_G = A_G^T`)という形でのみ間接的に対応する。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]], [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]]) - 第9章の閉路の定義(有向グラフでは長さ1の自己ループを除けば長さ2の閉歩道 `u→v→u` も閉路になりうる)と、第11章の閉路の定義(長さ3未満の閉歩道は閉路に含めない)は、同じ用語でありながら異なる規約を採用している。理由は単純グラフでは同じ辺を往復する長さ2の閉歩道が常に存在してしまい、それを閉路と呼んでも情報量がないためであり、章をまたいで「閉路」という語を使うときは対象が有向か無向かで最小長の規約が変わる点に注意が必要である。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]], [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]]) - 第11章は単純グラフを頂点集合と無向辺集合の組という純粋に代数的・離散的な構造として定義するが、第12章(平面グラフ)はその同じ離散構造に「平面に交差なく描けるか」という連続幾何学的な性質を重ね、平面描画(連続)と平面埋め込み(離散データ型)という二重定義でこれを扱う。第11章の握手補題(次数の総和=辺数の2倍)と二部グラフの奇閉路禁止(§11.9.2)は、そのまま第12章の平面グラフの辺数上界(e≤3v−6, e≤2v−4)の証明と K3,3 の非平面性の証明の前提として再利用されており、単純グラフの理論は平面グラフの理論に対して独立した前提ではなく積層した基盤として機能している。また第11章の木(閉路を持たない連結グラフ)は、第12章でマイナーの言葉により「C3(3頂点の閉路)をマイナーとして含まない連結グラフ」として再特徴づけられ、同一の対象が部分グラフ的性質とマイナー的性質という異なる抽象化レベルから記述できることが分かる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]], [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]]) ## 未解決の問い - 第10章(通信ネットワーク)は有向グラフ寄りの通信網トポロジを扱うが、単純グラフとしての通信網(無向リンク)との対応・使い分けは本章単独からは確認できていない。 ## 関連 - 概念: [[有向グラフ]] / [[マッチング]] / [[安定結婚問題]] / [[グラフ彩色]] / [[木(グラフ理論)]] / [[平面グラフ]] / [[二項関係]] / [[同値関係]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 11.