LCF-код — система обозначений в комбинаторной математике, разработанная Ледербергом и расширенная Коксетером и Фрухтом, для представления кубических графов, являющихся гамильтоновыми. Поскольку графы гамильтоновы, то вершины можно расположить на окружности, которая задаёт два ребра для каждой вершины. Третье ребро можно теперь описать количеством позиций, на которые отстоит конец ребра от начала (с плюсом по часовой стрелке и с минусом против часовой стрелки). Часто в результате получаем повторяющуюся последовательность чисел, в этом случае выписывается только эта повторяющаяся часть, а число повторений показывается верхним индексом (наподобие степени). Например, Граф Науру имеет LCF-код [5, −9, 7, −7, 9, −5]4. Один и тот же граф может иметь различные LCF-коды в зависимости от того, как вершины будут расположены на окружности (граф может иметь несколько вариантов гамильтонова цикла).
Числа внутри квадратных скобок рассматриваются по модулю , где — число вершин графа. Числа, сравнимые по модулю с 0, 1, и не разрешены, поскольку они не могут соответствовать какому-либо третьему ребру.
LCF-код полезен для лаконичного описания гамильтоновых кубических графов, в частности тех, что приведены ниже в таблице. Вдобавок, некоторые пакеты программного обеспечения для графов включают в себя утилиты для создания графа из его LCF-коданапример, Maple , NetworkX , R , и sage ..
Примеры Название Вершин LCF-кодГраф тетраэдра 4 4 6 6Граф куба 8 [3,-3]4Граф Вагнера 8 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]212-клетка Татта 126 [17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −17]7
Обобщённый LCF-кода Более сложный вариант LCF-кода был предложен Коксетером, Фрухтом и Пауэрсом в более поздней работе. В частности, они предложили «антипалидромический» код — если вторая половина чисел внутри квадратных скобок является обратной последовательностью первой части со сменой знаков на обратные, то вторую часть заменяем на точку с запятой и тире. Граф Науру удовлетворяет этому условию, так что его код [5, −9, 7, −7, 9, −5]4 в обобщённом виде можно записать как [5, −9, 7; −]4.
Примечания
Ссылки
«Cubic Hamiltonian Graphs from LCF Notation» — интерактивное приложение (на JavaScript), построенное с библиотекой D3js
Категория:Языки описания графов Категория:Гамильтоновы пути и циклы