ヌルグラフ

グラフ理論の数学分野において、「ヌルグラフ」という用語は、次数がゼロのグラフを指す場合もあれば、辺を持たないグラフ（後者は「空グラフ」と呼ばれることもある）を指す場合もある。

次数ゼロのグラフK ₀は、頂点を持たない唯一のグラフです(したがって、その次数はゼロです)。したがって、K ₀には辺もありません。つまり、ヌルグラフは次数ゼロの正則グラフです。一部の著者は、 K _{0 を}グラフとして考慮することから除外しています (定義による場合もあれば、単に便宜上の理由による場合もあります)。K _{0 を}有効なグラフとして含めることが有用かどうかは、文脈によります。良い点としては、K ₀は、通常の集合論的なグラフの定義から自然に導かれます (頂点集合Vと辺集合Eの両方が空である順序対( V、E )です)。証明では、数学的帰納法の自然な基本ケースとして機能します。同様に、再帰的に定義されたデータ構造では、 K ₀は再帰の基本ケースを定義するのに役立ちます (ヌル木を、ヌルでない二分木で欠落している辺の子として扱うことで、すべてのヌルでない二分木はちょうど2 つの子を持ちます)。マイナス面としては、K _{0 を}グラフとして含める場合、グラフの特性に関する多くの明確な公式に例外を設ける必要が生じる（例えば、「グラフのすべての強連結成分を数える」が「グラフのすべての非ヌル強連結成分を数える」になるか、連結グラフの定義を修正してK ₀を含めないようにする必要がある）。このような例外の必要性を避けるため、文献では、文脈上そうでないことが示唆されない限り、グラフという用語は「少なくとも 1 つの頂点を持つグラフ」を意味すると仮定されることが多い。^{[ 2 ] [ 3 ]}

圏論において、位数ゼロのグラフは、「グラフの圏」のいくつかの定義によれば、その圏における最初の対象である。

K _{0 は、} K ₁ (頂点が 1 つで辺がないグラフ)とほぼ同じ基本的なグラフ特性を(自明に)満たします。いくつかの例を挙げると、 K ₀はサイズがゼロであり、その補グラフK ₀と等しく、森であり、平面グラフです。無向グラフ、有向グラフ、またはその両方とみなすことができます。有向グラフとみなした場合、有向非巡回グラフになります。また、完全グラフであり、辺のないグラフでもあります。ただし、これらのグラフ特性の定義は、文脈がK ₀を許容するかどうかによって異なります。

各自然数nに対して、次数nの辺のないグラフ(または空グラフ) K _{n は}、 n個の頂点と 0 個の辺を持つグラフです。次数 0 のグラフが許容されない文脈では、辺のないグラフはヌル グラフと呼ばれることがあります。^{[ 2 ] [ 3 ]}

これは0-正則グラフです。K _nという表記は、 n個の頂点を持つ辺のないグラフが完全グラフK _nの補グラフであるという事実から来ています。

• グラフ理論用語集
• サイクルグラフ
• パスグラフ

• ウィキメディア・コモンズにあるヌルグラフ関連のメディア