Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Graphe nul
Résumé
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").
The order-zero graph, K_0, is the unique graph having no vertices (hence its order is zero). It follows that K_0 also has no edges. Thus the null graph is a regular graph of degree zero. Some authors exclude K_0 from consideration as a graph (either by definition, or more simply as a matter of convenience). Whether including K_0 as a valid graph is useful depends on context. On the positive side, K_0 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 K_0 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 K_0 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_0). 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 , the order-zero graph is, according to some definitions of "category of graphs," the initial object in the category.
K_0 does fulfill (vacuously) most of the same basic graph properties as does K_1 (the graph with one vertex and no edges). As some examples, K_0 is of size zero, it is equal to its complement graph _0, 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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.