“Null graph”的意思、由来-开放百科全书

词条

Null graph

释义

Order-zero graph
Edgeless graph
See also
Notes
References

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").

Order-zero graph

{{infobox graph
| name = Order-zero graph (null graph)
| vertices = 0
| edges = 0
| girth =

| properties = Integral
Symmetric
}}

The order-zero graph, , is the unique graph having no vertices (hence its order is zero). It follows that also has no edges. Some authors exclude from consideration as a graph (either by definition, or more simply as a matter of convenience). Whether including as a valid graph is useful depends on context. On the positive side, 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 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 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 K₀). 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]

In category theory, the order-zero graph is, according to some definitions of "category of graphs," the initial object in the category.

does fulfill (vacuously) most of the same basic graph properties as does (the graph with one vertex and no edges). As some examples, is of size zero, it is equal to its complement graph , a forest, and a planar graph. It may be considered undirected, directed, or even both; when considered as directed, it is a directed acyclic graph. And it is both a complete graph and an edgeless graph. However, definitions for each of these graph properties will vary depending on whether context allows for .

Edgeless graph

{{infobox graph
| name = Edgeless graph (empty graph, null graph)
| vertices = n
| edges = 0
| radius = 0
| diameter = 0
| girth =

| properties = Integral
Symmetric
}}

For each natural number n, the edgeless graph (or empty graph) of order n is the graph with n vertices and zero edges. An edgeless graph is occasionally referred to as a null graph in contexts where the order-zero graph is not permitted.^[1]^[2]

It is a 0-regular graph. The notation arises from the fact that the n-vertex edgeless graph is the complement of the complete graph .

Notes

1. ^¹{{MathWorld |urlname=EmptyGraph |title=Empty Graph}}
2. ^¹{{MathWorld |urlname=NullGraph |title=Null Graph}}

References

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.

2 : Graph families|Regular graphs

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Order-zero graph

Edgeless graph

See also

Notes

References