Pages Navigation Menu

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

Скачать PDF ( ) Страницы: 11-12 Выпуск: №3 (22) Часть 1 () Искать в Google Scholar
Цитировать

Цитировать

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

Скопируйте отформатированную библиографическую ссылку через буфер обмена или перейдите по одной из ссылок для импорта в Менеджер библиографий.
Магомедов А. М. СОКРАЩЕНИЕ ПЕРЕБОРА ДВУДОЛЬНЫХ ГРАФОВ / А. М. Магомедов // Международный научно-исследовательский журнал. — 2019. — №3 (22) Часть 1. — С. 11—12. — URL: https://research-journal.org/physics-mathematics/sokrashhenie-perebora-dvudolnyx-grafov/ (дата обращения: 07.12.2019. ).
Магомедов А. М. СОКРАЩЕНИЕ ПЕРЕБОРА ДВУДОЛЬНЫХ ГРАФОВ / А. М. Магомедов // Международный научно-исследовательский журнал. — 2019. — №3 (22) Часть 1. — С. 11—12.

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


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

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

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

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

Аннотация

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

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

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.

Введение. Двудольные графы 17-10-2019 14-45-30 степени всех вершин X равны 2a, а степени всех вершин Y равны a, будем называть 17-10-2019 14-46-47графом. Такое отображение множества ребер 17-10-2019 14-46-47-графа 17-10-2019 14-57-38 в множество из двух цветов, что в каждой вершине 17-10-2019 14-47-25 все a ребер, инцидентных вершине y, имеют один и тот же цвет, а любой вершине 17-10-2019 14-47-35 инцидентны по a ребра каждого из двух цветов, будем называть гармонической раскраской графа G; граф, для которого существует гармоническая раскраска, будем называть раскрашиваемым. Гармоническая раскраска для 3n-графа G существует тогда и только тогда, когда для графа G существует интервальная реберная раскраска 6 цветами. Последняя задача является NP-полной [1], поэтому для проверки раскрашиваемости при малых значений n есть смысл прибегнyть к алгоритму перебора всех неизоморфных an-графов, порожденных на заданных множествах вершин  и . Однако полный перебор -графов сопряжен со значительными проблемами даже при малых a и n.

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

Процесс перебора представим как построение корневого дерева с 17-10-2019 15-03-59 уровнями, с каждым узлом v которого ассоциируется двудольный граф , порожденный на множествах вершин 17-10-2019 15-04-48 с корневым узлом ассоциируется граф, где список смежности вершины 17-10-2019 15-05-20 остальные вершины X (и Y) являются изолированными; потомки узла v уровня i-1 индуцированы добавлением в 17-10-2019 15-04-37 того или иного количества ребер, инцидентных вершине xi.

Если в графе 17-10-2019 15-16-43 все вершины подмножества 17-10-2019 15-17-01 имеют степени меньше a и обладают идентичными списками смежности, то подмножество 17-10-2019 15-17-19 будем называть предполем; предполе, не являющееся собственным подмножеством другого предполя назовем полем. Количество полей «текущего» графа 17-10-2019 15-17-33 обозначим через N, поля – через 17-10-2019 15-17-58, их мощности – через 17-10-2019 15-18-08. С точностью до изоморфизма потомок узла v определяется количеством вершин ak из списка смежности вершины xi графа  принадлежащих полям Fk, таких, что

17-10-2019 15-19-35   (1)

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

Правило 1: достаточно ограничиться теми потомками узла , у которых список смежности вершины xi содержит точно ak начальных вершин поля 17-10-2019 15-25-58 таким образом, количество потомков, подлежащих дальнейшему рассмотрению, равно количеству наборов целых чисел, удовлетворяющих (1).

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

Правило 2: из потомков узла v, удовлетворяющих правилу 1, для дальнейшего рассмотрения выбираются лишь те узлы ω, у которых список смежности вершины xi в графе 17-10-2019 15-27-02 имеет не больше общих вершин с множеством 17-10-2019 15-27-09, чем список смежности вершины 17-10-2019 15-27-18 в графе 17-10-2019 15-27-02.

В самом деле, данное правило равносильно требованию упорядочить вершины 17-10-2019 15-35-32 по принципу невозрастания в их списках смежности количеств вершин, принадлежащих 17-10-2019 15-35-41

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

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

Литература

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

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

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

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