Null graph
Template:Short description 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 graphEdit
The order-zero graph, Template:Math, is the unique graph having no vertices (hence its order is zero). It follows that Template:Math also has no edges. Thus the null graph is a regular graph of degree zero. Some authors exclude Template:Math from consideration as a graph (either by definition, or more simply as a matter of convenience). Whether including Template:Math as a valid graph is useful depends on context. On the positive side, Template:Math follows naturally from the usual set-theoretic definitions of a graph (it is the ordered pair Template:Math for which the vertex and edge sets, Template:Mvar and Template:Mvar, are both empty), in proofs it serves as a natural base case for mathematical induction, and similarly, in recursively defined data structures Template:Math 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 Template:Math 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 Template:Math). 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.<ref name="mathworld emptygraph">{{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web |_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:EmptyGraph%7CEmptyGraph.html}} |title = Empty Graph |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}</ref><ref name="mathworld nullgraph">{{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web |_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:NullGraph%7CNullGraph.html}} |title = Null Graph |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}</ref>
In category theory, the order-zero graph is, according to some definitions of "category of graphs," the initial object in the category.
Template:Math does fulfill (vacuously) most of the same basic graph properties as does Template:Math (the graph with one vertex and no edges). As some examples, Template:Math is of size zero, it is equal to its complement graph Template:Math, 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 Template:Math.
Edgeless graphEdit
For each natural number Template:Mvar, the edgeless graph (or empty graph) Template:Mvar of order Template:Mvar is the graph with Template:Mvar 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.<ref name="mathworld emptygraph"/><ref name="mathworld nullgraph"/>
It is a 0-regular graph. The notation Template:Mvar arises from the fact that the Template:Mvar-vertex edgeless graph is the complement of the complete graph Template:Mvar.
See alsoEdit
NotesEdit
ReferencesEdit
- 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.