В математической области теории графов термин « нулевой граф » может относиться либо к графу нулевого порядка , либо, альтернативно, к любому графу без рёбер (последний иногда называют «пустым графом») .
Граф нулевого порядка , K 0 , является уникальным графом, не имеющим вершин (следовательно, его порядок равен нулю). Из этого следует, что K 0 также не имеет ребер . Таким образом, нулевой граф является регулярным графом нулевой степени. Некоторые авторы исключают 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- регулярный граф. Обозначение K n возникает из того факта, что n -вершинный граф без ребер является дополнением полного графа K n .
Медиа, связанные с Null graphs на Wikimedia Commons