Loading AI tools
З Вікіпедії, вільної енциклопедії
Граф МакЖі - це єдина (3,7) клітка (найменший кубічний з обхватом 7). Він є найменшою кубічної кліткою, яка не є графом Мура.
В теорії графів графом МакЖі, або (3-7)-клітиною, називається 3-регулярний граф з 24 вершинами і 36 ребрами[1]. Вперше відкритий Хорстом Саксом, але не опублікований[2][3], граф названий на честь МакЖі (англ. W. F. McGee), який опублікував результат в 1960 році. Пізніше, в 1966 році, Вільям Томас Татт довів, що це єдина (3,7)-клітина.
Відомі найменші кубічні графи з числом схрещень 1-8 (послідовність A110507 в OEIS), найменший граф з числом схрещень 8 - це граф МакГі. Існує 5 неізоморфних кубічних графів порядку 24 з числом схрещень 8, один з них - узагальнений граф Петерсена G (12,5), відомий також як Граф Науру.
Граф МакГі має радіус 4, діаметр 4, хроматичної число 3 і хроматичний індекс 3. Він також 3-вершинно-зв'язний і 3-реберно-зв'язний.
Характеристичний многочлен графа МакЖі дорівнює .
Автоморфізм групи графа МакГі має порядок 32 і не транзитива щодо вершин - мається дві орбіти вершин довжини 8 і 16. Граф МакЖі - це найменша кубічна клітина, яка не є вершинно-транзитивною.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.