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