Обозначение LCF - LCF notation

В Науру график[1] имеет обозначение LCF [5, −9, 7, −7, 9, −5]4.

В комбинаторный математика, Обозначение LCF или же Код LCF это обозначение, разработанное Джошуа Ледерберг, и продлен Х. С. М. Коксетер и Роберт Фрухт, для представления кубические графы которые содержат Гамильтонов цикл.[2][3] Сам цикл включает две из трех смежностей для каждой вершины, а нотация LCF указывает, как далеко в цикле находится третий сосед каждой вершины. Один граф может иметь несколько разных представлений в нотации LCF.

Описание

В гамильтоновом графе вершины могут быть организовано в цикл, что составляет два ребра на вершину. Третье ребро от каждой вершины может быть описано тем, сколько позиций по часовой стрелке (положительное) или против часовой стрелки (отрицательное) оно ведет. Основная форма нотации LCF - это просто последовательность этих чисел позиций, начиная с произвольно выбранной вершины и записанная в квадратных скобках. Числа в скобках интерпретируются как по модулю N, куда N количество вершин. Записи, совпадающие по модулю N на 0, 1 или N - 1 не появляется в этой последовательности цифр,[4] потому что они соответствовали бы либо петля или же множественная смежность, ни один из которых не допускается в простых графах.

Часто шаблон повторяется, и количество повторений может быть указано в обозначении с помощью верхнего индекса. Например, Науру график,[1] показанный справа, имеет четыре повторения одних и тех же шести смещений и может быть представлен нотацией LCF [5, −9, 7, −7, 9, −5]4. Один граф может иметь несколько различных обозначений LCF, в зависимости от выбора гамильтонова цикла и начальной вершины.

Приложения

Нотация LCF полезна при публикации кратких описаний гамильтоновых кубических графов, таких как примеры ниже. Кроме того, некоторые программные пакеты для управления графами включают утилиты для создания графа из его нотации LCF.[5]

Если граф представлен нотацией LCF, легко проверить, является ли граф двудольный: это верно тогда и только тогда, когда все смещения в нотации LCF нечетные.[6]

Примеры

ИмяВершиныОбозначение LCF
Тетраэдр график4[2]4
График полезности6[3]6
Кубический граф8[3,−3]4
График Вагнера8[4]8 или [4, −3,3,4]2
Куб Бидьякиса12[6,4,−4]4 или [6, −3,3,6,3, −3]2 или [−3,6,4, −4,6,3, −4,6, −3,3,6,4]
Граф Франклина12[5,−5]6 или [−5, −3,3,5]3
Граф Фрухта12[−5,−2,−4,2,5,−2,2,5,−2,−5,4,2]
Усеченный четырехгранный график12[2,6,−2]4
График Хивуда14[5,−5]7
График Мёбиуса – Кантора16[5,−5]8
График Паппа18[5,7,−7,7,−7,−5]3
Самый маленький нулевой симметричный граф[7]18[5,−5]9
График дезарга20[5,−5,9,−9]5
Додекаэдр график20[10,7,4,−4,−7,10,−4,7,−7,4]2
График Макги24[12,7,−7]8
Усеченный кубический график24[2,9,−2,2,−9,−2]4
Усеченный восьмигранный график24[3,−7,7,−3]6
Науру график24[5,−9,7,−7,9,−5]4
График F26A26[−7, 7]13
График Тутте – Кокстера30[−13,−9,7,−7,9,13]5
График Дика32[5,−5,13,−13]8
Серый график54[−25,7,−7,13,−13,25]9
Усеченный додекаэдр график60[30, −2, 2, 21, −2, 2, 12, −2, 2, −12, −2, 2, −21, −2, 2, 30, −2, 2, −12, −2, 2, 21, −2, 2, −21, −2, 2, 12, −2, 2]2
Граф Харриса70[−29,−19,−13,13,21,−27,27,33,−13,13,19,−21,−33,29]5
График Харриса – Вонга70[9, 25, 31, −17, 17, 33, 9, −29, −15, −9, 9, 25, −25, 29, 17, −9, 9, −27, 35, −9, 9, −17, 21, 27, −29, −9, −25, 13, 19, −9, −33, −17, 19, −31, 27, 11, −25, 29, −33, 13, −13, 21, −29, −21, 25, 9, −11, −19, 29, 9, −27, −19, −13, −35, −9, 9, 17, 25, −9, 9, 27, −27, −21, 15, −9, 29, −29, 33, −9, −25]
Балабан 10-клеточный70[−9, −25, −19, 29, 13, 35, −13, −29, 19, 25, 9, −29, 29, 17, 33, 21, 9,−13, −31, −9, 25, 17, 9, −31, 27, −9, 17, −19, −29, 27, −17, −9, −29, 33, −25,25, −21, 17, −17, 29, 35, −29, 17, −17, 21, −25, 25, −33, 29, 9, 17, −27, 29, 19, −17, 9, −27, 31, −9, −17, −25, 9, 31, 13, −9, −21, −33, −17, −29, 29]
Граф Фостера90[17,−9,37,−37,9,−17]15
График Биггса – Смита102[16, 24, −38, 17, 34, 48, −19, 41, −35, 47, −20, 34, −36, 21, 14, 48, −16, −36, −43, 28, −17, 21, 29, −43, 46, −24, 28, −38, −14, −50, −45, 21, 8, 27, −21, 20, −37, 39, −34, −44, −8, 38, −21, 25, 15, −34, 18, −28, −41, 36, 8, −29, −21, −48, −28, −20, −47, 14, −8, −15, −27, 38, 24, −48, −18, 25, 38, 31, −25, 24, −46, −14, 28, 11, 21, 35, −39, 43, 36, −38, 14, 50, 43, 36, −11, −36, −24, 45, 8, 19, −25, 38, 20, −24, −14, −21, −8, 44, −31, −38, −28, 37]
Балабан 11-клеточный112[44, 26, −47, −15, 35, −39, 11, −27, 38, −37, 43, 14, 28, 51, −29, −16, 41, −11, −26, 15, 22, −51, −35, 36, 52, −14, −33, −26, −46, 52, 26, 16, 43, 33, −15, 17, −53, 23, −42, −35, −28, 30, −22, 45, −44, 16, −38, −16, 50, −55, 20, 28, −17, −43, 47, 34, −26, −41, 11, −36, −23, −16, 41, 17, −51, 26, −33, 47, 17, −11, −20, −30, 21, 29, 36, −43, −52, 10, 39, −28, −17, −52, 51, 26, 37, −17, 10, −10, −45, −34, 17, −26, 27, −21, 46, 53, −10, 29, −50, 35, 15, −47, −29, −41, 26, 33, 55, −17, 42, −26, −36, 16]
Любляна график112[47, −23, −31, 39, 25, −21, −31, −41, 25, 15, 29, −41, −19, 15, −49, 33, 39, −35, −21, 17, −33, 49, 41, 31, −15, −29, 41, 31, −15, −25, 21, 31, −51, −25, 23, 9, −17, 51, 35, −29, 21, −51, −39, 33, −9, −51, 51, −47, −33, 19, 51, −21, 29, 21, −31, −39]2
Тутте 12 клеток126[17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −17]7

Расширенная нотация LCF

Более сложная расширенная версия нотации LCF была предоставлена ​​Кокстером, Фрухтом и Пауэрсом в более поздних работах.[8] В частности, они ввели «антипалиндромную» нотацию: если вторая половина чисел в квадратных скобках была обратной по отношению к первой половине, но с изменением всех знаков, то она заменялась точкой с запятой и тире. Граф Науру удовлетворяет этому условию с [5, −9, 7, −7, 9, −5]4, так что можно записать [5, −9, 7; -]4 в расширенных обозначениях.[9]

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

  1. ^ а б Эппштейн, Д., Многоликость графа Науру, 2007.
  2. ^ Писанский, Томаж; Серватиус, Бриджит (2013), «2.3.2 Кубические графы и нотация LCF», Конфигурации с графической точки зрения, Springer, стр. 32, ISBN  9780817683641.
  3. ^ Фрухт, Р. (1976), "Каноническое представление трехвалентных гамильтоновых графов", Журнал теории графов, 1 (1): 45–60, Дои:10.1002 / jgt.3190010111, МИСТЕР  0463029.
  4. ^ Кутнар, Клавдия; Марушич, Драган (2008), «Гамильтоничность вершинно-транзитивных графов порядка 4п", Европейский журнал комбинаторики, 29 (2): 423–438, arXiv:математика / 0606585, Дои:10.1016 / j.ejc.2007.02.002, МИСТЕР  2388379. См. Раздел 2.
  5. ^ например Клен, NetworkX В архиве 2012-03-02 в Wayback Machine, igraph, и мудрец.
  6. ^ Кокстер, Гарольд Скотт Макдональд; Фрухт, Роберто; Пауэрс, Дэвид Л. (1981), Нуль-симметричные графы, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], Нью-Йорк-Лондон, с. 13, ISBN  0-12-194580-4, МИСТЕР  0658666.
  7. ^ Coxeter, Frucht & Powers (1981), Рис. 1.1, стр. 5.
  8. ^ Coxeter, Frucht & Powers (1981), п. 54.
  9. ^ Coxeter, Frucht & Powers (1981), п. 12.

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