LCF-нотація

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

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

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

Приклади

Назва	Вершин	LCF-нотація
Граф тетраедра	4	[2]4
${\displaystyle K_{3,3}}$	6	[3]6
Граф куба	8	[3,-3]4
Граф Вангера	8	[4]8 or [4,-3,3,4]2
Бідіакіс-куб	12	[6,4,-4]4 or [6,-3,3,6,3,-3]2 or [-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
Граф Гарріса–Вонга[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]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-нотації запропонували Коксетер, Фрухт та Пауерс (Powers) у пізнішій роботі. Зокрема, вони запропонували «антипаліндромічну» нотацію — якщо друга половина чисел усередині квадратних дужок є зворотною послідовністю першої частини зі зміною знаків на зворотні, то другу частину замінють на крапку з комою й тире. Наприклад, граф Науру задовольняє цій умові, так що його нотацію [5, −9, 7, −7, 9, −5]⁴ у розширеній версії можна записати як [5, −9, 7; −]^4[5].