В математической области теории графов , то граф Эррера представляет собой график с 17 вершинами и 45 ребрами . Альфред Эррера опубликовал его в 1921 году как контрпример к ошибочному доказательству Кемпе теоремы о четырех цветах ; [1] [2] он был назван в честь Эрреры Хатчинсоном и Вагоном (1998) . [1]
График Эрреры | |
---|---|
Названный в честь | Альфред Эррера |
Вершины | 17 |
Края | 45 |
Радиус | 3 |
Диаметр | 4 |
Обхват | 3 |
Автоморфизмы | 20 ( Д 10 ) |
Хроматическое число | 4 |
Хроматический индекс | 6 |
Характеристики | Планарный гамильтониан |
Таблица графиков и параметров |
Характеристики
График Эррера является плоским и имеет хроматическое число 4, хроматический индекс 6, радиус 3, диаметр 4 и распорку 3. всей его вершина степени 5 или 6 , и это представляет собой 5- вершинный связной граф и 5- ребер соединены график .
Граф Эррера не является вершинно-транзитивным графом, и его полная группа автоморфизмов изоморфна группе диэдра порядка 20, группе симметрий десятиугольника , включая как вращения, так и отражения.
Характеристический полином графа Эррера является.
Приложение к теореме о четырех цветах
Теорема о четырех цветах утверждает, что вершины любого плоского графа можно раскрасить в четыре цвета, так что никакие две соседние вершины не имеют одинаковых цветов. Ошибочное доказательство было опубликовано в 1879 году Альфредом Кемпе , но оно оказалось ошибочным к 1890 году. Теорема о четырех цветах не имела действительного доказательства до 1976 года. Доказательство Кемпе можно преобразовать в алгоритм для раскрашивания плоских графов, который также является ошибочный. Контрпримеры к его доказательству были найдены в 1890 и 1896 годах ( граф Пуссена ), а позже граф Фрича и граф Сойфера предоставили два меньших контрпримера. [3] Однако до работы Эрреры эти контрпримеры не показали, что весь алгоритм раскраски дает сбой. Скорее они предположили, что все вершины графа, кроме одной, уже были раскрашены, и показали, что метод Кемпе (который якобы изменил раскраску, чтобы распространить ее на все графы) не удался в этих предварительно раскрашенных экземплярах. График Эрреры, с другой стороны, представляет собой контрпример ко всему методу Кемпе. Когда этот метод запускается на графе Эрреры, начиная с отсутствия раскрашенных вершин, он может не найти правильную раскраску для всего графа. [1] Кроме того, в отличие от графа Пуссена, все вершины в графе Эрреры имеют степень пять или больше. Следовательно, на этом графе невозможно избежать проблемных случаев метода Кемпе, выбирая вершины более низкой степени.
На рисунке показан пример того, как доказательство Кемпе может потерпеть неудачу для этого графика. На рисунке смежности между областями этой карты образуют граф Эррера, частично четырехцветный с неокрашенной внешней областью. Ошибочное доказательство Кемпе следует идее расширения частичных раскрасок, подобных этой, путем перекраски цепочек Кемпе , связанных подграфов, которые имеют только два цвета. Любую такую цепочку можно перекрасить, сохранив справедливость раскраски, поменяв местами два ее цвета на всех вершинах цепочки. Доказательство Кемпе имеет разные случаи в зависимости от того, имеет ли следующая раскрашиваемая вершина три, четыре или пять соседей, и от того, как эти соседи окрашены. В показанном случае следующей раскраской будет вершина, соответствующая внешней области карты. Этот регион нельзя раскрасить напрямую, потому что у него уже есть соседи всех четырех разных цветов. Синие и желтые соседи соединены одной цепочкой Кемпе (показаны пунктирными желтыми линиями на изображении), что предотвращает изменение их цвета как синими, так и желтыми, а также освобождение цвета. Точно так же синие и зеленые соседи соединены другой цепочкой Кемпе (пунктирные зеленые линии). В таком случае доказательство Кемпе будет пытаться одновременно поменять местами цвета двух цепочек Кемпе, левой красно-желтой цепочки и правой красно-зеленой цепочки (пунктирные красные линии). Сине-зеленая цепочка блокирует левую красно-желтую цепочку от достижения правой стороны графика, а сине-желтая цепочка блокирует попадание правой красно-зеленой цепочки в левую часть, поэтому может показаться, что одновременно меняя цвета две цепи - безопасная операция. Но поскольку сине-желтые и сине-зеленые цепи пересекают друг друга, а не остаются разделенными, в середине рисунка есть область, где могут встречаться красно-желтые и красно-зеленые цепи. Когда эти две цепочки встречаются в середине, одновременная перестановка приводит к тому, что соседние желтые и зеленые вершины в этой средней области (например, вершины, представленные верхней желтой и зеленой областями на рисунке) становятся красными, что приводит к неправильной окраске.
Приложения в химии
Химическая теория графов касается теоретико-графовой структуры молекул и других кластеров атомов. В этом контексте важны как сам граф Эрреры, так и его дуальный граф .
Атомы металлов, таких как золото, могут образовывать кластеры, в которых центральный атом окружен еще двенадцатью атомами, по образцу икосаэдра . Другой, более крупный тип кластера может быть сформирован путем объединения двух из этих икосаэдрических кластеров, так что центральный атом каждого кластера становится одним из граничных атомов для другого кластера. В результате кластер из 19 атомов имеет два внутренних атома (центры двух икосаэдров) с 17 атомами во внешней оболочке в образце графа Эррера. [4]
Двойственный граф графа Эррера является фуллерен [1] с 30 вершинами, обозначенных в химии литературе как C 30 (D 5 ч ) [5] или Р 30 (Д 5 ч ) [6] , чтобы указать его симметрию и различать это от других 30-вершинных фуллеренов. Эта форма также играет центральную роль в создании фуллеренов более высокой размерности. [6]
Рекомендации
- ^ a b c d Хатчинсон, Джоан ; Вагон, Стэн (1998), "вновь Кемпе", American Mathematical Monthly , 105 (2): 170-174, DOI : 10,2307 / 2589650 , MR 1605875.
- ^ Эррера, А. (1921), Du coloriage des cartes et de quelques questions d'analysis situs , доктор философии. Тезис.
- ^ Гетнер, Эллен; Спрингер, Уильям М., II (2003 г.), «Насколько ложно доказательство Кемпе теоремы о четырех цветах?», Труды Тридцать четвертой Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям, Congressus Numerantium , 164 : 159–175 , MR 2050581.
- ^ Майкл, Д .; Мингос, П. (2015), "Структурные и связывающие узоры в кластерах золота", Dalton Trans. , 44 (15): 6680-6695, DOI : 10.1039 / c5dt00253b.
- ^ Матур, Ракеш Бехари; Сингх, Бхану Пратап; Панде, Шайладжа (2016), Углеродные наноматериалы: синтез, структура, свойства и применение , CRC Press, стр. 59, ISBN 9781498702119.
- ^ а б Деза, Мишель ; Штогрин, Михаил (1999), «Трех-, четырех- и пятимерные фуллерены», Вестник математики Юго-Восточной Азии , 23 (1): 9–18, arXiv : math / 9906035 , Bibcode : 1999math ..... .6035D , Руководство по эксплуатации 1810781.
Внешние ссылки
- Вайсштейн, Эрик В. «Граф Эррера» . MathWorld .