максимальных паросочетаний (красные рёбра) в трёх графах. Наибольшее паросочетание (или максимальное по размеру паросочетание)— это такое паросочетание, которое...

Паросочетание без зависти (англ. envy-free matching, EFM) — это паросочетание между людьми и «объектами», в котором нет зависти в том смысле, что никто...

теоремы: граф G = ( V , E ) {\displaystyle G=(V,E)} имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества вершин U ⊆ V {\displaystyle...

O(|E||V|^{2})} . Микали и Вазирани показали алгоритм, который строит наибольшее паросочетание за время O ( | E | | V | 1 / 2 ) {\displaystyle O(|E||V|^{1/2})} . Другой...

{\displaystyle c} с обратным знаком. Рассмотрим задачу о максимальном паросочетании в двудольном графе: есть несколько юношей и девушек, причём для каждых...

алгоритм находит паросочетание M такое, что каждая вершина из V инцидентна не более чем одному ребру из M и |M| максимально. Паросочетание строится путём...

M {\displaystyle M} — наибольшее паросочетание в G {\displaystyle G} . Сначала рассмотрим случай, когда паросочетание M {\displaystyle M} насыщает все...

каждого участника. Паросочетание называется стабильным, когда нет ни одной пары элементов разных типов, не входящей в это паросочетание, в которой оба предпочитают...

Многочлен паросочетаний — производящая функция для числа паросочетаний различных размеров в графе. Известны несколько связанных типов определений: m Γ...

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

совершенное паросочетание? Определитель матрицы Татта не является тождественно нулевым многочленом если и только если в графе есть совершенное паросочетание. (Tutte...

Карпа в цикле увеличивает паросочетание, находя увеличивающие пути (цепи, рёбра которых попеременно принадлежат паросочетанию и не принадлежат ему, причём...

стоимость любого совершенного паросочетания не меньше, чем значение любого потенциала. Венгерский метод находит полное паросочетание и потенциал с одинаковой...

ребро паросочетания. Покрытия вершин графов паросочетаниями (показаны красным цветом) Паросочетание покрывает 8 вершин графа из 9 Паросочетание покрывает...

на мультиграфы. Паросочетанием в графе G {\displaystyle G} называется множество рёбер, никакие два из которых не смежны. Паросочетание называется совершенным...

{\displaystyle c(M)\leqslant c(C^{*})/2} , где M {\displaystyle M}  — паросочетание, а C ∗ {\displaystyle C^{*}}  — оптимальный маршрут: Пусть U {\displaystyle...

граф степени r ⩾ 1 {\displaystyle r\geqslant 1} допускает совершенное паросочетание. Теорема обобщается на двудольные графы с бесконечным множеством вершин...

совершенными паросочетаниями. Это свойство играет ключевую роль в доказательстве, что проверка, можно ли покрыть граф четырьмя совершенными паросочетаниями, является...

задач паросочетаний в терминах кососимметрических графов. В таком приложении два подмножества рёбер в каждой вершине являются входящими в паросочетание и...

чередуются рёбра из паросочетания и не входят в паросочетание (Берж 1962, С. 186 Теория чередующихся цепей) Теорема: Паросочетание графа является наибольшим...

Лемма Бержа утверждает, что паросочетание M в графе G является наибольшим (содержит наибольшее возможное число рёбер) тогда и только тогда, когда не существует...

совершенным паросочетанием рёбра, не входящие в это паросочетание, формируют 2-фактор. Ориентируя 2-фактор, рёбра совершенного паросочетания можно расширить...

может разбито на подмножества следующим образом: -Найти совершенное паросочетание G. -Построить ориентированный граф H, вершины которого соответствуют...

любое максимальное паросочетание. Максимальное паросочетание является доминирующим множеством рёбер. Более того, максимальное паросочетание M может быть вдвое...

котором каждый подграф с n − 1 вершинами имеет совершенное паросочетание. (Совершенное паросочетание в графе — это подмножество рёбер со свойством, что каждая...

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

задающих паросочетание. Здесь граф G — это двудольный граф с дугами (r,j), для которых c r , j ⩽ t {\displaystyle c_{r,j}\leqslant t} . Если паросочетание не...

не только рёберным покрытием, но и паросочетанием. Более того, это паросочетание является совершенным паросочетанием — в нём каждая вершина инцидентна...

максимальное по размеру МР-паросочетание, так и справедливое паросочетание, могут быть найдены путём сведение к паросочетанию максимального веса. 3. В задаче...

треугольника их соответствующее паросочетание имеет вес, который также не менее половины веса C. Совершенное паросочетание минимального веса не может иметь...

чётностью). Таким образом, число паросочетаний в таком графе равно числу рассаживаний. Для чередующихся узлов[англ.] это паросочетание достаточно для описания...