Null graph

In the mathematical field of graph theory, the 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

Order zero graph (null graph)
Vertices	0
Edges	0
Radius	0
Diameter	0
Girth	$\infty$
Automorphisms	1
Chromatic number	0
Chromatic index	0
Genus	0
Spectral Gap	undefined
Properties	Integral Symmetric
Notation	K0
v · order zero graph K0 is the unique graph of order zero (having zero vertices). As a consequence, it also has zero edges. In some contexts, K0 is excluded from being considered a graph (either by definition, or more simply as a matter of convenience). The order zero graph is the initial object in the category of graphs, according to some definitions of a category of graphs. Its inclusion within the definition of graph theory is more useful in some contexts than others. On the positive side, K0 follows naturally from the usual set-theoretic definitions of a graph (it is the ordered pair of empty sets), and 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, most well-defined formulas for graph properties must include exceptions for K0 if it is included as a graph ("counting all strongly-connected components of a graph" would become "counting all non-null strongly-connected components of a graph"). Due to the undesirable aspects, it is usually assumed in literature that the term "graph" implies "graph with at least one vertex" unless context suggests otherwise.[1][2] When acknowledged, K0 fulfills (vacuously) most of the same basic graph properties as K1 (the graph with one vertex and no edges): it has a size of zero, it is equal to its complement graph ($\bar K_0$), it is a connected component (namely, $\forall x \isin V : \forall y \isin V : \exists path(x,y)$), an acyclic graph, a tree, an arboricity, a forest, it may be an undirected graph or a directed graph (or even both), and it is both a complete graph and an empty graph (just to name a few). However, definitions for each of these graph properties will vary depending on whether context allows for K0. For example, the term "connected component" almost always excludes K0, whereas trees as data structures often include the "null tree" case. Edgeless graph Edgeless graph (empty graph, null graph) Vertices n Edges 0 Radius 0 Diameter 0 Girth $\infty$ Automorphisms n! Chromatic number 1 Chromatic index 0 Genus 0 Spectral Gap undefined Properties Integral Symmetric Notation $\bar K_n$ v · natural number n, the edgeless graph (or empty graph) $\bar K_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.[3][4] The n-vertex edgeless graph is the complement graph for the complete graph Kn, and therefore it is commonly denoted as $\bar K_n$. See also Glossary of graph theory Cycle graph Path graph Notes ^ Weisstein, Eric W., "Empty Graph" from MathWorld. ^ Weisstein, Eric W., "Null Graph" from MathWorld. ^ Weisstein, Eric W., "Empty Graph" from MathWorld. ^ Weisstein, Eric W., "Null Graph" from MathWorld. 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. Wikimedia Foundation. 2010. Игры ⚽ Нужно сделать НИР? Montalivet Islands Bistriţa (disambiguation) Look at other dictionaries: Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia Graph (data structure) — In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes (also called vertices) and a set of edges that establish relationships (connections) between the nodes. The graph… …   Wikipedia Complete bipartite graph — A complete bipartite graph with m = 5 and n = 3 Vertices n + m Edges mn …   Wikipedia Cycle graph — This article is about connected, 2 regular graphs. For other uses, see Cycle graph (disambiguation). Cycle graph A cycle graph of length 6 Vertices n …   Wikipedia Grötzsch graph — infobox graph name = Grötzsch graph namesake = Herbert Grötzsch vertices = 11 edges = 20 chromatic number = 4 chromatic index = girth = 4 properties = The Grötzsch graph is a triangle free graph with 11 vertices, 20 edges, and chromatic number 4 …   Wikipedia Path graph — infobox graph name = Path graph image caption = A path graph vertices = n edges = n 1 automorphisms = 2 diameter = n 1 radius = ⌊n/2⌋ chromatic number = 2 chromatic index = 2 properties = Unit distance Bipartite graphIn the mathematical field of… …   Wikipedia Bogen (Graph) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia K-regulärer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”