Регистрация / Вход
Прислать материал

Примитивные расширения линейных графов

Сведения об участнике
ФИО
Рипинен Алексей Александрович
Вуз
Федеральное государственное бюджетное образовательное учреждение высшего образования «Саратовский национальный исследовательский государственный университет им. Н.Г. Чернышевского»
Тезисы (информация о проекте)
Область наук
Математика. Механика
Раздел области наук
Математика
Тема
Примитивные расширения линейных графов
Резюме
Задача нахождения минимального примитивного расширения графа не решена для произвольного ориентированного графа, но решена для отдельных классов графов. В работе был рассмотрен класс линейных графов - графов, полученных из цепи переориентацией некоторых дуг. Линейные графы можно разделить на два типа: для одного из них проблема уже была решена, для второго нет. Поэтому в работе рассматривается только второй тип. Для линейного графа был получен полиномиальный алгоритм нахождения произвольного минимального примитивного расширения. Более того, благодаря структуре алгоритма есть возможность найти еще и количество минимальных примитивных расширений линейного графа.
Ключевые слова
линейные графы, минимальные примитивные расширения
Цели и задачи
Разработка полиномиального алгоритма, позволяющего найти произвольное минимальное примитивное расширение линейного графа.
Введение

Граф называется примитивным, если существует целое число \(r>0\) такое, что каждая вершина графа достижима из любой вершины за \(r\) шагов.

Примитивным расширением графа \(G = (V, \alpha)\) называется граф \(G'=(V, \alpha' ), \alpha\subseteq\alpha'\), являющийся примитивным. Интерес вызывают минимальные примитивные расширения – расширения, полученные присоединением минимального количества дуг.

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

Требуется разработать полиномиальный алгоритм, позволяющий найти минимальное примитивное расширение линейного графа.

Методы и материалы

Линейные графы делятся на два типа: I - линейные графы, у которых количество источников не равно количеству стоков, II - линейные графы, у которых количество источников равно количеству стоков. Для графов типа I задачу решил В.Н. Салий. Далее будут рассматриваться только графы типа II.

Основным инструментом решения является критерий примитивности графа: граф является примитивным тогда и только тогда, когда наибольший общий делитель всех его контуров равен 1.

Необходимым условием примитивности графа является его сильная связность.

Другим инструментом является теорема: если граф с числом вершин \(\ge3\)является сильно связным, но не примитивным, то всегда можно получить его минимальное примитивное расширение добавлением ровно одной дуги.

Так как у рассматриваемых линейных графов количество источников равно количеству стоков, можно установить биекцию \(\varphi\) между стоками и источниками.

\(\varphi\)-расширением линейного графа называется граф, полученный добавленим всех дуг вида \(v\varphi(v)\), где \(v\)- сток. Сильно связными расширениями линейного графа могут быть только его \(\varphi\)-расширения. Но не любое \(\varphi\)-расширение является сильно связным.

Главным методом решения задачи является рассмотрение минимальных сильно связных расширений графа, то есть \(\varphi\)-расширений. Если среди них есть примитивное, то оно является искомым. Если примитивных нет, то ответом будет произвольное сильно связное \(\varphi\)-расширение с еще одно добавленной дугой.

Описание и обсуждение результатов

Результатом работы является алгоритм нахождения минимального примитивного расширения линейного графа типа II.

Вход: граф \(G\) – линейный граф типа II.

Выход: граф \(H\)– минимальное примитивное расширение графа \(G\).

  1. Граф \(H=G\) – граф, который будет являться результатом алгоритма.
  2. Граф \(H\) сжимается. Результатом сжатия является новый граф \(K\), а соответствующее отношение эквивалентности - \(\theta\).
  3. Выбирается сток \(v\) в графе \(H\) следующим образом: если граф \(K\) – контур или петля, то \(v\) выбирается произвольно, иначе выбирается такой сток \(v\), что в \(K \theta(v)\) является стоком. Если в графе \(H\) нет стоков, то алгоритм завершен и граф \(H\) является минимальным примитивным расширением графа \(G\).
  4. Пусть \(m\) – количество источников в графе \(H\). Источники в графе \(H\) нумеруются числами от 1 до \(m\) в произвольном порядке. Полагается \(k=1\).
  5. Если \(k>m\), то у графа \(G\) не существует минимального примитивного -расширения. В этом случае \(H\) строится как произвольное \(\varphi\)-расширение, содержащее дугу из крайнего стока в крайний источник. В нем ищется контур \(v_1,v_2,...,v_t, t\ge3\), и проводится дуга \(v_1v_3\), граф \(H\) является минимальным примитивным расширением графа \(G\) и алгоритм завершен. Иначе выбирается источник \(u_k\) в соответствии с введенной нумерацией на шаге 4.
  6. В граф \(H\) добавляется дуга \(vu_k\) и граф \(H\) сжимается в новый граф \(T\).
  7. В \(T\) выполняется подсчет количества примитивных расширений - \(r\).
  8. Если \(r>0\), то переход на шаг 2. Иначе из \(H\) удаляется дуга \(vu_k\), \(k\) увеличивается на 1 и переход на шаг 5.

Асимптотическая сложность алгоритма: \(O(n^2k^2f(n))\), где \(n\) - количество вершин в \(G\), \(k\) - количество стоков в \(G\), \(f(n)\) - функция количества делителей.

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

Решение данной задачи включало в себя решение задачи вычисления количества минимальных сильно связных расширений линейных графов. 

Используемые источники
1. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997. 368 с.
2. Салий В.Н. Минимальные примитивные расширения ориентированных графов // Прикладная дискретная математика, 2008. С. 116 – 119.
3. Beasley Le Roy B., Kirkland S. A note on k-primitive directed graphs // Linear Algebra and Appl., 2003. P 67 – 74.
Information about the project
Surname Name
Ripinen Aleksey
Project title
Primitive expansion of linear graphs
Summary of the project
Problem of minimal primitive expansion is not solved for all directed graphs, but for some classes this problem have solution. This problem will be solved for linear graphs in this message. Linear graphs have two types: for first type this problem has solved, for second there was no solution. Because of this only second type graphs will be investigated. In this report was found the algorithm for building a minimal primitive expansion for linear graphs.
Keywords
linear graphs, minimal primitive expansion of graphs