LCF-нотация

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

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. 1 2 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 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