График Джонсона - Википедия - Johnson graph

Граф Джонсона
Граф Джонсона J(5,2)
Названный в честь	Селмер М. Джонсон
Вершины	${ displaystyle { binom {n} {k}}}$
Края	${ Displaystyle { гидроразрыва {1} {2}} к (п-к) { binom {п} {к}}}$
Диаметр	${ Displaystyle мин (к, п-к)}$
Характеристики	${ Displaystyle к (п-к)}$-обычный Вершинно-транзитивный Дистанционно-транзитивный Гамильтон-связанный
Обозначение	${ Displaystyle J (п, к)}$
Таблица графиков и параметров

Графики Джонсона особый класс неориентированные графы определяется из систем множеств. Вершины графа Джонсона ${ Displaystyle J (п, к)}$ являются ${ displaystyle k}$-элементные подмножества ${ displaystyle n}$-комплект элементов; две вершины смежны, если пересечение двух вершин (подмножеств) содержит ${ Displaystyle (к-1)}$-элементы.^[1] И графы Джонсона, и тесно связанные с ними Схема Джонсона названы в честь Селмер М. Джонсон.

Особые случаи

• ${ Displaystyle J (п, 1)}$ это полный график K_п.
• ${ Displaystyle J (4,2)}$ это октаэдрический граф.
• ${ Displaystyle J (5,2)}$ это дополнительный граф из Граф Петерсена,^[1] следовательно линейный график из K₅. В общем, для всех ${ displaystyle n}$, граф Джонсона ${ Displaystyle J (п, 2)}$ является дополнением к Граф Кнезера ${ Displaystyle К (п, 2).}$

Теоретико-графические свойства

• ${ Displaystyle J (п, к)}$ изоморфен ${ Displaystyle J (п, п-к).}$

• Для всех ${ Displaystyle 0 Leq J Leq OperatorName {diam} (J (п, к))}$, любая пара вершин на расстоянии ${ displaystyle j}$ Поделиться ${ displaystyle k-j}$ общие элементы.

• ${ Displaystyle J (п, к)}$ является Гамильтон-связанный, что означает, что каждая пара вершин образует концы Гамильтонов путь в графике. В частности, это означает, что он имеет гамильтонов цикл.^[2]

• Также известно, что граф Джонсона ${ Displaystyle J (п, к) ~}$ является${ Displaystyle ~ к (п-к)}$-вершинно-связанные.^[3]

• ${ Displaystyle J (п, к)}$ образует граф вершин и ребер (п - 1) -мерный многогранник, называется гиперсимплекс.^[4]

• то номер клики из ${ Displaystyle J (п, к)}$ дается выражением через его наименьшее и наибольшее собственные значения: ${ displaystyle omega (J (n, k)) = 1 - { tfrac { lambda _ { max}} { lambda _ { min}}}.}$

• В хроматическое число из ${ Displaystyle J (п, к)}$ самое большее ${ Displaystyle п, чи (J (п, к)) Leq п.}$^[5]

Группа автоморфизмов

Существует дистанционно-переходный подгруппа ${ displaystyle operatorname {Aut} (J (n, k))}$ изоморфен ${ displaystyle operatorname {Sym} (n)}$. Фактически, ${ Displaystyle OperatorName {Aut} (J (n, k)) cong OperatorName {Sym} (n)}$, пока не ${ Displaystyle п = 2к geq 4}$; иначе, ${ displaystyle operatorname {Aut} (J (n, k)) cong operatorname {Sym} (n) times C_ {2}}$.^[6]

Массив пересечений

Как следствие того, что они дистанционно транзитивны, ${ Displaystyle J (п, к)}$ это также дистанционно-регулярный. Сдача ${ displaystyle d}$ обозначим его диаметр, массив пересечений ${ Displaystyle J (п, к)}$ дан кем-то

${ displaystyle left {b_ {0}, ldots, b_ {d-1}, c_ {1}, ldots c_ {d} right }}$

куда:

${ displaystyle { begin {align} b_ {j} & = (kj) (nkj) && 0 leq j$

Оказывается, если ${ Displaystyle J (п, к)}$ является ${ Displaystyle J (8,2)}$, его массив пересечений не используется совместно с каким-либо другим дистанционно регулярным графом; массив пересечений ${ Displaystyle J (8,2)}$ разделяется с тремя другими дистанционно регулярными графами, которые не являются графами Джонсона.^[1]

Собственные значения и собственные векторы

• Характеристический многочлен ${ Displaystyle J (п, к)}$ дан кем-то

${ displaystyle phi (x): = prod _ {j = 0} ^ { operatorname {diam} (J (n, k))} left (x-A_ {n, k} (j) right ) ^ {{ binom {n} {j}} - { binom {n} {j-1}}}.}$

куда ${ Displaystyle A_ {n, k} (j) = (k-j) (n-k-j) -j.}$^[6]

• Собственные векторы ${ Displaystyle J (п, к)}$ иметь четкое описание.^[7]

Схема Джонсона

Граф Джонсона ${ Displaystyle J (п, к)}$ тесно связан с Схема Джонсона, схема ассоциации в котором каждая пара k-элементный набор связан с числом, половиной размера симметричная разница из двух наборов.^[8] Граф Джонсона имеет ребро для каждой пары множеств на расстоянии один в схеме ассоциации, и расстояния в схеме ассоциации в точности равны кратчайший путь расстояния в графе Джонсона.^[9]

Схема Джонсона также связана с другим семейством дистанционно-транзитивных графов, нечетные графики, вершины которого ${ displaystyle k}$-элементные подмножества ${ displaystyle (2k + 1)}$-элементное множество, ребра которого соответствуют непересекающимся парам подмножеств.^[8]

Открытые проблемы

Свойства расширения вершин графов Джонсона, а также структура соответствующих экстремальных множеств вершин заданного размера до конца не изучены. Однако недавно была получена асимптотически точная нижняя оценка разложения больших множеств вершин.^[10]

В общем, определение хроматического числа графа Джонсона - открытая проблема.^[11]

Смотрите также

• Граф Грассмана

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

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

• Вайсштейн, Эрик В. «График Джонсона». MathWorld.
• Брауэр, Андрис Э. «Графики Джонсона».