Изменения

== Алгоритм декодирования кодa Прюфера Формула Бержа ==

В массиве вершин исходного дерева <tex>V{{Определение|definition =</tex> найдём вершину <tex>v_\mathrm{minodd}</tex> с минимальным номером, не содержащуюся в массиве с кодом Прюфера <tex>P</tex>, т.е. такую, что она является листом или концом уже добавленного в граф ребра, т.е. она стала листом в процессе построения кода Прюфера (по первому пункту построения{G}). Вершина <tex>p_1</tex> была добавлена в код Прюфера как инцидентная листу с минимальным номером (по второму пункту построения), поэтому в исходном дереве существует ребро {<tex>p_1</tex>, <tex>v_{min---}</tex>}, добавим его число нечетных компонент связности в список ребер. Удалим первый элемент из массива графе <tex>Р</tex>, а вершину <tex>v_{minG}</tex> - из массива <tex>V</tex> т.к, где '''нечетная компонента''' (англ. она больше не может являться листом (по третьему пункту построения''odd component''). Будем выполнять вышеуказанные действия{{---}} это [[Отношение связности, пока массив <tex>P</tex> не станет пустым. В конце работы алгоритма в массиве <tex>V</tex> останутся две вершиныкомпоненты связности#def2|компонента связности]], составляющие последнее ребро дерева (это следует из построения)содержащая нечетное число вершин.}}

  {{Лемма|statement=<tex>(n + |S| + odd(G \setminus S)) \; \equiv \; 0 \; ( mod \; 2) \; </tex>, где <tex>G</tex> {{---}} граф с <tex>n</tex> вершинами, <tex>S \in {V}_{G}</tex>|proof=Удалим из графа <tex>G</tex> множество <tex>S</tex>, получим <tex>t</tex> компонент связности, содержащих <tex>k_1, k_2 ... k_t</tex> вершин соответственно.<tex>|S|\; + \; \sum_{i= Реализация 1}^{k}k_i \; =\; n \; </tex>, так как в сумме это все вершины исходного графа <tex>G</tex>. Возьмем данное равенство по модулю два: <tex>(|S|\; + \; \sum_{i=1}^{k}k_i) \; \equiv \; n \; (mod \; 2)</tex>В сумме <tex>\sum_{i=1}^{k}(k_i \; mod \; 2)</tex> число единиц равно числу нечетных компонент <tex>odd(G \setminus S)</tex>. Таким образом, <tex> \forall S \in V : \; (odd(G \setminus S) + |S|) \; \equiv \; n \; (mod \; 2) \;</tex>. # P - код Прюфера}}   {{Теорема # |statement= <tex>def G = \max\limits_{S \in V } (odd(G \setminus S) - вершины|S|)</tex>|proof= '''function''' buildTree<tex> \forall S \in V : \; (odd(G \setminus S) + |S|) \; \equiv \; n (P, Vmod \; 2)\;</tex>  Рассмотрим несколько случаев: '''while'' '''not'' P 1.emptyЕсли <tex> \max\limits_{S \in V}(odd(G \setminus S) \; - \; |S|)\; = 0 \; </tex>, тогда для любых <tex>S \in V: u = P\; odd(G \setminus S) \leq |S| \; </tex>, следовательно выполнено условие [[0Теорема Татта о существовании полного паросочетания|теоремы Татта]], значит, в графе есть совершенное паросочетание, то есть его дефицит равен нулю.   v 2. Если <tex> \max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \; </tex>, тогда рассмотрим исходный граф <tex>G</tex> и полный граф <tex>K_k</tex> с <tex>k</tex> вершинами, <tex>W</tex> - вершины <tex>K_k</tex>. Каждую вершину <tex>K_k</tex> соединим с каждой вершиной <tex>G</tex>. Получим граф <tex>H \; = min\; K_k + G \;</tex>, докажем, что для него выполнено условие теоремы Татта. Докажем, что для любых <tex>S \in V_{H}: odd(x '''H \setminus S) \; \leq \; |S| \; </tex>. Рассмотрим <tex>S \; \subset \; V_H\in;</tex>''' V: P.count * Если <tex>W \not\subset S</tex>, тогда поскольку граф <tex>K_k</tex> полный и все его вершины связаны с каждой вершиной графа <tex>G</tex>, то граф <tex>H</tex> связный и <tex>odd(xH \setminus S) \; == \; 0\;</tex> или <tex>odd(G \setminus S)\; = \; 1 \;</tex>. ** В случае <tex>odd(H \setminus S) \; = \; 0 \; </tex> условие очевидно выполняется, так как для любых <tex>S \in G: 0 \; \leq \; |S| \;</tex>.push** Рассмотрим случай <tex>odd(H \setminus S) \; = \; 1 \;</tex>, <tex>|V_H| \; = \; n \; + \; k \; = \; n \; + \; odd(G \setminus A) \; - \; |A| \; </tex>, где <tex>A \; = \; arg \max\limits_{u, vS \in V}(odd(G \setminus S) P\; - \; |S|) \; </tex>.eraseРазность <tex>odd(G \setminus A) \; - \; |A| \; </tex> имеет ту же четность, что и <tex>n</tex>, и <tex>odd(0H \setminus S)\; = \; 1 \;</tex>, поэтому <tex>|V_H|</tex> четно, значит, по лемме, мощность <tex>S</tex> нечетна, следовательно она не равна нулю, значит, <tex> 1 \leq |S| </tex>.   * Если <tex>W \subset S \;</tex>, то <tex>odd(H \setminus S) \; = \; odd(G \setminus (S \cap V)) \; = odd(G \setminus (S \cap V)) \; - \; |S \cap V| \; + \; |S \cap V| \; \leq \; |S \cap V| \; + \; k \leq |S| \; </tex>, так как <tex> \max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \; </tex>. Таким образом, для графа <tex>H</tex> выполнено условие теоремы Татта, следовательно в нём есть полное паросочетание. Рассмотрим полное паросочетание в графе <tex>H</tex>, удалим вершины <tex>W</tex> из графа <tex>H</tex>.eraseКоличество непокрытых вершин после удаления не больше, чем количество удаленных вершин <tex>k</tex>, значит, <tex>def(indexOfG) \; \leq \; k</tex>. Удалим множество вершин <tex>A \; = \; arg \max\limits_{S \in V}(odd(vH \setminus S) \; - \; |S|)\; </tex> из графа <tex>G\;</tex>. Заметим, что после удаления в графе осталось <tex>odd(G \setminus A) \; </tex> нечетных компонент и образовались новые непокрытые вершины, но при этом число нечетных компонент больше числа удаленных на <tex>k</tex>. Значит, хотя бы <tex>k</tex> нечетных компонент содержали исходно непокрытую вершину, следовательно <tex>def(G) \; \geq \; k \; </tex>.pushИз <tex>def(G) \; \leq \; k</tex> и <tex>def(G) \; \geq \; k \; </tex> следует <tex>def({vG) \; = \; k \; </tex>.}} ==См. также== ==Источники информации== [0], https://www.youtube.com/watch?v[1=1KggxCJZFRg {{---}} Лекция А.С. Станкевича]}) '''return''' G