Звезда (теория графов)
| Звезда | |
|---|---|
 Звезда S7 . (Некоторые авторы индексируют это как . S8 ) | |
| Вершины | к + 1 |
| Края | к |
| Диаметр | 2 |
| Обхват | ∞ |
| Хроматическое число | 2 |
| Хроматический индекс | к |
| Характеристики | Край-транзитивный Дерево Расстояние единицы двусторонний |
| Обозначения | С к |
| Таблица графиков и параметров | |
В теории графов звездой k S k называется полный двудольный граф K 1, k : дерево 1 с одним внутренним узлом и k листьев (но без внутренних узлов и k + 1 листьев, когда ≤ ) . В качестве альтернативы некоторые авторы определяют S k как дерево порядка k с максимальным диаметром 2; в этом случае звезда k > 2 имеет k - 1 листьев.
Звезда с тремя краями называется клешней .
Звезда S k имеет изящные края , когда k четное, а не когда k нечетное. Это реберно-транзитивный спичечный граф , имеющий диаметр 2 (когда l > 1 ), обхват ∞ (в нем нет циклов), хроматический индекс k и хроматическое число 2 (когда k > 0 ). Кроме того, у звезды имеется большая группа автоморфизмов, а именно симметрическая группа на k буквах.
Звезды также можно описать как единственные связные графы, в которых не более одной вершины имеет степень больше единицы.
Связь с другими семействами графов
[ редактировать ]Когти примечательны в определении графов без клешней , графов, которые не имеют клешней в качестве индуцированного подграфа . [1] [2] Они также являются одним из исключительных случаев теоремы об изоморфизме графов Уитни : в общем, графы с изоморфными линейными графами сами по себе изоморфны, за исключением клешни и треугольника К 3 . [3]
Звезда – это особый вид дерева . Как и любое дерево, звезды могут быть закодированы последовательностью Прюфера ; последовательность Прюфера для звезды K 1, k состоит из k − 1 копий центральной вершины. [4]
Несколько инвариантов графа определены в терминах звезд. Звездная древесность — это минимальное количество лесов, на которые можно разбить граф так, чтобы каждое дерево в каждом лесу было звездой. [5] а звездное хроматическое число графа — это минимальное количество цветов, необходимое для окраски его вершин таким образом, чтобы каждые два класса цвета вместе образовывали подграф, в котором все компоненты связности являются звездами. [6] Графы с шириной ветвления 1 — это именно те графы, в которых каждый компонент связности является звездой. [7]
Другие приложения
[ редактировать ]Набор расстояний между вершинами клешни представляет собой пример конечного метрического пространства , которое нельзя изометрически вложить в евклидово пространство любой размерности. [8]
Звездная сеть , компьютерная сеть, смоделированная по образцу звездного графа, играет важную роль в распределенных вычислениях .
Геометрическая реализация звездного графа, образованная путем отождествления ребер с интервалами некоторой фиксированной длины, используется как локальная модель кривых в тропической геометрии . Тропическая кривая определяется как метрическое пространство, локально изоморфное звездообразному метрическому графу.
См. также
[ редактировать ]- Звезда (симплициальный комплекс) — обобщение понятия звезды с графа на произвольный симплициальный комплекс.
Ссылки
[ редактировать ]
- ^ Фаудри, Ральф ; Фландрин, Эвелин; Рыячек, Зденек (1997), «Графы без клешней — обзор», Discrete Mathematics , 164 (1–3): 87–147, doi : 10.1016/S0012-365X(96)00045-3 , MR 1432221 .
- ^ Чудновская Мария ; Сеймур, Пол (2005), «Структура графов без когтей», Обзоры по комбинаторике 2005 г. (PDF) , London Math. Соц. Лекционная конспект. Сер., т. 1, с. 327, Кембридж: Кембриджский университет. Пресс, стр. 153–171, МР 2187738 .
- ^ Уитни, Хасслер (январь 1932 г.), «Конгруэнтные графы и связность графов», American Journal of Mathematics , 54 (1): 150–168, doi : 10.2307/2371086 , hdl : 10338.dmlcz/101067 , JSTOR 2371086 .
- ^ Готлиб, Дж.; Юльстрем, бакалавр; Ротлауф, Ф.; Райдл, Г. Р. (2001). «Числа Прюфера: плохое представление связующих деревьев для эволюционного поиска» (PDF) . GECCO-2001: Материалы конференции по генетическим и эволюционным вычислениям . Морган Кауфманн. стр. 343–350. ISBN 1558607749 .
- ^ Хакими, СЛ; Митчем, Дж.; Шмейхель, Э.Э. (1996), "Звездная древовидность графов", Discrete Math. , 149 : 93–98, doi : 10.1016/0012-365X(94)00313-8
- ^ Фертен, Гийом; Распо, Андре; Рид, Брюс (2004), «Звездная раскраска графов» , Journal of Graph Theory , 47 (3): 163–182, doi : 10.1002/jgt.20029 .
- ^ Робертсон, Нил ; Сеймур, Пол Д. (1991), «Минорные графы. X. Препятствия к разложению дерева», Journal of Combinatorial Theory , 52 (2): 153–190, doi : 10.1016/0095-8956(91)90061-N .
- ^ Линиал, Натан (2002), «Конечные метрические пространства – комбинаторика, геометрия и алгоритмы», Proc. Международный конгресс математиков, Пекин , вып. 3, стр. 573–586, arXiv : math/0304466 , Bibcode : 2003math......4466L