HOME

TheInfoList



OR:

In the
mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, the term "null graph" may refer either to the order-
zero 0 (zero) is a number representing an empty quantity. Adding (or subtracting) 0 to any number leaves that number unchanged; in mathematical terminology, 0 is the additive identity of the integers, rational numbers, real numbers, and compl ...
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. 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, denoted (''a'', ''b''), is a pair of objects in which their order is significant. The ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a''), unless ''a'' = ''b''. In contrast, the '' unord ...
for which the vertex and edge sets, and , are both empty), in proofs it serves as a natural base case for
mathematical induction Mathematical induction is a method for mathematical proof, proving that a statement P(n) is true for every natural number n, that is, that the infinitely many cases P(0), P(1), P(2), P(3), \dots  all hold. This is done by first proving a ...
, and similarly, in recursively defined
data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
s is useful for defining the base case for recursion (by treating the null
tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...
as the
child A child () is a human being between the stages of childbirth, birth and puberty, or between the Development of the human body, developmental period of infancy and puberty. The term may also refer to an unborn human being. In English-speaking ...
of missing edges in any non-null
binary tree In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the ''left child'' and the ''right child''. That is, it is a ''k''-ary tree with . A recursive definition using set theor ...
, 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 mathematics, mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachability, reachable from every other vertex. The strongly connected components of a directed graph form a partition of a s ...
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. It was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Category theory ...
, the order-zero graph is, according to some definitions of "category of graphs," the
initial object In category theory, a branch of mathematics, an initial object of a category is an object in such that for every object in , there exists precisely one morphism . The dual notion is that of a terminal object (also called terminal element) ...
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 Size in general is the Magnitude (mathematics), magnitude or dimensions of a thing. More specifically, ''geometrical size'' (or ''spatial size'') can refer to three geometrical measures: length, area, or volume. Length can be generalized ...
zero, it is equal to its
complement graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of ...
, a
forest A forest is an ecosystem characterized by a dense ecological community, community of trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, ...
, and a
planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
. It may be considered undirected,
directed Direct may refer to: Mathematics * Directed set, in order theory * Direct limit of (pre), sheaves * Direct sum of modules, a construction in abstract algebra which combines several vector spaces Computing * Direct access (disambiguation), a ...
, 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 In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
, 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 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 * Cycle graph * Path graph


Notes


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.


External links

* {{cci, Null graphs Graph families Regular graphs