ТЕОРЕМА О РАСКРАСКЕ РЕБЕР ГРАФА

Ниже дается топологическое решение проблемы раскраски применительно к цветной маркировке проводов в электрических схемах, таких, как релейные панели. В таких схемах имеется некоторое число реле, переключателей и других устройств , которые должны быть соединены между собой. Соединительные провода заранее объединены в жгуты таким образом, что все провода, идущие к А, выходят из общего жгута в одной точке, идущие к В, — в другой точке и т.д. Необходимо, чтобы все провода, выводимые из общего жгута в данной точке, имели бы разную окраску, исключающую возможность ошибочного соединения при монтаже. Произвольную пару устройств может соединить любое число проводов, но один провод может соединять не более двух устройств. Предполагая, что к одному устройству подходит не более проводов, требуется определить минимальное число цветов, достаточное для выполнения монтажа произвольной схемы.

Теорема. Ребра любого графа могут быть окрашены так, что любые два ребра с общим концом будут иметь различные цвета при использовании самое большее цветов, где т. — максимальное число ребер, исходящих из одной вершины. Это число цветов необходимо для некоторых графов.

Доказательство. Простой граф, требующий цветов, может быть построен следующим образом. Для пусть каждая пара из трех вершин А, В, С соединена ребрами. Так как все ребра, очевидно, должны быть окрашены различно,

необходимо цветов. Если то пусть А и В соединены ребрами, В и С также ребрами, а Л и С соединены ребрами. Здесь все ребра должны быть окрашены различно, и имеется ребер. Другой пример для получается при соединении двух пятиугольников и ребрами

Для доказательства достаточности предположим сначала, что четно. Пусть — заданный граф; хорошо известно, что можно добавлением ребер и вершин получить из него регулярный граф степени т. е. такой, в котором каждая вершина является концом ровно т. ребер. Если можно раскрасить граф то можно, конечно, раскрасить и граф Теорема Петерсена утверждает, что всякий регулярный граф четной степени может быть разложен в регулярных графов второй степени (факторов). Пусть в нашем случае — факторы графа каждый из них представляет собой совокупность многоугольников (циклов), не касающихся друг друга, и, следовательно, каждый может быть раскрашен самое большее тремя цветами. Это дает в общем цветов.

Петерсен высказал предположение, что каждый регулярный граф нечетной степени без мостиков может быть разложен в один граф первой и графов второй степени. Если это предположение верно, то теорема легко доказывается и в случае нечетной степени. Однако это предположение не было доказано для и здесь воспользуемся другим приемом.

Теорема будет доказываться по индукции; раскрашивание графа будет производиться в зависимости от раскраски графа, получающегося из удалением одной вершины с исходящими из нее ребрами. Удалим из вершину Р и исходящих из нее ребер (звезду) и предположим, что оставшийся граф может быть раскрашен требуемым способом цветами. Пусть вершины, которые были соединены с Я в исходном графе, занумерованы числами и предположим, что было параллельных ребер

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

Соберем наши данные в таблицу.

Таблица 1

В этой таблице ребер, исходящих из Р, соответствуют строкам, цветов — столбцам. Если некоторый цвет имеется для раскраски некоторого ребра, то тогда на пересечении соответствующих столбца и строки ставится 1, в противном случае строке, соответствующей ребру из должно быть единиц. Используя описанные ниже три операции, получаем в табл. 1 последовательность единиц вдоль главной диагонали, и это определит способ раскраски графа. Эти операции таковы.

1. Перестановка столбцов. Это соответствует перемене номеров цветов.

2. Перестановка строк. Это соответствует перемене номеров ребер, исходящих из Р.

3. Перестановка цветов в цепочке из двух цветов. Две вершины назовем соединенными цветами и если можно перейти от одной из них к другой по цепочке, вдоль которой эти два цвета чередуются. Если имеется правильно (т. е. в соответствии с условиями теоремы) раскрашенный граф и если переставить два цвета в такой цепочке графа вдоль всей ее длины (заметим, что в правильно раскрашенном графе такая цепочка не может разветвляться), то, очевидно, граф останется правильно раскрашенным. Воспользуемся также тем обстоятельством, что если только один из двух определенных цветов встречается около каждой из трех различных вершин, то

самое большее одна пара этих вершин может быть соединена этими двумя цветами, так как цепочка может иметь только два конца.

Теперь рассмотрим табл. 1. Предположим, что в первой строке имеется 0 в одном столбце и I в другом. Перестановка этих двух цветов в цепочке, исходящей из вершины А, к которой подходит первое ребро, очевидно, эквивалентна перестановке этих двух столбцов в первой строке и во всех остальных строках, которые соответствуют ребрам, подходящим к вершине А. Предположим, что уже получены единицы на главной диагонали D до некоторого места. Покажем, что можно получить следующую единицу на диагонали. Обратимся к табл. 2.

Таблица 2

Если в строке а имеются единицы, находящиеся в столбце Т или правее Т, то одна из них может быть перенесена посредством перестановки столбцов на место X. Предположим, что это не имеет места; тогда единиц должны находиться левее столбца Т в строке а (предполагается, что Следовательно, имеется строк над а, имеющих единицы в D в тех же самых столбцах, что и единицы в а. По крайней мере из этих строк не принадлежат так как имеет элементов и один из них уже был учтен, а именно а. Пусть (3— одна из этих строк, принадлежащая, скажем, Если Р имеет единицу в столбце Т или правее Т, то перестановкой сначала столбцов, а затем строк можно переместить эту единицу на место X, не затрагивая единиц вдоль D. Предположим, что это не так; тогда единиц в строке р

расположены левее Т и, следовательно, строк над строкой а имеют единицы на D в тех же столбцах, что и единицы в (3, и из них по крайней мере не принадлежат как имеет только элементов). Далее, над а расположено не более чем строк, и поэтому среди строк, связанных (указанным только что образом) с Р, и среди строк, связанных с а, должна быть по крайней мере одна общая строка, т. е. существует строка, не принадлежащая ни ни и имеющая единицу в D в том же столбце, в котором имеют единицу Обозначим эту строку через у и предположим, что она принадлежит Если у имеет единицу в столбце Т или правее Т, то ее можно переместить на место X путем перестановки сначала столбцов, а затем строк а к у.

Предположим, что это не имеет места, и нули и единицы на пересечениях и расположены так, как указано на табл. 2, а на месте X стоит 0. Следовательно, по крайней мере одна из строк не соединена ни с какой из остальных цепочкой с двумя цветами Если это а, то переменим местами цвета Т и в цепочке, начинающейся в в результате этого единица из пересечения перейдет на место X без изменения D. Если это то переменим местами цвета в цепочке, начинающейся в и переставим строки Это переместит единицу из пересечения на место X, а ее место займет единица из пересечения Если это оказалось у, то переменим местами цвета в цепочке, начинающейся в и переставим строки а и у так, что единица из перейдет на место X, а единица из займет ее место.