LCF-нотація

LCF-нотація (LCF-код) — система позначень у комбінаторній математиці, розроблена Ледербергом і розширена Коксетером і , для подання кубічних графів, що є гамільтоновими. Оскільки графи гамільтонові (існує цикл, що містить всі вершини графу), то вершини можна розташувати на колі, таким чином для кожної вершини буде визначено два ребра. Тоді третє ребро можна позначити кількістю позицій, на які кінець ребра відстоїть від його початку (застосовують додатні числа, якщо рахувати за годинниковою стрілкою на колі, або від'ємні, якщо проти годинникової стрілки). У результаті часто утворюється періодична послідовність чисел, у цьому випадку виписується тільки періодична частина, а кількість повторів позначається верхнім індексом (на зразок степеня). Наприклад, Граф НауруD. Eppstein, The many faces of the Nauru graph на сайте LiveJournal, 2007. має LCF-код [5, −9, 7, −7, 9, −5]4. Один і той же граф може мати різні LCF-нотації залежно від того, як вершини розташовані на колі (граф може мати кілька варіантів гамільтонового циклу).

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

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

Приклади НазваВершинLCF-нотаціяГраф тетраедра4466Граф куба8[3,-3]4Граф Вангера88 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Граф F26A26[-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]570[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]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]212-клітка Татта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]4 у розширеній версії можна записати як [5, −9, 7; −]4.

Примітки

Посилання

«Cubic Hamiltonian Graphs from LCF Notation»  — інтерактивна програма (на JavaScript), побудована з бібліотекою D3.js