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

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

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

В закрытие ${\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}$.

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

Представление

Графический матроид графа ${\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]

Несовершеннолетние и двойственность

Два разных графа (красный), которые являются двойниками одного и того же плоского графа (бледно-синий). Несмотря на то, что они неизоморфны как графы, они имеют изоморфные графические матроиды.

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

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

Алгоритмы

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

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

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

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

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

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

1. Тутт (1965) использует перевернутую терминологию, в которой он назвал матроиды облигаций «графическими», а матроиды циклов - «когографическими», но более поздние авторы не последовали этому.
2. Тутте, В. Т. (1965), «Лекции по матроидам» (PDF), Журнал исследований Национального бюро стандартов, 69B: 1–47, Дои:10.6028 / jres.069b.001, МИСТЕР  0179781. См., В частности, раздел 2.5, «Связующий матроид графа», стр. 5–6, раздел 5.6, «Графические и копографические матроиды», стр. 19–20, и раздел 9, «Графические матроиды», стр. 38–47.
3. Биркофф, Гарретт (1995), Теория решеток, Публикации коллоквиума, 25 (3-е изд.), Американское математическое общество, стр. 95, ISBN  9780821810255.
4. Сеймур, П.Д. (1980), "О характеристике Тутте графических матроидов", Анналы дискретной математики, 8: 83–90, Дои:10.1016 / S0167-5060 (08) 70855-0, МИСТЕР  0597159.
5. Джерардс, А. М. Х. (1995), "О характеристике Тутте графических матроидов - графическое доказательство", Журнал теории графов, 20 (3): 351–359, Дои:10.1002 / jgt.3190200311, МИСТЕР  1355434.
6. Тутте, В. Т. (1958), «Теорема о гомотопии для матроидов. I, II», Труды Американского математического общества, 88: 144–174, Дои:10.2307/1993244, МИСТЕР  0101526.
7. Каргер, Дэвид Р.; Klein, Philip N .; Тарджан, Роберт Э. (1995), "Рандомизированный алгоритм линейного времени для поиска минимальных остовных деревьев", Журнал Ассоциации вычислительной техники, 42 (2): 321–328, Дои:10.1145/201019.201022, МИСТЕР  1409738
8. Фредман, М.Л.; Уиллард, Д. Э. (1994), «Транс-дихотомические алгоритмы для минимальных остовных деревьев и кратчайших путей», Журнал компьютерных и системных наук, 48 (3): 533–551, Дои:10.1016 / S0022-0000 (05) 80064-9, МИСТЕР  1279413.
9. Шазель, Бернар (2000), "Минимальный алгоритм остовного дерева с обратной сложностью типа Аккермана", Журнал Ассоциации вычислительной техники, 47 (6): 1028–1047, Дои:10.1145/355541.355562, МИСТЕР  1866456.
10. Тутте, В. Т. (1960), «Алгоритм определения того, является ли данный двоичный матроид графическим». Труды Американского математического общества, 11: 905–917, Дои:10.2307/2034435, МИСТЕР  0117173.
11. Биксби, Роберт Э .; Каннингем, Уильям Х. (1980), "Преобразование линейных программ в сетевые задачи", Математика исследования операций, 5 (3): 321–357, Дои:10.1287 / moor.5.3.321, МИСТЕР  0594849.
12. Сеймур, П.Д. (1981), "Распознавание графических матроидов", Комбинаторика, 1 (1): 75–78, Дои:10.1007 / BF02579179, МИСТЕР  0602418.
13. Валлийский, Д. Дж. А. (1969), «Эйлер и двудольные матроиды», Журнал комбинаторной теории, 6: 375–377, Дои:10.1016 / с0021-9800 (69) 80033-5, МИСТЕР  0237368.
14. Уайтли, Уолтер (1996), «Некоторые матроиды из дискретной прикладной геометрии», Теория матроидов (Сиэтл, Вашингтон, 1995), Современная математика, 197, Провиденс, Род-Айленд: Американское математическое общество, стр. 171–311, Дои:10.1090 / conm / 197/02540, МИСТЕР  1411692.