Нулевой график - Null graph

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

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

График нулевого порядка (нулевой график)
Вершины	0
Края	0
Обхват	${\ displaystyle \ infty}$
Автоморфизмы	1
Хроматическое число	0
Хроматический индекс	0
Род	0
Свойства	Интегральная симметричная ширина дерева -1
Обозначение	${\ displaystyle K_ {0}}$
Таблица графиков и параметров

Порядок нуля граф , являются уникальными графами не имеющие вершин (следовательно , его порядок равен нуль). Отсюда следует, что также не имеет ребер . Таким образом, нулевой граф - это обычный граф нулевой степени. Некоторые авторы исключают из рассмотрения граф (либо по определению, либо проще для удобства). Полезно ли включение в качестве действительного графа, зависит от контекста. С положительной стороны, естественно следует из обычных теоретико-множественных определений графа (это упорядоченная пара ( V , E ), для которой множества вершин и ребер, V и E , оба пустые ), в доказательствах он служит как естественный базовый случай для математической индукции , и аналогично, в рекурсивно определенных структурах данных полезен для определения базового случая для рекурсии (путем обработки нулевого дерева как дочернего элемента отсутствующих ребер в любом ненулевом двоичном дереве , каждый ненулевой двоичный у дерева ровно двое детей). С другой стороны, включение в качестве графа требует, чтобы многие четко определенные формулы для свойств графа включали исключения для него (например, «подсчет всех сильно связанных компонентов графа» становится «подсчетом всех ненулевых сильно связанных компонентов графа» graph », или необходимо изменить определение связанных графов, чтобы не включать K ₀ ). Чтобы избежать необходимости в таких исключениях, в литературе часто предполагается, что термин граф подразумевает «граф по крайней мере с одной вершиной», если контекст не предполагает иное. ${\ displaystyle K_ {0}}$${\ displaystyle K_ {0}}$${\ displaystyle K_ {0}}$${\ displaystyle K_ {0}}$${\ displaystyle K_ {0}}$ ${\ displaystyle K_ {0}}$${\ displaystyle K_ {0}}$

В теории категорий граф нулевого порядка является, согласно некоторым определениям «категории графов», начальным объектом в категории.

${\ displaystyle K_ {0}}$действительно выполняет ( бесполезно ) большинство тех же основных свойств графа, что и (граф с одной вершиной и без ребер). В некоторых примерах, имеют размера нуля, равно ее граф комплемента , в лес , и планарный граф . Его можно считать ненаправленным , направленным или даже тем и другим одновременно; если рассматривать его как направленный, это ориентированный ациклический граф . И это одновременно и полный граф, и граф без ребер. Однако определения каждого из этих свойств графа будут различаться в зависимости от того, позволяет ли это контекст . ${\ displaystyle K_ {1}}$${\ displaystyle K_ {0}}$ ${\ displaystyle {\ overline {K_ {0}}}}$${\ displaystyle K_ {0}}$

Безреберный граф

Безреберный граф (пустой граф, нулевой граф)
Вершины	п
Края	0
Радиус	0
Диаметр	0
Обхват	${\ displaystyle \ infty}$
Автоморфизмы	п!
Хроматическое число	1
Хроматический индекс	0
Род	0
Свойства	Интегрально- симметричный
Обозначение	${\ displaystyle {\ overline {K}} _ {n}}$
Таблица графиков и параметров

Для каждого натурального числа п , в безреберном графе (или пустой граф) порядка п называется граф с п вершин и нулевых ребрами. Безреберный граф иногда называют нулевым графом в контекстах, где граф нулевого порядка не разрешен. ${\ displaystyle {\ overline {K}} _ {n}}$

Это 0- регулярный граф. Обозначение связано с тем, что граф без ребер с n вершинами является дополнением к полному графу . ${\ displaystyle {\ overline {K}} _ {n}}$ ${\ displaystyle K_ {n}}$

Смотрите также

• Глоссарий теории графов
• График цикла
• График пути

Ноты

Ссылки

• Харари Ф. и Рид Р. (1973), "Является ли нулевой граф бессмысленным понятием?", Графы и комбинаторика (Конференция, Университет Джорджа Вашингтона), Springer-Verlag, Нью-Йорк, Нью-Йорк.