Разбиение Matroid - Matroid partitioning - Wikipedia

В разделение матроидов проблема - проблема, возникающая при математическом исследовании матроиды и в проектировании и анализе алгоритмы, цель которого - разделить элементы матроида на как можно меньше независимых множеств. Примером может служить проблема вычисления родословие из неориентированный граф, минимальное количество леса нужно было покрыть все его края. Разбиение Matroid может быть решено в полиномиальное время, учитывая оракул независимости для матроида. Его можно обобщить, чтобы показать, что сумма матроидов сам является матроидом, чтобы предоставить алгоритм для вычисления разряды и независимых множеств в суммах матроидов, и для вычисления наибольшего общего независимого множества в пересечение двух данных матроидов.^[1]

Пример

Перегородка краев полный двудольный граф K_4,4 на три леса, показывая, что он имеет не более трех древесных пород.

В родословие из неориентированный граф это минимальное количество леса на которые могут быть разделены его ребра, или, что то же самое (добавляя перекрывающиеся ребра к каждому лесу по мере необходимости), минимальное количество покрывающий леса объединение которых составляет весь граф. Формула доказана Криспин Нэш-Уильямс точно характеризует древовидность: она максимальная по всем подграфам ${\displaystyle H}$ данного графа ${\displaystyle G}$, количества ${\displaystyle \left\lceil {\frac {|E(H)|}{|V(H)|-1}}\right\rceil }$.^[2]

Леса графа образуют независимые множества связанных графический матроид, а количество ${\displaystyle |V(H)|-1}$ в формуле Нэша-Вильямса фигурирует ранг графического матроида ${\displaystyle H}$, максимальный размер одного из его независимых наборов. Таким образом, задача определения древовидности графа - это в точности задача разбиения матроида для графического матроида. Тот факт, что ${\displaystyle |E(H)|}$ элементы этого матроида не могут быть разделены менее чем на ${\displaystyle {\frac {|E(H)|}{|V(H)|-1}}}$ независимых подмножеств тогда просто приложение принцип голубятни говоря это, если ${\displaystyle x}$ элементы разбиты на наборы размером не более ${\displaystyle y}$, то хотя бы ${\displaystyle x/y}$ нужны наборы. Более сложное направление формулы Нэша-Вильямса, которая может быть обобщена на все матроиды, - это доказательство того, что разбиение такого размера всегда существует.^[1]

Формула размера раздела

Чтобы обобщить формулу Нэша-Вильямса, можно заменить ${\displaystyle G}$ матроидом ${\displaystyle M}$, а подграф ${\displaystyle H}$ из ${\displaystyle G}$ с ограничение ${\displaystyle M|S}$ из ${\displaystyle M}$ к подмножеству ${\displaystyle S}$ его элементов. Количество ребер подграфа ${\displaystyle H}$ становится, в этом обобщении, мощность ${\displaystyle |S|}$ выбранного подмножества, и формула ${\displaystyle |V(H)|-1}$ для максимального размера леса в ${\displaystyle H}$ становится званием ${\displaystyle r(S)}$. Таким образом, минимальное количество независимых множеств в разбиении данного матроида ${\displaystyle M}$ должен быть задан формулой

${\displaystyle k(M)=\max _{S}\left\lceil {\frac {|S|}{r(S)}}\right\rceil ,}$

которое справедливо для всех матроидов и было алгоритмически доказано Эдмондс (1965).^[1][3]

Алгоритмы

Первый алгоритм разбиения матроидов был дан Эдмондс (1965).^[3] Это алгоритм инкрементального увеличения пути, который рассматривает элементы матроида один за другим в произвольном порядке, поддерживая на каждом шаге алгоритма оптимальное разбиение для элементов, которые были рассмотрены до сих пор. На каждом этапе при рассмотрении элемента ${\displaystyle x}$ который еще не был помещен в раздел, алгоритм строит ориентированный граф который имеет своими узлами элементы, которые уже были разделены, новый элемент ${\displaystyle x}$, и специальный элемент ${\displaystyle \bot _{i}}$ для каждого из ${\displaystyle k}$ независимые множества в текущем разделе. Затем он формирует ориентированный граф ${\displaystyle G_{x}}$ на этом наборе узлов с направленной дугой ${\displaystyle \bot _{i}\rightarrow y}$ для каждого элемента матроида ${\displaystyle y}$ который можно добавить в набор разделов ${\displaystyle i}$ не заставляя его становиться зависимым, и с направленной дугой ${\displaystyle z\rightarrow y}$ для каждой пары элементов матроида ${\displaystyle (y,z)}$ такое, что удаление ${\displaystyle z}$ из своего раздела и заменив его на ${\displaystyle y}$ образует еще один независимый набор.^[1][3]

Теперь есть два случая:

• Если этот граф содержит направленный путь из элемента ${\displaystyle \bot _{i}}$ к вновь рассмотренному элементу ${\displaystyle x}$, то кратчайший такой путь (или, в более общем смысле, любой путь, не имеющий никаких сокращающихся краев) описывает последовательность изменений, которые могут быть внесены одновременно в наборы разделов, чтобы сформировать новый раздел с тем же количеством наборов, что и также включает ${\displaystyle x}$. В этом случае алгоритм выполняет эти изменения и продолжает работу.
• Если же такого пути не существует, то пусть ${\displaystyle S}$ состоят из элементов матроида, из которых ${\displaystyle x}$ является достижимый в ${\displaystyle D}$. Каждый набор в текущем разделе должен быть максимальным независимым набором в ограничение ${\displaystyle M|S}$, если какой-то элемент ${\displaystyle y}$ из ${\displaystyle S}$ может быть добавлен в набор разделов ${\displaystyle i}$ в ограничении, то либо существовала бы дуга ${\displaystyle \bot _{i}\rightarrow y}$ (если установлен раздел ${\displaystyle i}$ не является максимальным в полном матроиде ${\displaystyle M}$) или дугу ${\displaystyle z\rightarrow y}$ куда ${\displaystyle z\notin S}$ (если множество разбиений не является максимальным в ${\displaystyle S}$ но максимальная в полном матроиде). В любом случае существование этой дуги противоречит предполагаемой конструкции множества ${\displaystyle S}$, и противоречие доказывает, что каждое множество разбиений является максимальным. Таким образом, согласно простой формуле разбиения матроида, количество наборов, необходимых для разбиения ${\displaystyle S}$ по крайней мере

${\displaystyle \left\lceil {\frac {|S|}{r(S)}}\right\rceil =\left\lceil {\frac {kr(S)+1}{r(S)}}\right\rceil =k+1}$,

поэтому в этом случае алгоритм может найти оптимальное разделение, поместив ${\displaystyle x}$ в свой новый независимый набор и оставив другие независимые наборы без изменений.^[1][3]

Таким образом, общий алгоритм рассматривает каждый элемент ${\displaystyle x}$ данного матроида, в свою очередь, строит граф ${\displaystyle G_{x}}$, тесты, какие узлы могут достигать ${\displaystyle x}$, и использует эту информацию для обновления текущего раздела, чтобы он включал ${\displaystyle x}$. На каждом шаге разбиение элементов, рассмотренных до сих пор, является оптимальным, поэтому, когда алгоритм завершится, он найдет оптимальное разбиение для всего матроида. Для доказательства правильности этого алгоритма требуется показать, что путь без кратчайших путей во вспомогательном графе всегда описывает последовательность операций, которая при одновременном выполнении правильно сохраняет независимость множеств в разбиении; Доказательство этого факта было дано Эдмондсом. Поскольку алгоритм увеличивает количество наборов в разбиении только тогда, когда формула разбиения матроида показывает, что необходимо большее число, правильность этого алгоритма также показывает правильность формулы.^[1][3]

Хотя этот алгоритм зависит только от наличия оракул независимости для его правильности во многих случаях можно найти более быстрые алгоритмы, используя более специализированную структуру определенных типов матроидов (таких как графические матроиды ), на основании которого была определена конкретная проблема разбиения.^[4]

Связанные проблемы

А сумма матроидов ${\displaystyle \sum _{i}M_{i}}$ (где каждый ${\displaystyle M_{i}}$ является матроидом) сам является матроидом, имеющим в качестве элементов объединение элементов слагаемых. Множество является независимым в сумме, если его можно разбить на множества, независимые внутри каждого слагаемого. Алгоритм разбиения матроидов обобщает задачу проверки того, является ли набор независимым в сумме матроидов, и его правильность может использоваться для доказательства того, что сумма матроидов обязательно является матроидом.^[3][4]

В пересечение матроидов задача поиска наибольшего независимого множества в двух матроидах ${\displaystyle M_{1}}$ и ${\displaystyle M_{2}}$ можно решить, превратив его в эквивалентную задачу о сумме матроидов: если ${\displaystyle B}$ является основой суммы ${\displaystyle M_{1}+M_{2}^{*}}$, куда ${\displaystyle M_{2}^{*}}$ является двойником ${\displaystyle M_{2}}$, тогда ${\displaystyle B}$ должен иметь полное звание в ${\displaystyle M_{2}^{*}}$ и удалив максимальный независимый набор ${\displaystyle M_{2}^{*}}$ из ${\displaystyle B}$ оставляет максимальное пересечение.^[5]

Разбиение Matroid - это форма установить обложку проблема, и соответствующий набор упаковки Задача (найти максимальное количество непересекающихся остовных множеств внутри заданного матроида) также представляет интерес. Ее можно решить с помощью алгоритмов, аналогичных алгоритмам разбиения матроидов.^[4] Дробная упаковка набора и задачи покрытия набора, связанные с матроидом (то есть, присвоить вес каждому независимому набору таким образом, чтобы для каждого элемента общий вес наборов, содержащих его, был не более одного или хотя бы одного, максимизируя или минимизация общего веса всех наборов соответственно) также может быть решена за полиномиальное время с использованием методов разбиения матроидов.^[1]

Помимо использования при вычислении древовидности графа, разбиение матроидов можно использовать с другими матроидами для поиска подграфа данного графа, среднее значение которого степень является максимальной, а для определения прочности ребра графа (вариант графическая стойкость с удалением ребер вместо вершин).^[1]

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

1. Шайнерман, Эдвард Р.; Ульман, Дэниел Х. (1997), "5. Дробное древовидность и методы матроидов", Теория дробных графов, Серия Wiley-Interscience по дискретной математике и оптимизации, Нью-Йорк: John Wiley & Sons Inc., стр. 99–126, ISBN  0-471-17864-0, МИСТЕР  1481157.
2. Нэш-Уильямс, К. Сент-Дж. А. (1964), «Разложение конечных графов на леса», Журнал Лондонского математического общества, 39 (1): 12, Дои:10.1112 / jlms / s1-39.1.12, МИСТЕР  0161333.
3. Эдмондс, Джек (1965), «Минимальное разбиение матроида на независимые подмножества», Журнал исследований Национального бюро стандартов, 69B: 67–72, Дои:10.6028 / jres.069b.004, МИСТЕР  0190025.
4. Габоу, Гарольд Н .; Вестерманн, Герберт Х. (1992), "Леса, фреймы и игры: алгоритмы для матроидных сумм и приложений", Алгоритмика, 7 (5–6): 465–497, Дои:10.1007 / BF01758774, МИСТЕР  1154585.
5. Эдмондс, Джек (1970), «Субмодульные функции, матроиды и некоторые многогранники», Комбинаторные структуры и их приложения (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), New York: Gordon and Breach, pp. 69–87, МИСТЕР  0270945.