WikiDer > Граф короны

Crown graph
Граф короны
Корона graphs.svg
Графы короны с шестью, восемью и десятью вершинами
Вершины2 п
Краяп (п - 1)
Радиус
Диаметр
Обхват
Хроматическое число
ХарактеристикиДистанционно-транзитивный
Обозначение
Таблица графиков и параметров

В теория графов, раздел математики, граф короны на 2п вершины - это неориентированный граф с двумя наборами вершин {ты1, ты2, ..., тып} и {v1, v2, ..., vп} и с опорой от тыя к vj в любое время я ≠ j.

График короны можно рассматривать как полный двудольный граф от которого края идеальное соответствие были удалены, поскольку двусторонняя двойная обложка из полный график, как тензорное произведение Kп × K2, как дополнение к декартову прямому произведению Kп и K2, или как двудольный граф Кнезера ЧАСп,1 представляющий 1-элемент и (п - 1) -элементные подмножества п-item set, с ребром между двумя подмножествами, если одно содержится в другом.

Примеры

6-вершинный граф короны образует цикл, а граф короны с 8 вершинами - изоморфный к графику кубШлефли двойная шестерка, конфигурация из 12 линий и 30 точек в трехмерном пространстве, двенадцать линий пересекаются друг с другом в образце графа короны с 12 вершинами.

Характеристики

Бикликовое покрытие десятивершинного графа короны

Количество ребер в графе короны - это проническое число п(п - 1). Его ахроматическое число является п: можно найти полная окраска выбирая каждую пару {тыя, vя} как один из цветовых классов.[1] Графики короны симметричный и дистанционно-транзитивный. Архидьякон и др. (2004) описывают разбиения ребер графа короны на циклы равной длины.

2п-вершинный коронный граф может быть вложен в четырехмерное евклидово пространство таким образом, что все его ребра имеют единичную длину. Однако это вложение может также разместить некоторые несмежные вершины на единичном расстоянии друг от друга. Вложение, в котором края находятся на единичном расстоянии, а не ребра не на единичном расстоянии, требует как минимум п - 2 измерения. Этот пример показывает, что для представления графика могут потребоваться очень разные измерения. графики единичных расстояний и как строгий граф единичных расстояний.[2]

Минимальное количество полные двудольные подграфы необходимо, чтобы покрыть края графа короны (его двудольное измерение, или размер минимального бикликового покрытия) составляет

обратная функция центральный биномиальный коэффициент.[3]

В дополнительный граф из 2п-вершинный граф - это Декартово произведение из полные графики K2 Kп, или эквивалентно 2 ×п график ладьи.

Приложения

В этикет, традиционное правило размещения гостей за обеденным столом состоит в том, что мужчины и женщины должны чередоваться позы и ни одна супружеская пара не должна сидеть рядом друг с другом.[4] Договоренности, удовлетворяющие этому правилу, для партии, состоящей из п супружеские пары, можно охарактеризовать как Гамильтоновы циклы графа короны. Например, расположение вершин, показанное на рисунке, можно интерпретировать как схемы рассадки этого типа, в которых каждый муж и жена сидят как можно дальше друг от друга. Проблема подсчета количества возможных расстановок сидений, или почти то же самое[5] количество гамильтоновых циклов в графе короны, известно в комбинаторике как проблема с мужем; для коронных графов с 6, 8, 10, ... вершинами количество (ориентированных) гамильтоновых циклов равно

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... (последовательность A094047 в OEIS)

Графики короны могут использоваться, чтобы показать, что жадная окраска алгоритмы плохо себя ведут в худшем случае: если вершины коронного графа представлены алгоритму в порядке ты0, v0, ты1, v1и т. д., то жадная раскраска использует п цветов, тогда как оптимальное количество цветов - два. Эту конструкцию приписывают Джонсон (1974); графы короны иногда называют Графики Джонсона с обозначениями Jп.[6] Фюрер (1995) использует графы короны как часть конструкции, показывающей трудность аппроксимации задач раскраски.

Матушек (1996) использует расстояния в графиках короны в качестве примера метрическое пространство это сложно встроить в нормированное векторное пространство.

В качестве Миклавич и Поточник (2003) показать, графы короны - это один из небольшого числа различных типов графов, которые могут появляться как дистанционно-регулярный циркулянтные графики.

Agarwal et al. (1994) описывать многоугольники, у которых есть графы короны как их графики видимости; они используют этот пример, чтобы показать, что представление графов видимости в виде объединения полных двудольных графов не всегда может быть эффективным с точки зрения пространства.

Граф короны с 2п вершины с его ребрами, ориентированными от одной стороны двудольных к другой, образуют стандартный пример частично заказанный набор с размер заказа п.

Примечания

  1. ^ Чаудхари и Вишванатан (2001).
  2. ^ Эрдеш и Симоновиц (1980).
  3. ^ де Кан, Грегори и Пуллман (1981).
  4. ^ Фокс, Сью (2011), Этикет для чайников (2-е изд.), John Wiley & Sons, стр. 244, ISBN 9781118051375
  5. ^ В задаче о найме начальное положение цикла считается значимым, поэтому количество гамильтоновых циклов и решение задачи о найме различаются в 2 раза.п.
  6. ^ Кубале (2004).

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

внешняя ссылка