Русская Википедия:LCF-код

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Nauru graph LCF.svg
Граф Науру[1] имеет LCF-код [5, −9, 7, −7, 9, −5]4.

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

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

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

Примеры

Название Вершин LCF-код
Граф тетраэдра 4 [2]4
<math>K_{3,3}</math> 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,0 1,1 Шаблон:Не переведено 5, The many faces of the Nauru graph Шаблон:Webarchive на сайте LiveJournal, 2007.
  2. ↑ Шаблон:Книга
  3. ↑ Шаблон:Статья
  4. ↑ Шаблон:Статья
  5. ↑ например, Maple Шаблон:Wayback, NetworkX Шаблон:Wayback, R Шаблон:Wayback, и sage Шаблон:Wayback.
  6. ↑ Шаблон:Harvnb
  7. ↑ Шаблон:Harvnb
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:LCF-код&oldid=8703795