LCF-код

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

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

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

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

ПримерыПравить

Название	Вершин	LCF-код
Граф тетраэдра	4	[2]⁴
$\text{[math]}$ $\text{[math]}$ $K_{3,3}$	6	[3]⁶
Граф куба	8	[3,-3]⁴
Граф Вагнера	8	[4]⁸ или [4,-3,3,4]²
Куб Бидиакиса	12	[6,4,-4]⁴ или [6,-3,3,6,3,-3]² или [-3,6,4,-4,6,3,-4,6,-3,3,6,4]
Граф Франклина	12	[5,-5]⁶ or [-5,-3,3,5]³
Граф Фрухта	12	[-5,-2,-4,2,5,-2,2,5,-2,-5,4,2]
Граф усечённого тетраэдра	12	[2,6,-2]⁴
Граф Хивуда	14	[5,-5]⁷
Граф Мёбиуса — Кантора	16	[5,-5]⁸
Граф Паппа	18	[5,7,-7,7,-7,-5]³
Граф Дезарга	20	[5,-5,9,-9]⁵
Граф додекаэдра	20	[10,7,4,-4,-7,10,-4,7,-7,4]²
Граф МакГи	24	[12,7,-7]⁸
Граф усечённого куба	24	[2,9,-2,2,-9,-2]⁴
Граф усечённого октаэдра	24	[3,-7,7,-3]⁶
Граф Науру	24	[5,-9,7,-7,9,-5]⁴
Граф F26A	26	[-7, 7]¹³
Граф Татта — Коксетера	30	[-13,-9,7,-7,9,13]⁵
Граф Дика	32	[5,-5,13,-13]⁸
Граф Грея	54	[-25,7,-7,13,-13,25]⁹
Усечённый граф додекаэдра	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]²
Граф Харриса	70	[-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29]⁵
Граф Харриса — Вонга	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]¹⁵
Граф Биггса — Смита	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]²
12-клетка Татта	126	[17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −17]⁷

Обобщённый LCF-кодаПравить

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

ПримечанияПравить

↑ ¹ ² D. Eppstein^[en], The many faces of the Nauru graph Архивировано 21 июля 2011 года. на сайте LiveJournal, 2007.
↑ Tomaž Pisanski, Brigitte Servatius. Configurations from a Graphical Viewpoint. — Springer, 2013. — ISBN 9780817683641.
↑ R. Frucht. A canonical representation of trivalent Hamiltonian graphs // Journal of Graph Theory. — 1976. — Т. 1, вып. 1. — С. 45–60. — doi:10.1002/jgt.3190010111.
↑ Klavdija Kutnar, Dragan Marušič. Hamiltonicity of vertex-transitive graphs of order 4 $\text{[math]}$ p // European Journal of Combinatorics. — Т. 29, вып. 2 (February 2008). — С. 423—438, section 2..
↑ например, Maple Архивная копия от 2 марта 2012 на Wayback Machine, NetworkX Архивная копия от 2 марта 2012 на Wayback Machine, R Архивная копия от 21 августа 2009 на Wayback Machine, и sage Архивная копия от 27 марта 2017 на Wayback Machine.
↑ Coxeter, Frucht, Powers, 1981, p. 54
↑ Coxeter, Frucht, Powers, 1981, p. 12

СсылкиПравить

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

[DE1-1] ¹ ² D. Eppstein^[en], The many faces of the Nauru graph Архивировано 21 июля 2011 года. на сайте LiveJournal, 2007.

[2] Tomaž Pisanski, Brigitte Servatius. Configurations from a Graphical Viewpoint. — Springer, 2013. — ISBN 9780817683641.

[3] R. Frucht. A canonical representation of trivalent Hamiltonian graphs // Journal of Graph Theory. — 1976. — Т. 1, вып. 1. — С. 45–60. — doi:10.1002/jgt.3190010111.

[4] Klavdija Kutnar, Dragan Marušič. Hamiltonicity of vertex-transitive graphs of order 4 $\text{[math]}$ p // European Journal of Combinatorics. — Т. 29, вып. 2 (February 2008). — С. 423—438, section 2..

[5] например, Maple Архивная копия от 2 марта 2012 на Wayback Machine, NetworkX Архивная копия от 2 марта 2012 на Wayback Machine, R Архивная копия от 21 августа 2009 на Wayback Machine, и sage Архивная копия от 27 марта 2017 на Wayback Machine.

[6] Coxeter, Frucht, Powers, 1981, p. 54

[7] Coxeter, Frucht, Powers, 1981, p. 12

[2]

[3]

[1]

[4]

[5]

[6]

[7]