58047

Автор(ы): 

Автор(ов): 

3

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

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

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

Название: 

Алгебраические методы раскраски кубических графов

Электронная публикация: 

Да

ISBN/ISSN: 

ISSN 2079-3537

DOI: 

10.26583/sv.12.2.03

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

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

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

T. 12, № 2

Город: 

  • Москва

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

  • МИФИ

Год издания: 

2020

Страницы: 

21-36 http://sv-journal.org/2020-2/03/
Аннотация
В работе рассмотрены алгебраические методы раскраски кубических графов, осно-ванные на теореме Тэйта. Для описания раскраски плоского кубического графа приме-няется групповое преобразование Клейна четвертого порядка. Для перехода к раскрас-ке графа производится раскраска ребер базисных циклов. Рассмотрен математический аппарат для описания топологического рисунка графа. На основе раскраски ребер рас-смотрены вопросы формирования цветных дисков и математическое описание опера-ции ротации цветных дисков с последующей перекраской ребер. Показано, что опера-ция ротации цветных дисков может быть описана как кольцевая сумма циклов. Для однозначного описания представления цветных дисков посредством базисных циклов введено понятие вложимости цветных дисков. Приведены примеры применения опе-рации ротации цветных дисков. В статье установлена связь между системой индуциро-ванных циклов порождаемой вращением вершин графа и раскраской 2-факторов ку-бического графа. Показано, что кольцевая сумма всех циклов входящих в цветные 2-факторы графа есть пустое множество. Также в статье рассмотрены вопросы раскраски непланарных кубических графов. Показана связь между базисными циклами и ободом в непланарном кубическом графе и кольцевой суммой цветных 2-факторов. Указана зависимость между цветным вращением вершин плоского кубического графа и за-мкнутыми маршрутами Хивуда.

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

Давидовский М.В., Курапов С.В., Толок А.В. Алгебраические методы раскраски кубических графов // Научная визуализация. 2020. T. 12, № 2. С. 21-36 http://sv-journal.org/2020-2/03/.