Pages Navigation Menu

ISSN 2227-6017 (ONLINE), ISSN 2303-9868 (PRINT), DOI: 10.18454/IRJ.2227-6017
ПИ № ФС 77 - 51217, 16+

DOI: https://doi.org/10.18454/IRJ.2016.51.139

Скачать PDF ( ) Страницы: 128-131 Выпуск: № 9 (51) Часть 2 () Искать в Google Scholar
Цитировать

Цитировать

Электронная ссылка | Печатная ссылка

Скопируйте отформатированную библиографическую ссылку через буфер обмена или перейдите по одной из ссылок для импорта в Менеджер библиографий.
Магомедов А. М. О РАСКРАШИВАЕМОСТИ ДВУДОЛЬНЫХ ГРАФОВ СПЕЦИАЛЬНОГО ВИДА / А. М. Магомедов // Международный научно-исследовательский журнал. — 2016. — № 9 (51) Часть 2. — С. 128—131. — URL: https://research-journal.org/physics-mathematics/o-raskrashivaemosti-dvudolnyx-grafov-specialnogo-vida/ (дата обращения: 02.06.2020. ). doi: 10.18454/IRJ.2016.51.139
Магомедов А. М. О РАСКРАШИВАЕМОСТИ ДВУДОЛЬНЫХ ГРАФОВ СПЕЦИАЛЬНОГО ВИДА / А. М. Магомедов // Международный научно-исследовательский журнал. — 2016. — № 9 (51) Часть 2. — С. 128—131. doi: 10.18454/IRJ.2016.51.139

Импортировать


О РАСКРАШИВАЕМОСТИ ДВУДОЛЬНЫХ ГРАФОВ СПЕЦИАЛЬНОГО ВИДА

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

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

Работа выполнена при поддержке проекта № 2588 в рамках базовой части государственного задания Минобрнауки РФ и Отдела математики и информатики ДНЦ РАН

О РАСКРАШИВАЕМОСТИ ДВУДОЛЬНЫХ ГРАФОВ СПЕЦИАЛЬНОГО ВИДА

Аннотация

S. Asratyan и C.J. Casselgren доказали, что задача об интервальной реберной раскраске бирегулярного двудольного графа со степенями 6 и 3 соответственно («(6,3)-граф») NP-полна. В статье показано, что минимальная мощность n вершин, при которой (6,3)-граф не допускает раскраски требуемого вида, равна 18: любой (6,3)-граф с n<18 допускает интервальную реберную раскраску; для каждого n, не меньшего, чем 18 (и кратного 3), существует (6,3)-граф с n вершинами, для которого такая раскраска невозможна. Результаты находят применение в вопросах построения оптимальных расписаний учебных занятий.

Ключевые слова: граф, двудольный, раскраска.

 

Magomedov A.M.

PhD in Physics and Mathematics, Professor, Dagestan State University

THE COLORING OF SPECIAL KIND BIPARTITE GRAPHS

Abstract

S. Asratyan and C. J. Casselgren proved that the problem of the interval edge-coloring of biregular bipartite graph with degrees 6 and 3 respectively («(6,3)-graph») is NP-complete. The article shows that the minimum capacity of vertices n such that (6,3)-graph prevents coloring of the required form equal to 18: any (6,3)-graph with n<18 allows interval edge-coloring; for each n not less than 18 (and divided by 3) there is (6,3)-graph with n vertices, for which a coloring impossible. The results are used for constructing an optimal schedules training sessions.

Keywords: graph, bipartite, coloring.

  1. Введение

В статье использованы обозначения и определения из книги [1]. Интервальной реберной раскраской графа t цветами будем называть отображение множества ребер графа в множество image002, такое, что: 1) для каждого i, image004, найдется ребро, раскрашенное в цвет i, 2) в каждой вершине графа все представленные в ней цвета попарно различны и образуют целочисленный интервал.

Двудольный граф image005 в котором степени всех вершин X равны 6, а степени всех вершин Y равны 3, будем называть (6,3)-бирегулярным или, кратко, (6,3)-графом. При image008 (6,3)-граф image009будем называть image010графом. Будем называть (6,3)-граф раскрашиваемым или нераскрашиваемым в зависимости от того, допускает ли он интервальную реберную раскраску шестью цветами или нет.

В [2] показана NP-полнота задачи о раскрашиваемости (6,3)-графа. Пример нераскрашиваемого image011–графа был построен еще в 1991 г. [3], в 2015 г. пример нераскрашиваемого image012-графа опубликован в [4].

Сформулируем основной результат статьи.

Теорема 1. При  image013 каждый image010-граф раскрашиваем, для любого image014  найдется нераскрашиваемый image010-граф.

  1. Нераскрашиваемые  image015-графы

Отображение множества ребер E (6,3)-графа image009 в множество из двух цветов, такое, что в каждой вершине image017 цвета всех трех ребер, инцидентных y, одинаковы, а каждой вершине image019 инцидентны три ребра каждого из двух цветов, будем называть гармонической раскраской графа G; значения цветов гармонической раскраски условимся обозначать -1 и + 1. Следующая лемма доказана независимо (и в разной терминологии) в [2] и [3].

Лемма 1. Для раскрашиваемости (6,3)–графа G необходимо и достаточно существование гармонической раскраски графа G.

Нетрудно заметить беперспективность проверки существования нераскрашиваемого image021графа путем полного перебора даже при  image022  Справедливость следующей леммы очевидна.

Лемма 2. При гармонической раскраске (6,3)-графа для любой вершины image019 сумма цветов ребер, инцидентных image023, равна нулю (свойство гармоничности для вершины image023).

Следствие. При гармонической раскраске (6,3)-графа сумма цветов всех ребер графа равна нулю.

Двудольный граф image024, где image025, а множество ребер image026 задано списками смежности вершин множества image027:     image028image029image030, будем называть базисным.

Теорема 2. Если image031-граф image009 является надграфом для базисного графа,  то image020 не допускает гармонической раскраски.

Доказательство. Допустим противное: пусть существует некоторая гармоническая раскраска image033 графа image020, являющегося надграфом для базисного графа. Цвет ребер, инцидентных вершине image034, будем обозначать через  image035 image036  Выполнив почленное сложение равенств, выражающих свойство гармоничности для вершин image037 соответственно:

image038

image039

image040

получим: image041+2(image042

Согласно следствию Леммы 2, image043. Отсюда image044, что невозможно для  image045image046 . Полученное противоречие доказывает, что гармоническая раскраска графа image020 не существует. Теорема доказана.

         Пусть image047 – целое положительное image048. Любой двудольный граф image049, где image050, image051, степени вершин:

image052          (1)

будем называть nдополнением базисного графа или, кратко, nдополнением.

В описанном ниже алгоритме построения n–дополнения текущие значения степеней вершин image053 обозначены через image054, разности image055 названы дефицитами вершин image053, а вершины с дефицитами, равными нулю (отличными от нуля), названы насыщенными (соответственно – не насыщенными).

Алгоритм 1. Построение n-дополнения

Вход: целое положительное image056 списки со значениями элементов, заданными в (1): image057  и  image058.

Комментарии: элементы этих списков приобретут смысл степеней соответствующих вершин лишь после завершения алгоритма.

Выход: –дополнение для базисного графа.

  1. Инициализация: image059; image060; image054:=0 для всех image061;

Комментарии: после инициализации сумма дефицитов вершин каждого из множеств image062  и image063  равна image064 , а разность любых двух элементов следующего списка:

image065                                           (2)

равна -1, 0 или 1 («свойство близости элементов списка»).

  1. пока в множестве image062 имеется ненасыщенная вершина image023, соединить image023 рёбрами с каждой из шести вершин множества image063, имеющих наибольшие значения дефицитов.

Комментарии: добавление ребра сопровождается увеличением текущих степеней его концевых вершин на единицу.

Конец алгоритма 1.

Справедливость следующей леммы очевидна.

Лемма 3. Для любого заданного целого положительного image056, алгоритм 1 генерирует n–дополнение image067.

Теорема 3. Для любого image014 существует image010-граф image009, не допускающий гармонической раскраски.

Доказательство. В качестве графа image020 можно взять объединение базисного графа и его n–дополнения  Теорема доказана.

Следствие. Для любого image014 существует 6-нераскрашиваемый image010-граф image009.

В качестве примера 6-дополнения укажем граф image049, где image071, а множество ребер image072 задано списками смежности вершин множества image073:   image074 image075 image076 .

Легко видеть, что граф image077, полученный объединением графов image078 и image079, является image031-графом. Согласно теореме 2, image077  не допускает гармонической раскраски, поэтому (по лемме 1) граф image077  нераскрашиваем.

Мы доказали вторую часть теоремы 1. Первая часть теоремы 1 всецело получена «компьютерным» путем; изложим принятый нами подход. Для фиксированного n обозначим множество всех image010–графов через image080. Ранее уже упоминалось о сложности полного перебора множества image080 при image081 проблема перебора сохраняет остроту и для image082, хотя вычислительные трудности не столь велики, как в случае  n=6.

Наша цель – построить подмножество image083, такое, что утверждение о нераскрашиваемости всех image010–графов – элементов множества M – справедливо тогда и только тогда, когда аналогичное утверждение справедливо для всех элементов подмножества image084. Любое подмножество image084, обладающее таким свойствами, будем называть характеристическим.

Отношение изоморфизма разбивает множество image080 на классы эквивалентности и, на первый взгляд, естественным представляется выбрать в качестве image084 подмножество, включающее точно одного представителя из каждого класса эквивалентности. Однако такое построение затруднительно: задача об изоморфизме графов была опубликована [5] еще в 1972 г. как «открытая» задача, относительно которой неизвестно, является ли она NP-полной (насколько автору известно, за истекшие десятилетия успех в решении проблемы не достигнут). Поэтому ограничимся целью построить характеристическое множество image084, включающее столь мало представителей (но не менее одного) из каждого класса эквивалентности, что мощность image084 не будет представлять трудности для «компьютерного перебора».

Введем обозначения:   image085 image086,   image087 image088;

image089image090

Построение множества image084 удобно изложить в виде построения корневого дерева image091 глубины image092, все узлы которого представлены двудольными графами (далее в тексте – «узловые графы»), а узловые графы, представляющие узлы последнего, image093-го уровня, являются image010–графами и образуют множество image084; при этом каждый узел image053 уровня image003, принадлежащий пути от корня к некоторой вершине image094 последнего уровня image092, будет представлен некоторым порожденным на множестве вершин image095 подграфом image096= image097 графа image098.

Алгоритм 2. Построение характеристического множества

Вход: целое положительное image099.

Выход: «слабо-избыточное» характеристическое множество image084 – множество узловых графов последнего уровня дерева image091.

  1. В качестве узлового графа для узла 0-го уровня (корня дерева image091) выбрать двудольный граф image100, где image101image102

image103 ( image104 – количество узлов в дереве image091).

  1. Для каждого image105 выполнить:

         для узлового графа image106 =image107  каждого узла image053 уровня image108 выполнить:

Begin_1

2.1. Разбить множество Y графа image118 на поля, где каждое поле представляет собой набор всех таких вершин степени <3, которые обладают одним и тем же списком смежности. Количество полей обозначить через N, поля – через image111, их мощности – через image112 индексы первых элементов полей – через image113

2.2. Для каждого неупорядоченного набора целых неотрицательных image114, удовлетворяющих условиям:

image115      и       image116

выполнить:

Begin_2

2.2.1. image117 двудольный граф, полученный из image118 добавлением вершины image119, список смежности которого содержит точно image120 начальных вершин поля image121, image122;

2.2.1.1. если а) список смежности вершины image119 в графе image079 содержит не более общих вершин с image123, чем список смежности вершины image124 в image118 и
б) граф image079 содержит image125 вершин множества Y, степени которых < 3,

то

добавить image079 в дерево image091 в качестве потомка вершины image053, для чего:
image126   и узлу с номером image104 приписать граф image079 (в подробной компьютерной реализации рекомендуется выполнить и следующие действия сопроводительного характера: в соответствующие массивы занести с позиции image104 значения image003, N, номер родительского узла image053 и векторы image127, image128 и image129).

End_2

End_1

Конец алгоритма 2.

Заметим, что image130 не принимают видимого участия в алгоритме, но их присутствие оправдано вычислительными целями (для удобства вычисления полей узла-потомка).

Для генерации наборов целых неотрицательных image114, удовлетворяющих условиям (*), применяется рекурсивная процедура AddSplit ( image131, где image127 и image128 – векторы из N целых неотрицательных и целых положительных чисел соответственно: по заданным image132 и image133 процедура генерирует все разбиения заданного целого положительного image134 на неупорядоченные целые неотрицательные слагаемые:  image135 image136  не превышающие соответствующие image137. Процедура содержит вложенный вызов процедуры AddVertex, действие которой равносильно выполнению фрагмента Begin_2 … End_2 алгоритма 2 по добавлению в дерево image091 нового узла – потомка узла image053. Приведем подробное описание.

Процедура AddSplit (image138 )

Если image139, то begin image120:=value; AddVertex end

иначе

для image140 от image141( image142) до image143 ( image134, image144) выполнить:

Begin_1 image145; AddSplit (image146) End_1

Комментарии: перед вызовом процедуры выполняются присваивания: image147 и image148.

Конец процедуры

Как видно из описания процедуры, память на хранение наборов image114, удовлетворяющих условиям (*), не расходуется: для каждого очередного набора немедленно после его генерации выполняется фрагмент Begin_2 … End_2.

Теорема 4. Алгоритм 2 вычисляет характеристическое множество.

Доказательство. Требуется показать, что для каждого image010–графа – элемента множества image080 – среди узловых графов последнего уровня дерева image091 найдется изоморфный ему граф (назовем это условие кратко: принцип достаточности). Отличия алгоритма 2 от алгоритма полного перебора начинаются с выбора (в пункте 1) единственного узлового графа для корня, остальные отличия сводятся к выбору (в пункте 2.2.1.1) не более одного потомка для узла image053 уровня image149 из каждого множества графов, соответствующего сгенерированному разбиению image150 числа 6 на целые положительные слагаемые.

Во-первых, выбор для вершины image151 любого иного списка смежности приводит к графу, изоморфному image152. В самом деле, пусть для вершины image151 выбран произвольный список смежности image154. Тогда любая биекция {image154} image155 приводит к (изоморфному) графу image152 с сохранением принципа достаточности.

Во-вторых, требование (см. 2.2.1.1а) «список смежности вершины image119 в графе image079 имеет не более общих вершин с image123, чем список смежности вершины image124 в image118» равносильно требованию упорядочить вершины image156 по принципу невозрастания в их списках смежности количеств вершин, принадлежащих image123; такое упорядочение соответствует принципу достаточности. Наконец, если (см. 2.2.1.1б) граф image079 содержит менее шести вершин множества Y степени меньше, чем три, то, очевидно, достроить граф image079 до image010–графа невозможно. Теорема доказана.

Как показали компьютерные расчеты, при image157 алгоритм 2 генерирует дерево image091 из 11645 узлов, из которых 2485 узлов относятся к последнему уровню, образуя искомое множество image084 image158графов. Проверка существования гармонической раскраски у каждого графа из image084 путем обычного перебора не представляет трудности; среди них обнаружены точно 62 нераскрашиваемых графа (в том числе – изоморфные между собой), включая рассмотренный выше граф image077. Для каждого image013 компьютерные расчеты подтвердили существование гармонической раскраски у всех графов характеристического множества, следовательно, их раскрашиваемость (лемма 1). Тем самым доказано и первое утверждение теоремы 1.

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

Область практического применения – построение «безоконного» расписания. Пусть рассматривается задача построения однодневного расписания учебных занятий:  – множество классов,  – множество учителей, исходные данные к расписанию заданы (6,3)-графом image005, где каждому классу запланированы шесть уроков, а каждому учителю – три урока. Если цвету image159 каждого ребра (image160  соотнести номер академического часа – урока учителя image140 в классе image003, то задача о раскрашиваемости графа image020 преобразуется в задачу о существовании расписания длительностью в шесть уроков без «окон» у учителей и классов.

Литература

  1. Swamy M. N. and Thulasiraman K. Graphs, Networks and Algorithms, Wiley-Inter-science, 1981. – 455 P.
  2. Casselgren C. J. On Some Graph Coloring Problems // Doctoral Thesis No. 48. Department of Mathematics and Mathematical Statistics Umea University, 2011.
  3. Магомедов А. М. К вопросу об условиях уплотнимости матрицы из 6 столбцов // Деп. в ВИНИТИ, 1991.
  4. Magomedov A. M. On interval -coloring bipartite graphs // ISSN 0005-1179, Automation and Remote Control, 2015, Vol. 76, No. 1, pp. 80–87.
  5. Karp R. M. Reducibility among combinatorial problems // in R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, New York, 1972. P. 85-103.

References

  1. Swamy M. N. and Thulasiraman K. Graphs, Networks and Algorithms, Wiley-Inter-science, 1981. – 455 P.
  2. Casselgren C. J. On Some Graph Coloring Problems // Doctoral Thesis No. 48. Department of Mathematics and Mathematical Statistics Umea University, 2011.
  3. Magomedov A. M. K voprosu ob uslovijah uplotnimosti matricy iz 6 stolbcov // Dep. v VINITI, 1991.
  4. Magomedov A. M. On interval -coloring bipartite graphs // ISSN 0005-1179, Automation and Remote Control, 2015, Vol. 76, No. 1, pp. 80–87.
  5. Karp R. M. Reducibility among combinatorial problems // in R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, New York, 1972. P. 85-103.

Оставить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Лимит времени истёк. Пожалуйста, перезагрузите CAPTCHA.