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

Матроид с графовыми лесами как независимыми множествами

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

Определение

Матроид может быть определен как семейство конечных множеств (называемых «независимыми множествами» матроида), замкнутое относительно подмножеств и удовлетворяющее «свойству обмена»: если множества и оба независимы и больше , то - это такой элемент , который остается независимым. Если - неориентированный граф и семейство наборов ребер, образующих леса в , то он явно замкнут относительно подмножеств (удаление ребер из леса оставляет другой лес). Он также удовлетворяет свойству обмена: если и оба являются лесами и имеют больше ребер, чем , то он имеет меньше связных компонентов, поэтому по принципу «ячейки» существует компонент , который содержит вершины из двух или более компонентов . Вдоль любого пути от вершины одного компонента к вершине другого компонента должно быть ребро с конечными точками в двух компонентах, и это ребро можно добавить, чтобы создать лес с большим количеством ребер. Таким образом, образует независимые множества матроида, называемого графическим матроидом или . В более общем смысле, матроид называется графическим, если он изоморфен графическому матроиду графа, независимо от того, являются ли его элементы сами ребрами графа. ^[2] ${\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}$ ${\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}$

Решетка квартир

Замыканием множества ребер в является плоскость , состоящая из ребер, не независимых от (т . е. ребер, концы которых соединены друг с другом путем в ). Эту плоскость можно отождествить с разбиением вершин на связные компоненты подграфа, образованного : вершин, поскольку он состоит из ребер, конечные точки которых принадлежат одному и тому же множеству в разбиении. В решетке квартир этого матроида существует отношение порядка всякий раз, когда разбиение, соответствующее Flat,  является уточнением разбиения, соответствующего Flat  . ${\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}$ ${\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}$

Возможность подключения Матроида

Матроид называется связным, если он не является прямой суммой двух меньших матроидов; то есть он связен тогда и только тогда, когда не существует двух непересекающихся подмножеств элементов, таких, что функция ранга матроида равна сумме рангов в этих отдельных подмножествах. Графические матроиды связны тогда и только тогда, когда базовый граф одновременно связен и 2-связен . ^[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 вершинами. dn минус ранг матроида. В двумерных матроидах жесткости графы Ламана играют роль, которую остовные деревья играют в графических матроидах, но структура матроидов жесткости в размерностях больше двух не совсем понятна. ^[14]

Рекомендации

1. Тутте (1965) использует обратную терминологию, в которой он назвал матроиды связи «графическими», а матроиды цикла «совместными графиками», но более поздние авторы этого не последовали.
2. Tutte, WT (1965), «Лекции по матроидам» (PDF) , Журнал исследований Национального бюро стандартов , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR  0179781. См., в частности, раздел 2.5 «Бонд-матроид графа», стр. 5–6, раздел 5.6 «Графические и кографические матроиды», стр. 19–20 и раздел 9 «Графические матроиды», стр. 38–47.
3. Биркгоф, Гарретт (1995), Теория решетки, Публикации коллоквиума, том. 25 (3-е изд.), Американское математическое общество, с. 95, ISBN 9780821810255.
4. Сеймур, П.Д. (1980), «О характеристике графических матроидов Тутте», Анналы дискретной математики , 8 : 83–90, doi : 10.1016/S0167-5060(08)70855-0, ISBN 9780444861108, МР  0597159.
5. Джерардс, AMH (1995), «О характеристике графических матроидов Тутте — графическое доказательство», Journal of Graph Theory , 20 (3): 351–359, doi : 10.1002/jgt.3190200311, MR  1355434, S2CID  31334681.
6. Тутте, WT (1958), «Гомотопическая теорема для матроидов. I, II», Transactions of the American Mathematical Society , 88 (1): 144–174, doi : 10.2307/1993244, JSTOR  1993244, MR  0101526.
7. Каргер, Дэвид Р .; Кляйн, Филип Н.; Тарьян, Роберт Э. (1995), «Рандомизированный алгоритм линейного времени для поиска минимальных остовных деревьев», Журнал Ассоциации вычислительной техники , 42 (2): 321–328, doi : 10.1145/201019.201022 , MR  1409738
8. Фредман, ML ; Уиллард, DE (1994), «Трансдихотомические алгоритмы для минимальных остовных деревьев и кратчайших путей», Journal of Computer and System Sciences , 48 ​​(3): 533–551, doi : 10.1016/S0022-0000(05)80064-9 , МР  1279413.
9. Шазель, Бернар (2000), «Алгоритм минимального остовного дерева со сложностью обратного типа Аккермана», Журнал Ассоциации вычислительной техники , 47 (6): 1028–1047, doi : 10.1145/355541.355562 , MR  1866456, S2CID  6276962.
10. Тутте, WT (1960), «Алгоритм определения того, является ли данный двоичный матроид графическим». Proceedings of the American Mathematical Society , 11 (6): 905–917, doi : 10.2307/2034435, JSTOR  2034435, MR  0117173.
11. Биксби, Роберт Э.; Каннингем, Уильям Х. (1980), «Преобразование линейных программ в сетевые задачи», Mathematics of Operations Research , 5 (3): 321–357, doi : 10.1287/moor.5.3.321, MR  0594849.
12. Сеймур, PD (1981), «Распознавание графических матроидов», Combinatorica , 1 (1): 75–78, doi : 10.1007/BF02579179, MR  0602418, S2CID  35579707.
13. Уэлш, DJA (1969), «Эйлер и двудольные матроиды», Журнал комбинаторной теории , 6 (4): 375–377, doi : 10.1016/s0021-9800(69)80033-5 , MR  0237368.
14. Уайтли, Уолтер (1996), «Некоторые матроиды из дискретной прикладной геометрии», Теория матроидов (Сиэтл, Вашингтон, 1995) , Contemporary Mathematics, vol. 197, Провиденс, Род-Айленд: Американское математическое общество, стр. 171–311, doi : 10.1090/conm/197/02540 , MR  1411692..