LCF-код (LCF-tk;)

Граф Науру имеет LCF-код [5, −9, 7, −7, 9, −5]⁴.

LCF-код — система обозначений в комбинаторной математике, разработанная Ледербергом и расширенная Коксетером и Фрухтом, для представления кубических графов, являющихся гамильтоновыми. Поскольку графы гамильтоновы, то вершины можно расположить на окружности, которая задаёт два ребра для каждой вершины. Третье ребро можно теперь описать количеством позиций, на которые отстоит конец ребра от начала (с плюсом по часовой стрелке и с минусом против часовой стрелки). Часто в результате получаем повторяющуюся последовательность чисел, в этом случае выписывается только эта повторяющаяся часть, а число повторений показывается верхним индексом (наподобие степени). Например, Граф Науру имеет LCF-код [5, −9, 7, −7, 9, −5]⁴. Один и тот же граф может иметь различные LCF-коды в зависимости от того, как вершины будут расположены на окружности (граф может иметь несколько вариантов гамильтонова цикла).

Числа внутри квадратных скобок рассматриваются по модулю $N$, где $N$ — число вершин графа. Числа, сравнимые по модулю $N$ с 0, 1, и $N-1$ не разрешены, поскольку они не могут соответствовать какому-либо третьему ребру.

LCF-код полезен для лаконичного описания гамильтоновых кубических графов, в частности тех, что приведены ниже в таблице. Вдобавок, некоторые пакеты программного обеспечения для графов включают в себя утилиты для создания графа из его LCF-кода.

Примеры

Название	Вершин	LCF-код
Граф тетраэдра	4	[2]4
$K_{3,3}$	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 or [-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
Граф Дезарга	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
Граф F26A	26	[-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-кода был предложен Коксетером, Фрухтом и Пауэрсом в более поздней работе. В частности, они предложили «антипалидромический» код — если вторая половина чисел внутри квадратных скобок является обратной последовательностью первой части со сменой знаков на обратные, то вторую часть заменяем на точку с запятой и тире. Граф Науру удовлетворяет этому условию, так что его код [5, −9, 7, −7, 9, −5]⁴ в обобщённом виде можно записать как [5, −9, 7; −]⁴.

Ссылки

• H. S. M. Coxeter, R. Frucht, D. L. Powers. Zero-symmetric graphs: trivalent graphical regular representations of groups. — Academic Press, 1981. — ISBN 0-12-194580-4.
• Weisstein, Eric W. LCF Notation (англ.) на сайте Wolfram MathWorld.
• Ed Pegg Jr. Math Games: Cubic Symmetric Graphs. — 29 December 2003.
• «Cubic Hamiltonian Graphs from LCF Notation» — интерактивное приложение (на JavaScript), построенное с библиотекой D3js