Граф Кнезера - Kneser graph
Граф Кнезера | |
---|---|
Названный в честь | Мартин Кнезер |
Вершины | |
Края | |
Хроматическое число | |
Характеристики | -обычный дуговой переходный |
Обозначение | K(п, k), КГп,k. |
Таблица графиков и параметров |
В теория графов, то Граф Кнезера K(п, k) (альтернативно КГп,k) - граф, вершины которого соответствуют k-элементные подмножества множества п элементы, причем две вершины смежны тогда и только тогда, когда две соответствующие множества не пересекаются. Графы Кнезера названы в честь Мартин Кнезер, которые впервые исследовали их в 1955 году.
Примеры
Граф Кнезера K(п, 1) это полный график на п вершины.
Граф Кнезера K(п, 2) это дополнять из линейный график полного графика на п вершины.
Граф Кнезера K(2п − 1, п − 1) это нечетный график Оп; особенно О3 = K(5, 2) это Граф Петерсена.
Характеристики
- Граф Кнезера K(п, k) имеет вершины. В каждой вершине ровно соседи.
- Граф Кнезера - это вершинно-транзитивный и переходная дуга. Однако в целом это не сильно регулярный граф, поскольку разные пары несмежных вершин имеют разное количество общих соседей в зависимости от размера пересечения соответствующей пары множеств.
- Поскольку графы Кнезера обычный и реберно-транзитивный, их связность вершин равняется их степень, кроме K(2k, k) который отключен. Точнее, возможность подключения K(п, k) является то же, что и количество соседей на вершину (Уоткинс 1970 ).
- Как Кнезер (1955 ) предположил, что хроматическое число графа Кнезера K(п, k) за точно п − 2k + 2; например, граф Петерсена требует трех цветов в любой правильной раскраске. Ласло Ловас (1978 ) доказал это топологическими методами, породив поле топологическая комбинаторика. Вскоре после этого Имре Барань (1978 ) дал простое доказательство, используя Теорема Борсука – Улама. и лемма о Дэвид Гейл, и Джошуа Е. Грин (2002 ) выиграл Премия Моргана для дальнейшего упрощенного, но все же топологического доказательства. Иржи Матушек (2004 ) нашел чисто комбинаторное доказательство.
- Граф Кнезера K(п, k) содержит Гамильтонов цикл если (Чен 2003 ):
- С
- относится ко всем k это условие выполняется, если
- Граф Кнезера K(п, k) содержит гамильтонов цикл, если существует неотрицательное целое число а такой, что (Мютце, Нумменпало и Вальчак 2018 ). В частности, нечетный график Оп имеет гамильтонов цикл, если п ≥ 4.
- За исключением графа Петерсена, все связные графы Кнезера K(п, k) с п ≤ 27 гамильтоновы (Щиты 2004 ).
- Когда п < 3k, граф Кнезера K(п, k) не содержит треугольников. В более общем плане, когда п < ск он не содержит клики размера c, а такие клики есть, когда п ≥ ск. Более того, хотя граф Кнезера всегда содержит циклы длины четыре, когда п ≥ 2k + 2, для значений п рядом с 2k кратчайший нечетный цикл может иметь непостоянную длину (Денли 1997 ).
- В диаметр связного графа Кнезера K(п, k) является (Валенсия-Пабон и Вера 2005 ):
- В спектр графа Кнезера K(п, k) состоит из k + 1 отличный собственные значения:
- более того происходит с множественность за и имеет кратность 1. См. это бумага для доказательства.
- В Теорема Эрдеша – Ко – Радо. заявляет, что число независимости графа Кнезера K(п, k) за является
Связанные графики
В Граф Джонсона J(п, k) - граф, вершинами которого являются k-элементные подмножества п-элементный набор, две вершины являются смежными, когда они встречаются в (k − 1)-элементный набор. Граф Джонсона J(п, 2) это дополнять графа Кнезера K(п, 2). Графы Джонсона тесно связаны с Схема Джонсона, оба названы в честь Селмер М. Джонсон.
В обобщенный граф Кнезера K(п, k, s) имеет то же множество вершин, что и граф Кнезера K(п, k), но соединяет две вершины всякий раз, когда они соответствуют множествам, которые пересекаются в s или меньше предметов (Денли 1997 ). Таким образом K(п, k, 0) = K(п, k).
В двудольный граф Кнезера ЧАС(п, k) имеет в качестве вершин множества k и п − k предметы, взятые из коллекции п элементы. Две вершины соединяются ребром, если одно множество является подмножеством другого. Как и граф Кнезера, он вершинно транзитивен со степенью Двудольный граф Кнезера может быть сформирован как двусторонняя двойная обложка из K(п, k) в котором делается две копии каждой вершины и каждое ребро заменяется парой ребер, соединяющих соответствующие пары вершин (Симпсон 1991 ). Двудольный граф Кнезера ЧАС(5, 2) это График дезарга и двудольный граф Кнезера ЧАС(п, 1) это граф короны.
Рекомендации
- Барань, Имре (1978), «Краткое доказательство гипотезы Кнезера», Журнал комбинаторной теории, серия А, 25 (3): 325–326, Дои:10.1016/0097-3165(78)90023-7, МИСТЕР 0514626
- Чен, Я-Чен (2003), "Гамильтоновы графы Кнезера без треугольников", Журнал комбинаторной теории, серия B, 89 (1): 1–16, Дои:10.1016 / S0095-8956 (03) 00040-6, МИСТЕР 1999733
- Денли, Тристан (1997), "Нечетный обхват обобщенного графа Кнезера", Европейский журнал комбинаторики, 18 (6): 607–611, Дои:10.1006 / eujc.1996.0122, МИСТЕР 1468332
- Грин, Джошуа Э. (2002), "Новое короткое доказательство гипотезы Кнезера", Американский математический ежемесячный журнал, 109 (10): 918–920, Дои:10.2307/3072460, JSTOR 3072460, МИСТЕР 1941810
- Кнезер, Мартин (1955), "Aufgabe 360", Jahresbericht der Deutschen Mathematiker-Vereinigung, 58 (2): 27
- Ловас, Ласло (1978), «Гипотеза Кнезера, хроматическое число и гомотопия», Журнал комбинаторной теории, Серия А, 25 (3): 319–324, Дои:10.1016/0097-3165(78)90022-5, HDL:10338.dmlcz / 126050, МИСТЕР 0514625
- Матушек, Иржи (2004), "Комбинаторное доказательство гипотезы Кнезера", Комбинаторика, 24 (1): 163–170, Дои:10.1007 / s00493-004-0011-1, HDL:20.500.11850/50671, МИСТЕР 2057690
- Мютце, Торстен; Нумменпало, Джерри; Вальчак, Бартош (2018), «Разреженные графы Кнезера гамильтоновы», STOC'18 - Материалы 50-го ежегодного симпозиума ACM SIGACT по теории вычислений, Нью-Йорк: ACM, стр. 912–919, arXiv:1711.01636, МИСТЕР 3826304
- Шилдс, Ян Бомонт (2004), Эвристика цикла Гамильтона в жестких графах, Кандидат наук. Тезис, Университет штата Северная Каролина, заархивировано из оригинал на 2006-09-17, получено 2006-10-01
- Симпсон, Дж. Э. (1991), "Гамильтоновы двудольные графы", Труды Двадцать второй Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Лос-Анджелес, 1991), Congressus Numerantium, 85, стр. 97–110, МИСТЕР 1152123
- Валенсия-Пабон, Марио; Вера, Хуан-Карлос (2005), "О диаметре графов Кнезера", Дискретная математика, 305 (1–3): 383–385, Дои:10.1016 / j.disc.2005.10.001, МИСТЕР 2186709
- Уоткинс, Марк Э. (1970), "Связность транзитивных графов", Журнал комбинаторной теории, 8: 23–29, Дои:10.1016 / S0021-9800 (70) 80005-9, МИСТЕР 0266804