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

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

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

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

В график нулевого порядка, ${\displaystyle K_{0}}$, - единственный граф, не имеющий вершины (следовательно, его порядок равен нулю). Следует, что ${\displaystyle K_{0}}$ также не имеет края. Таким образом, нулевой граф является регулярный график нулевой степени. Некоторые авторы исключают ${\displaystyle K_{0}}$ из рассмотрения как графа (либо по определению, либо, проще говоря, для удобства). Включая ли ${\displaystyle K_{0}}$ насколько полезен действительный график, зависит от контекста. С положительной стороны, ${\displaystyle K_{0}}$ естественно следует из обычного теоретико-множественный определения графа (это упорядоченная пара (V, E), для которого множества вершина и ребро, V и 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}}$
Таблица графиков и параметров

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

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

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

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

Примечания

1. Вайсштейн, Эрик В. «Пустой график». MathWorld.
2. Вайсштейн, Эрик В. «Нулевой график». MathWorld.

Рекомендации

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