48180

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Визуальный алгоритм раскраски плоских графов

DOI: 

10.26583/sv.10.3.01

Наименование источника: 

  • Научная визуализация

Обозначение и номер тома: 

Т. 10, № 3

Город: 

  • Москва

Издательство: 

  • МИФИ

Год издания: 

2018

Страницы: 

1-33
Аннотация
В статье рассматривается задача раскраски плоских графов. Авторами предложен визуальный алгоритм раскраски плоских графов и представлен дедуктивный способ доказательства теоремы о четырех красках, основанный на свойствах группы Клейна четвертого порядка. Показано, что произвольный кубический граф имеет три раскрашенных 2-фактора и добавление цветов происходит в соответствии с законами трансформации группы Клейна четвертого порядка. Рассмотрены свойства раскрашенных плоских кубических графов. Сформулированы и доказаны теоремы о существовании цветного диска, проходящего по сцепленным ребрам, и о реберной раскраске плоского кубического графа. Показано, что теорема о четырех красках может быть получена как следствие этих теорем. С целью перекраски ребер в раскрашенном плоском кубическом графе введена новая операция – ротация цветного диска. В статье приведены примеры решения задачи раскраски плоских графов.

Библиографическая ссылка: 

Курапов С.В., Давидовский М.В., Толок А.В. Визуальный алгоритм раскраски плоских графов // Научная визуализация. 2018. Т. 10, № 3. С. 1-33.