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

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

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

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

Примеры

Название	Вершин	LCF-код
Граф тетраэдра	4	[2]4
${\displaystyle K_{3,3}}$	6	[3]6
Граф куба	8	[3,-3]4
Граф Вагнера	8	[4]8 или [4,-3,3,4]2
Куб Бидиакиса[en]	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
Граф Харриса–Вонга[en]	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-клетка Балабана[en]	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
Граф Гиббса-Смита[en]	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-клетка Тутте[en]	126	[17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −17]7

Обобщённый LCF-кода

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