Loading AI tools
З Вікіпедії, вільної енциклопедії
В математичній галузі теорії графів, неорієнтований граф Грея є двочастковим графом з 54 вершинами і 81 ребром. Це кубічний граф, де кожна вершина має рівно три ребра. Цей граф відкритий Меріаном К. Греєм в 1932 році (результат не був оприлюднений), потім виявлений незалежно Баувером (Bouwer) у 1968 року у відповідь на питання, яке задав Джон Фолкман[en] у 1967 році. Граф Грея є першим відомим прикладом кубічного графу, що має алгебраїчну властивість бути реберним, але не вершинно-транзитивним (див. нижче).
Граф Грея | |
---|---|
Названо на честь | Marion Cameron Gray |
Вершин | 54 |
Ребер | 81 |
Радіус | 6 |
Діаметр | 6 |
Обхват | 8 |
Автоморфізм | 1296 |
Хроматичне число | 2 |
Хроматичний індекс | 3 |
Число черг | 2 |
Властивості | Кубічний Напівсиметричний Гамільтонів граф Двочастковий граф |
Граф Грея має хроматичне число що дорівнює 2, хроматичний індекс 3, радіус 6 і діаметр 6. Він також є 3-вершинно-зв'язний та 3-реберно-зв'язний не планарний граф.
Граф Грея може бути побудований (Bouwer, 1972) з 27 точок, сітки 3×3×3 і 27 паралельних прямих через ці точки. Ця колекція з точок і прямих утворює проективні конфігурації: через кожну точку проходять три прямі, і на кожній прямій лежать три точки. В цій конфігурації граф Грея є графом Леві; він має вершину для кожної точки у кожному рядку конфігурації, і ребра для кожної пари точки з прямою, якщо точка лежить на прямій. Ця конструкція узагальнюється для будь-якої розмірності N ≥ 3, поступаючись N-валентному графу Леві, алгебраїчними властивостями, близькими до властивостей графу Грея. Граф Грея з'являється у вигляді різного роду графів Леві. Він є першим в нескінченному сімействі аналогічно побудованих кубічних графів.
Марушич і Пісанскі (Marušič та Pisanski, 2000) дають декілька альтернативних методів побудови графу Грея. Як і у будь-якого двочасткового графу, у нього немає непарних циклів довжини, а також відсутні цикли з чотирьох або шести вершин, тому обхват графу Грея дорівнює 8. Найпростіша орієнтована поверхня, на якій граф Грея може впроваджуватися має рід 7 (Marušič, Pisanski та Wilson, 2005).
Граф Грея та Гамільтонів граф можуть бути побудовані з LCF-нотації:
Група автоморфізмів графу Грея — це група 1296 порядку. Вона діє транзитивно на ребрах графу, але не на своїх вершинах, отже, вона є симетричною, тому приймає кожне ребро будь-якому іншому ребру, але не приймає кожну вершину будь-якій іншій вершині. Вершини, які відповідають точкам базової конфігурації можуть бути тільки симетричні іншим вершинам, які відповідають точкам, і вершини, відповідні прямі, можуть бути симетричні тільки до інших вершин, які відповідають прямим. Тому граф Грея — це напівсиметричний граф і мінімальний можливий кубічний напівсиметричний граф.
Характеристичний поліном графу Грея:
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.