ヌルグラフ

数学のグラフ理論の分野では、「ヌル グラフ」という用語は、順序がゼロの グラフ、またはエッジのないグラフ (後者は「空のグラフ」と呼ばれることもあります)のいずれかを指します。

次数ゼロのグラフK 0_は、頂点を持たない唯一のグラフです（したがって、次数はゼロです）。したがって、K ₀には辺もありません。したがって、ヌルグラフは次数ゼロの正則グラフです。著者の中には、 K _{0 を}グラフとして考慮に入れない人もいます（定義により、またはもっと単純に便宜上）。K _{0 を}有効なグラフに含めることが有用かどうかは、コンテキストによって異なります。肯定的な面では、K _{0 は、}グラフの通常の集合論的定義から自然に従います（頂点と辺の集合VとEが両方とも空である順序付きペア （V、E）です）。証明では、数学的帰納法の自然な基本ケースとして機能し、同様に、再帰的に定義されたデータ構造では、 K _{0 は}再帰の基本ケースを定義するのに役立ちます（ヌルツリーを任意の非ヌルバイナリツリーの欠落している辺の子として扱うことにより、すべての非ヌルバイナリツリーにはちょうど2つの子があります）。一方、K _{0 を}グラフに含めるには、グラフ特性の明確に定義された多くの式に例外を含める必要があります (たとえば、「グラフの強く連結されたすべてのコンポーネントを数える」が「グラフのヌルでない強く連結されたすべてのコンポーネントを数える」になるか、連結グラフの定義がK _{0 を}含まないように変更される必要があります)。このような例外の必要性を回避するために、文脈が別のことを示唆しない限り、グラフという用語は「少なくとも 1 つの頂点を持つグラフ」を意味すると文献で想定されることがよくあります。^{[1] [2]}

圏論では、いくつかの「グラフの圏」の定義によれば、ゼロ次グラフは、その圏の 初期オブジェクトです。

K _{0 は、} K ₁ (頂点が 1 つで辺のないグラフ)と同じ基本的なグラフ特性のほとんどを(空虚に) 満たしています。例として、 K _{0 は}サイズが 0であること、補グラフK ₀と等しいこと、フォレストであること、平面グラフであることなどが挙げられます。 K 0 は無向、有向、またはその両方であると見なされる場合があります。有向と見なされる場合は、有向非巡回グラフです。また、完全グラフであり、辺のないグラフでもあります。ただし、これらのグラフ特性のそれぞれの定義は、コンテキストがK ₀を許可するかどうかによって異なります。

それぞれの自然数 nに対して、次数nの辺なしグラフ（または空グラフ）K _{n は}、頂点がn個で辺が 0 個あるグラフです。辺なしグラフは、次数 0 のグラフが許可されていないコンテキストでは、ヌルグラフと呼ばれることがあります。^{[1] [2]}

これは 0正則グラフです。K n_という表記は、n頂点のエッジのないグラフが完全グラフK _nの補グラフであるという事実から生じます。

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

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