Просмотр кода страницы LCF-код

[[Файл:Nauru graph LCF.svg|thumb|220px|[[Граф Науру]]<ref name="DE1">{{не переведено 5|Эпштейн, Дэвид|D. Eppstein||David Eppstein}}, [http://11011110.livejournal.com/124705.html The many faces of the Nauru graph] {{webarchive|url=https://web.archive.org/web/20110721032621/http://11011110.livejournal.com/124705.html |date=2011-07-21 }} на сайте LiveJournal, 2007.</ref> имеет LCF-код [5, −9, 7, −7, 9, −5]<sup>4</sup>.]]

'''LCF-код''' — система обозначений в [[Комбинаторика|комбинаторной]] математике, разработанная [[Ледерберг, Джошуа|Ледербергом]] и расширенная [[Коксетер, Гарольд|Коксетером]] и [[Фрухт, Роберт|Фрухтом]], для представления [[Кубический граф|кубических графов]], являющихся [[Гамильтонов граф|гамильтоновыми]]<ref>{{книга
 | автор = Tomaž Pisanski, Brigitte Servatius
 | вклад = 2.3.2 Cubic graphs and LCF notation
 | isbn = 9780817683641
 | страница = 32
 | издательство = Springer
 | заглавие = Configurations from a Graphical Viewpoint
 | url = https://books.google.com/books?id=bnh2zkuTZr4C&pg=PA32
 | год = 2013
}}</ref><ref>{{статья
|автор=R. Frucht 
|заглавие=A canonical representation of trivalent Hamiltonian graphs
|издание=Journal of Graph Theory
|том=1
|страницы=45–60
|год=1976
|выпуск=1
|doi=10.1002/jgt.3190010111
}}</ref>. Поскольку графы гамильтоновы, то вершины можно [[Круговое расположение|расположить на окружности]], которая задаёт два ребра для каждой вершины. Третье ребро можно теперь описать количеством позиций, на которые отстоит конец ребра от начала (с плюсом по часовой стрелке и с минусом против часовой стрелки). Часто в результате получаем повторяющуюся последовательность чисел, в этом случае выписывается только эта повторяющаяся часть, а число повторений показывается верхним индексом (наподобие степени). Например, [[Граф Науру]]<ref name="DE1"/> имеет LCF-код [5, −9, 7, −7, 9, −5]<sup>4</sup>. Один и тот же граф может иметь различные LCF-коды в зависимости от того, как вершины будут расположены на окружности (граф может иметь несколько вариантов гамильтонова цикла).

Числа внутри квадратных скобок рассматриваются по [[Сравнение по модулю|модулю]] <math>N</math>, где <math>N</math> — число вершин графа. Числа, сравнимые по модулю <math>N</math> с 0, 1, и <math>N-1</math> не разрешены<ref>{{статья
|автор=Klavdija Kutnar, Dragan Marušič
|ссылка=http://arxiv.org/abs/math/0606585v1
|заглавие=Hamiltonicity of vertex-transitive graphs of order 4{{mvar|p}}
|издание=European Journal of Combinatorics
|том=29
|выпуск=2 (February 2008)
|страницы=423—438, section 2.
|archivedate=2019-02-09
|archiveurl=https://web.archive.org/web/20190209123946/https://arxiv.org/abs/math/0606585v1
}}</ref>, поскольку они не могут соответствовать какому-либо третьему ребру.

LCF-код полезен для лаконичного описания гамильтоновых кубических графов, в частности тех, что приведены ниже в таблице. Вдобавок, некоторые пакеты программного обеспечения для графов включают в себя утилиты для создания графа из его LCF-кода<ref>например, [http://www.maplesoft.com/support/help/AddOns/view.aspx?path=GraphTheory/SpecialGraphs/LCFGraph Maple] {{Wayback|url=http://www.maplesoft.com/support/help/AddOns/view.aspx?path=GraphTheory%2FSpecialGraphs%2FLCFGraph |date=20120302195926 }}, [http://networkx.lanl.gov/reference/generated/networkx.LCF_graph.html NetworkX] {{Wayback|url=http://networkx.lanl.gov/reference/generated/networkx.LCF_graph.html |date=20120302195926 }}, [http://igraph.sourceforge.net/doc/R/graph.lcf.html R] {{Wayback|url=http://igraph.sourceforge.net/doc/R/graph.lcf.html |date=20090821090801 }}, и [http://www.sagemath.org/doc/reference/sage/graphs/graph_generators.html#sage.graphs.graph_generators.GraphGenerators.LCFGraph sage] {{Wayback|url=http://www.sagemath.org/doc/reference/sage/graphs/graph_generators.html#sage.graphs.graph_generators.GraphGenerators.LCFGraph |date=20170327202907 }}.</ref>.

== Примеры ==
{| class="wikitable"
|-
|'''Название''' || '''Вершин''' || '''LCF-код'''
|-
|Граф [[тетраэдр]]а || 4 || [2]<sup>4</sup>
|-
|[[Домики и колодцы|<math>K_{3,3}</math>]] || 6 || [3]<sup>6</sup>
|-
|[[Граф гиперкуба|Граф куба]] || 8 || [3,-3]<sup>4</sup>
|-
|[[Граф Вагнера]] || 8 || [4]<sup>8</sup> или [4,-3,3,4]<sup>2</sup>
|-
|[[Бидиакис-куб|Куб Бидиакиса]] || 12 || [6,4,-4]<sup>4</sup> или [6,-3,3,6,3,-3]<sup>2</sup> или [-3,6,4,-4,6,3,-4,6,-3,3,6,4]
|-
|[[Граф Франклина]] || 12 || [5,-5]<sup>6</sup> or [-5,-3,3,5]<sup>3</sup>
|-
|[[Граф Фрухта]] || 12 || [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2]
|-
|Граф усечённого [[тетраэдр]]а|| 12 || [2,6,-2]<sup>4</sup>
|-
| [[Граф Хивуда]] || 14 || [5,-5]<sup>7</sup>
|-
|[[Граф Мёбиуса — Кантора]] || 16 || [5,-5]<sup>8</sup>
|-
| [[Граф Паппа]] || 18 || [5,7,-7,7,-7,-5]<sup>3</sup>
|-
|[[Граф Дезарга]] || 20 || [5,-5,9,-9]<sup>5</sup>
|-
|Граф [[додекаэдр]]а|| 20 || [10,7,4,-4,-7,10,-4,7,-7,4]<sup>2</sup>
|-
| [[Граф МакГи]] || 24 || [12,7,-7]<sup>8</sup>
|-
|Граф усечённого [[куб]]а|| 24 || [2,9,-2,2,-9,-2]<sup>4</sup>
|-
|Граф усечённого [[октаэдр]]а|| 24 || [3,-7,7,-3]<sup>6</sup>
|-
|[[Граф Науру]]|| 24 || [5,-9,7,-7,9,-5]<sup>4</sup>
|-
|[[Граф F26A]]|| 26 || [-7, 7]<sup>13</sup>
|-
| [[Граф Татта — Коксетера]] || 30 || [-13,-9,7,-7,9,13]<sup>5</sup>
|-
|[[Граф Дика]]|| 32 || [5,-5,13,-13]<sup>8</sup>
|-
|[[Граф Грея]] || 54 || [-25,7,-7,13,-13,25]<sup>9</sup>
|-
|Усечённый граф [[додекаэдр]]а|| 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]<sup>2</sup>
|-
|[[Граф Харриса]] || 70 || [-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29]<sup>5</sup>
|-
|[[Граф Харриса — Вонга]] || 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]<sup>15</sup>
|-
|[[Граф Биггса — Смита]] || 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]<sup>2</sup>
|-
|[[12-клетка Татта]]|| 126 || [17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −17]<sup>7</sup>
|}

== Обобщённый LCF-кода ==
Более сложный вариант LCF-кода был предложен Коксетером, Фрухтом и Пауэрсом <!--Powers--> в более поздней работе<ref>{{harvnb|Coxeter, Frucht, Powers|1981|p=54}}</ref>. В частности, они предложили «антипалидромический» код — если вторая половина чисел внутри квадратных скобок является обратной последовательностью первой части со сменой знаков на обратные, то вторую часть заменяем на точку с запятой и тире. Граф Науру удовлетворяет этому условию, так что его код [5, −9, 7, −7, 9, −5]<sup>4</sup> в обобщённом виде можно записать как [5, −9, 7; −]<sup>4</sup><ref>{{harvnb|Coxeter, Frucht, Powers|1981|p=12}}</ref>.

== Примечания ==
{{примечания}}

== Ссылки ==
* {{книга
|автор=H. S. M. Coxeter, R. Frucht, D. L. Powers 
|заглавие=Zero-symmetric graphs: trivalent graphical regular representations of groups 
|ссылка=https://archive.org/details/zerosymmetricgra0000coxe
|год=1981 
|издательство=Academic Press 
|isbn=0-12-194580-4
|mr=0658666 
|ref=Coxeter, Frucht, Powers}}
* {{MathWorld|title=LCF Notation|urlname=LCFNotation}}
* {{статья
|автор=Ed Pegg Jr.
|заглавие=Math Games: Cubic Symmetric Graphs
|год=29 December 2003
|издаетлство=Mathematical Association of America
|url=http://www.maa.org/editorial/mathgames/mathgames_12_29_03.html
}}
* [http://bl.ocks.org/1703449 «Cubic Hamiltonian Graphs from LCF Notation»] — интерактивное приложение (на JavaScript), построенное с библиотекой [[D3js]]

{{Представления графов}}

[[Категория:Языки описания графов]]
[[Категория:Гамильтоновы пути и циклы]]