Сопоставление (теория графов) - Matching (graph theory)

В математической дисциплине теории графов , A соответствие или независимое множество краев в неориентированном графе представляет собой набор ребер без общих вершин . Поиск соответствия в двудольном графе можно рассматривать как проблему сетевого потока .

Пары покрытие / упаковка-проблема
Покрытие проблем Проблемы с упаковкой Крышка минимального набора Максимальный набор упаковки Минимальное краевое покрытие Максимальное соответствие Минимальное покрытие вершины Максимальный независимый набор Покрытие мусорного ведра Бин упаковка Полигональное покрытие Прямоугольная упаковка
v т е

Определения

Учитывая график G = ( V ,  E ), соответствие М в G представляет собой набор попарно несмежных ребер, ни один из которых являются петли ; то есть никакие два ребра не имеют общих вершин.

Вершина совпадает (или насыщается ), если она является конечной точкой одного из ребер в сопоставлении. В противном случае вершина не найдена .

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

Соответствие максимального (также известный как согласование максимальной мощности) является соответствие , которое содержит наибольшее возможное число ребер. Максимальных совпадений может быть много. Число совпадений на графике - это размер максимального совпадения. Каждое максимальное совпадение является максимальным, но не каждое максимальное совпадение является максимальным совпадением. На следующем рисунке показаны примеры максимального совпадения на тех же трех графиках. ${\ Displaystyle \ Nu (G)}$${\ displaystyle G}$

Совершенное паросочетание является соответствие , которое соответствует всем вершинам графа. То есть сопоставление является совершенным, если каждая вершина графа инцидентна ребру сопоставления. Каждое идеальное совпадение является максимальным и, следовательно, максимальным. В некоторой литературе используется термин полное соответствие . На приведенном выше рисунке только часть (b) показывает идеальное совпадение. Идеально сочетается также с кромкой минимального размера . Таким образом, размер максимального согласования не больше размера минимального краевого покрытия: ν (G) ≤ ρ (G) . Граф может содержать идеальное соответствие, только если у него четное число вершин.

Почти идеальное совпадение - это совпадение, при котором ровно одна вершина не совпадает. Ясно, что граф может содержать почти идеальное соответствие только тогда, когда граф имеет нечетное число вершин, а почти идеальное совпадение является максимальным соответствием. На приведенном выше рисунке часть (c) показывает почти идеальное соответствие. Если каждая вершина не соответствует некоторому почти идеальному совпадению, то граф называется фактор-критическим .

Учитывая соответствие М , переменный путь представляет собой путь , который начинается с непревзойденной вершиной и чьи ребра принадлежат поочередно к соответствующему , а не к соответствию. Путь приумножения является переменным путем , который начинается с и заканчивается на свободных (несогласованных) вершинах. Лемма Берж гласит , что соответствие М максимально тогда и только тогда , когда нет увеличивающего пути по отношению к М .

Индуцированное соответствие является соответствие , что является множеством ребер из индуцированного подграфа .

Характеристики

В любом графе без изолированных вершин сумма совпадающего числа и числа покрытия ребер равна количеству вершин. Если есть идеальное совпадение, то и номер совпадения, и номер кромочного покрытия равны | V | / 2 .

Если A и B - два максимальных совпадения, то | А | ≤ 2 | B | и | B | ≤ 2 | А | . Чтобы убедиться в этом, заметьте, что каждое ребро в B  \  A может быть смежным не более чем с двумя ребрами в A  \  B, потому что A - соответствие; кроме того, каждое ребро в A  \  B смежно с ребром в B  \  A по максимальности B , поэтому

${\ Displaystyle | A \ setminus B | \ leq 2 | B \ setminus A |.}$

Далее выводим, что

${\ Displaystyle | A | = | A \ cap B | + | A \ setminus B | \ leq 2 | B \ cap A | +2 | B \ setminus A | = 2 | B |.}$

В частности, это показывает, что любое максимальное сопоставление является 2-приближением максимального сопоставления, а также 2-приближением минимального максимального сопоставления. Это неравенство строгое: например, если G - путь с 3 ребрами и 4 вершинами, размер минимального максимального сопоставления равен 1, а размер максимального сопоставления равен 2.

Спектральная характеристика совпадающего числа графа дана Хассани Монфаредом и Малликом следующим образом: Пусть будет граф на вершинах, и будут различные ненулевые чисто мнимые числа, где . Тогда соответствующий номер из является тогда и только тогда , когда (а) существует реальная кососимметрическая матрица с графом и собственными значениями и нулями, и (б) все действительные кососимметрические матрицы с графом имеют в большинстве ненулевых собственных значений . Обратите внимание, что (простой) граф реальной симметричной или кососимметричной матрицы порядка имеет вершины и ребра, заданные ненулевыми внедиагональными элементами матрицы . ${\ displaystyle G}$${\ displaystyle n}$${\ displaystyle \ lambda _ {1}> \ lambda _ {2}> \ ldots> \ lambda _ {k}> 0}$${\ displaystyle k}$${\ displaystyle 2k \ leq n}$${\ displaystyle G}$${\ displaystyle k}$ ${\ displaystyle A}$${\ displaystyle G}$ ${\ displaystyle \ pm \ lambda _ {1}, \ pm \ lambda _ {2}, \ ldots, \ pm \ lambda _ {k}}$${\ displaystyle n-2k}$${\ displaystyle G}$${\ displaystyle 2k}$${\ displaystyle A}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle A}$

Соответствующие многочлены

Производящая функция от числа к -Станок паросочетаний в графе называется соответствующим многочленом. Пусть G - граф, а m _k - количество k- реберных паросочетаний. Один полином согласования группы G равен

${\ displaystyle \ sum _ {k \ geq 0} m_ {k} x ^ {k}.}$

Другое определение дает соответствующий многочлен как

${\ Displaystyle \ сумма _ {к \ geq 0} (- 1) ^ {k} m_ {k} x ^ {n-2k},}$

где n - количество вершин в графе. Каждый тип имеет свое применение; для получения дополнительной информации см. статью о сопоставлении многочленов.

Алгоритмы и вычислительная сложность

Соответствие максимальной мощности

Основная проблема комбинаторной оптимизации - найти максимальное соответствие . В этой задаче используются разные алгоритмы для разных классов графов.

В невзвешенном двудольном графе задача оптимизации состоит в том, чтобы найти соответствие максимальной мощности . Проблема решается алгоритмом Хопкрофта-Карпа за время O ( √ V E ) , и существуют более эффективные рандомизированные алгоритмы , алгоритмы аппроксимации и алгоритмы для специальных классов графов, таких как двудольные плоские графы , как описано в основной статье .

Соответствие максимального веса

В взвешенном двудольном графе задача оптимизации состоит в том, чтобы найти соответствие максимального веса; двойная проблема - найти соответствие с минимальным весом. Эту проблему часто называют максимальным взвешенным двудольным соответствием или проблемой присваивания . Венгерский алгоритм решает задачу присваивания и это один из истоков комбинаторных алгоритмов оптимизации. Он использует модифицированный поиск кратчайшего пути в алгоритме увеличения пути. Если для этого шага используется алгоритм Беллмана – Форда , время выполнения венгерского алгоритма становится равным или стоимость ребер может быть смещена с потенциалом достижения времени выполнения с помощью алгоритма Дейкстры и кучи Фибоначчи . ${\ displaystyle O (V ^ {2} E)}$${\ Displaystyle O (V ^ {2} \ log {V} + VE)}$

В недвудольном взвешенном графе проблема соответствия максимального веса может быть решена во времени с помощью алгоритма цветения Эдмондса . ${\ displaystyle O (V ^ {2} E)}$

Максимальные соответствия

Максимальное соответствие можно найти с помощью простого жадного алгоритма . Максимальное соответствие также является максимальным соответствием, и, следовательно, можно найти наибольшее максимальное соответствие за полиномиальное время. Однако не известен полиномиальный алгоритм поиска минимального максимального совпадения , то есть максимального совпадения, содержащего наименьшее возможное количество ребер.

Максимальное паросочетание с k ребрами - это множество с преобладанием ребер с k ребрами. И наоборот, если нам дано минимальное множество с преобладанием ребер с k ребрами, мы можем построить максимальное паросочетание с k ребрами за полиномиальное время. Следовательно, проблема поиска минимального максимального соответствия по существу равна проблеме поиска минимального набора с преобладанием ребер. Обе эти две задачи оптимизации, как известно, NP-трудны ; варианты решения этих задач являются классическими примерами NP-полных задач. Обе эти проблемы могут быть аппроксимированы в 2 раза за полиномиальное время: просто найти произвольный максимальное паросочетание М .

Проблемы с подсчетом

Количество совпадений в графе известно как индекс Хосоя графа. Это # P-полное вычисление этой величины даже для двудольных графов. Также # P-полно для подсчета совершенных паросочетаний , даже в двудольных графах , потому что вычисление перманента произвольной матрицы 0–1 (другая проблема # P-полной) аналогично вычислению числа точных паросочетаний в двудольном графе. имеющий данную матрицу в качестве матрицы двойственности . Однако существует полностью полиномиальная схема рандомизированной аппроксимации по времени для подсчета количества парных совпадений. Замечательная теорема Кастелейна утверждает, что количество совершенных паросочетаний в плоском графе может быть вычислено точно за полиномиальное время с помощью алгоритма FKT .

Количество совершенных паросочетаний в полном графе K _n (с четным n ) задается двойным факториалом ( n  - 1) !!. Номера совпадений в полных графах, без ограничения совпадений на идеальность, задаются телефонными номерами .

Нахождение всех максимально совпадающих ребер

Одна из основных проблем теории согласования - найти в данном графе все ребра, которые могут быть расширены до максимального соответствия в графе (такие ребра называются максимально совместимыми ребрами или разрешенными ребрами). Алгоритмы решения этой проблемы включают:

• Для общих графиков это детерминированный алгоритм по времени и рандомизированный алгоритм по времени .${\ displaystyle O (VE)}$${\ displaystyle {\ tilde {O}} (V ^ {2.376})}$
• Для двудольных графов, если найдено единственное максимальное совпадение, детерминированный алгоритм работает во времени .${\ Displaystyle О (В + Е)}$

Двухстороннее соответствие онлайн

Проблема разработки онлайн-алгоритма сопоставления была впервые рассмотрена Ричардом М. Карпом , Умешом Вазирани и Виджаем Вазирани в 1990 году.

В интерактивном режиме узлы на одной стороне двудольного графа прибывают по одному и должны либо быть немедленно сопоставлены с другой стороной графа, либо отброшены. Это естественное обобщение проблемы секретарей, которое можно найти на аукционах онлайн-рекламы. Лучший онлайн алгоритм для невесовой максимизации случае со случайной моделью прибытия, достигает конкурентное соотношение в 0,696 .

Характеристики

Теорема Кёнига утверждает, что в двудольных графах максимальное согласование равно по размеру минимальному покрытию вершин . Благодаря этому результату задачи минимального покрытия вершин, максимального независимого множества и максимума вершин бикликов могут быть решены за полиномиальное время для двудольных графов.

Теорема Холла о браке дает характеристику двудольных графов, которые имеют полное соответствие, а теорема Тутте дает характеристику для произвольных графов.

Приложения

Сопоставление в общих графиках

• Структура Кекулы из ароматического соединения состоит из идеального соответствия его углеродного скелета , показывающее расположение двойных связей в химической структуре . Эти структуры названы в честь Фридриха Августа Кекуле фон Страдоница , который показал, что бензол (в терминах теории графов, 6-вершинный цикл) может иметь такую ​​структуру.
• Индекс Хосоя - это количество непустых совпадений плюс один; он используется в вычислительной химии и исследованиях математической химии органических соединений.

Сопоставление в двудольных графах

• Задача выпуска состоит в выборе минимального набора классов из заданных требований для выпуска.
• Транспортная проблема Хичкока включает в себя подзадачу двудольного сопоставления.
• Проблема изоморфизма поддерева включает в себя двудольное сопоставление как подзадачу.

Смотрите также

• Сопоставление в гиперграфах - обобщение сопоставления в графах.
• Дробное соответствие .
• Разложение Далмажа – Мендельсона , разбиение вершин двудольного графа на подмножества, такое что каждое ребро принадлежит идеальному паросочетанию тогда и только тогда, когда его концы принадлежат одному и тому же подмножеству
• Раскраска ребер, разбиение ребер графа на паросочетания
• Сопоставление преклюзии , минимальное количество ребер, которые нужно удалить, чтобы предотвратить идеальное совпадение существующего
• Сопоставление радуги , сопоставление в двудольном графе с краской цвета без повторяющихся цветов
• Кососимметричный граф , тип графа, который можно использовать для моделирования поиска чередующихся путей для сопоставлений.
• Стабильное соответствие , соответствие, при котором никакие два элемента не предпочитают друг друга своим согласованным партнерам.
• Независимый от вершин набор , набор вершин (а не ребер), никакие две из которых не смежны друг с другом.
• Проблема стабильного брака (также известная как проблема стабильного соответствия)

использованная литература

дальнейшее чтение

1. Ловас, Ласло ; Пламмер, доктор медицины (1986), Теория соответствия , Анналы дискретной математики, 29 , Северная Голландия, ISBN 0-444-87916-1, Руководство по ремонту  0859549
2. Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн (2001), Введение в алгоритмы (второе изд.), MIT Press и McGraw – Hill, Глава 26, стр. 643–700, ISBN 0-262-53196-8CS1 maint: несколько имен: список авторов ( ссылка )
3. Андраш Франк (2004). О венгерском методе Куна - дань уважения Венгрии (PDF) (Технический отчет). Egerváry Research Group.
4. Майкл Л. Фредман и Роберт Э. Тарджан (1987), «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети», журнал ACM , 34 (3): 595–615, doi : 10.1145 / 28869.28874 , S2CID  7904683 .
5. SJ Cyvin & Ivan Gutman (1988), Структуры Кекуле в бензоидных углеводородах , Springer-Verlag
6. Марек Карпински и Войцех Риттер (1998), быстрые параллельные алгоритмы для задач сопоставления графов , Oxford University Press, ISBN 978-0-19-850162-6

внешние ссылки

• Библиотека графов с реализацией сопоставления максимальной мощности элементов на основе Хопкрофта – Карпа и Пуш – Релабеля.