Построение минимальной сильно связной реконструкции произвольных орграфов Выполнила А.С. Кадушкина Научный руководитель. проф. В.Н. Салий

Под ориентированным графом понимается пара G = (V,α), где V конечное непустое множество и α – отношение смежности на нем. Элементы множества V называются вершинами графа, а пары, входящие в отношение смежности α, - его дугами. Двудольным орграфом называется орграф H=(U U V, α), где U V = Ǿ, α U V. Все элементы из U - источники, из V - стоки. Пусть U ={u1, … un}, V= {v1, …. vk}. Паросочетанием в неориентированном графе называется множество попарно несмежных ребер. Паросочетание называется наибольшим, если число ребер в нем наибольшее среди всех паросочетаний графа H. Конденсацией орграфа G называется орграф G*, вершины v 1, v 2, …v m которого соответствуют классам отношения ε взаимной достижимости орграфа G, и пара (v i, v j ) является дугой в G* тогда и только тогда, когда в G есть дуга, начало которой принадлежит компоненте v i, а конец – v j. Необходимые определения

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

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

2. Построим двудольный граф Н=(U H S H, α H ), где U H – множество источников орграфа G 0, S H – множество его стоков, α H = {(u i, s j )| s j достижима из u i }. Введем новый порядок перечисления вершин графа G 0. Построим симметризацию графа Н. Введенные переобозначения: v 1 w 1 ; v 2 u 1 ; v 3 s 1 ; v 4 s 2 ; v 6 s 3 ; {v 7, v 8 } u 2 ; v 9 s 4.

3.Найдем наибольшее паросочетание М симметризации графа H; Пусть m 1, m 2, …m n – ребра из M, m i ={u i, s j }. Пусть Q H = U Q S Q – множество вершин, не насыщенных парос очетанием

4. Построим контур следующим образом:

5. Если множество Q H непустое, то

6. Возвращаясь к исходным обозначениям (сопоставление вершин двудольного графа вершинам исходного графа в шаге 2), строим дуги, проведенные в двудольном графе H, в исходном орграфе G.

Доказательство минимальности данного построения. k = max(k u,k s )+k w, где k – число добавочных дуг, k u - число источников конденсации, k s – число стоков конденсации, k w – число изолированных вершин.

Результатом работы является следующая Теорема Каждый произвольный орграф путем добавления дуг может быть перестроен в сильно связный, при этом минимальное число добавочных дуг k = max(k u, k s )+k w, где k – число добавочных дуг, k u - число источников конденсации, k s – число стоков конденсации, k w – число изолированных вершин конденсации.

Литература Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. Емеличев В.А., Мельников О.И. Лекции по теории графов. Кадушкина А.С. Минимальные сильно связные реконструкции ориентированных графов // Компьютерные науки и информационные технологии. Материалы науч. конф. – Саратов: Изд-во Сарат. ун-та, – с Кадушкина А.С. Программа для ЭВМ «Нахождение минимальной сильно связной реконструкции для связных ориентированных графов». Свидетельство РОСПАТЕНТа от Мирзаянов М.Р. Сильно связные конгруэнции ориентированных графов // Теоретические проблемы информатики и ее приложений. Вып Саратов: Изд-во Сарат. ун-та, С Салий В.Н. Оптимальные реконструкции графов/ В кн.: Современные проблемы дифференциальной геометрии и общей алгебры. – Саратов: Изд-во Сарат.ун-та, 2008, С

Спасибо за внимание