В математической области теории графов , термин « нуль - граф » может относиться либо к порядке - нулевой граф , или в качестве альтернативы, к любому безреберных графа (последний иногда называют «пустой граф»).
График нулевого порядка
График нулевого порядка (нулевой график) | |
---|---|
Вершины | 0 |
Края | 0 |
Обхват | |
Автоморфизмы | 1 |
Хроматическое число | 0 |
Хроматический индекс | 0 |
Род | 0 |
Характеристики | Интегральная симметричная ширина дерева -1 |
Обозначение | |
Таблица графиков и параметров |
Порядок нуля график ,, - единственный граф, не имеющий вершин (следовательно, его порядок равен нулю). Следует, чтотакже не имеет краев . Таким образом, нулевой граф - это обычный граф нулевой степени. Некоторые авторы исключаютиз рассмотрения как графа (либо по определению, либо, проще говоря, для удобства). Включая липолезность действительного графа зависит от контекста. С положительной стороны,естественно следует из обычных теоретико-множественных определений графа (это упорядоченная пара ( V , E ), для которой множества вершин и ребер, V и E , оба пустые ), в доказательствах он служит естественным базовым случаем для математическая индукция и аналогично в рекурсивно определенных структурах данных полезен для определения базового случая для рекурсии (если рассматривать пустое дерево как дочерний элемент для отсутствующих ребер в любом двоичном дереве , отличном от нуля, каждое двоичное дерево , отличное от нуля, имеет ровно два дочерних элемента ). С отрицательной стороны, в том числепоскольку граф требует, чтобы многие четко определенные формулы для свойств графа включали для него исключения (например, либо «подсчет всех сильно связанных компонентов графа» становится «подсчетом всех ненулевых сильносвязных компонентов графа», либо определение связных графов необходимо изменить, чтобы не включать K 0 ). Чтобы избежать необходимости в таких исключениях, в литературе часто предполагается, что термин граф подразумевает «граф по крайней мере с одной вершиной», если контекст не предполагает иное. [1] [2]
В теории категорий граф нулевого порядка является, согласно некоторым определениям «категории графов», начальным объектом в категории.
выполняет ( бессмысленно ) большинство тех же основных свойств графа, что и(граф с одной вершиной и без ребер). В качестве некоторых примеровимеет размер ноль, он равен своему дополнительному графу , лес и планарный граф . Его можно считать ненаправленным , направленным или даже тем и другим одновременно; если рассматривать его как направленный, это ориентированный ациклический граф . И это одновременно и полный граф, и граф без ребер. Однако определения для каждого из этих свойств графа будут различаться в зависимости от того, позволяет ли контекст.
Безреберный граф
Безреберный граф (пустой граф, нулевой граф) | |
---|---|
Вершины | п |
Края | 0 |
Радиус | 0 |
Диаметр | 0 |
Обхват | |
Автоморфизмы | п! |
Хроматическое число | 1 |
Хроматический индекс | 0 |
Род | 0 |
Характеристики | Интегрально- симметричный |
Обозначение | |
Таблица графиков и параметров |
Для каждого натурального числа п , в безреберном графе (или пустой граф)порядка n - это граф с n вершинами и нулевыми ребрами. Безреберный граф иногда называют нулевым графом в контекстах, где граф нулевого порядка не разрешен. [1] [2]
Это 0- регулярный граф. Обозначениевозникает из того, что граф без ребер с n вершинами является дополнением к полному графу .
Смотрите также
- Глоссарий теории графов
- График цикла
- График пути
Заметки
- ^ a b Вайсштейн, Эрик В. «Пустой график» . MathWorld .
- ^ а б Вайсштейн, Эрик В. «Нулевой граф» . MathWorld .
Рекомендации
- Харари Ф. и Рид Р. (1973), «Является ли нулевой граф бессмысленным понятием?», Графы и комбинаторика (Конференция, Университет Джорджа Вашингтона), Springer-Verlag, Нью-Йорк, Нью-Йорк.