In the
mathematical field of
graph theory, the term "null graph" may refer either to the
order
Order, ORDER or Orders may refer to:
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
* Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of d ...
-
zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
Order-zero graph
The order-zero graph, , is the unique graph having no
vertices (hence its order is zero). It follows that also has no
edges
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed by ...
. Thus the null graph is a
regular graph of degree zero. 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
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
for which the vertex and edge sets, and , are both
empty), in
proofs it serves as a natural base case for
mathematical induction, and similarly, in
recursively defined data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s is useful for defining the base case for recursion (by treating the null
tree as the
child
A child ( : children) is a human being between the stages of birth and puberty, or between the developmental period of infancy and puberty. The legal definition of ''child'' generally refers to a minor, otherwise known as a person younger ...
of missing edges in any non-null
binary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
, 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 component
In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that a ...
s 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 ). 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.
In
category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
, the order-zero graph is, according to some definitions of "category of graphs," the
initial object in the category.
does fulfill (
vacuously
In mathematics and logic, a vacuous truth is a conditional or universal statement (a universal statement that can be converted to a conditional statement) that is true because the antecedent cannot be satisfied. For example, the statement "she ...
) 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
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
. It may be considered
undirected
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ...
,
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
For each
natural number , the edgeless graph (or empty graph) of order is the graph with 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.
It is a 0-
regular
The term regular can mean normal or in accordance with rules. It may refer to:
People
* Moses Regular (born 1971), America football player
Arts, entertainment, and media Music
* "Regular" (Badfinger song)
* Regular tunings of stringed instrum ...
graph. The notation arises from the fact that the -vertex edgeless graph is the
complement of the
complete graph .
See also
*
Glossary of graph theory
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A
B
...
*
Cycle graph
*
Path graph
Notes
References
{{commons category, Null graphs
*
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.
Graph families
Regular graphs