For faster navigation, this Iframe is preloading the Wikiwand page for LCF-нотація.

LCF-нотація

Матеріал з Вікіпедії — вільної енциклопедії.

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

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

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

Приклади

[ред. | ред. код]
Назва Вершин LCF-нотація
Граф тетраедра 4 [2]4
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]4 у розширеній версії можна записати як [5, −9, 7; −]4[5].

Примітки

[ред. | ред. код]
  1. R. Frucht. A canonical representation of trivalent Hamiltonian graphs // Journal of Graph Theory. — 1976. — Т. 1, вип. 1. — С. 45–60. — DOI:10.1002/jgt.3190010111.
  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 4p // 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.].
  5. 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.
{{bottomLinkPreText}} {{bottomLinkText}}
LCF-нотація
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?