У теорії графів, граф Науру — симетричний двочастковий кубічний граф з 24 вершинами і 36 ребрами. Він був названий Девідом Епштейном на честь двадцятизіркового прапору Науру.
Nauru graph | |
---|---|
![]() Граф Науру є Гамільтоновим графом. | |
Вершин | 24 |
Ребер | 36 |
Радіус | 4 |
Діаметр | 4 |
Обхват | 6 |
Автоморфізм | 144 (S4×S3) |
Хроматичне число | 2 |
Хроматичний індекс | 3 |
2 | |
Властивості | симетричний кубічний гамільтонів цілий граф Келі двочастковий |
Його хроматичне число — 2, хроматичний індекс — 3, діаметр — 4, радіус — 4 та обхват — 6. Він так само містить 3-вершинно-зв'язний та 3-реберно-зв'язний графи.
Найменші кубічні графи з числами схрещень 1-8 відомі (послідовність A110507 з Онлайн енциклопедії послідовностей цілих чисел, OEIS). Найменший граф з числом схрещень 8 — граф Науру. Існує 5 неізоморфних кубічних графів 24-го порядку з числом перетину 8. Один з них являє собою граф Маꥳ, також відомий як (3-7)-клітина.
Конструкція
Граф Науру це Гамільтонів граф, він може бути описаний (LCF-нотацією): [5, −9, 7, 9, −7, −5]4.
Граф Науру може бути побудований як узагальнений граф Петерсена G (12, 5), який утворюється на вершинах (дванадцятикутника), пов'язаних з вершинами дванадцяти-кінцевої зірки, в якій кожна точка зірки поєднується точками за п'ять кроків від нього.
Така можлива комбінаторна побудова графа Науру. Візьміть три неоднакові об'єкти і розмістіть їх у чотири неоднакові коробки, не більше одного об'єкта в коробці. Є 24 способи, щоб розподілити об'єкти, відповідно 24 вершинам графа. Якщо можливо перейти з одного положення в інше, переміщуючи рівно один об'єкт із його поточного місця розташування у порожнє місце, то вершини, що відповідають двом положенням, поєднуються ребром. Як результат, графом переходу станів є граф Науру.
Алгебраїчні властивості
Група автоморфізмів графа Науру — група порядку 144. Вона ізоморфна прямому добутку симетричних груп S4 і S3 і діє транзитивно на вершинах по краях і на дугах графа. Тому графік Науру — симетричний граф. Він має автоморфізми, які переміщують будь-яку вершину до будь-якої іншої вершини і будь-яке ребро до будь-якого іншого ребра. За даними (перепису Фостера), граф Науру є єдиним кубічно-симетричним графом на 24 вершинах.
Узагальнений граф Петерсена G(n, k) є вершинно-транзитивним тоді, і тільки тоді, коли n = 10 і k = 2 або якщо k2 ≡ ± 1 (mod n) і є реберно-транзитивним тільки в наступних випадках: (n, k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5). Таким чином, граф Науру є одним з семи симетричних узагальнених графів Петерсена. Серед цих семи графів кубічний граф , граф Петерсена
, граф Мебіуса — Кантора
, додекаедрічний граф
і граф Дезарга
.
Граф Науру — це граф Келі групи S4, симетричної групи перестановок чотирьох елементів, що породжується трьома різними способами перестановки першого елементу з трьома іншими: (1 2), (1 3) і (1 4).
Характеристичний поліном графа Науру дорівнює
що робить його цілим графом, тобто графом спектр якого складається повністю з цілих чисел.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODNMemN4TDA1aGRYSjFYekV0Y0d4aGJtRnlYemd0WTNKdmMzTnBibWN1YzNabkx6SXpPSEI0TFU1aGRYSjFYekV0Y0d4aGJtRnlYemd0WTNKdmMzTnBibWN1YzNabkxuQnVadz09LnBuZw==.png)
![]() Тор формується, топологічно, склеюванням протилежних країв правильного шестикутника один до одного. | ![]() | ![]() |
Топологічні властивості
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHdMekJpTDA1aGRYSjFYMmR5WVhCb1h6TmtMbkJ1Wnk4ek1EQndlQzFPWVhWeWRWOW5jbUZ3YUY4elpDNXdibWM9LnBuZw==.png)
Граф Науру має два різних вкладення у вигляді [en]: топологічні поверхні розбиваються на ряд ребер, вершин і граней таким чином, що існує симетричний перекид будь-якого (прапорця) (інцидентна трійка з вершини, ребра та грані) у будь-який інший прапорець.
Одне з цих двох вкладень утворює тор, тому граф Науру — це (тороїдальний граф): він складається з 12 шестикутних граней разом з 24 вершинами і 36 ребрами графа Науру. Двоїстий граф — це вкладення симетричного 6-регулярного графа з 12 вершинами і 36 ребрами.
Інші симетричні вкладення графа Науру мають шість дванадцятикутних граней, які утворюють поверхню 4 роду . Двоїстий граф може бути сформований з простого графа.
Геометричні властивості
Як і у всіх узагальнених графах Петерсена, граф Науру можна представити точками на площині таким чином, що сусідні вершини знаходяться на одиниці відстані один від одного. Це граф одиничної відстані. Такими є тільки узагальнені графи Петерсена G (n, р), вони не можуть бути представлені таким чином, що симетрії малюнка утворюють циклічну групу порядку n. Замість цього, одинична відстань графа має діедральну групу Dih6 як групу її симетрії.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODJMelkzTDA1aGRYSjFYM1Z1YVhSZlpHbHpkR0Z1WTJVdWMzWm5MekkwTUhCNExVNWhkWEoxWDNWdWFYUmZaR2x6ZEdGdVkyVXVjM1puTG5CdVp3PT0ucG5n.png)
Історія
Першою людиною, що написала про граф Науру був (Рональд Фостер), він зробив це у спробі зібрати усі кубічні симетричні графи. Список кубічних симетричних графів зараз носить ім'я (Перепис Фостера) і всередині цього списку граф Науру має номер F24A, але не має конкретного імені. У 1950 р. Гарольд Коксетер описав граф у другий раз, даючи ствердження Гамільтона для ілюстрації цієї статті, та описуючи його як граф Леві проєктивної конфігурації, описаного Захарієм.
У 2003, [en] написав у своєму онлайн-МАА рубрику про те, що F24A заслуговує на назву, але не запропонував її. Нарешті, у 2007 році, Девід Епштейн використав назву Граф Науру, тому що прапор Республіки Науру має 12-кінцеву зірку, аналогічну до тієї, що з'являється в конструкції графа як узагальнений граф Петерсена.
Примітки
- Eppstein, D., The many faces of the Nauru graph [ 21 липня 2011 у Wayback Machine.] on LiveJournal, 2007.
- and Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
- ; Exoo, G. (2009), , Mathematica Journal, 11, архів оригіналу за 6 березня 2019, процитовано 6 червня 2015.
- Weisstein, Eric W. Graph Crossing Number(англ.) на сайті Wolfram MathWorld.
- Royle, G. F024A data [ 6 березня 2011 у Wayback Machine.]
- ; Graver, J. E.; Watkins, M. E. (1971), The groups of the generalized Petersen graphs, Proceedings of the , 70: 211—218, doi:10.1017/S0305004100049811.
- (1992), The regular polyhedra of type {p, 3} with 2p vertices, Geometriae Dedicata, 43 (3): 285—289, doi:10.1007/BF00151518.
- Žitnik, Arjana; Horvat, Boris; (2010), (PDF), IMFM preprints, т. 1109, архів оригіналу (PDF) за 2 березня 2012, процитовано 6 червня 2015.
- (Foster, R. M.) (1932), Geometrical circuits of electrical networks, , 51: 309—317, doi:10.1109/T-AIEE.1932.5056068.
- Bouwer, I. Z.; Chernoff, W. W.; Monson, B.; Star, Z (1988), The Foster Census, Charles Babbage Research Centre.
- Coxeter, H. S. M. (1950), Self-dual configurations and regular graphs, Bulletin of the American Mathematical Society, 56: 413—455, doi:10.1090/S0002-9904-1950-09407-5.
- Zacharias, M. (1941), Untersuchungen über ebene Konfigurationen (124, 163), Deutsche Mathematik, 6: 147—170.
- (2003), , Mathematical Association of America, архів оригіналу за 7 травня 2013, процитовано 6 червня 2015.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет