Нулевой граф и пустой граф в теории графов

Введение

Граф нулевого порядка или любой граф без рёбер. В математической области теории графов термин "нулевой граф" может означать либо граф нулевого порядка, либо, альтернативно, любой граф без рёбер (последний иногда называют "пустым графом").

График нулевого порядка

Граф нулевого порядка, , – это единственный граф, не имеющий вершин (следовательно, его порядок равен нулю). Из этого следует, что у него также нет рёбер. Таким образом, пустой граф является регулярным графом степени ноль. Некоторые авторы исключают из рассмотрения как граф (либо по определению, либо просто из соображений удобства). Полезно ли включать в рассмотрение как допустимый граф, зависит от контекста. С положительной стороны, он естественно вытекает из обычных теоретико-множественных определений графа (это упорядоченная пара (V, E), для которой множества вершин V и рёбер E оба пусты), в доказательствах он служит естественным базовым случаем для математической индукции, и аналогично, в рекурсивно определенных структурах данных он полезен для определения базового случая рекурсии (рассматривая пустой граф как дочерний элемент отсутствующих рёбер в любом непустом бинарном дереве, каждое непустое бинарное дерево имеет ровно два дочерних элемента). С отрицательной стороны, включение в качестве графа требует, чтобы многие чётко определённые формулы для свойств графа включали исключения для него (например, либо «подсчёт всех сильно связных компонент графа» становится «подсчёт всех непустых сильно связных компонент графа», либо определение связных графов должно быть изменено, чтобы не включать ). Чтобы избежать необходимости таких исключений, в литературе часто подразумевается, что термин «граф» подразумевает «граф с по крайней мере одной вершиной», если контекст не предполагает иного. В теории категорий граф нулевого порядка, согласно некоторым определениям «категории графов», является начальным объектом в этой категории. выполняет (тривиально) большинство тех же основных свойств графа, что и (граф с одной вершиной и без рёбер). В качестве примеров, он имеет размер ноль, равен своему дополнительному графу, является лесом и планарным графом. Его можно считать неориентированным, ориентированным или даже обоими; при рассмотрении как ориентированного, это ориентированный ациклический граф. И он является одновременно полным графом и безрёберным графом. Однако определения для каждого из этих свойств графа будут варьироваться в зависимости от того, допускает ли контекст .

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 (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 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 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 ). 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, the order zero graph is, according to some definitions of "category of graphs," the initial object 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 zero, it is equal to its complement graph , 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 .

График без краев

Для каждого натурального числа n, безреберный граф (или пустой граф) порядка n — это граф с n вершинами и нулем ребер. Безреберный граф иногда называют нулевым графом в тех случаях, когда граф нулевого порядка не допускается. Это 0-регулярный граф. Обозначение происходит из того факта, что безреберный граф с n вершинами является дополнением к полному графу с n вершинами.