Графы, гиперграфы и миноры их матриц инцидентности

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет информатики, математики и компьютерных наук

Программа подготовки бакалавров по направлению Прикладная математика и информатика

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Графы, гиперграфы и миноры их матриц инцидентности

Сафронов Денис Сергеевич

Научный руководитель

к.ф.-м.н.. Грибанов Дмитрий Владимирович

Нижний Новгород, 2019



ВВЕДЕНИЕ

В данной работе представлена и исследована тема «Графы, гиперграфы и миноры их матриц инцидентности», её целью является изучение взаимосвязей между внешним видом матрицы и её определителем. Для этого исследования мы будем использовать возможности программирования на языке C++ и библиотеку uBLAS. На начальном этапе мы сделали некоторые прогнозы относительно будущих результатов, основываясь на выводах из наших двух предыдущих работ. Затем создали алгоритм, который осуществляет полный перебор, модернизировали его и сравнили полученные результаты с результатами, которые мы ожидали.

Как известно, одним из приоритетных направлений современной теории оптимизации является целочисленное линейное программирование и комбинаторная оптимизация. Задачи такого рода часто представляют собой вопросы максимизации или минимизации определенного линейного функционала на многограннике, определяемом системой линейных неравенств. Среди рассматриваемых задач мы можем выделить подкласс задач, многогранники которых определяются системами линейных неравенств с ограниченным спектром миноров. В своей статье J. W. Grossman [3] рассматривает взаимосвязь между спектром миноров для матриц инцидентности простых графов и структурой этих графов. Матрица инцидентности -это форма представления графа, в которой указываются связи между ребрами и вершинами.Столбцы матрицы инцидентности соответствуют ребрам, а строки - вершинам. Ненулевое значение в ячейке матрицы указывает на связь между соответствующими ребрами и вершинами. Результаты этой статьи помогают лучше понять структуру матриц и систем с ограниченным спектром миноров. Гиперграф - это обобщение обычного графа, ребра которого могут содержать не только два элемента, но и любые подмножества вершин[15]. Такие объекты давно известны в математике, но термин «гиперграф» был введен в связи с успешным распространением на них многих понятий и методов теории обыкновенных графов.

Цель исследования - сформулировать и описать минорные характеристики матриц инцидентности некоторых классов гиперграфов. Данное исследование является актуальным, поскольку оно находит применение в теории задач целочисленного линейного программирования, которая является важной частью современной теории оптимизации. Особое внимание будет уделено классам унициклических гиперграфов, гиперграфов, генерируемых циркулянтами особого типа, и гиперграфовс числом упаковки циклами равным 1. Вособенности, их минимальным и максимальным минорам. Основная цель - попытаться применить методы и результаты, изученные в предыдущих работах2017 г. [1] и 2018 г. [2] к более широкому классу задач. матрица программирование гиперграф

В статье исследуются и определяются возможные миноры матрицы. Эти миноры зависят от максимального числа непересекающихся вершин нечетных циклов графа. Обращаясь к максимальным минорам, мы определили ранг матрицы инцидентности. Он зависит от количества компонент графа, которые не содержат нечетный цикл. Затем мы определили максимальные и минимальные абсолютные значения максимальных миноров матрицы инцидентности, а также ее форму Смита. Эти результаты используются для получения достаточных условий для ослабления ограничений целостности в задачах целочисленного линейного программирования, связанных с неориентированными графами. Попытка применить эти выводы к отдельным классам гиперграфов показала, что не все минорные свойства матриц инцидентности обычных графов сохраняются для гиперграфов. Однако нам удалось разобраться с принципом нахождения определителей некоторого класса циркулянтов. Несмотря на это, циркулянты генерируют только определенный класс гиперграфов, и ситуация будет более сложной, когда положение единиц и нулей в матрице инцидентности будет менее предсказуемым.

Обобщённые результаты и теоремы, которые мы будем использовать представлены в следующем разделе.



1. ОБОБЩЁННЫЕ РЕЗУЛЬТАТЫ

1.1 Теорема

Положимграф Gимеет одинаковое количество вершин и рёбер. Тогда:

±2,еслис1>0

det(A)= 0,если с1=0

Доказательство: Из условия того, что графGсвязный и количество вершин и рёбер в нём одинаково, следует, чтоG является унициклическим графом. Необходимо рассмотреть два случая.Пусть в первом случаеG не содержит листьев, это означает, чтоG является простым циклом и имеет длинуn. Если G- это простой цикл четной длины, то det(A) = 0, в обратном случае |det(A)| = 2.

Тогда во втором случае предположим, что в Gесть листья, а каждому листу в матрицеA соответствует строка с ровно одной 1. Далее, используя теорему Лапласа, разложим определитель матрицы A по выбранной строке. Такое разложение соответствует удалению выбранного листа и ребра, которое ему соответствует из графа G. Таким образом, получим граф G', состоящий из n-1 вершин и n-1 ребер. Исходный определитель может отличаться от определителя матрицы инцидентности графа G' исключительно знаком. Если таким образом мы удалим все листья, то доказательство сведётся к первому случаю.¦

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



1.2 Теорема

Пусть M- это подматрица А(G), имеющая размерность pxp. Тогда det(M) равен 0 или ±2k, где 0 ? k ? t0. Для каждого k есть минор, абсолютное значение которого равно 2k.

Доказательство:

Воспользуемся индукцией по p. Для p=1 det(M)=0, либоdet(M)=1. Будем считать, что данная теорема верна для любых матриц размерности от 1 до p-1. Пусть матрица М размерности pxpсодержит строку или столбец с одной единицей, тогда, если мы, используя теорему Лапласа, разложимdet(M) по этой строке(столбцу), то мы сведём вычисление определителя M к вычислению минора более низкого порядка, для которого справедливо предположение об индукции.

Далее предположим, что матрица М содержит нулевую строку или столбец, тогда, очевидно, чтоdet(M)=0. То есть,можем считать, что все столбцы, содержащиеся в матрице Мбудут иметь ровно две единицы. Отсюда следует, что все строки матрицы М также будут содержатьпо две единицы.

Таким образом, М - это матрица инцидентности некоторого графа с n вершинами, степень каждой из которых равна 2. Не трудно заметить, что граф такого вида будет являться объединением простых циклов (возможно одного), которые непересекаются. Если мы переупорядочим вершины и рёбра данной матрицы инцидентности, то она примет следующий вид, называемый блочно-диагональным:

Рис.1Блочно-диагональный вид



где M1, M2…Mkявляются матрицами инцидентности простых циклов. То естьdet(M)=?det(Mi).

Мы воспользовались предположением об индукции и получили, что если среди циклов есть хотя бы один чётный, то det(M)=0, либо det(M)=±2k, где k ? t0.Если 1 ? k ? t0, то в графеGбудут существоватьk экземпляровнечетных циклов, которыевершинно-непересекающиеся. Далее по тому же принципу составим матрицу M для графа, являющегося объединением данных циклов. Очевидно, что det(M)= ±2k. ¦

Сформулируем некоторые следствия из теоремы 1.2:

Следствие 1

НОК ненулевых миноров по абсолютным значениям из А есть 2t0.

Следствие 2

ЕслиGявляется Эйлеровым циклом с нечётным числом рёбер, то матрицаA(G) не тотально унимодулярная.

Известно, что любой цикл, являющийся Эйлеровым можно представить как объединение рёберно-непересекающихся простых циклов, посколькучисло рёбер в исходном графе нечётно, то в нём найдётся простой цикл, имеющий нечётную длину.Следующая теорема является дополнительным следствием из Теоремы 1.2:

0-----------------ннн7ззззззззззз=====-1.3 Теорема 1.3

Если граф G неориентированный, то он является двудольным, тогда и только тогда, когда матрица инцидентности А этого графа является тотально унимодулярной.

Доказательство:

Пусть графGявляется двудольным так, что t0=0. В этом случаевсе миноры из А равны 0или ±20=±1, это означает, что матрицаAявляется тотально унимодулярной.Если граф G не двудольный, тоt0?1, а значит матрица инцидентности A имеет минор, который по абсолютной величине больше, чем 1, т.е. матрица A не тотально унимодулярная. ¦



1.4 Теорема 1.4

Rank(A) = n-c0. Если удалятьс0строки из матрицы А, каждая из которых соответствует вершине для c0 компонентов графаG без нечётных циклов, то ранг полученной в результате матрицы будетn-c0.

Доказательство:

Ранг матрицы A=A(G) можем представить как сумму рангов матриц инцидентности компонент связности графа G. В первом случае предположим, что граф G является связным, и будем доказывать, что rank(A)=n в случае, если граф Gсодержит в себе нечётный цикл и rank(A)=n-1 если не содержит. Пусть графGсодержит в себе цикл нечётнымчислом вершин (т.е. с0=0). Граф G - связный, для данного дерева построим остов и присоединим к этому остову ребро, которое принадлежит нечётному циклу. В результате получим унициклический граф G, состоящий изn вершин и n рёбер. По теореме 1.1: матрица инцидентности такого графа имеет определитель, который по модулю равен двум. Отсюдаrank(A)=n.

Пусть граф G не имеет нечётного цикла (т.е. c0=1) во втором случае. По аналогичному принципу выделимT корневое остовное дерево для графа G, и в данном случае M будет (n-1) x (n-1) подматрицей матрицы A, которая была получена из A(T) путём удаления строки, которая соответствует корню. Как результат удаления данной строки появляются столбцы с только одной единицей.

Если расписать определитель М по данным столбцам, используя теорему Лапласа исвести вычисление определителя к вычислению определителя, который имеет на единицу меньший порядок, то получим, что |det(M)|=1. Таким образом, rank(A) ? n-1.

Чтобы понять, что исходный ранг не может быть равенn, достаточно того, что любая подматрица А, размерности nxn обязательно содержит в себе все строки и, следовательно, является матрицей инцидентности для подграфа графа G. Определитель такой матрицы равен 0, если G не содержит нечётный цикл, согласно теореме 1.1. ¦

1.5 Теорема 1.5

Максимальный минор матрицы А (по порядку) с максимальным значением по абсолютной величине будет равен 2t0, аненулевой максимальный минор с минимальным значением по абсолютной величине будет равен 2С1. Более того, для всехk, таких, что с1 ? k ? t0 существует максимальный минор (по порядку), значение по абсолютной величине которого равно 2k.

Доказательство:

Воспользуемся теоремой 1.2 для графа Gи определим подграф G', который будет состоять из объединения t0 вершинно-непересекающихся цикловс нечётным числом вершин. Для такого подграфа определитель матрицы инцидентности будет равен ±2t0.

Будем расширятьG' до G'' с n вершинами по следующему правилу. Для каждой из компонент связности графаG без нечётных циклов будем выделятьостовное дерево и присоединять к G''. Этихдобавлений будет с0 штук. Для всех компонент связности, которые имеют хотя бы 1 нечётный цикл сделаем следующее: будем добавлять сначала вершины, которые не содержатся ни в одном из нечётных циклов, затем будем добавлять рёбра, которые соединят нечётные циклы, выделенные нами раньше и эти компоненты связности. Для обеспечения связности компонент в G'' количество добавляемых нами рёбер должно быть минимальным. Тогда, потеореме 2.2: rank(A(G''))=n-c0=rank(A(G)). Построим матрицу М, которая будет получена удалением c0 строк из A(G''), как мы делали это в теореме 1.2, отсюдаrank(M)=n-c0. Вполне очевидно, что М содержит максимальный минор с определителем, модуль которогоравен ±2t0.

Следующая часть теоремы получается благодаря незначительному изменению предыдущей конструкции. Выберем вершинно-непересекающиеся циклыс нечётным числом вершин из t0 в количестве k штук. Далее убедимся, что из каждой компоненты связности, которая содержитцикл с нечётным числом вершин, мы выбрали по как минимум одному циклус нечётным числом вершин, это возможно из-за того, чтоk?c1. Далее доказательство аналогичное.¦

Следствие 3

НОД максимальных отличных от нуля миноров матрицыA равен 2C1.

Определение 1

Гиперграфом назовём пару G = (V, E), где V- этопроизвольное конечное множество, а E- это семейство подмножеств множества V.

Определение 2

Граф Gбудем называтьk-равномерным, если мощность всех его рёбер будет равна k. Очевидно, что 2-равномерный гиперграф является обычным графом.В работе не рассматриваем графы с кратными рёбрами.

Определение 3

Цепью длины L>0 или (v1, vi+1)-цепью в гиперграфе H = (V, E) будем называть такую последовательность v1, e1, v2, e2, … , eL, vL+1, что:

1) все вершиныv1, v2, … ,vL+1 будут различны, кроме крайних, если этонеобходимо.

2) e1,e2, … ,eL- это различные рёбра в гиперграфе H.

3) vi, vi+1 ?eiдля любыхi, в диапазоне от 1 до L.

Мы подразумеваем различные члены семейства EH как различные рёбра в гиперграфе H, хотя они могут совпадать как подмножества.

Определение 4

Циклом называется цепь, если L>1 и vL+1 = v1.

Определение 5

ЕслиH = (V, E) - это гиперграф и Ш ? V'?V, то подгиперграфом, который порождён множеством вершин V', будем называть гиперграф H' = (V', E'), где E' = {e': e' = e ? V' ? Ш, e?E}.

Определение 6

В гиперграфе Hвершины u и vназываем связанными только в том случае, еслиu = v, или в гиперграфе H существует (u, v)-цепь.

Определение 7

На множестве вершин исходного графа отношение связанности является в том числе и отношением эквивалентности. Классами такого отношения будем называть области связности гиперграфа H.В Гиперграфе Hкомпонентами называются подгиперграфы, порождённые областями связности. Будем обозначать как k(H)количество компонент гиперграфа H. Тогда,гиперграф Hназовём связным, если k(H) = 1. Заметим, что k(H) = k(K(H)), где k(K(H)) - это число компонент графа K(H).

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

Утверждение 1

Гиперграф H, где n-это число вершин, а m - число рёбер не имеет циклов,когда:

Утверждение 2

В гиперграфеHне будет циклов, если для каждого его непустого подмножества E' ?EHбудетвыполняться неравенство:



Утверждение 3

Если для каждого непустого подмножестваV' ? V гиперграфа H выполняется следующее неравенство:

, то гиперграф Hне имеет циклов.

Определение 8

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

Определение 9

Двудольный граф, который содержит внутри себя множество вершин V ? E и множество рёбер {(v, e) : (v, e)?VxE, v?e} называется кёниговым представлением гиперграфа H = (V, E), и обозначается как K(H).

Рис.2 Кёнигово представление

Определение 10

В гиперграфеH циклическим рангом называют циклический ранг его кёнигова представления, и обозначают какv(H).



Исходный гиперграфGимеет единственный цикл, когда v(H) = 1, т.е. когда (|e| - 1) = n - k(H) + 1.

Это следует из Определения 10 благодаря следствию о том, что гиперграф будет иметь единственный цикл, когда его циклический ранг равен 1. Определение 11

Для гиперграфа H = (V, E) введём понятие простого цикла, имеющего длину равнуюS. Этим циклом будет называться последовательность (A0, V0, A1,…, AS-1, VS-1, AS), где:

различные рёбра H- этоA0…AS-1,

ребро AS совпадает с A0,

различные вершины H-это V0,…,VS-1 ,более того,ViAi?Ai+1 для любых i= 0,…,s-1.

Теперь очевидно, что для любого графа, содержащего цикл, существует и простой цикл.

Для гиперграфов будем вводить понятие матрицы инцидентности аналогично тому, как это было сделано для простых графов. Получаем, что столбцы такой матрицы будут соответствоватьвершинам, а строки - рёбрам гиперграфа. Если соответствующая вершина входит в исходное гиперребро, то на пересечении i-й строки и j-го столбца поставим 1, и 0, в обратном случае.Для того, чтобы показать, что матрица инцидентности гипердерева будет являться тотально унимодулярной, мы воспользуемся леммой:

1.6 Лемма 2.1

Любое гипердерево всегда будет содержать лист (вершину степени 1).

Доказательство:

Данную лемму докажем от противного: пусть исходное гипердерево не содержит в себелистьев. Тогда, каждая вершина должна быть связана с хотя бы одной другой. Что означает, путём перебора полученной цепочки, мы обнаружим цикл, что будет противоречить определению гипердерева. ¦

1.7 Теорема 2.1

ПустьG- это гиперлес, тогда матрица A(G) будет являться матрицейинцидентности данного гиперлеса, а это означает, что матрица A(G) будет являться тотально унимодулярной.

Доказательство:

Предположим, что М будет являтьсяразмера kxk подматрицей A(G). Такая подматрица будет определять гиперграф G', внутри которого множество вершин является ещё и подмножеством вершин в исходном гиперграфе, в то время как рёбра будут соответствовать подмножеству рёбер в гиперграфе с условием того, что из ребра можно свободно изымать какое-либо подмножество вершин.G' является гиперлесом благодаря тому, что Gявляется гиперлесом.

Покажем, что det(M)= ±1 или 0. Для этого необходимо предположить, что в G' будут существовать изолированные вершины, это в свою очередь означает, что в М будет существоватькак минимум одна нулевая строка, соответственно определитель матрицы будет равен 0. Далее предположим, что в G' не будет существовать вершин, которые изолированы, тогда в исходном графебудет лист, а в матрице М будет существовать строка, соответствующая данному листу с только одной 1. Разложим определитель исходной матрицы с помощью теоремы Лапласа относительно выбираемой нами строки. В этом случае, все вычисления определителя будут сведены к вычислению определителя матрицы, имеющей порядокk-1 наk-1. Такая матрица соответствует гиперграфу, который мы можем получить удалением вершины и ребра из гиперлеса G'. Воспользуемся индукцией и получим, чтоdet(M) = ±1, 0. ¦

Рис.3 Гипердерево

1.8 Теорема 2.2

В матрице инцидентности унициклического гиперграфа максимальный минор не превосходит 2 по абсолютному значению.

Доказательство:

Для доказательства данной теоремы можем рассмотреть любую из квадратных подматриц.Всего 2 возможных случая:

1) Цикл не находится внутри матрицы.В таком случае подматрица будет задавать гиперлес. Нам известно, что любой из возможных миноров гиперлеса будет равен 0 или 1.

2)Цикл находится внутри матрицы.Тогда необходимо привести матрицу к такому виду, когда в каждой её строке и столбце содержатся минимум две единицы.Чтобы это сделать, нужно использовать теорему Лапласа. Как результат, все строки и столбцы, которые соответствуют висячим вершинам, будут удалены. Если рассмотреть кёнигово представление исходного графа, то заметим, что оно так же является унициклическим. Такое представление, по определению, является обыкновенным графом, а это означает, что выбранный нами граф так же является обыкновенным. Для обыкновенного графа можем применить теорему 1.1, что означает:

±2, если с1>0

det(A)=

0, если с1=0 ¦

Определение 12

Циркулянтом будем называть матрицу, если каждая следующая строка в ней, начиная с первой, получается путём циклической перестановки элементов строки, перед ней идущей.Циркулянт, который был получен из строки, где сначала идут k единиц, а затемn - k нулей будем обозначать как C(n,k).Циркулянт, который был получен из C(n, k) по следующему правилу: между каждой парой единиц первой строки поставимs - 1 нулей будем обозначать, какC(n, k, s). Очевидно, что C(n, k, 1) = C(n, k).

Приведём некоторые значения для определителей циркулянтов C(n, k, s). В данной таблице значения по строкам соответствуют числу вершин, а значения по столбцам - количеству нулей между друг за другом следующими единицами.

Рис.5 Циркулянт без пропусков



Рис.4 Таблица значений определителей циркулянтов

Рис.6 Циркулянт с пропусками

Если в циркулянте рёбра соединяют не соседние вершины, а вершины, которые находятся на некотором расстоянии друг от друга (например, через 1,2 и т.д. вершины), то граф всё ещё не унициклический. Каждая связка вершин представляет из себя квадратную подматрицу.Определитель состоит из блоков квадратных матриц, которые стоят по диагонали, его значение равно количеству единиц (в матрице инцидентности) возведённому в степень количества таких блоков квадратных матриц.

Утверждение 4

Пусть е - это первообразный корень n-й степени из единицы, тогда f(x) = b0 + b1x + ... + bn?1xn?1, тогда R(b0, b1, ..., bn?1) = f(1)f(е)f(е2)...f(еn?1).

Доказательство:

Чтобы доказать данное утверждение, необходимо умножить циркулянт на определитель Вандермонда. Если рассмотреть случай, когда n = 3, то используя теорему об умножении определителей, мы получим:

То есть, R(b0,b1,...,bn?1)W(1,е,е2,...,еn?1) = f(1)f(е)...f(еn?1)W(1,е,е2,...,еn?1). Поскольку определитель Вандермонда не равен нулю, мы получаем то, что требовалось. В общем случае можно провести аналогию с рассуждениями, представленными выше.¦

1.9 Теорема 2.3

|det(C(n, k))| = k [НОД(n, k)=1]

Доказательство:

Для доказательства рассмотрим следующий циркулянт:



Благодаря приведённому утверждению имеем f(x) = 1 + x + ... + xk?1 и R = k(1 + е + е2 + ... + еk?1)(1 + е2 + е4 + ... + е2(k?1))...(1 + еn?1 + е(n?1)2 + ... + е(n?1)(k?1)) = (Обозначим 1*)

здесь е является первообразным корнем n-й степени из единицы. Обозначим НОД(n, k) как d. Имеем еkn/d = 1. Дляd > 1 будет следовать, что один из множителей в 1* будет равен 0, соответственно R будет равен 0. Для d = 1, еkбудет являться первообразным корнем n-й степени из единицы, а числа 1, еk, е2k,..., е(n?1)kбудут исчерпывать абсолютно все значения корня n-й степени из единицы, поэтому R = k. ¦

1.10 Теорема 2.4

|det(C(n, k, s))| = kd [НОД(n/d, k)=1], гдеd= НОД(n, s)

1) Если НОД(n/НОД(n, s), k) ? 1, то det = 0

2) Если НОД(n/НОД(n, s), k) = 1, то det = kНОД(n, s)

где n - это число вершин, k - эторавномерностьгиперграфа, s = p+1 - это число пропусков между вершинами.

Доказательство:

Для доказательства необходимо показать, что C(n, k, s) будет разделяться на d циркулянтов C(n/d, k).В этом случаетекущая формула следует из предыдущей теоремы. ¦



2. ХОД РАБОТЫ НАД АЛГОРИТМОМ

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

Это было ожидаемо, потому как алгоритм грубой силы не отсеивает заведомо неверные структуры. Затем алгоритм был слегка модернизирован путем добавления простейших условий, которые понятны на интуитивном уровне, таких как: матрица не может состоять целиком из 0, количество единиц в матрице не должно быть меньше размерности и т. д. Однако, программа по-прежнему не могла эффективно работать даже с матрицами размерности 5 х 5. На этом этапе было важно провести математическое исследование и найти соответствующие условия для лексикографической оптимизации, поскольку мы заинтересованы в переборе матриц более высокой размерности.

Далее мы выявили такие условия, и смогли рассчитать максимальный и минимальный миноры для интересующих нас матриц. Таким образом, за приемлемое время мы можем перебрать все матрицы размерности 7 x 8, которые удовлетворяют сформулированным ранее условиям. Это позволяет нам проверить некоторые интересующие нас гипотезы и с высокой долей вероятности сформулировать новые.

Благодаря алгоритму модернизированного полного перебора мы сформулировали ряд правил, которые позволили сделать выводы о минорныххарактеристиках матрицы. Кроме того, мы смогли проверить некоторые гипотезы, которые являются логическими следствиями наших предыдущих работ. Для ускорения работы с матрицами использовали библиотекуuBLAS.

2.1 Описание алгоритма

Матрица размерности n(число рёбер) xm(число вершин) где m>n.

Количество единиц в столбцах рассматриваем строго k=3. То есть каждое ребро содержит в себе строго три вершины.

1. Класс VectorEnumerator()состоит из функций для генерации столбца. Создаём первыйстолбец матрицы, запоминаем положение единиц. Реализуем функцию next() для прибавления единиц, которая заканчивает свою работу при выполнении условия о том, что три единицы следуют друг за другом. 2. Класс MatrixEnumerator() содержит в себе функции для генерации матрицы.Каждыйследующийстолбец должен удовлетворять двум правилам: Используем лексикографию по столбцам, т.е. каждыйстолбецследующий правее должен быть меньше текущего (как число в двоичной с.с.). Это позволит уменьшить перебор на n! элементов.В каждом следующем столбцеположение хотя бы одной единицы должно совпадать с положением хотя бы одной единицы в одном из предыдущих столбцов.

3. Используем поиск в глубину для проверки связности графа (в том числе отсеиваем графы с блочно-диагональной структурой).Функцией isMatrixZero проверяемусловие, что матрица ненулевая.

4. С помощью библиотеки uBLAS считаем максимальный и минимальный по модулю ненулевыеминоры подматриц исходной матрицы.Используем uBLASпотому какэта библиотека помогает нам упрощать и ускорять выполнение подзадач.

5. Запоминаем ранг матрицы инцидентности.

6. В конце файла выводим значение максимального и минимального миноров и значение максимального минора среди минимальных.

7.Печатаем всю необходимую информацию в файл «results.txt».

2.2 Сложность алгоритма

Сложность алгоритма полного перебора оценивается как

C(mn) = (m!) / ((m-n)!*n!)= (m*(m-1)*(m-2)*…*(m-n-1)) / (m!), что грубо можем оценить как (mn) / (m!).

Однако, добавив условия лексикографической оптимизации сложность модернизированного алгоритма оценивается какCm(Сkn), k =3, что при грубой оценке равно (m3n) / ((6n*(n)!). Таким образом, получили n! выигрыш во времени.

Гипотезы, которые хотим проверить:

1. У матрицы инцидентности связного k-равномерного гиперграфа

минимальный по модулю минор всегда будет расти линейно относительно k и n.

У матрицы инцидентности связного k-равномерного гиперграфа есть минорприблизительно равный k по абсолютному значению, если матрица полного ранга. 3. Максимальный по модулю минор матрицы инцидентности связного k-равномерного гиперграфа является степенью k.

2.3 Результаты

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



Рис.7 Значения миноров

Некоторые выводы, которые удалось сформулировать благодаря анализу результатов работы алгоритма:

1.У матрицы инцидентности связного 3-равномерного гиперграфа максимальный среди минимальных по абсолютному значению минор всегда маленькийи имеет значение, которое растёт линейно относительно kи n.Следующие результаты работы алгоритма показывают, что у матрицы инцидентности связного 3-равномерного гиперграфа с числом рёбер равным 5, максимальный среди минимальных по абсолютному значению минор равен 5, что не противоречит условию, ведь 5 < 3 * 4. Значение 5 удалось найти для двух матриц:

Рис. 8 Матрица №1 с min = 5



Рис. 9 Матрица №2 с min = 5

2. Значения максимальных и минимальных по абсолютному значениюминоров зависят только от количества рёбер, количество вершин не оказывает влияния. Следующие два результата работы программы подтверждают этот вывод. Результаты для матрицы размерности 4 x5:

Рис. 10 Результаты для 4 x 5



Результаты для матрицы размерности 4 x6:

Рис. 11 Результаты для 4 x6

3.Заметили, что по значениям максимальных миноров все матрицы можно разделять на условные группы по соответствующим строкам (Рис. 7). В каждую из таких групп входит одна матрица с нечётным числом столбцов и одна с чётным (например, матрица с 9 рёбрами и матрица с 10 рёбрами).Значения миноров для этих двух матриц будут пропорциональны друг-другу и отличаться в два раза. Таким образом мы должны рассматривать пару, состоящую из нечётного и чётного числа столбцов в матрице инцидентности.Мы сформулировали принцип нахождения максимального минора для матрицы интересующей нас размерности в виде следующей гипотезы:

Гипотеза4

Пусть x(m) - это значение максимального по модулю минорадля исходной матрицы, который хотим вычислить, тогдаx(m -1)-это значение максимального по модулю минора для матрицы, число столбцов которой на один меньше исходной. Обозначим Dкак множество чисел, которые можно разделить на x(m).

Правила вычисления:

x(m)>x(m - 1).

Числа из Dне делятся на нечётное число из пары, созданной для поискаx(m).

x(m) * 2 делится на чётное число из пары, созданной для поискаx(m).

Выбираем минимальное x(m)из возможных.

Пример: Мы хотим вычислить максимальный по модулю минордля матрицы,в которой 9 столбцов (m = 9). Обозначим x(9)

Известно, что для матрицы, в которой 8 столбцов максимальный по

модулюминор равен 40 (x(8) = 40), следовательно x(9) >x(8) > 40.

2. x(9) = 45 не подходит, т.к. 45 делится на 9.

3-4. Из оставшихся чисел выбираем наименьшее, которое при умножении на 2 будет делиться на 10(как m+1). Это число 50. Следовательно x(9) = 50,x(10) = 100.

Таким образом, мы вычислили максимальные по абсолютному значению миноры для матриц с числом столбцов равным 9 и 10.



ЗАКЛЮЧЕНИЕ

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

Если гипотеза 1 получит математическое подтверждение, то в будущем мы сможем получить новые алгоритмы для задач целочисленного линейного программирования с ограниченными минорами, так как сможем построить алгоритм вычисления максимального минора для матриц инцидентности

3-равномерных гиперграфов с любым числом рёбер.



СПИСОК ЛИТЕРАТУРЫ

1. Сафронов Д. С. Грибанов Д. В. Графы, гиперграфы и миноры их матриц инцидентности (2017).

2. Сафронов Д. С. Грибанов Д. В. Графы, гиперграфы и миноры их матриц инцидентности (2018).

3. J. W. Grossman On the Minors of an Incidence Matrix and Its Smith Normal Form, Elsevier Science Inc. (1995).

4. K. A. Berman, Bicycles and spanning trees, SIAM J. Algebraic Discrete Methods (1986).

5. K. Corradi and A. J. Hajnal, On the maximal number of independent circuits in a graph, Acta Math. 14:423-439 (1963).

6. P. Erdos and L. Posa, On the maximal number of disjoint circuits of a graph, Publ. Math. Debrecen 9:3-12(1962).

7. Gribanov D., Veselov S. On integer programming with bounded determinants // Optimization Letters. Vol 10. No. 6. P. 1169-1177 (2016).

8. Gribanov D., Chirkov A. The width and integer optimization on simplices with bounded minors of the constraint matrices // Optimization Letters. Vol. 10. No. 6. P. 1179-1189 (2016).

9. Veselov S. I., Chirkov A. J. Integer program with bimodular matrix // Discrete // Optimization. V. 6, No 2. P. 220-222 (2009).

10. B. A. Trakhtenbrot Survey of Russian Approaches to Perebor (Brute-ForceSearch) Algorithms.

11. Грибанов Д. В., Малышев Д. С. Сложность некоторых задач на графах с ограниченными минорами их матриц ограничений // Журнал Средневолжского математического общества. Т. 18. № 3. С. 19-31. (2016)

12. Прасолов В. В., Задачи и теоремы линейной алгебры, Москва (2008). 13. А.А. Зыков, Гиперграфы, Успехи математических наук-1974. -№ 6.

13. 14. В.А. Евстигнеев, В.Н. Касьянов, Толковый словарь по теории графов,Новосибирск(1999).

14. 15. https://ru.wikipedia.org/wiki/Гиперграф



ПРИЛОЖЕНИЕ

Кодпрограммы:

#include "pch.h"

#include <iostream>

#include <fstream>

#include <bitset>

#include <cmath>

#include <vector>

#include <boost/numeric/ublas/matrix.hpp>

#include <boost/numeric/ublas/io.hpp>

#include <boost/numeric/ublas/lu.hpp>

#include <algorithm>

const int N = 50;

const int M = 50;

namespace ublas = boost::numeric::ublas;

class VectorEnumerator

{

private:

int m;

std::vector<int> line;

std::vector<int> indexes;

bool isComplete;

public:

VectorEnumerator(int _m, std::vector<int> _line) :

m(_m),

isComplete(false)

{

line.resize(m);

int j = 0;

for (int i = 0; i< m; i++)

{

line[i] = _line[i];

if (line[i])

{

indexes.push_back(i);

}

}

}

std::vector<int> get()

{

return line;

}

void next()

{

if (indexes[1] == (indexes[0] + 1) && indexes[2] == (indexes[1] + 1) && indexes[2] == (m - 1))

{

isComplete = true;

}

else if (indexes[2] < (m - 1))

{

int fInd = indexes[0];

int sInd = indexes[1];

int tInd = ++indexes[2];

line.assign(m, 0);

line[fInd] = 1;

line[sInd] = 1;

line[tInd] = 1;

}

else if (indexes[1] < (m - 2))

{

int fInd = indexes[0];

int sInd = ++indexes[1];

int tInd = indexes[2] = sInd + 1;

line.assign(m, 0);

line[fInd] = 1;

line[sInd] = 1;

line[tInd] = 1;

}

else

{

int fInd = ++indexes[0];

int sInd = indexes[1] = fInd + 1;

int tInd = indexes[2] = sInd + 1;

line.assign(m, 0);

line[fInd] = 1;

line[sInd] = 1;

line[tInd] = 1;

}

}

bool isCompleted()

{

return isComplete;

}

};

class MatrixEnumerator

{

private:

int n;

int m;

ublas::matrix<int> matrix;

bool isComplete;

void setLine(std::vector<int> line, int i)

{

for (int j = 0; j < m; j++)

{

matrix(i, j) = line[j];

}

}

std::vector<int>getLine(int i)

{

std::vector<int> line(m);

for (int j = 0; j < m; j++)

{

line[j] = matrix(i, j);

}

return line;

}

public:

MatrixEnumerator(int _n, int _m) :

n(_n),

m(_m),

isComplete(false)

{

matrix.resize(n, m);

std::vector<int> line;

line.assign(m, 0);

line[0] = line[1] = line[2] = 1;

VectorEnumeratorenumerator(m, line);

setLine(enumerator.get(), 0);

for (int i = 1; i< n; i++)

{

enumerator.next();

if (!enumerator.isCompleted())

{

setLine(enumerator.get(), i);

}

else

{

isComplete = true;

}

}

}

ublas::matrix<int> get()

{

return ublas::trans(matrix);

}

void next()

{

for (int i = n - 1; i>= 0; i--)

{

VectorEnumeratorenumerator(m,

getLine(i));

for (int j = i; j < n; j++)

{

enumerator.next();

if (!enumerator.isCompleted())

{

isComplete = false;

setLine(enumerator.get(), j);

}

else

{

isComplete = true;

break;

}

}

if (!isComplete)

{

break;

}

}

}

bool isCompleted()

{

return isComplete;

}

};

int dfs(int u, std::vector<bool>& visited, int n, int m, ublas::matrix<int> matrix)

{

int visitedVertices = 1;

visited[u] = true;

for (int i = 0; i< m; i++)

{

if (matrix(u, i))

{

for (int v = 0; v < n; v++)

{

if (v == u)

{

continue;

}

else if (!visited[v])

{

if (matrix(v, i))

{

visitedVertices += dfs(v, visited, n, m, matrix);

}

}

}

}

}

return visitedVertices;

}

std::vector<int> div(int x)

{

std::vector<int> result;

for (int i = 1; i< x; i++)

{

if (x % i == 0)

{

result.push_back(i);

}

}

return result;

}

bool isMatrixZero(int i, int j, int n, int m, ublas::matrix<int> matrix)

{

for (; i< n; i++)

{

for (; j < m; j++)

{

if (matrix(i, j))

{

return false;

}

}

}

return true;

}

template<typenameoutT>

void printMatrix(const ublas::matrix<int>& m, outT&fout)

{

for (size_ti = 0; i<m.size1(); i++)

{

fout<< "| ";

for (size_t j = 0; j <m.size2(); j++)

{

fout<<m(i, j) << " | ";

}

fout<<std::endl;

}

}

bool nextSet(std::vector<int>& a, int n, int m)

{

int k = m;

for (int i = k - 1; i>= 0; --i)

if (a[i] < n - k + i + 1)

{

++a[i];

for (int j = i + 1; j < k; ++j)

a[j] = a[j - 1] + 1;

return true;

}

return false;

}

ublas::matrix<int>getA(const ublas::matrix<int>& matrix, std::vector<int>ind)

{

int n = matrix.size2();

ublas::matrix<int> A(n, n);

for (int i = 0; i< n; i++)

{

for (int j = 0; j < n; j++)

{

A(i, j) = matrix(i, ind[j] - 1);

}

}

return A;

}

template<typenameValType>

ValTypedeterminant(const ublas::matrix<ValType>& matrix)

{

ublas::matrix<ValType>mLu(matrix);

ublas::permutation_matrix<std::size_t> pivots(matrix.size1());

auto isSingular = ublas::lu_factorize(mLu, pivots);

if (isSingular)

return static_cast<ValType>(0);

ValType det = static_cast<ValType>(1);

for (std::size_ti = 0; i<pivots.size(); ++i)

{

if (pivots(i) != i)

det *= static_cast<ValType>(-1);

det *= mLu(i, i);

}

return det;

}

std::vector<int>getMinors(const ublas::matrix<int>& matrix)

{

int n = matrix.size1();

int m = matrix.size2();

std::vector<int> minors;

std::vector<int> a(n);

for (int i = 1; i<= n; i++)

{

a[i - 1] = i;

}

minors.push_back(std::abs(determinant(getA(matrix, a))));

while (nextSet(a, n, m))

{

minors.push_back(

static_cast<int>(

std::abs(determinant<float>(getA(matrix, a)))

)

);

}

return minors;

}

int main()

{

std::ofstreamfout("results.txt");

int n, m;

std::cout<< "Enter n and m: ";

std::cin>> n;

std::cin>> m;

bool printOrNot;

std::cout<< "Print or not(1/0): ";

std::cin>>printOrNot;

int maxMinor = 0;

int minMinor = 100000;

int currentMax = 0;

int currentMin = 1000000;

int minDifference = 0;

std::vector <int>vectorMin;

MatrixEnumeratorenumerator(n, m);

while (!enumerator.isCompleted())

{

std::vector<bool> visited;

visited.assign(n, false);

if (dfs(0, visited, n, m, enumerator.get()) == n)

{

if (printOrNot)

{

printMatrix(enumerator.get(), fout);

}

fout<< "rang = " << n <<std::endl;

fout<< "minors by abs: ";

std::vector<int> minors =

getMinors(enumerator.get());

for (auto minor : minors)

{

fout<< minor << ", ";

if ((std::abs(minor) >

std::abs(currentMax)) && (minor > 0))

{

currentMax = std::abs(minor);

if (maxMinor<

std::abs(currentMax))

{

maxMinor =

std::abs(currentMax);

}

}

if ((std::abs(minor) <

std::abs(currentMin)) && (minor > 0))

{

currentMin = std::abs(minor);

if ((minMinor>

std::abs(currentMin)) && (minMinor> 0))

{

minMinor =

std::abs(currentMin);

}

}

}

if ((currentMax == 0) && (currentMin == 1000000))

{

currentMin = 0;

}

vectorMin.push_back(

static_cast<int>(currentMin)

);

fout<<std::endl;

fout<< "max: " <<currentMax<< ' ';

fout<< "min: " <<currentMin<< ' ';

fout<<std::endl;

}

currentMax = 0;

currentMin = 1000000;

enumerator.next();

fout<<std::endl;

}

fout<<std::endl<< "Maximal minor is = " <<maxMinor<< std::endl;

fout<<std::endl<< "Minimal minor is = " <<minMinor<< std::endl;

fout<<std::endl;

for (unsigned int i = 0; i<vectorMin.size(); i++)

if (vectorMin[i] >minDifference)

{

minDifference = vectorMin[i];

}

fout<<std::endl<< "Maximaum of minimums is " <<minDifference<< std::endl;

fout.close();

return 0;

}

Размещено на Allbest.ru