Графический матроид

В математической теории матроидов , А графический матроид (также называемый цикл матроидом или многоугольник матроидом ) является матроидом , чьи независимых множества являются лесами в заданном конечном неориентированном графе . В двойных матроидах графических матроидов называются совместно графические матроиды или матроиды облигаций . ^[1] Матроид, который является одновременно графическим и копографическим, называется плоским матроидом ; это и есть графические матроиды, образованные из плоских графов .

Определение [ править ]

Матроид может быть определен как семейство конечных множеств ( так называемого «независимые наборы» матроид) , который закрыт под подмножествами и удовлетворяет «обменную собственность»: если наборы и оба независимы, и больше , чем , то есть - такой элемент , который остается независимым. Если - неориентированный граф и - семейство множеств ребер, которые образуют леса в , то очевидно, что он замкнут относительно подмножеств (удаление ребер из леса оставляет другой лес). Он также удовлетворяет свойству обмена: если и являются лесами, и имеет больше ребер, чем , то он имеет меньше связных компонентов, поэтому${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle x \ in A \ setminus B}$${\displaystyle B\cup \{x\}}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$Принцип закуток есть компонент из который содержит вершины из двух или более компонентов . Вдоль любого пути от вершины одного компонента до вершины другого компонента должно быть ребро с конечными точками в двух компонентах, и это ребро может быть добавлено для создания леса с большим количеством ребер. Таким образом, образует независимые наборы матроида, называемого графическим матроидом или . В более общем смысле матроид называется графическим, если он изоморфен графическому матроиду графа, независимо от того, являются ли его элементы ребрами графа. ^[2]${\displaystyle C}$${\displaystyle A}$${\displaystyle B}$${\displaystyle C}$${\displaystyle B}$${\displaystyle B}$${\displaystyle F}$${\displaystyle G}$${\displaystyle M(G)}$

Основания графической матроиды являются полным затягивающим лесом из , и схем являются простыми циклами из . Ранг в множестве ребер графа является , где этим количество вершин в подграфе , образованных ребрами в и этом числе компонент связности одного и тот же подграф. ^[2] Коранг графического матроида известен как ранг цепи или цикломатическое число.${\displaystyle M(G)}$${\displaystyle G}$${\displaystyle M(G)}$${\displaystyle G}$${\displaystyle M(G)}$${\displaystyle X}$${\displaystyle G}$${\displaystyle r(X)=n-c}$${\displaystyle n}$${\displaystyle X}$${\displaystyle c}$

Решетка квартир [ править ]

Замыкание множества ребер в является плоской , состоящий из ребер, которые не зависят от (то есть края, концы которого соединены друг с другом путем в ). Эту плоскость можно отождествить с разбиением вершин на компоненты связности подграфа, образованного : Любым множеством ребер, имеющим такое же замыкание, которое дает одно и то же разбиение вершин, и может быть восстановлено из разбиения графа. вершин, так как состоит из ребер, концы которых принадлежат одному и тому же набору в разбиении. В решетке плоскостей этого матроида существует отношение порядка${\displaystyle \operatorname {cl} (S)}$${\displaystyle S}$${\displaystyle M(G)}$${\displaystyle S}$${\displaystyle S}$${\displaystyle G}$${\displaystyle S}$${\displaystyle S}$${\displaystyle \operatorname {cl} (S)}$${\displaystyle x\leq y}$всякий раз, когда перегородка, соответствующая flat,  является уточнением перегородки, соответствующей flat  .${\displaystyle x}$${\displaystyle y}$

В этом аспекте графических матроидов особенно важен графический матроид для полного графа , потому что он позволяет формировать каждое возможное разбиение набора вершин как набор связанных компонентов некоторого подграфа. Таким образом, решетка квартир графического матроида системы естественно изоморфна решетке разбиений -элементного множества . Поскольку решетки плоскостей матроидов являются в точности геометрическими решетками , отсюда следует, что решетка разбиений также является геометрической. ^[3]${\displaystyle K_{n}}$${\displaystyle K_{n}}$${\displaystyle n}$

Представление [ править ]

График матроид графа может быть определен как столбец матроида любой ориентированной матрицы инцидентности из . Такая матрица имеет по одной строке для каждой вершины и по одному столбцу для каждого ребра. Столбец для ребра имеет в строке для одной конечной точки, в строке для другой конечной точки и в другом месте; выбор конечной точки и какого знака является произвольным. Матроид столбцов этой матрицы имеет в качестве своих независимых наборов линейно независимые подмножества столбцов.${\displaystyle G}$${\displaystyle G}$${\displaystyle e}$${\displaystyle +1}$${\displaystyle -1}$${\displaystyle 0}$

Если набор ребер содержит цикл, то соответствующие столбцы (умноженные на, если необходимо, чтобы переориентировать ребра последовательно вокруг цикла) суммируются до нуля и не являются независимыми. И наоборот, если набор ребер образует лес, то, многократно удаляя листья из этого леса, можно по индукции показать, что соответствующий набор столбцов независим. Следовательно, матрица-столбец изоморфна .${\displaystyle -1}$${\displaystyle M(G)}$

Этот метод представления графических матроидов работает независимо от поля, в котором определен угол падения. Следовательно, графические матроиды образуют подмножество обычных матроидов , матроидов, которые имеют представления по всем возможным полям. ^[2]

Решетка плоскостей графического матроида также может быть реализована как решетка расположения гиперплоскостей , фактически как подмножество расположения кос , гиперплоскости которого являются диагоналями . А именно, если вершины являются вершинами , мы включаем гиперплоскость всякий раз, когда является ребром .${\displaystyle H_{ij}=\{(x_{1},\ldots ,x_{n})\in \mathbb {R} ^{n}\mid x_{i}=x_{j}\}}$${\displaystyle G}$${\displaystyle v_{1},\ldots ,v_{n},}$${\displaystyle H_{ij}}$${\displaystyle e=v_{i}v_{j}}$${\displaystyle G}$

Подключение к Matroid [ править ]

Матроид называется связным, если он не является прямой суммой двух меньших матроидов; то есть он связан тогда и только тогда, когда не существует двух непересекающихся подмножеств элементов таких, что функция ранга матроида равна сумме рангов в этих отдельных подмножествах. Графические матроиды связаны тогда и только тогда, когда лежащий в их основе граф связан и с двумя вершинами . ^[2]

Несовершеннолетние и двойственность [ править ]

Матроид является графическим тогда и только тогда, когда его миноры не включают ни одного из пяти запрещенных миноров: равномерный матроид , плоскость Фано или ее двойник, или двойники и, определенные из полного графа и полного двудольного графа . ^{[2] [4] [5]} Первые три из них являются запрещенными минорами для обычных матроидов, ^[6] и двойники и являются регулярными, но не графическими.${\displaystyle U{}_{4}^{2}}$${\displaystyle M(K_{5})}$${\displaystyle M(K_{3,3})}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$${\displaystyle M(K_{5})}$${\displaystyle M(K_{3,3})}$

Если матроид является графическим, его дуал («копографический матроид») не может содержать дуалы этих пяти запрещенных миноров. Таким образом, дуал также должен быть обычным и не может содержать в качестве миноров два графических матроида и . ^[2]${\displaystyle M(K_{5})}$${\displaystyle M(K_{3,3})}$

Из-за этой характеристики и теоремы Вагнера, характеризующей плоские графы как графы без графа или без второстепенного графа , следует, что графический матроид является копографическим тогда и только тогда, когда он плоский; это критерий планарности Уитни . Если плоская, двойственным является графическим матроидом из двойственного графа из . Хотя они могут иметь несколько двойных графов, все их графические матроиды изоморфны. ^[2]${\displaystyle K_{5}}$${\displaystyle K_{3,3}}$ ${\displaystyle M(G)}$${\displaystyle G}$${\displaystyle G}$${\displaystyle M(G)}$${\displaystyle G}$${\displaystyle G}$

Алгоритмы [ править ]

Минимальный весовой базис графического матроида - это минимальное остовное дерево (или минимальный остовный лес, если базовый граф отключен). Алгоритмы вычисления минимальных остовных деревьев интенсивно изучаются; известно, как решить проблему за линейное рандомизированное ожидаемое время в сравнительной модели вычислений ^[7] или за линейное время в модели вычислений, в которой веса ребер являются небольшими целыми числами, а побитовые операции разрешены с их двоичными представлениями. ^[8] Самая быстрая из известных временных рамок, которая была доказана для детерминированного алгоритма, является слегка сверхлинейной. ^[9]

Несколько авторов исследовали алгоритмы проверки того, является ли данный матроид графическим. ^{[10] [11] [12]} Например, алгоритм Тутте (1960) решает эту проблему, когда известно, что вход является двоичным матроидом . Сеймур (1981) решает эту проблему для произвольных матроидов, которым предоставляется доступ к матроиду только через оракул независимости , подпрограмму, которая определяет, является ли данный набор независимым.

Связанные классы матроидов [ править ]

Некоторые классы матроидов были определены из хорошо известных семейств графов путем формулирования характеристики этих графов в терминах, которые имеют более общий смысл для матроидов. К ним относятся двудольные матроиды , в которых все схемы четные, и матроиды Эйлера , которые можно разбить на непересекающиеся схемы. Графический матроид является двудольным тогда и только тогда, когда он происходит от двудольного графа, а графический матроид является эйлеровым тогда и только тогда, когда он происходит от эйлерова графа . В графических матроидах (и в более общем плане в бинарных матроидах ) эти два класса двойственны: графический матроид является двудольным, если и только если его двойственный матроидэйлеров, а графический матроид эйлеров тогда и только тогда, когда его двойственный матроид двудольный. ^[13]

Графические матроиды - это одномерные матроиды жесткости, матроиды , описывающие степени свободы структур жестких балок, которые могут свободно вращаться в вершинах, где они встречаются. В одном измерении такая структура имеет количество степеней свободы, равное количеству связанных компонентов (количество вершин минус ранг матроида), а в более высоких измерениях - количество степеней свободы d -мерной структуры с n вершинами. является дп минус матроидом ранга. В двумерных матроидах жесткости графы Ламана играют роль, которую остовные деревья играют в графических матроидах, но структура матроидов жесткости в размерностях больше двух изучена недостаточно. ^[14]

Ссылки [ править ]