Нулевой график
В математической области теории графов термин « нулевой граф » может относиться либо к порядка нулевого . графу , либо, альтернативно, к любому графу без ребер (последний иногда называют «пустым графом»)
График нулевого порядка
[ редактировать ]| График нулевого порядка (нулевой график) | |
|---|---|
| Вершины | 0 |
| Края | 0 |
| Обхват | ∞ |
| Автоморфизмы | 1 |
| Хроматическое число | 0 |
| Хроматический индекс | 0 |
| Род | 0 |
| Характеристики | Интеграл Симметричный Ширина дерева -1 |
| Обозначения | до 0 |
| Таблица графиков и параметров | |
Граф нулевого порядка K 0 — это единственный граф, не имеющий вершин (следовательно, его порядок равен нулю). Отсюда следует, что также K0 не имеет ребер . Таким образом, нулевой граф является регулярным графом нулевой степени. Некоторые авторы исключают 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 .
Безграничный граф
[ редактировать ]| Граф без ребер (пустой граф, нулевой граф) | |
|---|---|
| Вершины | н |
| Края | 0 |
| Радиус | 0 |
| Диаметр | 0 |
| Обхват | ∞ |
| Автоморфизмы | н ! |
| Хроматическое число | 1 |
| Хроматический индекс | 0 |
| Род | 0 |
| Характеристики | Интеграл Симметричный |
| Обозначения | К н |
| Таблица графиков и параметров | |
Для каждого натурального числа n граф без ребер (или пустой граф) K n порядка n — это граф с n вершинами и нулевыми ребрами. Граф без ребер иногда называют нулевым графом в контекстах, где граф нулевого порядка не допускается. [1] [2]
Это 0- регулярный граф. Обозначение Kn n возникает из-за того, что - граф без ребер является дополнением полного графа Kn вершинный .
См. также
[ редактировать ]Примечания
[ редактировать ]Ссылки
[ редактировать ]- Харари Ф. и Рид Р. (1973), «Является ли нулевой граф бессмысленной концепцией?», Графы и комбинаторика (конференция, Университет Джорджа Вашингтона), Springer-Verlag, Нью-Йорк, штат Нью-Йорк.
Внешние ссылки
[ редактировать ]
СМИ, связанные с нулевыми графами, на Викискладе?
