空グラフ

空グラフ（英: null graph）は、数学のグラフ理論において、位数0のグラフ、または辺のないグラフ (edgeless graph) を意味する（後者は empty graph とも呼ぶ）。

位数0のグラフ

位数0のグラフ（空グラフ）
頂点 0
辺 0
半径 0
直径 0
内周 ∞ {\displaystyle \infty }
自己同型 1
彩色数 0
彩色指数 0
特性 整数
対称
種数 0
表記 K 0 {\displaystyle K_{0}}
テンプレートを表示

位数0（頂点が0個）のグラフ K 0 {\displaystyle K_{0}} は、位数0の唯一のグラフである。したがって、辺も0個である。文脈によっては K 0 {\displaystyle K_{0}} はグラフとは見なされない（定義上除外される場合や単に利便性のために除外される場合がある）。

いくつかのグラフの圏に関する定義によれば、位数0のグラフはグラフの圏における始対象である。一部の文脈ではグラフ理論の定義にこれを含めた方が便利である。例えば、グラフを集合論的に定義する場合 K 0 {\displaystyle K_{0}} を使うのが自然であり（その場合、空集合の順序対とされる）、データ構造を再帰的に定義する場合、再帰の基本のケースとして K 0 {\displaystyle K_{0}} を使うのが便利である（null tree を任意のnullでない二分木、すなわち必ず2つの子ノードを持つ木から辺を除去した子ノードとして扱う）。逆にグラフのプロパティを定義する際には、 K 0 {\displaystyle K_{0}} をグラフに含めるなら例外扱いしなければならない。例えば、あるグラフの強連結成分を数え上げる場合、「グラフの『空でない』強連結成分を数え上げる」としなければならない。このような不適当な面があるため「グラフ」と文字に書いたとき、文脈上それ以外の定義を示唆していない限り、暗に「少なくとも頂点を1つ持つグラフ」を指しているのが一般的である[1][2]。

グラフだと認めた場合 K 0 {\displaystyle K_{0}} はおおよそ K 1 {\displaystyle K_{1}} （頂点が1個で辺のないグラフ）と同じ基本的プロパティを（空虚に）満たす。サイズ（辺の総数）はゼロであり、自身の補グラフ ( K ¯ 0 {\displaystyle {\bar {K}}_{0}} ) と等しく、1つの連結成分（すなわち ∀ x ∈ V : ∀ y ∈ V : ∃ p a t h ( x , y ) {\displaystyle \forall x\in V:\forall y\in V:\exists path(x,y)} ）があり、閉路がなく、木であり、森であり、有向グラフまたは無向グラフ（あるいは両方）であり、完全グラフであり、辺のないグラフ (empty graph) である。しかし、これらのプロパティの定義は、文脈上 K 0 {\displaystyle K_{0}} を許容するかどうかで変わってくる。例えば、「連結成分」といった場合 K 0 {\displaystyle K_{0}} を除外するのが一般的だが、データ構造としての木構造には "null tree" の場合を含むことが多い。

辺のないグラフ

辺のないグラフ（empty graph、空グラフ）
頂点 n
辺 0
半径 0
直径 0
内周 ∞ {\displaystyle \infty }
自己同型 n!
彩色数 1
彩色指数 0
特性 整数
対称
種数 0
表記 K ¯ n {\displaystyle {\bar {K}}_{n}}
テンプレートを表示

任意の自然数 n について、辺のないグラフ（edgeless graph または empty graph） K ¯ n {\displaystyle {\bar {K}}_{n}} は、頂点が n 個で辺が0個のグラフである。位数0のグラフをグラフとして許容しない文脈では、辺のないグラフ (edgeless graph) を空グラフ (null graph) と称する[2][1]。

この定義はある種のグラフ操作（例えば、分解）には確かな基盤を与えるが、グラフを頂点と辺の集合 (V, E) と考えたとき、この定義はグラフの空要素の一意性に問題が生じる。

n-頂点で辺のないグラフは完全グラフ K n {\displaystyle K_{n}} の補グラフであり、一般に K ¯ n {\displaystyle {\bar {K}}_{n}} と表記する。

関連項目

注釈・出典

  1. ^ a b Weisstein, Eric W. "Empty Graph". mathworld.wolfram.com (英語).
  2. ^ a b Weisstein, Eric W. "Null Graph". mathworld.wolfram.com (英語).

参考文献

ウィキメディア・コモンズには、空グラフに関連するカテゴリがあります。
  • Harary, F. and Read, R. (1973), "Is the null graph a pointless concept?", Graphs and Combinatorics (Conference, George Washington University), Springer-Verlag, New York, NY.