WikiSort.ru - Не сортированное

Граф Паппа
Назван в честь	Папп Александрийский
Вершин	18
Рёбер	27
Радиус	4
Диаметр	4
Обхват	6
Автоморфизмы	216
Хроматическое число	2
Хроматический индекс	3
Свойства	двудольный симметричный кубический гамильтонов дистанционно-транзитивен дистанционно-регулярен

В теории графов графом Паппа называется двудольный 3-регулярный неориентированный граф с 18 вершинами и 27 рёбрами, являющийся графом Леви конфигурации Паппа^[1]. Он назван в честь Паппа Александрийского, математика Древней Греции, который верил, что доказал «теорему о шестиугольнике», в которой описывал конфигурацию Паппа. Все кубические дистанционно-регулярные графы известны. Граф Паппа — один из тринадцати таких графов^[2].

Число прямолинейных скрещиваний^[en]* графа Паппа равно 5, и этот граф является наименьшим кубическим графом с таким числом скрещиваний (последовательность A110507 в OEIS). Граф имеет обхват 6, диаметр 4, радиус 4, хроматическое число 2, хроматический индекс 3, а также является и вершинно 3-связным, и рёберно 3-связным.

Хроматический многочлен графа Паппа равен ${\displaystyle (x-1)x(x^{16}-26x^{15}+325x^{14}-2600x^{13}+14950x^{12}-65762x^{11}+}$ ${\displaystyle 229852x^{10}-653966x^{9}+1537363x^{8}-3008720x^{7}+4904386x^{6}-}$ ${\displaystyle 6609926x^{5}+7238770x^{4}-6236975x^{3}+3989074x^{2}-1690406x+356509)}$ .

Имя «граф Паппа» используется также для близкого графа с девятью вершинами^[3], по вершине для каждой точки конфигурации Паппа с рёбрами для каждой пары точек, находящихся на одной линии. Этот граф 6-регулярен и является дополнением объединения трёх не связанных друг с другом треугольных графов. Первый граф Паппа можно вложить в тор, получая при этом правильную карту^[en] с девятью шестиугольными гранями. Второй граф образует при таком вложении правильную карту с 18 треугольными гранями.

Алгебраические свойства

Группа автоморфизмов графа Паппа — это группа с порядком 216. Она действует транзитивно на вершины и рёбра графа. Таким образом, граф Паппа является симметричным. У него есть автоморфизмы, переводящие любую вершину в любую другую и любое ребро в любое другое ребро. В списке Фостера граф Папа обозначен как F018A и является единственным кубическим симметричным графом с 18 вершинами^[4][5].

Характеристический многочлен графа Паппа равен ${\displaystyle (x-3)x^{4}(x+3)(x^{2}-3)^{6}}$ . Это единственный граф с таким характеристическим полиномом, так что в данном случае граф определяется своим спектром.

Галерея

• 
  Граф Паппа, раскрашенный для выделения различных циклов.
• 
  хроматический индекс графа Паппа равен 3.
• 
  Хроматическое число графа Паппа равно 2.

Примечания

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.