Введение

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

Определение

Матроид может быть определен как семейство конечных множеств (называемых "независимыми множествами" матроида), которое замкнуто относительно подмножеств и удовлетворяет "свойству обмена": если множества A и B оба независимы, и A больше B, то существует элемент x, такой что B ∪ {x} остается независимым. Если G – ненаправленный граф, а F – семейство множеств ребер, образующих леса в G, то F очевидно замкнуто относительно подмножеств (удаление ребер из леса дает другой лес). Оно также удовлетворяет свойству обмена: если A и B – оба леса, и A содержит больше ребер, чем B, то у A меньше связных компонент, поэтому, по принципу Дирихле, существует компонента в A, содержащая вершины из двух или более компонент B. Вдоль любого пути в G от вершины в одной компоненте B к вершине в другой компоненте, должен быть ребро с концами в двух компонентах, и это ребро можно добавить к B, чтобы получить лес с большим количеством ребер. Таким образом, F формирует независимые множества матроида, называемого графическим матроидом графа G или M(G). В более общем смысле, матроид называется графическим, если он изоморфен графическому матроиду некоторого графа, независимо от того, являются ли его элементы сами ребрами в графе.

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

Графический матроид графа может быть определен как матроид столбцов любой ориентированной матрицы инцидентности. Такая матрица имеет одну строку для каждой вершины и один столбец для каждого ребра. Столбец для ребра содержит 1 в строке для одной конечной точки, -1 в строке для другой конечной точки и 0 в остальных местах; выбор конечной точки, которой присвоить какой знак, произволен. Матроид столбцов этой матрицы имеет в качестве независимых множеств линейно независимые подмножества столбцов. Если множество ребер содержит цикл, то соответствующие столбцы (умноженные на -1, если необходимо, чтобы согласованно переориентировать ребра вдоль цикла) суммируются в ноль и не являются независимыми. И наоборот, если множество ребер образует лес, то путем многократного удаления листьев из этого леса можно индуктивно доказать, что соответствующее множество столбцов независимо. Следовательно, матроид столбцов изоморфен. Этот метод представления графических матроидов работает независимо от поля, над которым определена матрица инцидентности. Поэтому графические матроиды образуют подмножество регулярных матроидов, матроидов, которые имеют представления над всеми возможными полями. Первые три из них являются запрещенными минорами для регулярных матроидов, а дуалы и являются регулярными, но не графическими. Если матроид графический, его дуал (сографический матроид) не может содержать дуалов этих пяти запрещенных миноров. Таким образом, дуал также должен быть регулярным и не может содержать в качестве миноров два графических матроида и / или за линейное время в модели вычислений, в которой веса ребер являются небольшими целыми числами и допускаются побитовые операции над их двоичными представлениями. Самая быстрая известная доказанная временная сложность для детерминированного алгоритма немного сверхлинейна. Несколько авторов исследовали алгоритмы для проверки, является ли данный матроид графическим. Например, алгоритм решает эту проблему, когда известно, что входные данные являются бинарным матроидом. решает эту проблему для произвольных матроидов, предоставляя доступ к матроиду только через оракул независимости – подпрограмму, определяющую, является ли заданное множество независимым.

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

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