位数0のグラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2012/02/04 02:02 UTC 版)
位数0（頂点が0個）のグラフ K0 は、位数0の唯一のグラフである。したがって、辺も0個である。文脈によっては K0 はグラフとは見なされない（定義上除外される場合や単に利便性のために除外される場合がある）。 いくつかのグラフの圏に関する定義によれば、位数0のグラフはグラフの圏における始対象である。一部の文脈ではグラフ理論の定義にこれを含めた方が便利である。例えば、グラフを集合論的に定義する場合 K0 を使うのが自然であり（その場合、空集合の順序対とされる）、データ構造を再帰的に定義する場合、再帰の基本のケースとして K0 を使うのが便利である（null tree を任意のnullでない二分木、すなわち必ず2つの子ノードを持つ木から辺を除去した子ノードとして扱う）。逆にグラフのプロパティを定義する際には、K0 をグラフに含めるなら例外扱いしなければならない。例えば、あるグラフの強連結成分を数え上げる場合、「グラフの『空でない』強連結成分を数え上げる」としなければならない。このような不適当な面があるため「グラフ」と文字に書いたとき、文脈上それ以外の定義を示唆していない限り、暗に「少なくとも頂点を1つ持つグラフ」を指しているのが一般的である。 グラフだと認めた場合 K0 はおおよそ K1（頂点が1個で辺のないグラフ）と同じ基本的プロパティを（空虚に）満たす。サイズ（辺の総数）はゼロであり、自身の補グラフ () と等しく、1つの連結成分（すなわち ）があり、閉路がなく、木であり、森であり、有向グラフまたは無向グラフ（あるいは両方）であり、完全グラフであり、辺のないグラフ (empty graph) である。しかし、これらのプロパティの定義は、文脈上 K0 を許容するかどうかで変わってくる。例えば、「連結成分」といった場合 K0 を除外するのが一般的だが、データ構造としての木構造には "null tree" の場合を含むことが多い。
※この「位数0のグラフ」の解説は、「空グラフ」の解説の一部です。
「位数0のグラフ」を含む「空グラフ」の記事については、「空グラフ」の概要を参照ください。
- 位数0のグラフのページへのリンク
