LCF-код
LCF-код — система обозначений в комбинаторной математике, разработанная Ледербергом и расширенная Коксетером и Фрухтом?!, для представления кубических графов, являющихся гамильтоновыми[2] [3]. Поскольку графы гамильтоновы, вершины можно расположить на окружности[англ.], которая задаёт два ребра для каждой вершины. Третье ребро можно теперь описать количеством позиций, на которые отстоит конец ребра от начала (с плюсом по часовой стрелки и с минусом против часовой стрелки). Часто в результате получаем повторяющуюся последовательность чисел, в этом случае выписывается только эта повторяющаяся часть, а число повторений показывается верхним индексом (наподобие степени). Например, Граф Науру[1] имеет LCF-код [5, −9, 7, −7, 9, −5]4. Один и тот же граф может иметь различные LCF-коды в зависимости от того, как вершины будут расположены на окружности (граф может иметь несколько вариантов гамильтонова цикла).
Числа внутри квадратных скобок рассматриваются по модулю , где — число вершин графа. Числа, сравнимые по модулю с 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 |
| Граф 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-кода был предложен Коксетером, Фрухтом и Пауэрсом в более поздней работе[6]. В частности, они предложили «антипалидромический» код — если вторая половина чисел внутри квадратных скобок является обратной последовательностью первой части со сменой знаков на обратные, то вторую часть заменяем на точку с запятой и тире. Граф Науру удовлетворяет этому условию, так что его код [5, −9, 7, −7, 9, −5]4 в обобщённом виде можно записать как [5, −9, 7; −]4[7].
Примечания
- ↑ 1 2 D. Eppstein[англ.], 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 4p // European Journal of Combinatorics. — Т. 29, вып. 2 (February 2008). — С. 423—438, section 2..
- ↑ например, Maple, NetworkX Архивная копия от 2 марта 2012 на Wayback Machine, R, и sage.
- ↑ 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