Войти
В комбинаторной оптимизации, то матроид пересечение проблема является найти большой общий независимый набор в двух матроидах над тем же набором земли. Если элементам матроида присвоены действительные веса, задача взвешенного пересечения матроидов состоит в том, чтобы найти общий независимый набор с максимально возможным весом. Эти задачи обобщают многие проблемы комбинаторной оптимизации, включая нахождение максимальных сопоставлений и сопоставлений максимального веса в двудольных графах и нахождение ветвей в ориентированных графах.
Теорема о пересечении матроидов, разработанная Джеком Эдмондсом, гласит, что всегда существует простой сертификат верхней границы, состоящий из разделения основного набора между двумя матроидами, значение которого (сумма соответствующих рангов ) равно размеру максимального общего независимого набор. На основе этой теоремы проблема пересечения матроидов для двух матроидов может быть решена за полиномиальное время с использованием алгоритмов разбиения матроидов.
Пусть G = ( U, V, E) двудольный граф. Можно определит раздел матроид M U на первом множество Е, в которой множество ребер не зависит, если не два из ребер не имеет ту же конечную точку в U. Аналогично можно определить матроид M V, в которой множество ребер является независимым, если никакие два из ребер не имеет ту же самую конечную точку в V. Любой набор ребер, который является независимым как в M U, так и в M V, обладает тем свойством, что никакие два его ребра не имеют общей конечной точки; то есть это совпадение. Таким образом, наибольшее общее независимое множество М U и M V представляет собой максимальное соответствие в G.
Проблема пересечения матроидов становится NP-сложной, когда задействованы три матроида, а не только два.
Одно доказательство этого результата о трудностях использует редукцию из проблемы гамильтонова пути в ориентированных графах. Для ориентированного графа G с n вершинами и заданными узлами s и t проблема гамильтонова пути - это проблема определения, существует ли простой путь длины n - 1, который начинается в s и заканчивается в t. Без ограничения общности можно предположить, что s не имеет входящих ребер, а t не имеет исходящих ребер. Тогда гамильтонов путь существует тогда и только тогда, когда существует набор из n - 1 элементов на пересечении трех матроидов на множестве ребер графа: два матроида разбиения, гарантирующие, что внутренняя и исходящая степень выбранного ребра набор оба не более одного, и графическая матроида из неориентированного графа, образованного забывая краевые ориентации в G, гарантируя, что выбранный набор ребра не имеет циклов ( Валлийские 2010).
Другая вычислительная проблема на матроидах, проблема четности матроидов, была сформулирована Лоулером (1976) как общее обобщение пересечения матроидов и недвудольного сопоставления графов. Однако, хотя для линейных матроидов она может быть решена за полиномиальное время, для других матроидов она NP-сложна и требует экспоненциального времени в модели матроидов-оракулов ( Jensen amp; Korte, 1982).
