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

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

Определение

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

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

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

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

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

Представительство

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

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

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

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

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

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

Миноры и двойственность

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

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

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

Алгоритмы

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

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

Родственные классы матроидов

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

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

Ссылки

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

[1] Тутте (1965) использует обратную терминологию, в которой он назвал матроиды связи «графическими», а матроиды цикла «совместными графиками», но более поздние авторы этого не последовали.

[tutte65-2] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Тутте, 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), «О характеристике графических матроидов Тутте», Annals of Discrete Mathematics , 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] Тутте, В.Т. (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] Сеймур, П.Д. (1981), «Распознавание графических матроидов», Combinatorica , 1 (1): 75–78, doi : 10.1007/BF02579179 , MR 0602418 , S2CID 35579707 .

[w69-13] Уэлш, DJA (1969), «Эйлер и двудольные матроиды», Journal of Combinatorial Theory , 6 (4): 375–377, doi : 10.1016/s0021-9800(69)80033-5 , MR 0237368 .

[whiteley-14] Уайтли, Уолтер (1996), «Некоторые матроиды из дискретной прикладной геометрии», Теория матроидов (Сиэтл, Вашингтон, 1995) , Contemporary Mathematics, vol. 197, Провиденс, Род-Айленд: Американское математическое общество, стр. 171–311, doi : 10.1090/conm/197/02540 , ISBN. 978-0-8218-0508-4 , МР 1411692 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]