Jump to content

Обозначение LCF

График Науру [1] имеет обозначение LCF [5, –9, 7, –7, 9, –5] 4 .

В математической области графов теории нотация LCF или код LCF — это обозначение, разработанное Джошуа Ледербергом и расширенное HSM Coxeter и Робертом Фрухтом для представления кубических графов , содержащих гамильтонов цикл . [2] [3] Сам цикл включает в себя две из трех смежностей для каждой вершины , а обозначение LCF указывает, насколько далеко в цикле находится третий сосед каждой вершины. Один граф может иметь несколько разных представлений в нотации LCF.

Описание [ править ]

В гамильтоновом графе вершины могут быть расположены в цикле , что соответствует двум ребрам на вершину. Третье ребро от каждой вершины можно тогда описать тем, на сколько позиций по часовой стрелке (положительное) или против часовой стрелки (отрицательное) оно ведет. Основная форма нотации LCF — это просто последовательность этих чисел позиций, начиная с произвольно выбранной вершины и записанная в квадратных скобках.Числа в скобках интерпретируются по модулю N , где N — количество вершин. Записи, совпадающие по модулю N с 0, 1 или N - 1, не появляются в этой последовательности чисел. [4] потому что они будут соответствовать либо циклу , либо множественной смежности , ни один из которых не разрешен в простых графах.

Часто узор повторяется, и количество повторений может быть указано верхним индексом в обозначениях. Например, график Науру , [1] показано справа, имеет четыре повторения одних и тех же шести смещений и может быть представлено обозначением LCF [5, -9, 7, -7, 9, -5] 4 . Один граф может иметь несколько различных обозначений LCF, в зависимости от выбора гамильтонова цикла и начальной вершины.

Приложения [ править ]

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

Если граф представлен в нотации LCF, проверить, является ли граф двудольным, несложно : это верно тогда и только тогда, когда все смещения в нотации LCF нечетны. [6]

Примеры [ править ]

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

Ссылки [ править ]

  1. Перейти обратно: Перейти обратно: а б Эппштейн, Д. , Многоликий график Науру , 2007.
  2. ^ Писански, Томаж ; Серватиус, Бриджит (2013), «2.3.2 Кубические графы и нотация LCF» , Конфигурации с графической точки зрения , Springer, стр. 32, ISBN  9780817683641 .
  3. ^ Фрухт, Р. (1976), «Каноническое представление трехвалентных гамильтоновых графов», Journal of Graph Theory , 1 (1): 45–60, doi : 10.1002/jgt.3190010111 , MR   0463029 .
  4. ^ Кутнар, Клавдия ; Марушич, Драган (2008), «Гамильтонность вершинно-транзитивных графов порядка 4 p », European Journal of Combinatorics , 29 (2): 423–438, arXiv : math/0606585 , doi : 10.1016/j.ejc.2007.02. 002 , МР   2388379 . См. раздел 2.
  5. ^ например, Maple , NetworkX. Архивировано 2 марта 2012 г. в Wayback Machine , igraph и sage .
  6. ^ Коксетер, Гарольд Скотт Макдональд ; Фрухт, Роберто ; Пауэрс, Дэвид Л. (1981), Нуль-симметричные графы , Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], Нью-Йорк-Лондон, стр. 13, ISBN  0-12-194580-4 , МР   0658666 .
  7. ^ Coxeter, Frucht & Powers (1981) , рис. 1.1, с. 5.
  8. ^ Коксетер, Фрухт и Пауэрс (1981) , стр. 54.
  9. ^ Коксетер, Фрухт и Пауэрс (1981) , стр. 12.

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 7fc3e035fcfada3b3be1bf440e1b49e5__1685335980
URL1:https://arc.ask3.ru/arc/aa/7f/e5/7fc3e035fcfada3b3be1bf440e1b49e5.html
Заголовок, (Title) документа по адресу, URL1:
LCF notation - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)