In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
The order-zero graph, K0, is the unique graph having no vertices (hence its order is zero). It follows that K0 also has no edges. Thus the null graph is a regular graph of degree zero. Some authors exclude K0 from consideration as a graph (either by definition, or more simply as a matter of convenience). Whether including K0 as a valid graph is useful depends on context. On the positive side, K0 follows naturally from the usual set-theoretic definitions of a graph (it is the ordered pair (V, E) for which the vertex and edge sets, V and E, are both empty), in proofs it serves as a natural base case for mathematical induction, and similarly, in recursively defined data structures K0 is useful for defining the base case for recursion (by treating the null tree as the child of missing edges in any non-null binary tree, every non-null binary tree has exactly two children). On the negative side, including K0 as a graph requires that many well-defined formulas for graph properties include exceptions for it (for example, either "counting all strongly connected components of a graph" becomes "counting all non-null strongly connected components of a graph", or the definition of connected graphs has to be modified not to include K0). To avoid the need for such exceptions, it is often assumed in literature that the term graph implies "graph with at least one vertex" unless context suggests otherwise.[1][2]
В теории категорий граф нулевого порядка является, согласно некоторым определениям «категории графов», исходным объектом в категории.
K 0 выполняет ( пусто ) большинство тех же основных свойств графа, что и K 1 (граф с одной вершиной и без ребер). В качестве некоторых примеров, K 0 имеет размер ноль, он равен своему дополнительному графу K 0 , лесу и планарному графу . Его можно считать неориентированным , ориентированным или даже обоими; если рассматривать его как ориентированный, он является ориентированным ациклическим графом . И он является как полным графом , так и графом без ребер. Однако определения для каждого из этих свойств графа будут различаться в зависимости от того, допускает ли контекст K 0 .
Для каждого натурального числа n , граф без ребер (или пустой граф) K n порядка n — это граф с n вершинами и нулевыми ребрами. Граф без ребер иногда называют нулевым графом в контекстах, где граф нулевого порядка не допускается. [1] [2]
Это 0- регулярный граф. Обозначение K n возникает из того факта, что n -вершинный граф без ребер является дополнением полного графа K n .
Медиа, связанные с Null graphs на Wikimedia Commons