Изменения

Перейти к: навигация, поиск

Декомпозиция Эдмондса-Галлаи

10 889 байт добавлено, 20:53, 21 ноября 2018
Нет описания правки
В этом направлении много усилий приложили Вильям Томас '''Татт''' (''William Thomas Tutte''), Клод '''Берж''' (''Claude Berge''), Джек '''Эдмондс''' (''Jack Edmonds'') и Тибор '''Галлаи''' (''Tibor Gallai'').
{{Определение
|id = deficit
|definition=
<tex>o'''Дефицитом''' (G-Uангл. ''deficit'')</tex> - количество компонент связности нечетного размера в графа <tex> G[V - U]</tex>.}} {{Определение |definition='''Дефицитом''' графа G мы будем называть величину: <br><tex>\mathrm{def}(G) = |V(G) | - 2\alpha (G)</tex>, <br>где <tex>\alpha (G)</tex> {{- --}} размер [[Теорема о максимальном паросочетании и дополняющих цепях#theorem1|максимального поросочетания паросочетания]] в <tex>G</tex>, а <br><tex>V(G)</tex> {{- --}} множество вершин графа <tex>G. </tex>
}}
 
{{Теорема
|id = Th_Berge
|about=Бержа
|statement=
для Для любого графа <tex>G </tex> выполняется:<br><tex>\mathrm{def}(G) = max_\max\limits_{S \subset V(G)} \{o\mathrm{odd}(G - S) - |S|\}.</tex>
}}
{{Теорема
|id = theorem_Tatt_Berge
|about=Татта-Бержа
|statement=
дан Дан граф <tex>G</tex>, размер максимального паросочетания в нем равен:<br><tex>\mathrm{\alpha }(G) = min_\min\limits_{U \in V} \{\dfrac{1}{2}(|V|+|U|-\mathrm{odd}(G - U)\}. </tex>|proof=Предположим <tex>G</tex> {{---}} связный, иначе мы можем применить индукцию к компонентам <tex>G</tex>. Приведем доказательство по индукции по числу вершин в графе. <br><u> ''База индукции:''</u> <br>Очевидно, для <tex> n = 1 </tex> утверждение верно. <br><u> ''Индукционный переход:''</u> <br>Рассмотрим два случая:# <tex>G</tex> {{---}} содержит вершину <tex>v</tex> покрытую всеми максимальными паросочетаниями (например средняя вершина)#: Тогда <tex> \mathrm{\alpha}(G - v) = \mathrm{\alpha}(G) - 1 </tex>.#: По индукции, формула Татта-Берджа содержит <tex>G - v</tex> для некоторого множества <tex>U'</tex>. Пусть <tex>U = U' \bigcup v</tex>. Тогда:#: <tex> \mathrm{\alpha}(G) = \mathrm{\alpha}(G - v) + 1 = \dfrac{1}{2}(|V - v|+|U - v| - \mathrm{odd}(G - v - (U - v))) + 1 = </tex>#: <tex> = \dfrac{1}{2}(|V|-1 + |U|- 1 - \mathrm{odd}(G - U)) + 1 = \dfrac{1}{2}(|V|+|U|-o\mathrm{odd}(G-U)). </tex>#:# Для каждой вершины <tex>v</tex> есть максимальное паросочетание <tex>M</tex> которое не покрывает <tex>v</tex> (например <tex>C_3</tex>)#:#: Покажем, что существует паросочетание размера <tex> \dfrac{1}{2}(|V| - 1) </tex>, из которого следует теорема (при <tex> U = \emptyset </tex>).#: <u> ''От противного:''</u>#: Предположим что любое максимальная паросочетание <tex> M </tex> не покрывает, по крайней мере, две различные вершины <tex> u </tex> и <tex> v </tex>. Среди всех таких <tex> (M, u, v) </tex> выберем их так, что <tex> \mathrm{d}(u, u) </tex> в <tex> G </tex> {{---}} минимально.#: Если <tex> \mathrm{d}(u, u) = 1 </tex>, то <tex> u </tex> и <tex> v </tex> являются смежными, и, следовательно, мы можем увеличить <tex> M </tex>, что противоречит его максимальности.#: Значит <tex> \mathrm{d}(u, u) \geqslant 2 </tex>, и, следовательно, мы можем выбрать промежуточную вершину <tex> t </tex> на пути <tex> u-v </tex> и <tex> N </tex> максимальное паросочетание, такое что симметрическая разность с <tex> M </tex> минимальна. Так как <tex> (M, u, v) </tex> минимально, то <tex> N </tex> должно охватывать <tex> u </tex> и <tex> v </tex> так, что есть другая вершина <tex> x </tex>, покрытая только в <tex> M </tex>.#: Пусть <tex> y </tex> будет вершиной покрытой с <tex> x </tex> в <tex> M </tex> и заметим <tex> y \neq t </tex> (иначе можно было бы добавить к <tex> N </tex>). Пусть <tex> z </tex> будет вершиной покрытой с <tex> y </tex> в <tex> N </tex> и заметим <tex> z \neq x </tex> (так как <tex> x </tex> не покрыто в <tex> N </tex>). Тогда <tex> N - yz + xy </tex> {{---}} паросочетание, которое имеет с <tex> M </tex> меньшую симметрическую разность, что противоречит выбору <tex> N </tex>.}}{{Определение |id=barrier|definition=Множество <tex>S \subset V (G)</tex>, для которого <tex>\mathrm{odd}(G - S) - |S| = \mathrm{def}(G) </tex>, называется '''барьером''' (англ. ''barrier'').}}{{Определение|definition=Пусть <tex>X \subset V </tex>. '''Множeство соседей''' (англ. ''neighbors'') <tex>X</tex> определим формулой: <tex>N(X)= \{ y \in V:(x,y) \in E \} </tex>
}}
==Структурная теорема Эдмондса-Галлаи==
{{Определение
|neat = 1
|definition=
Множество Структурные единицы декопозиции:# <tex>S D(G) = \subset {v \in V \mid </tex> существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]], не покрывающее <tex> v\}</tex># <tex>A(G) = N(D(G)) \setminus D(G)</tex>, для которого # <tex>oC(G - S) - |S| = defV \setminus(D(G) \bigcup A(G))</tex># <tex> \alpha (G) </tex> называется '''барьером'''{{---}} размер максимального паросочетания в <tex> G.</tex>
}}
   =Структурная теорема Эдмондса-Галлаи=[[Файл: EG_red.png|300px|thumb|right|Пример. Рёбра из паросочетания выделены красным]]
{{Определение
|definition=
необходимые определения:[[Файл: Edmonds-Gallai.png|300px|thumb|right|Пример. Рёбра из паросочетания выделены жирным]]* Граф <tex>D(G) = \{v \in V |</tex> существует максимальное паросочетаниеназывается '''фактор-критическим''' (англ. ''factor-critical graph''), не покрывающее если для любой вершины <tex> v\}</tex>* <tex>A(G) = N(D(in G)) \setminus D(G)</tex>* в графе <tex>C(G) = V \setminus( D(G) \bigcup A(G) )</tex>* <tex> \alpha (G) </tex> - размер максимального паросочетания в <tex>G{v}</tex>существует [[Теорема Холла#def1|совершенное паросочетание]].
}}
 
 
{{Теорема
|id = theorem_Gallai
|about=Галлаи
|statement=
<tex>G</tex> {{- --}} фактор-критический граф <tex> \Leftrightarrow </tex> <br><tex>G</tex> {{--- }} связен и для любой вершины<tex> u \in V(G) </tex> выполняется равенство <tex> \alpha (G - u) = \alpha (G)</tex>.
}}
 
{{Лемма
|id = stability_lemma|about= Галлаи, о стабильности (англ. ''stability lemma'')
|statement=
пусть Пусть <tex> a \in A(G).</tex> Тогда: * # <tex>D(G - a) = D(G)</tex> * # <tex>A(G - a) = A(G) \setminus \{a\}</tex>* # <tex>C(G - a) = C(G)</tex> * # <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
|proof=
Достаточно доказатьДля начала докажем, что <tex>D(G-a) = D(G)</tex>. <br><tex>1)</tex> покажем[[Файл: Gallai-lema-a.png|150px|thumb|right|Случай '''а''']][[Файл: Gallai-lema-b.png|150px|thumb|right|Случай '''b''']][[Файл: Gallai-lema-с.png|150px|thumb|right|Случай '''c''']]# Покажем, что <tex>D(G - a) \supset D(G)</tex> : <br>#:Пусть <tex>u \in D(G)</tex>. Тогда существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание ]] <tex> Mu M_u</tex> графа <tex>G</tex>, не покрывающее <tex>u</tex>. Поскольку любое максимальное паросочетание графа <tex>G</tex> покрывает <tex>a</tex>, то <tex> \alpha (G - a) = \alpha (G) - 1 </tex> и более того, если , для некоторой вершины <tex>x \in D(G)</tex>, <tex> ax \in Mu M_u</tex>, то <tex>Mu M_u \setminus {ax} </tex> {{- --}} максимальное паросочетание графа <tex> G - a </tex>, не покрывающее <tex> u </tex>. Таким образом, <tex>D(G - a) \supset D(G) </tex>. <br><tex>2)</tex>#покажем, что <tex> D(G - a) \subset D(G)</tex>: <br>Предположим, что существует максимальное паросочетание <tex>M'</tex> графа<tex> G - a</tex>, не покрывающее вершину <tex>v not </tex> <tex> \in notin D(G)</tex>. Пусть <tex> w \in D(G) </tex>{{-- -}} смежная с<tex> a \in A(G)</tex> вершина, а <tex> Mw M_w </tex>{{--- }} максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> w </tex>. Так как <tex> v not </tex> <tex> \in notin D(G) </tex>, максимальное паросочетание <tex> Mw M_w </tex> покрывает вершину <tex>v</tex>. Рассмотрим граф <tex> H = G(Mw M_w \bigcup M') </tex> {{- --}} очевидно, он является объединением нескольких путей и чётных циклов. Пусть <tex> U </tex> {{-- -}} компонента связности графа <tex> H </tex>, содержащая <tex>v</tex>. Так как <tex> dHdeg_H(v) = 1 </tex>(степень вершины), то <tex> P = H(U) </tex> {{--- }} путь с началом в вершине <tex>v</tex>. В пути <tex>P</tex> чередуются рёбра из <tex> Mw M_w</tex> и <tex>M' </tex>, причём начинается путь ребром из <tex>Mw M_w </tex> . Так как <tex> dHdeg_H(a) = 1 </tex>, то вершина a либо не принадлежит пути <tex>P</tex>, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию <tex> MwM_w</tex>). Рассмотрим несколько случаев: <br>
[[Файл: Gallai-lema-a.png|150px|thumb|right|случай '''а''']]
'''a.''' Путь <tex>P</tex> кончается ребром из <tex> M'</tex> (см. рисунок)<br>
Рассмотрим паросочетание <tex>Mv M_v = Mw M_w \oplus E(P)</tex> (симметрическая разность<tex> Mw M_w</tex> и <tex>E(P)</tex>. то есть, рёбра, входящие ровно в одно из двух множеств).Очевидно, <tex>MvM_v</tex> {{--- }} максимальное паросочетание графа <tex> G</tex>, не покрывающее <tex> v</tex>, поэтому <tex> v \in D(G)</tex>, противоречие. <br>
[[Файл: Gallai-lema-b.png|150px|thumb|right|случай '''b''']]'''b.''' Путь <tex>P</tex> кончается ребром из <tex> MwM_w</tex>, вершина <tex>a </tex> {{--- }} конец пути <tex>P</tex>. (см.рисунок)<br>Рассмотрим паросочетание <tex>Mv∗ M_v∗ = (Mw M_w \oplus E(P)) \bigcup \{aw\} </tex>. Тогда <tex> Mv∗ M_v∗ </tex> {{- --}} максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> v </tex>, поэтому <tex> v \in D(G) </tex>, противоречие.
[[Файл: Gallai-lema-с.png|150px|thumb|right|случай '''c''']]'''c.''' Путь <tex> P </tex> кончается ребром из <tex> MwM_w, a \in V(P) </tex> (см. рисунок)
Рассмотрим паросочетание <tex> M'' = M \oplus E(P) </tex>. Тогда <tex> |M''| = |M'| + 1 </tex>, причём <tex>M'' \subset E(G - a)</tex>. Противоречие с максимальностью паросочетания <tex>M'</tex>.
 
Таким образом, наше предположение невозможно и <tex>D(G - a) \subset D(G)</tex>.
А значит, <tex>D(G - a) = D(G)</tex>.
Таким образомТак как <tex>D(G - a) = D(G)</tex>, то все вершины, которые были соседями <tex>D(G)</tex>, наше предположение невозможно таковыми и остались. Однако, по условию <tex> a \in A(G)</tex>, значит <tex>A(G - a) = A(G) \setminus \{a\}</tex>.  Так же заметим, что <tex>C(G - a) = V(G - a) \setminus (D(G - a) \subset cup A(G - a)) = V(G - a) \setminus (D(G) \cup (A(G) \setminus \{a\}))</tex>.<tex> = V(G) \setminus (D(G) \cup A(G)) = C(G)</tex> 
А значитНаконец, так как <tex>Da \in A(G)</tex>, то все максимальные паросочетания в <tex>G</tex> включали <tex>a</tex>. Следовательно, <tex>\alpha (G - a) < \alpha (G)</tex>. Заметим, что, взяв любое максимальное паросочетания в <tex>G</tex> и удалив ребро инцидентное <tex>a</tex>, мы получим паросочетание <tex>M'</tex>, которое на 1 меньше исходного, при этом <tex>M' \in E(G - a)</tex>. В свою очередь, это самое большое паросочетание, которое мы могли теоретически получить в <tex>G - a</tex>. Следовательно, <tex> \alpha (G - a) = D\alpha (G)- 1.</tex>.
}}
 
{{Теорема
|id = theorem_Gallai_Edmonds
|about = Галлаи, Эдмондс
|statement=
Пусть <tex>G </tex> {{- --}} граф, <tex>U1,{...},UnU_1\ldots U_n</tex> {{--- }} компоненты связности графа <tex>G(D(G))</tex> , <tex>Di D_i = G(UiU_i), C = G(C(G))</tex>. тогдаТогда:# Граф <tex>C</tex> имеет совершенное паросочетание.<br># Графы <tex>D_1\ldots D_n</tex> {{---}} фактор-критические. <br># Любое максимальное паросочетание <tex>M</tex> графа <tex> G </tex> состоит из совершенного паросочетания графа <tex> C </tex>, почти совершенных паросочетаний графов <tex> D_1\ldots D_n </tex> и покрывает все вершины множества <tex> A(G) </tex> рёбрами с концами в различных компонентах связности <tex> U_1\ldots U_n. </tex> <br># <tex>\mathrm{def}(G) = n - |A(G)|.</tex> <br># <tex>2\mathrm{\alpha}(G) = v(G) + |A(G)| - n</tex>.|proof=
[[Файл: Edmonds-Gallai_2.png|300px|thumb|right|Пример]]
1# Последовательно удаляя вершины множества <tex>A = A(G) Граф </tex>, по лемме о стабильности мы получим:#:* <tex>CD(G - A) = D(G),</tex> имеет совершенное паросочетание.#:* <tex>A(G - A) = \O, <br/tex>2) Графы #:* <tex>D1C(G - A) = C(G),{...},Dn</tex> #:* <tex>\alpha (G - факторA) = \alpha (G) -критические|A|. <br/tex>3#:#:Это означает, что не существует рёбер, соединяющих вершины из <tex>C(G - A)</tex> и <tex>D(G - A) Любое </tex>. Каждое максимальное паросочетание <tex>M'</tex> графа <tex>G- A</tex> состоит из совершенного паросочетания графа покрывает все вершины множества <tex>C(G)</tex>, почти совершенных паросочетаний графов поэтому <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex>D1,{...}Тем самым,Dnмы доказали пункт <tex>1)</tex> и покрывает все вершины множества .#:# Из формулы <tex>\alpha(G - A) = \alpha (G)- |A|</tex> следует, что <tex>U_1\ldots U_n</tex> рёбрами с концами в различных компонентах {{---}} компоненты связности графа <tex>U1G - A</tex>. Для любой вершины <tex>u \in U_i</tex> существует максимальное паросочетание <tex>M_u</tex> графа <tex>G - A</tex>,не содержащее <tex>u</tex>. Так как <tex>U_i</tex> {...{---}}компонента связности графа <tex>G - A</tex>,Unпаросочетание <tex>M_u</tex> содержит максимальное паросочетание графа <tex>D_i</tex> (разумеется, не покрывающее вершину <tex>u<br/tex>4) . Следовательно, <tex>def\alpha (GD_i) = n \alpha (D_i - u) </tex> и по теореме Галлаи (мы получаем, что граф <tex>D_i</tex> {{---}} фактор-критический.#:# Пусть <tex>M</tex> {{---}} максимальное паросочетание графа <tex>G</tex>, а <tex>M'</tex> получено из <tex>M</tex> удалением всех рёбер, инцидентных вершинам множества <tex>A</tex>. Тогда <tex>|M'| \geqslant |M| - |A|</tex> и по формуле <tex> \alpha (G- A)= \alpha (G) - |A|</tex> понятно, 2что <tex>M'</tex> {{---}} максимальное паросочетание графа <tex>G - A</tex>. Более того, из <tex> \alpha (G- A) = v\alpha (G) + - |A(|</tex> следует <tex>|M'| = |M| - |A|</tex>, а значит, все вершины множества <tex>A</tex> покрыты в <tex>M</tex> различными рёбрами. Так как <tex>M'</tex> {{---}} максимальное паросочетание графа <tex>G- A</tex>, то по пунктам <tex>1)| </tex> и <tex>2)</tex> очевидно, что <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex> и почти совершенные паросочетания фактор- nкритических графов <tex>D_1\ldots D_n</tex>. Значит, рёбра паросочетания <tex>M</tex> соединяют вершины <tex>A</tex> с непокрытыми <tex>M'</tex> вершинами различных компонент связности из <tex>U_1\ldots U_n</tex>.# Из пункта <tex>3)</tex> сразу же следуют равенства пункта <tex>4)</tex> и <tex>5)</tex>.}}
{{Утверждение|proofabout=следствие из теоремы 1) Последовательно удаляя вершины множества<tex> A |statement= A(G)</tex>, по лемме о стабильности мы получим:* <tex>D(G - A) = D(G),</tex> * <tex>A(G {{--- A) = \O, }} '''барьер''' графа </tex>* <tex>C(G - A) = C(G),</tex>* <tex>\alpha (G - A) = \alpha (G) - |A|.</tex>}}
Это означает, что не существует рёбер, соединяющих вершины из {{Лемма|id = barier_struct1|about = о связи барьера с <tex>CD(G - A)</tex> и |statement= Для любого барьера <tex>B</tex>графа <tex>G</tex> верно, что <tex>B\cap D(G ) = \varnothing</tex>|proof= Рассмотрим <tex>U_{1}, U_{2}, \ldots U_{n}</tex> {{--- A)}} нечётные компоненты связанности <tex>G \setminus B</tex>, <tex>\ M</tex>. Каждое {{---}} максимальное паросочетание в <tex>G</tex>. <tex>\forall\ U_{i}\ \exists x \in U_{i}: x</tex> не покрыта <tex>\ M'</tex> графа или <tex>G - Axv \in M \land v \in B</tex> покрывает все вершины множества . Всего графе не покрыто хотя бы <tex>Codd(G\setminus B)- |B|</tex>вершин. Однако, поэтому так как <tex>M'B</tex> содержитсовершенное {{---}} барьер, непокрыто '''ровно''' столько вершин. Следовательно, любое максимальное паросочетание графа не покрывает только вершины из <tex>CG \setminus B</tex>, а значит каждая вершина барьера покрыта в любом максимальном паросочетании. Тем самымОтсюда получаем, мы доказали пункт 1что ни одна вершина из <tex>D(G)</tex> не могла оказаться в барьере.}}
2) Из формулы <tex> \alpha(G - A) {{Утверждение|id = \alpha (G) - barier_struct1a|Aabout=Следствие из леммы|</tex> следует, что <tex>U1,{...},Un</tex>- компоненты связности графа statement=В любом максимальном паросочетании все вершины барьера соединены соединены с вершинами <tex>G - A</tex>. Для любой вершины <tex>u \in Ui setminus B</tex>существует максимальное паросочетание <tex>Mu</tex> графа <tex>G - A</tex>, не содержащее <tex>u</tex>. |proof=Так как для барьера <tex>UiB</tex> - компонента связности графа верно, что <tex>odd(G \setminus B) - A|B|=def(G) \geqslant 0</tex>, паросочетание то ровно <tex>Mu|B|</tex> содержит максимальное паросочетание графа вершин из нечётных компонент <tex>DiG \setminus B</tex> (разумеется, не покрывающее вершину <tex>u</tex>). Следовательно, покрыты рёбрами <tex> xv \in M \alpha (Di) = land v \alpha (Di - u) in B</tex> и по теореме Галлаи(выше) мы получаем, что граф <tex>Di</tex> - фактор-критический.}}
3) {{Лемма|id = barier_struct2|about = о дополнении барьера|statement= Пусть <tex>Mx\in A(G)\cup C(G),\ G'=G\setminus x,\ B'</tex> {{- максимальное паросочетание --}} барьер графа <tex>G'</tex>, а . Тогда <tex>MB=B'\cup x</tex> получено из {{---}} барьер графа <tex>MG</tex> удалением всех рёбер, инцидентных вершинам множества <tex>A</tex>. Тогда <tex>|M'| \ge |M| - |A|</tex> и по формуле proof= Так как <tex> x \alpha (G - A) = \alpha notin D(G) - |A|</tex> понятно, что то для любого максимального паросочетания <tex>M'</tex> - максимальное паросочетание графа <tex>G - A: x \in M</tex>. Более тогоСледовательно, из <tex> \alpha (G - A) = \alpha (G) - |A|</tex> следует <tex>|M'| = |M| - |A|1</tex>, а значит, все вершины множества <tex>A</tex> покрыты в <tex>M</tex> различными рёбрамию Так как где <tex>M'</tex> {{- --}} максимальное паросочетание графа в <tex>G - A</tex>, то по пунктам 1) и 2) очевидно, что <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex> и почти совершенные паросочетания фактор-критических графов <tex>D1,{...},Dn</tex>. Значит, рёбра паросочетания <tex>M</tex> соединяют вершины <tex>A</tex> с непокрытыми <tex>M'</tex> вершинами различных компонент связности из <tex>U1,{...},Un</tex>. 4) Из пункта 3) сразу же следуют оба равенства пункта 4).
<tex>def(G') = (|V| - 1)- 2 \cdot |M'| = |V| - 2 \cdot |M| + 1 = def(G) + 1</tex>
<tex>odd(G - (B'\cup x)) = odd(G' - B') = </tex><tex>|B'| + def(G') = |B'| + 1 + def(G) = |B'\cup x| + def(G)</tex>Отсюда следует, что <tex>B</tex> {{---}} барьер графа <tex>G</tex>. }}
{{УтверждениеТеорема|id=barier_struct3 |about=следствие из теоремыо структуре барьера|statement=Любой барьер графа состоит только из вершин <tex>A(G)\cup C(G)</tex> , причём каждая вершина из этого множества входит в какой- '''то барьер''' графа |proof=По лемме о связи барьера с <tex>D(G)</tex> мы знаем, что в барьере нет вершин вершин из <tex>D(G)</tex>. По лемме о дополнение барьера мы можем взять любую вершину из <tex>A(G)\cup C(G)</tex>, удалить из графа, и с помощью барьера нового графа получить барьер исходного, включающий данную вершину.
}}
== См. также ==
* [[Теорема Татта о существовании полного паросочетания]]
* [[Лапы и минимальные по включению барьеры в графе]]
* [[Пересечение всех максимальных по включению барьеров]]
== Источники информации==
*[http://www.people.vcu.edu/~dcranston/691/edmonds-gallai.pdf Edmonds-Gallai Decomposition and Factor-Critical Graphs]
*[http://logicimmorlica.pdmi.ras.ru/~dvkcom/211combOpt/graphs_dklec2.pdf Д.В Карпов Edmonds- теория графовGallai Decomposition, Edmonds’ Algorithm]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Задача о паросочетании]]
Анонимный участник

Навигация