LCF-нотація

LCF-нотація (LCF-код) — система позначень у комбінаторній математиці, розроблена Ледербергом і розширена Коксетером і Фрухтом^[en], для подання кубічних графів, що є гамільтоновими^[1]. Оскільки графи гамільтонові (існує цикл, що містить всі вершини графу), то вершини можна розташувати на колі, таким чином для кожної вершини буде визначено два ребра. Тоді третє ребро можна позначити кількістю позицій, на які кінець ребра відстоїть від його початку (застосовують додатні числа, якщо рахувати за годинниковою стрілкою на колі, або від'ємні, якщо проти годинникової стрілки). У результаті часто утворюється періодична послідовність чисел, у цьому випадку виписується тільки періодична частина, а кількість повторів позначається верхнім індексом (на зразок степеня). Наприклад, Граф Науру^[2] має LCF-код [5, −9, 7, −7, 9, −5]⁴. Один і той же граф може мати різні LCF-нотації залежно від того, як вершини розташовані на колі (граф може мати кілька варіантів гамільтонового циклу).

Числа всередині квадратних дужок розглядаються за модулем $N$ , де $N$ — кількість вершин графу. Числа, порівнянні за модулем $N$ з 0, 1, і $N-1$ не дозволені^[3], оскільки вони не можуть відповідати будь-якому третьому ребру.

LCF-нотація корисна для лаконічного опису гамільтонових кубічних графів, зокрема тих, що наведені нижче в таблиці. Деякі пакети програмного забезпечення для графів містять утиліти для створення графу за його LCF-нотацією^[4].

Приклади

Назва	Вершин	LCF-нотація
Граф тетраедра	4	[2]⁴
$K_{3,3}$	6	[3]⁶
Граф куба	8	[3,-3]⁴
Граф Вангера	8	[4]⁸ or [4,-3,3,4]²
Бідіакіс-куб	12	[6,4,-4]⁴ or [6,-3,3,6,3,-3]² or [-3,6,4,-4,6,3,-4,6,-3,3,6,4]
Граф Франкліна	12	[5,-5]⁶ or [-5,-3,3,5]³
Граф Фрухта	12	[-5,-2,-4,2,5,-2,2,5,-2,-5,4,2]
Граф зрізаного тетраедра	12	[2,6,-2]⁴
Граф Хівуда	14	[5,-5]⁷
Граф Мебіуса — Кантора	16	[5,-5]⁸
Граф Паппа	18	[5,7,-7,7,-7,-5]³
Граф Дезарга	20	[5,-5,9,-9]⁵
Граф додекаедра	20	[10,7,4,-4,-7,10,-4,7,-7,4]²
Граф МакҐі	24	[12,7,-7]⁸
Граф зрізаного куба	24	[2,9,-2,2,-9,-2]⁴
Граф зрізаного октаедра	24	[3,-7,7,-3]⁶
Граф Науру	24	[5,-9,7,-7,9,-5]⁴
Граф F26A	26	[-7, 7]¹³
Граф Татта—Коксетера	30	[-13,-9,7,-7,9,13]⁵
Граф Діка	32	[5,-5,13,-13]⁸
Граф Грея	54	[-25,7,-7,13,-13,25]⁹
Зрізаний граф додекаедра	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]²
Граф Гарріса	70	[-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29]⁵
Граф Гарріса–Вонга^[en]	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-клітина Балабана^[en]	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]¹⁵
Граф Бігса — Сміта	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]²
12-клітка Татта	126	[17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −17]⁷

Розширена LCF-нотація

Складніший варіант LCF-нотації запропонували Коксетер, Фрухт та Пауерс (Powers) у пізнішій роботі. Зокрема, вони запропонували «антипаліндромічну» нотацію — якщо друга половина чисел усередині квадратних дужок є зворотною послідовністю першої частини зі зміною знаків на зворотні, то другу частину замінють на крапку з комою й тире. Наприклад, граф Науру задовольняє цій умові, так що його нотацію [5, −9, 7, −7, 9, −5]⁴ у розширеній версії можна записати як [5, −9, 7; −]⁴^[5].

Примітки

↑ R. Frucht. A canonical representation of trivalent Hamiltonian graphs // Journal of Graph Theory. — 1976. — Т. 1, вип. 1. — С. 45–60. — DOI:10.1002/jgt.3190010111.
↑ D. Eppstein, The many faces of the Nauru graph [Архівовано 21 липня 2011 у Wayback Machine.] на сайте LiveJournal, 2007.
↑ Klavdija Kutnar, Dragan Marušič. Hamiltonicity of vertex-transitive graphs of order 4 $p$ // European Journal of Combinatorics. — Т. 29, вип. 2 (February 2008). — С. 423—438, section 2..
↑ наприклад, Maple [Архівовано 2 березня 2012 у Wayback Machine.], NetworkX [Архівовано 2 березня 2012 у Wayback Machine.], R [Архівовано 21 серпня 2009 у Wayback Machine.], і sage [Архівовано 27 березня 2017 у Wayback Machine.].
↑ Coxeter, Frucht та Powers, 1981, с. 12.

Посилання

Weisstein, Eric W. LCF Notation(англ.) на сайті Wolfram MathWorld.
Ed Pegg Jr. Math Games: Cubic Symmetric Graphs. — 29 December 2003.
«Cubic Hamiltonian Graphs from LCF Notation» [Архівовано 10 серпня 2012 у Wayback Machine.] — інтерактивна програма (на JavaScript), побудована з бібліотекою D3.js
Coxeter, H.S.M. Zero-Symmetric Graphs : Zero-Symmetric Graphs Trivalent Graphical Regular Representations of Groups : [англ.] / H.S.M. Coxeter, Roberto Frucht, David L. Powers. — Academic Press. — 1981. — ISBN 978-0-12-194580-0. — DOI:10.1016/C2013-0-10543-0.

[1] R. Frucht. A canonical representation of trivalent Hamiltonian graphs // Journal of Graph Theory. — 1976. — Т. 1, вип. 1. — С. 45–60. — DOI:10.1002/jgt.3190010111.

[DE1-2] D. Eppstein, The many faces of the Nauru graph [Архівовано 21 липня 2011 у Wayback Machine.] на сайте LiveJournal, 2007.

[3] Klavdija Kutnar, Dragan Marušič. Hamiltonicity of vertex-transitive graphs of order 4 $p$ // European Journal of Combinatorics. — Т. 29, вип. 2 (February 2008). — С. 423—438, section 2..

[4] наприклад, Maple [Архівовано 2 березня 2012 у Wayback Machine.], NetworkX [Архівовано 2 березня 2012 у Wayback Machine.], R [Архівовано 21 серпня 2009 у Wayback Machine.], і sage [Архівовано 27 березня 2017 у Wayback Machine.].

[FOOTNOTECoxeterFruchtPowers198112-5] Coxeter, Frucht та Powers, 1981, с. 12.

[1]

[2]

[3]

[4]

[5]