Jump to content

График колеса

График колеса
Несколько примеров колесных графов
Вершины п ≥ 4
Края 2( п - 1)
Диаметр 2, если n > 4
1, если n = 4
Обхват 3
Хроматическое число 4, если n четное
3, если n нечетное
Спектр
Характеристики гамильтониан
Самодвойственный
Планарный
Обозначения W н
Таблица графиков и параметров

В математической дисциплине теории графов граф -колесо — это граф, образованный соединением одной универсальной вершины со всеми вершинами цикла . Колесо графа с n можно определить как 1- скелет пирамиды ( n – 1 )-угольной вершинами также . Некоторые авторы [1] напишите W n для обозначения графа-колеса с n вершинами ( n ≥ 4 ); другие авторы [2] вместо этого используйте W n для обозначения графа-колеса с n + 1 вершиной ( n ≥ 3 ), который формируется путем соединения одной вершины со всеми вершинами цикла длины n . В оставшейся части статьи используются прежние обозначения.

Конструктор-конструктор

[ редактировать ]

Учитывая набор вершин {1, 2, 3, …, v}, набор ребер колесного графа может быть представлен в обозначениях построителя множеств как {{1, 2}, {1, 3}, …, {1 , v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}}. [3]

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

[ редактировать ]

Колесные графы являются плоскими графами и имеют уникальное планарное вложение. Точнее, каждый граф-колесо является графом Халина . Они самодуальны: планарный двойственный граф любого колесного графа является изоморфным графом . Каждый максимальный планарный граф, кроме K 4 = W 4 , содержит в качестве подграфа либо W 5 , либо W 6 .

В графе колеса всегда существует гамильтонов цикл и существуют циклов в W n (последовательность A002061 в OEIS ).

7 циклов колесного графа W 4 .

Для нечетных значений n . W n представляет собой идеальный граф с хроматическим числом 3: вершинам цикла можно присвоить два цвета, а центральной вершине — третий цвет Для четного W n n имеет хроматическое число 4 и (когда n ≥ 6) не является идеальным. W 7 — единственный граф-колесо, представляющий собой граф единичных расстояний на евклидовой плоскости. [4]

Хроматический многочлен колесного графа W n равен:

В теории матроидов два особенно важных специальных класса матроидов — это матроиды колес и матроиды вихрей , оба производные от колесных графов. Матроид k -колеса — это графический матроид колеса W k+1 , тогда как матроид k -вихря получается из k -колеса путем рассмотрения внешнего цикла колеса, а также всех его остовных деревьев как независимый.

Колесо W6 W6 послужило контрпримером к гипотезе Пола Эрдеша о теории Рамсея : он предположил, что полный граф имеет наименьшее число Рамсея среди всех графов с одинаковым хроматическим числом, но Фаудри и Маккей (1993) показали, что число имеет Рамсея. номер 17, тогда как полный граф с тем же хроматическим числом K 4 имеет число Рамсея 18. [5] То есть для каждого 17-вершинного графа G , либо G либо его дополнение содержат W 6 в качестве подграфа, в то время как ни 17-вершинный граф Пэли , ни его дополнение не содержат копию K 4 .

  1. ^ Вайсштейн, Эрик В. «Колесо графика» . Математический мир .
  2. ^ Розен, Кеннет Х. (2011). Дискретная математика и ее приложения (7-е изд.). МакГроу-Хилл. п. 655 . ISBN  978-0073383095 .
  3. ^ Трюдо, Ричард Дж. (1993). Введение в теорию графов (Исправленное, расширенное издание. Под ред.). Нью-Йорк: Паб Dover. п. 56. ИСБН  978-0-486-67870-2 . Проверено 8 августа 2012 г.
  4. ^ Бакли, Фред; Харари, Фрэнк (1988), «О евклидовом измерении колеса», Graphs and Combinatorics , 4 (1): 23–30, doi : 10.1007/BF01864150 , S2CID   44596093 .
  5. ^ Фаудри, Ральф Дж .; Маккей, Брендан Д. (1993), «Гипотеза Эрдёша и число Рамсея r ( W 6 , J. Combinatorial Math. и комбинаторные вычисления. , 13 : 23–31 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: e45fef4cead85fc30ada5a788890b139__1711400820
URL1:https://arc.ask3.ru/arc/aa/e4/39/e45fef4cead85fc30ada5a788890b139.html
Заголовок, (Title) документа по адресу, URL1:
Wheel graph - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)