Максимальный вес соответствия и субмодульные функции

Для двудольного графа с положительными весами пусть с равным максимальному совпадению весов в графе .f : 2 U → R f ( S ) G [ S ∪ V $G = (U \cup V, E)$$f: 2^U \rightarrow \mathbb{R}$$f(S)$$G[S\cup V]$

Правда ли, что субмодулярная функция?$f$

Определение . Для заданного конечного множества функция f : 2 A → R является субмодулярной, если для любого X , Y ⊆ A выполнено, что: f ( X ) + f ( Y ) ≥ f ( X ∪ Y ) + f ( X ∩ Y ) $A$$f:2^A \rightarrow \mathbb{R}$$X, Y \subseteq A$

$$f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y).$$

Лемма. Учитывая двудольный граф с положительными весами ребер, пусть f : 2 A → R + будет функцией, которая отображает S ⊆ A на значение соответствия максимального веса в G [ S ∪ B ] , Тогда f субмодулярна.$G = (A \cup B, E)$$f: 2^A \rightarrow \mathbb{R}^+$$S\subseteq A$$G[S \cup B]$$f$

Доказательство. Зафиксируем два множества и пусть M ∩ и M ∪ будут двумя совпадениями для графов G [ ( X ∩ Y ) ∪ B ] и G [ ( X ∪ Y ) ∪ B ] соответственно. Для доказательства леммы достаточно показать, что можно разбить ребра в M ∩ и M ∪ на два непересекающихся соответствия M X и M $X, Y \subseteq A$$M_\cap$$M_\cup$$G[(X\cap Y) \cup B]$$G[(X \cup Y) \cup B]$$M_\cap$$M_\cup$$M_X$$M_Y$для графиков и G [ Y ∪ B ] соответственно.$G[X\cup B]$$G[Y\cup B]$

Ребра и M ∪ образуют совокупность чередующихся путей и циклов. Пусть C обозначим эту коллекцию и заметим , что не цикл C не содержит вершин из X ∖ Y или Y ∖ X . Это верно, потому что M ∩ не совпадает с этими вершинами.$M_\cap$$M_\cup$$\mathcal{C}$$\mathcal{C}$$X\setminus Y$$Y\setminus X$$M_\cap$

Пусть множество путей в C , по меньшей мере с одной вершиной в X ∖ Y и пусть Р У множества путей в C , по меньшей мере с одной вершиной в Y ∖ X . Два таких пути изображены на рисунке ниже.$\mathcal{P}_X$$\mathcal{C}$$X \setminus Y$$\mathcal{P}_Y$$\mathcal{C}$$Y \setminus X$

Утверждение 1. . $\mathcal{P}_X \cap \mathcal{P}_Y = \emptyset$

$P \in \mathcal{P}_X \cap \mathcal{P}_Y$$x$$X\setminus Y$$P$$y$$Y \setminus X$$P$$x$$y$$X \cap Y$$M_\cap$$P$$x$$y$$A$$P$$M_\cap$$M_\cap$$x$$y$

$$M_X = (\mathcal{P}_X \cap M_\cup) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cap)$$ $$M_Y = (\mathcal{P}_X \cap M_\cap) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cup).$$ $M_X \cup M_Y = M_\cap\cup M_\cup$$M_X \cap M_Y = M_\cap \cap M_\cup$$M_X$$M_Y$$G[X\cup B]$$G[Y\cup B]$$M_X$$G[X\cup B]$$Y \setminus X$$M_X$$\mathcal{P}_X$$Y \setminus X$$M_\cap$$Y \setminus X$$M_X$$X \cup B$$x\in X$$M_X$$x$$M_\cup$$M_\cap$$M_X$$G[X\cup B]$$M_Y$$G[Y\cup B]$