空グラフのソースを表示

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

== 位数0のグラフ ==
{{Infobox graph
| name     = 位数0のグラフ（空グラフ）
 | vertices = 0
 | edges    = 0
 | radius   = 0
 | diameter = 0
 | girth    = <math>\infty</math>
 | automorphisms = 1
 | chromatic_number = 0
 | chromatic_index  = 0
 | genus = 0
 | spectral_gap = 未定義
 | notation =  <math>K_0</math>
 | properties = [[:en:Integral graph|整数]]<br/>[[:en:Symmetric graph|対称]]
}}
[[位数]][[0]]（頂点が0個）のグラフ <math>K_0</math> は、位数0の唯一のグラフである。したがって、辺も0個である。文脈によっては <math>K_0</math> はグラフとは見なされない（定義上除外される場合や単に利便性のために除外される場合がある）。

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

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

== 辺のないグラフ ==
{{Infobox graph
| name     = 辺のないグラフ（empty graph、空グラフ）
 | vertices = n
 | edges    = 0
 | radius   = 0
 | diameter = 0
 | girth    = <math>\infty</math>
 | automorphisms    = n!
 | chromatic_number = 1
 | chromatic_index  = 0
 | genus = 0
 | spectral_gap = 未定義
 | notation =  <math>\bar K_n</math>
 | properties = [[:en:Integral graph|整数]]<br/>[[:en:Symmetric graph|対称]]
}}
任意の[[自然数]] ''n'' について、辺のないグラフ（edgeless graph または empty graph） <math>\bar K_n</math> は、頂点が ''n'' 個で辺が0個のグラフである。位数0のグラフをグラフとして許容しない文脈では、辺のないグラフ (edgeless graph) を空グラフ (null graph) と称する<ref name="NullGraph" /><ref name="EmptyGraph" />。

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

''n''-頂点で辺のないグラフは[[完全グラフ]] <math>K_n</math> の[[補グラフ]]であり、一般に <math>\bar K_n</math> と表記する。

== 関連項目 ==
* [[グラフ理論]]
* [[閉路グラフ]]
* [[道 (グラフ理論)]]

== 注釈・出典 ==
{{Reflist}}

== 参考文献 ==
{{Commonscat|Null graphs}}
* 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.

{{DEFAULTSORT:くうくらふ}}

[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]
[[Category:無]]