СОКРАЩЕНИЕ ПЕРЕБОРА ДВУДОЛЬНЫХ ГРАФОВ

Магомедов А.М.

Доктор физико-математических наук, Дагестанский государственный университет

СОКРАЩЕНИЕ ПЕРЕБОРА ДВУДОЛЬНЫХ ГРАФОВ

Аннотация

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

Ключевые слова: раскраска, изоморфизм, граф.

Magomedov A.M.

Doctor of physico-mathematical Sciences, Dagestan state University

REDUCTION ENUMERATION OF BIPARTITE GRAPHS

Abstract

The article consideres method of elimination enumeration of nonisomorphic biregular graphs generated by a small set of vertices.

Keywords: coloring, isomorphism, graph.

Введение. Двудольные графы  степени всех вершин X равны 2a, а степени всех вершин Y равны a, будем называть -графом. Такое отображение множества ребер -графа  в множество из двух цветов, что в каждой вершине  все a ребер, инцидентных вершине y, имеют один и тот же цвет, а любой вершине  инцидентны по a ребра каждого из двух цветов, будем называть гармонической раскраской графа G; граф, для которого существует гармоническая раскраска, будем называть раскрашиваемым. Гармоническая раскраска для 3n-графа G существует тогда и только тогда, когда для графа G существует интервальная реберная раскраска 6 цветами. Последняя задача является NP-полной [1], поэтому для проверки раскрашиваемости при малых значений n есть смысл прибегнyть к алгоритму перебора всех неизоморфных a_n-графов, порожденных на заданных множествах вершин  и . Однако полный перебор -графов сопряжен со значительными проблемами даже при малых a и n.

Сокращение перебора. Отношение изоморфизма разбивает множество M всех a_n–графов на классы эквивалентности. Если M₀ – подмножество множества M, включающее не менее одного представителя из каждого класса эквивалентности, то проверка существования нераскрашиваемого a_n–графа сводится к проверке раскрашиваемости графов из M.

Процесс перебора представим как построение корневого дерева с  уровнями, с каждым узлом v которого ассоциируется двудольный граф , порожденный на множествах вершин  с корневым узлом ассоциируется граф, где список смежности вершины  остальные вершины X (и Y) являются изолированными; потомки узла v уровня i-1 индуцированы добавлением в  того или иного количества ребер, инцидентных вершине x_i.

Если в графе все вершины подмножества  имеют степени меньше a и обладают идентичными списками смежности, то подмножество  будем называть предполем; предполе, не являющееся собственным подмножеством другого предполя назовем полем. Количество полей «текущего» графа  обозначим через N, поля – через , их мощности – через . С точностью до изоморфизма потомок узла v определяется количеством вершин a_k из списка смежности вершины x_i графа  принадлежащих полям F_k, таких, что

   (1)

Отсюда следует корректность следующего правила.

Правило 1: достаточно ограничиться теми потомками узла , у которых список смежности вершины x_i содержит точно a_k начальных вершин поля  таким образом, количество потомков, подлежащих дальнейшему рассмотрению, равно количеству наборов целых чисел, удовлетворяющих (1).

Графы, ассоциированные с потомками одного и того же родительского узла, неизоморфны; однако графы, ассоциированные с потомками разных узлов одного уровня, могут оказаться изоморфными.

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

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

Заключение. Сформулированные правила элиминации перебора малоизбыточного множества неизоморфных -графов свели задачу к построению дерева из 11645 узлов, из которых 2485 узлов принадлежат к последнему уровню и образуют искомое множество  -графов. Компьютерная программа обнаружила среди них 62 нераскрашиваемых графа, а для  выявила раскрашиваемость всех -графов.

Статья написана при финансовой поддержки госзадания Минобрнауки России в сфере научной деятельности и отдела математики и информатики ДНЦ РАН.

Литература

1. Casselgren C. J. On Some Graph Coloring Problems // Doctoral Thesis No. 48. Department of Mathematics and Mathematical Statistics Umea University, 2011.