1. Введение

В работе [3] была доказана теорема о существовании цветного диска проходящего по сцепленным ребрам в базисном простом цикле плоского правильно раскрашенного кубического графа H. На основании доказанной теоремы было показано, что задачу о четырех красках можно представить как её следствие. Введение новой операции – ротации цветного диска – позволило производить перекраску ребер в плоском раскрашенном кубическом графе и построить визуальный алгоритм раскраски. Представленный метод позволяет рекурсивно производить раскраску в три цвета ребер последующего плоского кубического графа Н с n вершинами на основе предыдущего раскрашенного плоского кубического графа с n-2 вершинами.

С точки зрения раскраски между максимальным плоским графом G ^¢ и двойственным к нему плоским кубическим графом Н существует связь, устанавливаемая следующей теоремой Тэйта.

Теорема 1. ( Тэйт ) [4]. Пусть Н — плоский однородный кубический граф без перешейков; необходимое и достаточное условие возможности такого раскрашивания граней графа четырьмя цветами, при котором ни какие две смежные грани не окрашиваются в одинаковый цвет, состоит в том, чтобы хроматический класс графа Н был равен трем.

Таким образом, раскраска ребер и граней плоского кубического графа адекватна раскраске вершин и ребер в максимально плоском графе G ^¢ . Поэтому удобно рассматривать только процесс раскраски плоского кубического графа.

Теорема Тейта не только устанавливает связь между раскраской вершин максимально плоского графа и раскраской ребер двойственного к нему плоского кубического графа, но и указывает на применение для раскраски графа операции преобразования группы Клейна четвертого порядка [2]. Данное преобразование позволяет связать в единое целое раскраску граней плоского кубического графа Н в четыре цвета и раскраску ребер в три цвета.

+ 0 1 2 3 W W R B G R R W G B B B G W R G G B R W

(1)

Дальнейшее развитие методов раскраски ребер и граней в плоском кубическом графе показало наличие тесной связи между раскраской и топологическим рисунком плоского графа. В данной работе будем рассматривать алгебраические раскраски в плоском кубическом графе

2. Математические структуры для описания топологического рисунка графа

Граф G = ( V , E ), как правило, задается множеством вершин V , множеством ребер E и трехместным предикатом Р в виде матрицы смежностей или матрицы инциденций [1,6] без описания рисунка графа. Необходимым понятием для топологического описания плоского рисунка графа G является понятие вращения вершин графа, введенное Г. Рингелем [5].

Определение 1. Для данного графа G вращение вершины А – это ориентированный циклический порядок (или циклическая перестановка) всех ребер, инцидентных вершине А.

 

Рис. 1. Граф G и его вращение вершин.

 

Определение 2. Вращение вершин графа – совокупность вращений всех его вершин.

Вращение всех вершин графа будем представлять в виде диаграмм, и обозначать . Например, для нашего рисунка графа (рис. 1) диаграмма вращения вершин имеет вид:

1:	2	3	4
2:	6	5	3	1
3:	2	5	4	1
4:	1	3	5	6
5:	3	2	6	4
6:	2	4	5

Для удобства в диаграмме вращения вершин цифры означают номера вершин.

В свою очередь, вращение вершин графа индуцирует систему ориентированных простых циклов. Для получения такой системы осуществляем обход по ребрам с учетом перехода с ребра на ребро согласно вращению вершин. Заметим, что во вращении каждое ориентированное ребро всегда появляется дважды, второй раз – в противоположном направлении и в другом цикле [5].

Например, для представленного на рис. 1, плоского графа G с вращением имеем следующую систему индуцированных циклов: < v ₁ ,v ₃ ,v ₂ >, < v ₁ ,v ₄ ,v ₃ >, < v ₂ ,v ₃ ,v ₅ >, < v ₅ ,v ₃ ,v ₄ >, < v ₂ ,v ₅ ,v ₆ >, < v ₆ ,v ₅ ,v ₄ >, < v ₂ ,v ₆ ,v ₄ ,v ₁ >. Индуцированные циклы будем записывать в виде циклического кортежа вершин, описывающего замкнутый ориентированный маршрут (либо по часовой стрелке, либо против, но всегда оговаривая это). Индуцированные циклы также можно представлять в виде множества ребер: {e ₁ ,e ₂ ,e ₄ }, {e ₂ ,e ₃ ,e ₇ }, {e ₇ ,e ₈ ,e ₉ }, {e ₄ ,e ₅ ,e ₈ }, {e ₅ ,e ₆ ,e ₁₁ }, {e ₉ ,e ₁₀ ,e ₁₁ }. Еще один индуцированный цикл {e ₁ ,e ₃ ,e ₆ ,e ₁₀ } является ободом графа и равен кольцевой сумме циклов описывающих границы граней рисунка графа [5]. Таким образом, вращение вершин графа – это не только диаграмма вращения вершин, но и система простых циклов являющихся границами граней (2-клеток) плоского рисунка графа. С другой стороны, такие циклы составляют базис подпространства циклов. Впредь мы будем их называть базисными циклами .

Иногда индуцированные ориентированные циклы можно записать в виде замкнутой последовательности ориентированных ребер (дуг). Например, цикл < v ₁ ,v ₃ ,v ₂ > = (v ₁ ,v ₃ ) + + (v ₃ ,v ₂ ) + (v ₂ ,v ₁ ).

Определение 3. Будем говорить, что топологический рисунок плоского графа – это граф с заданным вращением вершин

3. Построение цветного диска

Таким образом, вращение вершин индуцирует простые циклы, которые образуют базис в подпространстве циклов графа С . Для установления раскраски плоского кубического графа H необходимо произвести раскраску его ребер (рис. 2).

 

Рис. 2. Раскраска ребер в кубическом графе Н ₁ .

 

Если кубический граф Н имеет хроматический класс равный трем, то его ребра должны быть раскрашены в три цвета. Раскраска предполагает наличие трех разноцветных ребер для каждой вершины графа Н . Кубический граф имеющий хроматический класс равный трем будем называть раскрашенным плоским кубическим графом Н . Например, кубический граф представленный на рис. 2 является раскрашенным кубическим графом Н . Здесь белый цвет будем обозначать буквой W или цифрой 0, а на рисунках графа ребра данного цвета будем представлять штрихпунктирной линией. Красный цвет будем обозначать буквой R или цифрой 1, а на рисунках графа ребра данного цвета будем представлять сплошной линией. Синий цвет будем обозначать буквой B или цифрой 2, а на рисунках графа ребра данного цвета будем представлять точечной линией. Зеленый цвет будем обозначать буквой G или цифрой 3, а на рисунках графа ребра данного цвета будем представлять пунктирной линией. Согласно теореме Тэйта раскраска ребер индуцирует раскраску граней плоского кубического графа Н , а раскраска граней, в свою очередь, индуцирует раскраску ребер.

 

Рис. 3. Обозначение цветных линий

 

Определение 4. В раскрашенном плоском кубическом графе цветной диск – это замкнутый маршрут четной длины с ребрами только двух цветов.

Таким образом, красный цветной диск состоит только из синих и зеленных ребер. Зеленый цветной диск состоит только из синих и красных ребер. Синий цветной диск состоит только из зеленых и красных ребер.

Процесс построения цветного диска можно рассматривать как последовательность подключения цветных ребер двух цветов

D = < v 1 ,e 1 ,v 2 ,e 2 ,…,v p-1 ,e p-1 v p ,e p ,v 1 >

(2)

где p – длина цветного диска.

Будем обозначать цветной диск латинской буквой D и именем цвета. Например, красный цветной диск D R плоского кубического графа Н на рис. 2 можно представить в виде кортежа:

DR = < v ₁ ,e ₂ ,v ₅ ,e ₁₀ ,v ₁₀ ,e ₁₂ ,v ₆ ,e ₁₁ ,v ₇ ,e ₁₃ ,v ₈ ,e ₁₄ ,v ₉ ,e ₉ ,v ₄ ,e ₆ ,v ₃ ,e ₄ ,v ₂ ,e _1, v ₁ >;

или с учетом цвета ребра, указанного в квадратных скобках:

DR = < e ₂ [2],e ₁₀ [3],e ₁₂ [2],e ₁₁ [3],e ₁₃ [2],e ₁₄ [3],e ₉ [2],e ₆ [3],e ₄ [2],e ₁ [3]>.

Цветной диск в плоском кубическом графе Н можно представлять в виде кольцевого сложения циклов [6]. Причем кольцевое сложение осуществляется в порядке соприкосновения двух циклов, имеющих общее ребро цвета диска. Например, раскрашенные индуцированные циклы графа Н на рис. 2,

с ₁ = {e ₂ [2],e ₃ [1],e ₁₀ [3],e ₁₂ [2]};            с ₂ = {e ₁ [3],e ₃ [1],e ₅ [1],e ₁₁ [3]};

с ₃ = {e ₄ [2],e ₅ [1],e ₇ [1],e ₁₃ [2]};              с ₄ = {e ₆ [3],e ₇ [1],e ₉ [2],e ₁₄ [3]};

с ₅ = {e ₈ [1],e ₉ [2],e ₁₀ [3],e ₁₅ [1]};            с ₆ = {e ₁₁ [3],e ₁₂ [2],e ₁₃ [2],e ₁₄ [3],e ₁₅ [1]};

с ₀ = {e ₁ [3],e ₂ [2],e ₄ [2],e ₆ [3],e ₈ [1]}.

образуют следующие цветные 2-факторы:

R _c = с ₁ Å с ₂ Å с ₃ Å с ₄ = {e ₂ [2],e ₃ [1],e ₁₀ [3],e ₁₂ [2]} Å

Å {e ₁ [3],e ₃ [1],e ₅ [1],e ₁₁ [3]} Å {e ₄ [2],e ₅ [1],e ₇ [1],e ₁₃ [2]} Å

Å {e ₆ [3],e ₇ [1],e ₉ [2],e ₁₄ [3]} =

= {e ₂ [2],e ₁₀ [3],e ₁₂ [2],e ₁ [3],e ₅ [1],e ₁₁ [3]} Å {e ₄ [2],e ₅ [1],e ₇ [1],e ₁₃ [2]} Å

Å {e ₆ [3],e ₇ [1],e ₉ [2],e ₁₄ [3]} =

= {e ₂ [2],e ₁₀ [3],e ₁₂ [2],e ₁ [3],e ₁₁ [3],e ₄ [2],e ₇ [1],e ₁₃ [2]} Å

Å {e ₆ [3],e ₇ [1],e ₉ [2],e ₁₄ [3]} =

= {e ₂ [2],e ₁₀ [3],e ₁₂ [2],e ₁ [3],e ₁₁ [3],e ₄ [2],e ₁₃ [2],e ₆ [3],e ₉ [2],e ₁₄ [3]} =

= < e ₂ [2],e ₁₀ [3],e ₁₂ [2],e ₁₁ [3],e ₁₃ [2],e ₁₄ [3],e ₉ [2],e ₆ [3],e ₄ [2],e ₁ [3]>;

B _c = (с ₄ Å с ₅ ) Å (с ₂ ) = ({e ₆ [3],e ₇ [1],e ₉ [2],e ₁₄ [3]} Å

Å {e ₈ [1],e ₉ [2],e ₁₀ [3],e ₁₅ [1]}) Å

Å ({e ₁ [3],e ₃ [1],e ₅ [1],e ₁₁ [3]}) = ({e ₆ [3],e ₇ [1],e ₁₄ [3],e ₈ [1],e ₁₀ [3],e ₁₅ [1]}) Å

Å ({e ₁ [3],e ₃ [1],e ₅ [1],e ₁₁ [3]}) = (< e ₆ [3],e ₇ [1],e ₁₄ [3],e ₁₅ [1],e ₁₀ [3],e ₈ [1]>),

(< e ₁ [3],e ₅ [1],e ₁₁ [3],e ₃ [1]>);

G _c = (с ₁ Å с ₅ ) Å (с ₃ ) = ({e ₂ [2],e ₃ [1],e ₁₀ [3],e ₁₂ [2]} Å

Å {e ₈ [1],e ₉ [2],e ₁₀ [3],e ₁₅ [1]}) Å

Å ({e ₄ [2],e ₅ [1],e ₇ [1],e ₁₃ [2]}) = ({e ₂ [2],e ₃ [1],e ₁₂ [2],e ₈ [1],e ₉ [2],e ₁₅ [1]}) Å

Å ({e ₄ [2],e ₅ [1],e ₇ [1],e ₁₃ [2]}) = (< e ₂ [2],e ₃ [1],e ₁₂ [2],e ₁₅ [1],e ₉ [2],e ₈ [1]>),

(< e ₁₃ [2],e ₅ [1],e ₄ [2],e ₇ [1]>).

Так как в раскраске плоского графа дважды участвуют все ребра (согласно теореме Маклейна), то из построения следует:

Следствие 1. Кольцевая сумма всех ребер входящих в цветные диски есть пустое множество

(3)

Особое место занимают белые циклы , не входящие в выражение (2), где ребра могут быть раскрашены тремя цветами. Для нашего примера:

W _c = c ₆ c ₀ = ({e ₁₁ [3],e ₁₂ [2],e ₁₃ [2],e ₁₄ [3],e ₁₅ [1]}) ({e ₁ [3],e ₂ [2],e ₄ [2],e ₆ [3],e ₈ [1]}).

 

Если образование цветных дисков как замкнутый маршрут ребер формируется однозначно, то формирование цветных дисков циклами имеет свои специфические черты. Для этого рассмотрим следующий рисунок раскрашенного графа Н ₂ (рис. 4)

Для данного кубического графа Н ₂ выберем базисные циклы:

c ₁ = {e ₁ [3],e ₂ [1],e ₅ [2],e ₁₇ [3]}, c ₂ = {e ₄ [1],e ₅ [2],e ₆ [3],e ₈ [1],e ₁₁ [3],e ₁₆ [1]},

c ₃ = {e ₁₀ [3],e ₁₁ [2],e ₁₂ [1],e ₁₄ [3]}, c ₄ = {e ₁₄ [3],e ₁₅ [2],e ₁₆ [1],e ₁₇ [3]},

c ₅ = {e ₂ [1],e ₃ [2],e ₁₂ [1],e ₁₃ [2],e ₁₅ [2],e ₁₉ [3],e ₂₈ [1]},

c ₆ = {e ₈ [1],e ₉ [2],e ₁₀ [3],e ₁₃ [2],e ₂₁ [1],e ₂₃ [3],e ₂₅ [1],e ₂₆ [3]},

c ₇ = {e ₆ [3],e ₇ [2],e ₉ [2],e ₂₀ [3]},

c ₈ = {e ₁ [3],e ₃ [2],e ₄ [1],e ₇ [2],e ₁₈ [1]}, c ₉ = {e ₂₂ [2],e ₂₃ [3],e ₂₄ [2],e ₃₀ [3],e ₃₂ [1]},

c ₁₀ = {e ₂₄ [2],e ₂₅ [1],e ₂₇ [2],e ₃₃ [1]},

c ₁₁ = {e ₂₆ [3],e ₂₇ [2],e ₂₈ [1],e ₂₉ [2],e ₃₄ [3],e ₃₅ [1]},

c ₁₂ = {e ₃₀ [3],e ₃₁ [2],e ₃₃ [1],e ₃₄ [3]}, c ₁₃ = {e ₃₁ [2],e ₃₂ [1],e ₃₅ [1],e ₃₆ [3]}.

Формируем обод графа c ₀ = {e ₁₈ [1],e ₁₉ [3],e ₂₀ [3],e ₂₁ [1],e ₂₂ [2],e ₂₉ [2],e ₃₆ [3]}.

Рассмотрим случай формирования цветного диска DB, состоящего из следующих циклов:

DB = c ₄ Å c ₅ Å c ₆ Å c ₇ Å c ₈ = {e ₁₄ [3],e ₁₅ [2],e ₁₆ [1],e ₁₇ [3]} Å

Å {e ₂ [1],e ₃ [2],e ₁₂ [1],e ₁₃ [2],e ₁₅ [2],e ₁₉ [3],e ₂₈ [1]} Å

Å {e ₈ [1],e ₉ [2],e ₁₀ [3],e ₁₃ [2],e ₂₁ [1],e ₂₃ [3],e ₂₅ [1],e ₂₆ [3]} Å

Å {e ₆ [3],e ₇ [2],e ₉ [2],e ₂₀ [3]} Å {e ₁ [3],e ₃ [2],e ₄ [1],e ₇ [2],e ₁₈ [1]} =

= {e ₁₄ ,e ₁₆ ,e ₁₇ ,e ₂ ,e ₁₂ ,e ₈ ,e ₁₀ ,e ₆ ,e ₁ ,e ₄ ,e ₁₉ ,e ₂₈ ,e ₂₁ ,e ₂₃ ,e ₂₅ ,c ₂₆ ,e ₂₀ ,e ₁₈ } =

=< e ₁₄ [3],e ₁₆ [1],e ₁₇ [3],e ₂ [1],e ₁ [3],e ₄ [1],e ₆ [3],e ₈ [1],e ₁₀ [3],e ₁₂ [1]> Å

< e ₁₉ [3],e ₂₈ [1],e ₂₆ [3],e ₂₅ [1],e ₂₃ [3],e ₂₁ [1],e ₂₀ [3],e ₁₈ [1]>.

Как видно, данная совокупность циклов формирует два одноцветных диска. Для однозначного формирования цветного диска следует добавить циклы с ₁ ,с ₂ ,с ₃ , которые в свою очередь также однозначно формируют цветной диск

Для графа, представленного на рис. 6, цветные диски до ротации имеют следующий вид:

DB ₁ = с ₁ Å с ₂ Å с ₃ = < e ₁₄ [3],e ₁₆ [1],e ₁₇ [3],e ₂ [1],e ₁ [3],e ₄ [1],e ₆ [3],

e ₈ [1],e ₁₀ [3],e ₁₂ [1]>;

DB ₂ = c ₄ Å c ₅ Å c ₆ Å c ₇ Å c ₈ Å с ₁ Å с ₂ Å с ₃ =

= < e ₁₉ [3],e ₂₈ [1],e ₂₆ [3],e ₂₅ [1],e ₂₃ [3],e ₂₁ [1],e ₂₀ [3],e ₁₈ [1] _> .

DB ₃ = c ₁₂ Å c ₁₃ = < e ₃₀ [3],e ₃₂ [1],e ₃₆ [3],e ₃₅ [1],e ₃₄ [3],e ₃₃ [1]>;

Таким образом, возникает понятие вложимости цветных дисков. Рассматривая циклы данного графа Н _2, можно сказать, что циклы цветного диска DB ₁ вложимы в цветной диск DB ₂ .

Построим все цветные диски кубического графа Н ₂ (рис. 4).

DR ₁ = c ₁ Å c ₅ Å c ₃ Å c ₁₁ Å c ₁₃ Å c ₉ =

= < e ₁₉ [3],e ₂₉ [2],e ₃₆ [3],e ₂₂ [2],e ₂₃ [3],e ₂₄ [2],e ₃₀ [3],e ₃₁ [2],e ₃₄ [3],e ₂₇ [2],

e ₂₆ [3],e ₁₃ [2],e ₁₀ [3], e ₁₁ [2],e ₁₄ [3],e ₁₅ [2],e ₁₇ [3],e ₅ [2],e ₁ [3],e ₃ [2]>;

DR ₂ = c ₇ = < e ₇ [2],e ₂₀ [3],e ₉ [2],e ₆ [3]>;

DG ₁ = с ₁₀ = < e ₂₄ [2],e ₃₃ [1],e ₂₇ [2],e ₂₅ [1]>;

DG ₂ = c ₁ Å c ₃ Å c ₄ Å c ₆ Å c ₈ Å с ₉ Å с ₁₀ Å с ₁₁ Å с ₁₂ =

= < e ₁₈ [1],e ₃ [2],e ₂ [1],e ₁₅ [2],e ₁₂ [1],e ₁₃ [2],e ₂₈ [1],e ₂₉ [2],e ₃₅ [1],e ₃₁ [2],e ₃₂ [1],

e ₂₂ [2],e ₂₁ [1], e ₉ [2],e ₈ [1],e ₁₁ [2],e ₁₆ [1],e ₅ [2],e ₄ [1],e ₇ [2]>;

Как видим, диск DG ₂ вложим в диск DG ₁ .

 

 

W _c = c ₀ = < e ₁₈ [1],e ₁₉ [3],e ₂₀ [3],e ₂₁ [1],e ₂₂ [2],e ₂₉ [2],e ₃₆ [3]>;

Цветные 2-факторы образуются как кольцевая сумма соответствующих цветных дисков. Например, для графа Н ₂ красные диски представлены на рис. 5.

R _с = D R ₁ Å D R ₂ = (c ₁ Å c ₅ Å c ₃ Å c ₁₁ Å c ₁₃ Å c ₉ ) Å (c ₇ ) =

= < e ₁₉ [3],e ₂₉ [2],e ₃₆ [3],e ₂₂ [2],e ₂₃ [3],e ₂₄ [2],e ₃₀ [3],e ₃₁ [2],e ₃₄ [3],e ₂₇ [2],

e ₂₆ [3],e ₁₃ [2],e ₁₀ [3],e ₁₁ [2], e ₁₄ [3],e ₁₅ [2],e ₁₇ [3],e ₅ [2],e ₁ [3],e ₃ [2]> Å

Å < e ₇ [2],e ₂₀ [3],e ₉ [2],e ₆ [3]>;

 

 

Синие диски представлены на рис. 6.

B _с = DB ₁ Å DB ₂ Å DB ₃ = (с ₁ Å с ₂ Å с ₃ ) Å (c ₄ Å c ₅ Å c ₆ Å c ₇ Å c ₈ Å с ₁ Å с ₂ Å

Å с ₃ ) Å (c ₁₂ Å c ₁₃ ) = (c ₄ Å c ₅ Å c ₆ Å c ₇ Å c ₈ ) Å (c ₁₂ Å c ₁₃ ) =

= < e ₁₄ [3],e ₁₆ [1],e ₁₇ [3],e ₂ [1],e ₁ [3],e ₄ [1],e ₆ [3],e ₈ [1],e ₁₀ [3],e ₁₂ [1]> Å

Å < e ₁₈ [1],e ₂₀ [3],e ₂₁ [1],e ₂₃ [3],e ₂₅ [1],e ₂₆ [3],e ₂₈ [1],e ₁₉ [3]> Å

Å < e ₃₀ [3],e ₃₂ [1],e ₃₆ [3],e ₃₅ [1],e ₃₄ [3],e ₃₃ [1]>;

Зеленные диски представлены на рис. 7.

G _с = DG ₁ Å DG ₂ = (c ₈ Å c ₁ Å c ₄ Å c ₃ Å c ₆ Å c ₁₁ Å c ₁₂ Å c ₉ Å c ₁₀ ) Å (c ₁₀ ) =

= c ₈ Å c ₁ Å c ₄ Å c ₃ Å c ₆ Å c ₁₁ Å c ₁₂ Å c ₉ =

= < e ₂ [1],e ₁₅ [2],e ₁₂ [1],e ₁₃ [2],e ₂₈ [1],e ₂₉ [2],e ₃₅ [1],e ₃₁ [2],e ₃₂ [1],e ₂₂ [2],e ₂₁ [1],

e ₉ [2],e ₈ [1],e ₁₁ [2], e ₁₆ [1],e ₅ [2],e ₄ [1],e ₇ [2],e ₁₈ [1],e ₃ [2]> Å < e ₂₄ [2],e ₃₃ [1],

e ₂₇ [2],e ₂₅ [1]>.

Кольцевая сумма всех цветных дисков одного цвета образует 2-фактор того же цвета. Например, на рис. 5-7 представлены цветные 2-факторы.

; ;

Из построения следует:

Следствие 2. Кольцевая сумма всех циклов участвующих в формировании цветных 2-факторов есть пустое множество,

R c B c G c =

(4)

Следующее выражение устанавливает связь между цветными 2-факторами и базисными циклами плоского кубического графа:

(5)

Следствие 3. Удвоенная сумма базисных циклов топологического рисунка и обода равна кольцевой сумме циклов цветных 2-факторов плюс удвоенная сумма белых циклов.

4. Ротация цветных дисков

Под ротацией цветного гамильтонова диска будем понимать изменение последовательности раскраски ребер данного диска. Ротация диска приводит к изменению других цветных дисков.

Будем проводить ротацию цветного диска DR ₂ . При ротации меняются только цвета ребер e ₆ , e ₇ , e ₉ , e ₂₀ , принадлежащих цветному диску DR ₂ . Цвета других ребер не меняются. Для определения новых последовательностей в цветных дисках, присоединим циклы, принадлежащие диску DR ₂ , к другим цветным 2-факторам.

R _с = DR ₁ Å DR ₂ = ( c ₁ Å c ₅ Å c ₃ Å c ₁₁ Å c ₁₃ Å c ₉ ) Å ( c ₇ );

B _с = DB ₁ Å DB ₂ Å DB ₃ = ( c ₄ Å c ₅ Å c ₆ Å c ₇ Å c ₈ ) Å ( c ₁₂ Å c ₁₃ ) Å (с ₇ );

G _с = DG ₁ Å DG ₂ = ( c ₈ Å c ₁ Å c ₄ Å c ₃ Å c ₆ Å c ₁₁ Å c ₁₂ Å c ₉ ) Å (с ₇ );

В результате получим раскраску красных цветных дисков (рис. 8):

R _с = ( c ₁ Å c ₅ Å c ₃ Å c ₁₁ Å c ₁₃ Å c ₉ ) Å ( c ₇ ) =

= < e ₁₉ [3], e ₂₉ [2], e ₃₆ [3], e ₂₂ [2], e ₂₃ [3], e ₂₄ [2], e ₃₀ [3], e ₃₁ [2], e ₃₄ [3], e ₂₇ [2],

e ₂₆ [3], e ₁₃ [2], e ₁₀ [3], e ₁₁ [2], e ₁₄ [3],e ₁₅ [2],e ₁₇ [3],e ₅ [2],e ₁ [3],e ₃ [2]> Å

Å < e ₇ [3],e ₂₀ [2],e ₉ [3],e ₆ [2]>;

синих цветных дисков (рис. 9):

B _с = ( c ₄ Å c ₅ Å c ₆ Å c ₇ Å c ₈ ) Å ( c ₁₂ Å c ₁₃ ) Å (с ₇ ) =

= { e ₁₄ [3] , e ₁₅ [2] , e ₁₆ [1] , e ₁₇ [3] } Å { e ₂ [1] , e ₃ [2] , e ₁₂ [1] , e ₁₃ [2] , e ₁₅ [2] ,

e ₁₉ [3] , e ₂₈ [1] } Å { e ₈ [1] , e ₉ [3] , e ₁₀ [3] , e ₁₃ [2] , e ₂₁ [1] , e ₂₃ [3] , e ₂₅ [1] ,

e ₂₆ [3] } Å { e ₆ [2] , e ₇ [3] , e ₉ [3] , e ₂₀ [2] } Å { e ₁ [3], e ₃ [2], e ₄ [1], e ₇ [3], e ₁₈ [1]}

Å { e ₃₀ [3], e ₃₁ [2], e ₃₃ [1], e ₃₄ [3]} Å { e ₃₁ [2], e ₃₂ [1], e ₃₅ [1], e ₃₆ [3]} Å

{ e ₆ [2], e ₇ [3], e ₉ [3], e ₂₀ [2]} =

= { e ₁₄ [3], e ₁₆ [1], e ₁₇ [3], e ₂ [1], e ₁₂ [1], e ₁₉ [3], e ₂₈ [1], e ₈ [1], e ₁₀ [3], e ₂₁ [1],

e ₂₃ [3], e ₂₅ [1], e ₂₆ [3], e ₁ [3], e ₄ [1], e ₇ [3], e ₁₈ [1], e ₃₀ [3], e ₃₃ [1], e ₃₄ [3],

e ₃₂ [1], e ₃₅ [1], e ₃₆ [3]} =

= < e ₁₄ [3], e ₁₆ [1], e ₁₇ [3], e ₂ [1], e ₁ [3], e ₄ [1], e ₇ [3], e ₁₈ [1], e ₁₉ [3], e ₂₈ [1],

e ₂₆ [3], e ₂₅ [1], e ₂₃ [3], e ₂₁ [1], e ₉ [3], e ₈ [1], e ₁₀ [3], e ₁₂ [1]> Å

Å < e ₃₀ [3], e ₃₂ [1], e ₃₆ [3], e ₃₅ [1], e ₃₄ [3], e ₃₃ [1]>;

зеленых цветных дисков (рис. 10):

G _с = ( c ₈ Å c ₁ Å c ₄ Å c ₃ Å c ₆ Å c ₁₁ Å c ₁₂ Å c ₉ ) Å (с ₇ ) = { e ₁ [3], e ₃ [2], e ₄ [1],

e ₇ [3], e ₁₈ [1]} Å { e ₁ [3], e ₂ [1], e ₅ [2], e ₁₇ [3]} Å { e ₁₄ [3], e ₁₅ [2], e ₁₆ [1], e ₁₇ [3]} Å

Å { e ₁₀ [3], e ₁₁ [2], e ₁₂ [1], e ₁₄ [3]} Å

Å { e ₈ [1], e ₉ [3], e ₁₀ [3], e ₁₃ [2], e ₂₁ [1], e ₂₃ [3], e ₂₅ [1], e ₂₆ [3]} Å

Å { e ₂₆ [3], e ₂₇ [2], e ₂₈ [1], e ₂₉ [2], e ₃₄ [3], e ₃₅ [1]} Å

Å { e ₃₀ [3], e ₃₁ [2], e ₃₃ [1], e ₃₄ [3]} Å { e ₂₂ [2], e ₂₃ [3], e ₂₄ [2], e ₃₀ [3], e ₃₂ [1]} Å

Å { e ₆ [2], e ₇ [3], e ₉ [3], e ₂₀ [2]} = { e ₁₅ [2], e ₁₆ [1], e ₁₁ [2], e ₁₂ [1], e ₈ [1], e ₁₃ [2],

e ₂₁ [1], e ₂₅ [1], e ₂₇ [2], e ₂₈ [1], e ₂₉ [2], e ₃₅ [1], e ₃₁ [2], e ₃₃ [1], e ₂₂ [2], e ₂₄ [2],

e ₃₂ [1], e ₆ [2], e ₁₈ [1], e ₃ [2], e ₄ [1], e ₂ [1], e ₅ [2], e ₂₀ [2]} =

= < e ₁₅ [2], e ₁₂ [1], e ₁₃ [2], e ₂₈ [1], e ₂₉ [2], e ₃₅ [1], e ₃₁ [2], e ₃₂ [1], e ₂₂ [2], e ₂₁ [1],

e ₂₀ [2], e ₁₈ [1], e ₃ [2], e ₂ [1]> Å < e ₅ [2], e ₄ [1], e ₆ [2], e ₈ [1], e ₁₁ [2], e ₁₆ [1]> Å

Å < e ₂₄ [2], e ₂₅ [1], e ₂₇ [2], e ₃₃ [1]>.

Формируем обод графа , c ₀ = { e ₁₈ [1] , e ₁₉ [3] , e ₂₀ [3] , e ₂₁ [1] , e ₂₂ [2] , e ₂₉ [2] , e ₃₆ [3] }.

 

 

Правило определения состава дисков после ротации. Для определения состава цветных дисков после ротации цветного диска Y необходимо произвести перекраску его ребер и к другим цветным 2-факторам присоединить циклы цветного диска Y , затем произвести их реберное построение согласно (2).

Интерес представляют раскрашенные кубические графы, у которых белые цветные диски имеют четную длину и их суммарная длина равна 2 m /3.

Для раскрашенного кубического графа Н ₃ (рис. 11) выберем следующие базисные циклы:

c ₁ = { e ₂ [2] , e ₃ [1] , e ₈ [1] , e ₁₀ [2] } ;         c ₂ = { e ₁ [3] , e ₂ [2] , e ₄ [1] , e ₆ [3] } ;

c ₃ = { e ₉ [3] , e ₁₀ [2] , e ₁₁ [1] , e ₁₃ [3] } ;

c ₄ = { e ₄ [1] , e ₅ [2] , e ₇ [2] , e ₁₈ [1] } ;          c ₅ = { e ₁₁ [1] , e ₁₂ [2] , e ₁₄ [2] , e ₂₃ [1] } ;

c ₆ = { e ₆ [3] , e ₇ [2] , e ₈ [1] , e ₉ [3] , e ₁₂ [2] , e ₁₅ [3] , e ₁₇ [1] , e ₂₄ [3] } ;

c ₇ = { e ₁₆ [2] , e ₁₇ [1] , e ₂₀ [1] , e ₂₂ [2] } ;

c ₈ = { e ₁₅ [3], e ₁₆ [2], e ₁₈ [1], e ₁₉ [3]};          c ₉ = { e ₂₁ [3], e ₂₂ [2], e ₂₃ [1], e ₂₄ [3]}.

 

 

Формируем обод, c ₀ = { e ₁ [3] , e ₃ [1] , e ₅ [2] , e ₁₃ [3] , e ₁₄ [2] , e ₁₉ [3] , e ₂₀ [1] , e ₂₁ [3] } .

R _с = DR ₁ Å DR ₂ = ( c ₃ Å c ₅ Å c ₉ ) Å ( c ₂ Å c ₄ Å c ₈ ) =

= ({e ₉ [3], e ₁₀ [2], e ₁₁ [1], e ₁₃ [3]} Å

Å { e ₁₁ [1], e ₁₂ [2], e ₁₄ [2], e ₂₃ [1]} Å { e ₂₁ [3], e ₂₂ [2], e ₂₃ [1], e ₂₄ [3]}) Å

Å ({ e ₁ [3], e ₂ [2], e ₄ [1], e ₆ [3]} Å

Å { e ₄ [1], e ₅ [2], e ₇ [2], e ₁₈ [1]} Å { e ₁₅ [3], e ₁₆ [2], e ₁₈ [1], e ₁₉ [3]}) =

= < e ₉ [3], e ₁₀ [2], e ₁₃ [3], e ₁₄ [2], e ₂₁ [3], e ₂₂ [2], e ₂₄ [3], e ₁₂ [2]> Å

Å < e ₁ [3], e ₂ [2], e ₆ [3], e ₇ [2], e ₁₅ [3], e ₁₆ [2], e ₁₉ [3], e ₅ [2]>;

B _с = DB ₁ Å DB ₂ = ( c ₁ Å c ₂ Å c ₃ ) Å ( c ₇ Å c ₈ Å c ₉ ) =

= ({e ₂ [2], e ₃ [1], e ₈ [1], e ₁₀ [2]} Å

Å { e ₁ [3], e ₂ [2], e ₄ [1], e ₆ [3]} Å { e ₉ [3], e ₁₀ [2], e ₁₁ [1], e ₁₃ [3]}) Å

Å ({ e ₁₆ [2], e ₁₇ [1], e ₂₀ [1], e ₂₂ [2]} Å

Å { e ₁₅ [3], e ₁₆ [2], e ₁₈ [1], e ₁₉ [3]} Å { e ₂₁ [3], e ₂₂ [2], e ₂₃ [1], e ₂₄ [3]}) =

= < e ₃ [1], e ₁ [3], e ₄ [1], e ₆ [3], e ₈ [1], e ₉ [3], e ₁₁ [1], e ₁₃ [3]> Å

Å < e ₁₇ [1], e ₁₅ [3], e ₁₈ [1], e ₁₉ [3], e ₂₀ [1], e ₂₁ [3], e ₂₃ [1], e ₂₄ [3]>;

G _с = DG ₁ Å DG ₂ Å DG ₃ Å DG ₄ = ( c ₁ ) Å ( c ₄ ) Å ( c ₅ ) Å ( c ₇ ) =

= < e ₂ [2], e ₃ [1], e ₈ [1], e ₁₀ [2]> Å

Å < e ₄ [1], e ₅ [2], e ₇ [2], e ₁₈ [1]> Å < e ₁₁ [1], e ₁₂ [2], e ₁₄ [2], e ₂₃ [1]> Å

Å < e ₁₆ [2], e ₁₇ [1], e ₂₀ [1], e ₂₂ [2]>.

W _c = c ₆ Å c ₀ = { e ₆ [3], e ₇ [2], e ₈ [1], e ₉ [3], e ₁₂ [2], e ₁₅ [3], e ₁₇ [1], e ₂₄ [3]} Å

Å { e ₁ [3] , e ₃ [1] , e ₅ [2] , e ₁₃ [3] , e ₁₄ [2] , e ₁₉ [3] , e ₂₀ [1] , e ₂₁ [3] } .

Осуществим перекраску ребер, взяв за основу цветные диски вместо белых (рис. 12).

c ₁ = { e ₂ [1] , e ₃ [2] , e ₈ [2] , e ₁₀ [1] },         c ₂ = { e ₁ [3] , e ₂ [1] , e ₄ [1] , e ₆ [3] },

c ₃ = { e ₉ [3] , e ₁₀ [1] , e ₁₁ [1] , e ₁₃ [3] },

c ₄ = { e ₄ [1] , e ₅ [2] , e ₇ [2] , e ₁₈ [1] },         c ₅ = { e ₁₁ [1] , e ₁₂ [2] , e ₁₄ [2] , e ₂₃ [1] },

c ₆ = { e ₆ [3] , e ₇ [2] , e ₈ [2] , e ₉ [3] , e ₁₂ [2] , e ₁₅ [3] , e ₁₇ [2] , e ₂₄ [3] },

c ₇ = { e ₁₆ [1] , e ₁₇ [2] , e ₂₀ [2] , e ₂₂ [1] },

c ₈ = { e ₁₅ [3], e ₁₆ [1], e ₁₈ [1], e ₁₉ [3]},         c ₉ = { e ₂₁ [3], e ₂₂ [1], e ₂₃ [1], e ₂₄ [3]}.

Обод c ₀ = {e ₁ [3],e ₃ [2],e ₅ [2],e ₁₃ [3],e ₁₄ [2],e ₁₉ [3],e ₂₀ [2],e ₂₁ [3]}.

R _с = DR ₁ Å DR ₂ =

= (c ₆ ) Å (c ₀ ) = (c ₆ ) Å (c ₁ Å c ₂ Å c ₃ Å c ₄ Å c ₅ Å c ₆ Å c ₇ Å c ₈ Å c ₉ ) =

= < e ₆ [3],e ₇ [2],e ₁₅ [3],e ₁₇ [2],e ₂₄ [3],e ₁₂ [2],e ₉ [3],e ₈ [2]> Å

Å < e ₁ [3],e ₃ [2],e ₁₃ [3],e ₁₄ [2],e ₂₁ [3],e ₂₀ [2],e ₁₉ [3],e ₅ [2]>;

B _с = DB ₁ Å DB ₂ Å DB ₃ Å DB ₄ = (c ₂ ) Å (c ₃ ) Å (c ₈ ) Å (c ₉ ) =

= < e ₁ [3],e ₂ [1],e ₆ [3],e ₄ [1]> Å

Å < e ₉ [3],e ₁₀ [1],e ₁₃ [3],e ₁₁ [1]> Å < e ₁₅ [3],e ₁₆ [1],e ₁₉ [3],e ₁₈ [1]> Å

Å < e ₂₁ [3],e ₂₂ [1],e ₂₄ [3],e ₂₃ [1]>;

G _ф = DG ₁ Å DG ₂ Å DG ₃ Å DG ₄ = (c ₁ ) Å (c ₄ ) Å (c ₅ ) Å (c ₇ ) =

= < e ₂ [1],e ₃ [2],e ₁₀ [1],e ₈ [2]> Å

Å < e ₄ [1],e ₅ [2],e ₁₈ [1],e ₇ [2]> Å < e ₁₁ [1],e ₁₂ [2],e ₂₃ [1],e ₁₄ [2]> Å

= < e ₁₆ [1],e ₁₇ [2],e ₂₂ [1],e ₂₀ [2]>.

5. Раскраска непланарных кубических графов

Интересен случай раскраски циклов в неплоских кубических графах (рис. 13).

Выделим базисные циклы в графе:

c ₁ = { e ₁ , e ₂ , e ₄ , e ₆ }; c ₂ = { e ₉ , e ₁₀ , e ₁₁ , e ₁₂ }; c ₃ = { e ₂ , e ₃ , e ₈ , e ₁₁ };

c ₄ = { e ₄ , e ₅ , e ₇ , e ₁₀ }; c ₅ = { e ₆ , e ₇ , e ₈ , e ₉ , e ₁₀ }; c ₀ = { e ₁ , e ₃ , e ₅ , e ₁₀ , e ₁₂ }.

Представим цветные диски для данной раскраски ребер в следующем виде:

DR ₁ = ( e ₁ , G ) Å ( e ₅ , B ) Å ( e ₉ , G ) Å ( e ₈ , B ) Å ( e ₆ , G ) Å ( e ₇ , B ) Å

Å ( e ₁₂ , G ) Å ( e ₃ , B ) = с ₁ Å с ₂ Å с ₃ Å с ₄ ;

DB ₁ = (e ₁ ,G) (e ₄ ,R) Å (e ₆ ,G) Å (e ₂ ,R) = с ₁ ;

DB ₂ = (e ₉ ,G) (e ₁₀ ,R) Å (e ₁₃ ,G) Å (e ₁₁ ,R) = с ₂ ;

DG ₁ = (e ₂ ,R) (e ₃ ,B) Å (e ₁₁ ,R) Å (e ₃ ,B) = с ₃ ;

DG ₂ = (e ₄ ,R) (e ₇ ,B) Å (e ₁₀ ,R) Å (e ₅ ,B) = с ₄ .

 

Рис. 13. Раскрашенный кубический непланарный граф H ₃ .

 

Цветные 2-факторы раскрашенного кубического непланарного графа H ₃ :

R _c = DR ₁ ;

B _c = DB ₁ DB ₂ ;

G _c = DG ₁ DG ₂ ;

Отсюда можно определить цвета базисных циклов.

c ₁ (R _c B _c ) G;                c ₂ (R _c B _c ) G;

c ₃ (R _c G _c ) B;                c ₄ (R _c G _c ) B;

c ₅ W ; c ₀ W .

Рассмотрим раскраску ребер

e ₁ (c ₁ c ₀ ) G + W = G;              e ₂ (c ₁ c ₃ ) G + B = R;

e ₃ (c ₃ c ₀ ) B + W = B;              e ₄ (c ₁ c ₄ ) G + B = R;

e ₅ (c ₄ c ₀ ) B + W = B;              e ₆ (c ₁ c ₅ ) G + W = G;

e ₇ (c ₄ c ₅ ) B + W = B;              e ₈ (c ₃ c ₅ ) B + W = B;

e ₉ (c ₂ c ₅ ) G + W = G;

e ₁₀ (c ₂ c ₄ c ₅ c ₀ ) G + W + W + B = R;

e ₁₁ (c ₂ c ₃ ) G + B = R;              e ₁₂ (c ₂ c ₀ ) G + W = G.

Рассмотрим следующий непланарный граф Н ₄ (рис. 14).

Выделим следующие базисные циклы в графе:

c ₁ = { e ₁ , e ₂ , e ₅ , e ₁₂ , e ₁₅ }; c ₂ = { e ₁₀ , e ₁₁ , e ₁₂ , e ₁₆ }; c ₃ = { e ₁ , e ₃ , e ₄ , e ₇ , e ₁₃ };

c ₄ = { e ₄ , e ₅ , e ₆ , e ₉ , e ₁₇ }; c ₅ = { e ₆ , e ₇ , e ₈ , e ₁₁ , e ₁₈ };

c ₆ = { e ₈ , e ₉ , e ₁₀ , e ₁₂ , e ₁₅ , e ₁₇ };

c ₇ = { e ₁₃ , e ₁₄ , e ₁₅ , e ₁₆ , e ₁₇ , e ₁₈ }; c ₀ = { e ₂ , e ₃ , e ₁₂ , e ₁₄ , e ₁₅ , e ₁₇ }.

 

Рис. 14. Раскрашенный непланарный граф Н ₄

 

Цветные диски для данной раскраски ребер:

DR ₁ = ( e ₂ , G ) Å ( e ₁₂ , B ) Å ( e ₁₆ , G ) Å ( e ₁₁ , B ) Å ( e ₈ , G ) Å ( e ₉ , B ) Å

Å ( e ₁₇ , G ) Å ( e ₅ , B ) Å ( e ₄ , G ) Å ( e ₇ , B ) Å ( e ₁₃ , G ) Å ( e ₃ , B ) =

= с ₁ Å с ₂ Å с ₃ Å с ₆ ;

DB ₁ = ( e ₁ , R ) Å ( e ₂ , G ) Å ( e ₁₀ , R ) Å ( e ₈ , G ) Å ( e ₆ , R ) Å ( e ₄ , G )=

= с ₁ Å с ₄ Å с ₆ ;

DB ₂ = ( e ₁₃ , G ) Å ( e ₁₈ , R ) Å ( e ₁₆ , G ) Å ( e ₁₅ , R ) Å ( e ₁₇ , G ) Å ( e ₁₄ , R ) = с ₇ ;

DG ₁ = ( e ₁₀ , R ) Å ( e ₁₁ , B ) Å ( e ₁₈ , R ) Å ( e ₇ , B ) Å ( e ₆ , R ) Å ( e ₉ , B ) Å

Å ( e ₁₄ , R ) Å ( e ₃ , B ) Å ( e ₁ , R ) Å ( e ₅ , B ) Å ( e ₁₅ , R ) Å ( e ₁₂ , B ) =

= с ₂ Å с ₃ Å с ₄ Å с ₇ .

Цветные 2-факторы раскрашенного кубического непланарного графа H ₄ :

R _c = DR ₁ ;

B _c = DB ₁ DB ₂ ;

G _c = DG ₁ ;

Отсюда можно определить цвета базисных циклов.

c ₁ (R _c B _c ) G;                c ₂ (R _c G _c ) B;

c ₃ (R _c G _c ) B;                c ₄ (B _c G _c ) R;

c ₅ W;                                      c ₆ (B _c R _c ) G;

c ₇ ( B _c G _c ) R ; c ₀ W .

Рассмотрим раскраску ребер

e ₁ (c ₁ c ₃ ) G + B = R;               e ₂ (c ₁ c ₀ ) G + W = G;

e ₃ (c ₃ c ₀ ) B + W = B;              e ₄ (c ₃ c ₄ ) B + R = G;

e ₅ (c ₁ c ₄ ) G + R = B;               e ₆ (c ₄ c ₅ ) R + W = R;

e ₇ (c ₃ c ₅ ) B + W = B;              e ₈ (c ₅ c ₆ ) G + W = G;

e ₉ (c ₄ c ₆ ) R + G = B;               e ₁₀ (c ₂ c ₆ B + G = R;

e ₁₁ (c ₂ c ₅ ) B + W = B;

e ₁₂ (c ₁ c ₂ c ₆ c ₀ ) G + B + G + W = B;

e ₁₃ (c ₃ c ₇ ) B + R = G;              e ₁₄ (c ₇ c ₀ ) R + W = R;

e ₁₅ (c ₇ c ₀ ) R + W = R;             e ₁₆ (c ₂ c ₇ ) B + R = G;

e ₁₇ (c ₄ c ₆ c ₇ c ₀ ) G + R + W + R = G;

e ₁₈ ( c ₅ c ₇ ) R + W = R .

Таким образом, формула 5 применима и для раскрашенных непланарных графов.

6. Цветное вращение вершин

Будем называть цветным вращением вершин циклический порядок вида 1 – 2 – 3 ( R – B – G ) обхода ребер для вершины плоского кубического графа Н . Если ребра вершины раскрашены тремя цветами, то порядок обхода цветов 1 – 2 – 3 ( R – B – G ) для раскрашенных ребер может происходить либо по часовой стрелке, либо против. Поставим «+1» в соответствие тем вершинам, у которых цветное вращение происходит по часовой стрелке, а «-1» – тем, у которых против. Рассмотрим следующее цветное вращение вершин представленное на рис. 15 .

 

 

Тогда для множества вершин, принадлежащих грани плоского кубического графа, можно записать систему уравнений Хивуда [1] для каждого базисного цикла и обода:

(6)

где a = 1,2,... , m - n +2.

При этом решение системы Хивуда определяет раскраску, так как в системе Хивуда цветному вращению вершин плоского кубического графа по часовой стрелке можно поставить в соответствие «+1», а цветному вращению против – «-1».

Тогда можно записать уравнения Хивуда [1] в виде:

x(v ₁ ) + x(v ₄ ) + x(v ₅ ) + x(v ₈ ) = (-1) + (+1) + (-1) + (+1) º 0 (mod 3);

x(v ₁ ) + x(v ₂ ) + x(v ₃ ) + x(v ₄ ) = (-1) + (-1) + (+1) + (+1) º 0 (mod 3);

x(v ₅ ) + x(v ₆ ) + x(v ₇ ) + x(v ₈ ) = (-1) + (-1) + (+1) + (+1) º 0 (mod 3);

x(v ₂ ) + x(v ₃ ) + x(v ₁₀ ) + x(v ₁₁ ) = (-1) + (+1) + (-1) + (+1) º 0 (mod 3);

x(v ₆ ) + x(v ₇ ) + x(v ₁₄ ) + x(v ₁₅ ) = (-1) + (+1) + (-1) + (+1) º 0 (mod 3);

x(v ₃ ) + x(v ₄ ) + x(v ₅ ) + x(v ₆ ) + x(v ₉ ) + x(v ₁₀ ) + x(v ₁₅ ) + x(v ₁₆ ) =

= (+1) + (+1) + (-1) + (-1) + (-1) + (-1) + (+1) + (+1) º 0 (mod 3);

x(v ₉ ) + x(v ₁₂ ) + x(v ₁₃ ) + x(v ₁₆ ) = (-1) + (+1) + (-1) + (+1) º 0 (mod 3);

x(v ₉ ) + x(v ₁₀ ) + x(v ₁₁ ) + x(v ₁₂ ) = (-1) + (-1) + (+1) + (+1) º 0 (mod 3);

x(v ₁₃ ) + x(v ₁₄ ) + x(v ₁₅ ) + x(v ₁₆ ) = (-1) + (-1) + (+1) + (+1) º 0 (mod 3);

x(v ₁ ) + x(v ₂ ) + x(v ₇ ) + x(v ₈ ) + x(v ₁₁ ) + x(v ₁₂ ) + x(v ₁₃ ) + x(v ₁₄ ) =

= (-1) + (-1) + (+1) + (+1) + (+1) + (+1) + (-1) + (-1) º 0 ( mod 3);

Для максимально плоских графов справедлива следующая теорема.

Теорема 1 [4] . Пусть М – множество вершин плоского кубического графа. Тогда для любой правильной раскраски

(7)

И действительно:

x(v ₁ ) + x(v ₂ ) + x(v ₃ ) + x(v ₄ ) + x(v ₅ ) + x(v ₆ ) + x(v ₇ ) + x(v ₈ ) + x(v ₉ ) + x(v ₁₀ ) + x(v ₁₁ ) + x(v ₁₂ ) + x(v ₁₃ ) + x(v ₁₄ ) + x(v ₁₅ ) + x(v ₁₆ ) = (-1) + (-1) + (+1) + (+1) + (-1) + (+1) + (+1) + (-1) + (-1) + (-1) + (+1) + (+1) + (-1) + (-1) + (+1) + (+1) º 0 (mod4).

Построим замкнутые маршруты Хивуда в плоском раскрашенном кубическом графе, последовательно выбирая ребра согласно цветному вращению вершин.

= < e ₃ [1],e ₁₀ [2],e ₉ [3],e ₁₁ [1],e ₁₄ [2],e ₂₁ [3],e ₂₀ [1],e ₁₆ [2],e ₁₅ [3],e ₁₈ [1],
e ₅ [2],e ₁ [3]>;

= < e ₃ [1],e ₂ [2],e ₆ [3],e ₄ [1],e ₅ [2],e ₁₉ [3],e ₂₀ [1],e ₂₂ [2],e ₂₄ [3],e ₂₃ [1],
e ₁₄ [2],e ₁₃ [3]>;

= < e ₂₃ [1],e ₁₂ [2],e ₉ [3],e ₈ [1],e ₂ [2],e ₁ [3],e ₄ [1],e ₇ [2],e ₁₅ [3],e ₁₇ [1],
e ₂₂ [2],e ₂₁ [3]>;

= < e ₁₁ [1],e ₁₂ [2],e ₂₄ [3],e ₁₇ [1],e ₁₆ [2],e ₁₉ [3],e ₁₈ [1],e ₇ [2],e ₆ [3],e ₈ [1],
e ₁₀ [2],e ₁₃ [3]>.

Замкнутые маршруты Хивуда проходят по ребру дважды, но второй раз всегда в обратном направлении. Длина замкнутого маршрута Хивуда кратна трем.

7. Заключение

В работе рассмотрены алгебраические методы раскраски плоских кубических графов, основанные на теореме Тэйта. Описание раскраски плоского кубического графа выполнено с применением группового преобразования Клейна четвертого порядка. Топологический рисунок плоского графа, описываемый вращением вершин, индуцирует базисные простые циклы подпространства циклов. Переход к раскраске графа производится при помощи раскраски ребер базисных циклов. Предполагается, что такая раскраска произведена методами, представленными в работе [3]. Выполнено формирование цветных дисков на основе раскраски ребер. Для однозначного описания представления цветных дисков через базисные циклы введено понятие вложимости цветных дисков. Рассмотрены вопросы математического описания операции ротации цветных дисков и последующей их перекраски. Выявлена зависимость между цветным вращением вершин плоского кубического графа и замкнутыми маршрутами Хивуда .

Список литературы

1. А.А. Зыков. Основы теории графов / Зыков А.А. – М.: Наука, ГРФМЛ, 1987. – 384 с.

2. И. Гроссман . Группы и их графы / Гроссман, И., Магнус В. – М.: Мир, 1971. – 238 с.

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

4. Н.З. Шор, Г.А. Донец. Алгебраический подход к проблеме раскраски плоских графов / Г.А. Донец, Н.З. Шор. – Київ: Наук.думка, 1982. – 144 с.

5. Г . Рингель . Теорема о раскраске карт / Рингель, Г. – М.: Мир, 1977. – 126 с.

6. М. Свами. Графы, сети и алгоритмы. М.: Мир. – 1984. – 455 с.

---

Algebraic methods for coloring cubic graphs

Authors: S.V. Kurapov^1,A, M.V. Davidovsky^2,B, A.V. Tolok^3,C

^A Zaporozhye National University, Ukraine

^B Zaporozhye Institute of Postgraduate Pedagogical Education, Ukraine

^C Moscow State Technological University «STANKIN», Russia

¹ ORCID: 0000-0003-4563-7227, lilili5050@rambler.ru

² ORCID: 0000-0002-9472-3351, m.davidovsky@gmail.com

³ ORCID: 0000-0002-7257-9029, a.tolok@stankin.ru

 

Abstract

The article addresses algebraic methods for coloring arbitrary cubic graphs. The results are partially based on the corollaries of the Tait theorem. In the article, the authors propose using a fourth-order Klein group transform in order to formally describe the coloring of a cubic graph. The transition to graph coloring is done by coloring the edges of basis cycles. Overall, the mathematical framework for describing topological graph drawing is presented and formally described in the article. Based on the edge coloring, the formation of colored disks and the mathematical description of the operation of colored disks rotation with subsequent recoloring of the edges are considered. It is shown that the operation of rotating color disks can be represented as a ring sum (addition modulo 2) of cycles. In order to unambiguously describe the representation of colored disks by means of basis cycles, the authors introduce the concept of embeddability of colored disks. For clarity, the authors provide several examples illustrating the application of colored disks rotation operation to concrete cubic graphs. The relation between the system of induced cycles generated by the rotation of graph vertices and the coloring of 2-factors of the cubic graph is established in the present study. It is shown that the ring sum of all cycles included in the colored 2-factors of the graph is an empty set. The article also addresses the issues of coloring non-planar cubic graphs. The relationship between basis cycles and a rim in a non-planar cubic graph and a ring sum of colored 2-factors is explicitly shown in the article. In addition, the relationship between the colored vertex rotation of a plane cubic graph and the closed Heawood paths is revealed and formally described.

 

Keywords: graph, topological graph drawing, geometric image of graph drawing, rotation of graph vertices, isometric cycles, planarity.

 

References

1. A.A. Zykov. Fundamentals of Graph Theory. – B C S Associates, 1990. – 365 p.

2. I. Grossman, W Magnus. In Groups and Their Graphs. – Mathematical Association of America, 1992. – 195 p.

3. Kurapov S. V, Davidovsky M. V. Visual algorithm for coloring planar graphs // Scientific Visualization. – 201 8 , Vol. 10, No 3 – P. 1–33.

4. N. Z. Shor, G. A. Donets. Algebraic Approach to the Plane Graph Coloring. – Naukova Dumka, 1982. English translation published by Springer-Verlag, Berlin, 1985.

5. G. Ringel . Map Color Theorem. – Repr. of the orig. 1st ed. (1974), Springer, 2011. – 212 p.

6. M. N. S. Swamy . Graphs, networks, and algorithms / Swamy, M.N.S., Thulasiraman K. – Wiley New York, 1981. – 592 p.

7. P. G. Tait . Remarks on the Colourings of Maps // In Proc. R. Soc. Edinburgh 10: 729, 1880.