В математической области теории графов термин « нулевой граф » может относиться либо к графу нулевого порядка , либо , альтернативно, к любому графу без ребер (последний иногда называют «пустым графом»).
Граф нулевого порядка K 0 — это единственный граф, не имеющий вершин (следовательно, его порядок равен нулю). Отсюда следует, что K0 также не имеет ребер . Таким образом, нулевой граф является регулярным графом нулевой степени. Некоторые авторы исключают K 0 из рассмотрения как графа (то ли по определению, то ли просто для удобства). Полезность включения K 0 в качестве допустимого графа зависит от контекста. С положительной стороны, K 0 естественным образом следует из обычных теоретико-множественных определений графа (это упорядоченная пара ( V , E ) , для которой множества вершин и ребер, V и E , оба пусты ), в доказательствах это служит естественным базовым случаем для математической индукции , и аналогично, в рекурсивно определенных структурах данных K 0 полезен для определения базового случая для рекурсии (путем рассмотрения нулевого дерева как дочернего элемента отсутствующих ребер в любом непустом двоичном дереве , каждое ненулевое двоичное дерево имеет ровно два дочерних элемента). С другой стороны, включение K 0 в качестве графа требует, чтобы многие четко определенные формулы для свойств графа включали исключения для него (например, либо «подсчет всех сильно связных компонентов графа» становится «подсчетом всех ненулевых сильно связных компонентов» графа», или определение связных графов должно быть изменено, чтобы исключить K 0 ). Чтобы избежать необходимости в таких исключениях, в литературе часто предполагается, что термин « граф» подразумевает «граф по крайней мере с одной вершиной», если контекст не предполагает иного. [1] [2]
В теории категорий граф нулевого порядка, согласно некоторым определениям «категории графов», является исходным объектом в категории.
K 0 действительно выполняет ( пусто ) большинство тех же основных свойств графа, что и K 1 (граф с одной вершиной и без ребер). В качестве примера: K 0 имеет нулевой размер , он равен графу дополнений K 0 , лесу и плоскому графу . Его можно считать ненаправленным , направленным или даже тем и другим; если рассматривать его как направленный, то это ориентированный ациклический граф . И это одновременно полный граф и граф без ребер. Однако определения каждого из этих свойств графа будут различаться в зависимости от того, допускает ли контекст K 0 .
Для каждого натурального числа n граф без ребер (или пустой граф) K n порядка n — это граф с n вершинами и нулевыми ребрами. Граф без ребер иногда называют нулевым графом в контекстах, где граф нулевого порядка не допускается. [1] [2]
Это 0- регулярный граф. Обозначение Kn возникает из-за того, что n - вершинный граф без ребер является дополнением полного графа Kn .
СМИ, связанные с нулевыми графами, на Викискладе?