LCF-код

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

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

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

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

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

Примечания
  1. D. Eppstein, 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 4p // European Journal of Combinatorics. — Т. 29, вып. 2 (February 2008). — С. 423—438, section 2..
  5. например, Maple, NetworkX Архивная копия от 2 марта 2012 на Wayback Machine, R, и sage.
  6. Coxeter, Frucht, Powers, 1981, p. 54
  7. 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.