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

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

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

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

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

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

${\ 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}}$
Таблица графиков и параметров

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

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

Викискладе есть медиафайлы, связанные с нулевыми графами .

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