Граф Эрреры

Перейти к навигацииПерейти к поиску
граф Эрреры
Назван в честь Альфреда Эрреры
Вершин 17
Рёбер 45
Радиус 3
Диаметр 4
Обхват 3
Хроматическое число 4
Хроматический индекс 6
Свойствапланарный
гамильтонов
Логотип Викисклада Медиафайлы на Викискладе

Граф Эрреры — граф с 17 вершинами и 45 рёбрами. Альфред Эррера[англ.] опубликовал его в 1921 году как контрпример ошибочному доказательству Альфредом Кемпе[англ.] теоремы о четырёх красках[1][2]. Граф назвали именем Эрреры в статье 1998 года Хатчинсон и Вэгон[1].

Свойства

Граф Эрреры планарен, имеет хроматическое число 4, хроматический индекс 6, радиус 3, диаметр 4, обхват 3. Кликовая ширина графа равна 8[3]. Все вершины графа имеют степень 5 или 6, он вершинно 5-связен и рёберно 5-связен.

Граф Эрреры не вершинно транзитивен и его полная группа автоморфизмов изоморфна диэдральной группе порядка 20, группе симметрий десятиугольника, включая вращения и отражения.

Характеристический многочлен матрицы графа Эрреры рвен .

Хроматическое число графа Эрреры равно 4.
Хроматический индекс графа Эрреры ревен 6.
Граф Эрреры планарен.

Приложение к проблеме четырёх красок

Переплетённые цепи Эрреры[англ.] в графе Эрреры.

Теорема о четырёх красках утверждает, что вершины любого планарного графа могут быть выкрашены в четыре цвета так, что никакие две смежные вершины не выкрашены одним цветом. Доказательство теоремы опубликовал в 1879 году Альфред Кемпе[англ.], но в 1890 была обнаружена его ошибочность. Теореме о четырёх красках не было дано верного доказательства до 1976 года. Доказательство Кемпе можно преобразовать в алгоритм раскраски планарных графов, который также ошибочен. Контрпримеры доказательства были найдены в 1890 и 1896 (граф Пуссена), а позднее появились контрпримеры меньшего размера — граф Фрича[англ.] и граф Сойфера[4]. До работы Эрреры эти контрпримеры не давали повода считать, что алгоритм полностью неверен. Скорее показывали, что когда все, кроме одной, вершины графа выкрашены, метод Кемпе (который подразумевает модификацию цветов для расширения раскраски) не работает в этой конкретной раскраске. Граф Эрреры, с другой стороны, даёт контрпример полному методу Кемпе. Когда метод Кемпе применяется на графе Эрреры начиная с полностью незакрашенного графа (ни одной вершины не закрашено), он может потерпеть неудачу в поиске правильной раскраски для всего графа[1]. Кроме того, в отличие от графа Пуссена, все вершины в графе Эрреры имеют степень пять и более. Поэтому на этом графе невозможно избежать проблемные случаи метода Кемпе путём выбора вершин с малой степенью.

Рисунок показывает пример, как доказательство Кемпе может потерпеть неудачу для этого графа. На рисунке соседство областей карты образует граф Эрреры, который частично раскрашен в четыре цвета, но внешняя область не раскрашена. Ошибочное доказательство Кемпе следует идее расширения частичной раскраски, такой как приведена на рисунке, путём перекраски цепи Кемпе[англ.] связанных подграфов, имеющих только два цвета. Любая такая цепь может быть перекрашена с сохранением допустимости раскраски путём обмена двух цветов на всех вершинах цепочки. Доказательство Кемпе имеет различные случаи в зависимости от того, имеет ли следующая вершина для раскрашивания три, четыре или пять соседей и как эти соседи выкрашены. В показанном примере вершина, требующая раскраски, соответствует внешней области карты. Эту область невозможно раскрасить непосредственно, поскольку она уже имеет соседей всех четырёх цветов. Синие и жёлтые соседи соединены одной цепью Кемпе (показана как штриховая жёлтая линия), что предотвращает от раскраски всех их одним синим или жёлтым цветом с освобождением второго цвета. Аналогично, синие и зеленые соседи связаны другой цепью Кемпе (зелёные штриховые линии). В таком случае доказательство Кемпе попытается обменять одновременно цвета двух цепей, левой красной/жёлтой цепи и правой красной/зелёной цепи (штриховые красные линии). Синяя/зелёная цепь блокирует левую красную/жёлтую цепь от достижения правого края графа, а синяя/жёлтая цепь блокирует правую красную/зелёную цепь от достижения левого края, так что выглядит операция одновременного обмена цветов этих цепей безопасной операцией. Но, поскольку синяя/жёлтая и синяя/зелёная цепи пересекаются, есть область посередине фигуры, где красная/жёлтая и красная/зелёная цепи могут встретиться. Когда эти две цепи встречаются, одновременный обмен приводит к тому, что соседние зелёная и жёлтая вершины в средней области (так как вершины представляют верхнюю жёлтую и зелёную области на рисунке) обе превращаются в красные, получая недопустимую раскраску.

Приложения в химии

Химическая теория графов касается структуры молекул и других кластеров с точки зрения теории графов. Как сам граф Эрреры, так и его двойственный граф актуальны в этом контексте.

Атомы металлов, таких как золото, могут образовывать кластеры[англ.], в которых центральный атом окружён двенадцатью другими атомами в виде икосаэдра. Другой, больший, тип кластера может быть образован путём соединения таких икосаэдральных кластеров, так что центральный атом каждого кластера становится одним из граничных атомов другого кластера. Результирующий кластер из 19 атомов имеет два внутренних атома (центры двух икосаэдров) с 17 атомами на внешней оболочке в виде графа Эрреры[5].

Двойственным графом графа Эрреры является фуллерен[1] с 30 вершинами, который в химической литературе обозначается как [6] или [7] для обозначения симметрии и различия от фулеренов с 30 вершинами. Эта форма играет также центральную роль в построении фулуренов высокой размерности[7] .

Примечания

  1. ↑ 1 2 3 4 Hutchinson, Wagon, 1998, с. 170–174.
  2. ↑ Errera, 1921.
  3. ↑ Heule, Szeider, 2015, Table III.
  4. ↑ Gethner, Springer, 2003, с. 159–175.
  5. ↑ Michael, Mingos, 2015, с. 6680–6695.
  6. ↑ Mathur, Singh, Pande, 2016, с. 59.
  7. ↑ 1 2 Deza, Shtogrin, 1999, с. 9–18.

Литература

  • Alfred Errera. Du coloriage des cartes et de quelques questions d'analysis situs. — 1921. — (Ph.D. thesis).
  • Michel Deza, Mikhail Shtogrin. Three-, four-, and five-dimensional fullerenes // Southeast Asian Bulletin of Mathematics. — 1999. — Т. 23, вып. 1. — С. 9–18. — Bibcode: 1999math......6035D. — arXiv:math/9906035.
  • Ellen Gethner, William M., II Springer. How false is Kempe's proof of the four color theorem? // Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing. — Congressus Numerantium, 2003. — Т. 164. — С. 159–175.
  • Joan Hutchinson, Stan Wagon. Kempe revisited // American Mathematical Monthly. — 1998. — Т. 105, вып. 2. — С. 170–174. — doi:10.2307/2589650.
  • Rakesh Behari Mathur, Bhanu Pratap Singh, Shailaja Pande. Carbon Nanomaterials: Synthesis, Structure, Properties and Applications. — CRC Press, 2016. — С. 59. — ISBN 9781498702119.
  • Michael D., Mingos P. Structural and bonding patterns in gold clusters // Dalton Trans.. — 2015. — Т. 44, вып. 15. — С. 6680–6695. — doi:10.1039/c5dt00253b.
  • Marijn J. H. Heule, Stefan Szeider. A SAT approach to clique-width // ACM Transactions on Computational Logic. — 2015. — Vol. 16, № 3. — P. 24. — doi:10.1145/2736696.

Ссылки