Материал из Викиконспекты
|
|
| Строка 1: |
Строка 1: |
| − | == Алгоритм декодирования кодa Прюфера == | + | == Формула Бержа == |
| | | | |
| − | В массиве вершин исходного дерева <tex>V</tex> найдём вершину <tex>v_{min}</tex> с минимальным номером, не содержащуюся в массиве с кодом Прюфера <tex>P</tex>, т.е. такую, что она является листом или концом уже добавленного в граф ребра, т.е. она стала листом в процессе построения кода Прюфера (по первому пункту построения). Вершина <tex>p_1</tex> была добавлена в код Прюфера как инцидентная листу с минимальным номером (по второму пункту построения), поэтому в исходном дереве существует ребро {<tex>p_1</tex>, <tex>v_{min}</tex>}, добавим его в список ребер. Удалим первый элемент из массива <tex>Р</tex>, а вершину <tex>v_{min}</tex> - из массива <tex>V</tex> т.к. она больше не может являться листом (по третьему пункту построения). Будем выполнять вышеуказанные действия, пока массив <tex>P</tex> не станет пустым. В конце работы алгоритма в массиве <tex>V</tex> останутся две вершины, составляющие последнее ребро дерева (это следует из построения).
| + | {{Утверждение |
| | + | |statement= <tex>(n + |S| + odd(G \setminus S)) \; mod \; 2 = 0</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|\; mod\; 2 \; + \; \sum_{i=1}^{k}(k_i \; mod \; 2)) \; mod \; 2 = 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|) \; mod \; 2 = n \; mod \; 2 </tex> |
| | + | }} |
| | | | |
| − | === Реализация ===
| + | |
| − | # P - код Прюфера
| + | |
| − | # V - вершины
| + | {{Теорема |
| − | '''function''' buildTree(P, V):
| + | |statement= <tex>def G = \max\limits_{S \in V} (odd(G \setminus S) - |S|)</tex> |
| − | '''while'' '''not'' P.empty():
| + | |proof= |
| − | u = P[0]
| + | |
| − | v = min(x '''<tex>\in</tex>''' V: P.count(x) == 0)
| + | }} |
| − | G.push({u, v})
| |
| − | P.erase(0)
| |
| − | V.erase(indexOf(v))
| |
| − | G.push({v[0], v[1]})
| |
| − | '''return''' G
| |
Версия 13:03, 3 июня 2021
Формула Бержа
| Утверждение: |
[math](n + |S| + odd(G \setminus S)) \; mod \; 2 = 0[/math], где [math]G[/math] - граф с [math]n[/math] вершинами, [math]S \in {V}_{G}[/math] |
| [math]\triangleright[/math] |
|
Удалим из графа [math]G[/math] множество [math]S[/math], получим [math]t[/math] компонент связности, содержащих [math]k_1, k_2 ... k_t[/math] вершин соответсвенно.
[math]|S|\; + \; \sum_{i=1}^{k}k_i = n[/math] т. к в сумме это все вершины исходного графа [math]G[/math].
Возьмем данное равенство по модулю два: [math](|S|\; mod\; 2 \; + \; \sum_{i=1}^{k}(k_i \; mod \; 2)) \; mod \; 2 = n \; mod \; 2[/math]
В сумме [math]\sum_{i=1}^{k}(k_i \; mod \; 2)[/math] число единиц равно числу нечетных компонент [math]odd(G \setminus S)[/math]. Таким образом, [math] \forall S \in V \; (odd(G \setminus S) + |S|) \; mod \; 2 = n \; mod \; 2 [/math] |
| [math]\triangleleft[/math] |
| Теорема: |
[math]def G = \max\limits_{S \in V} (odd(G \setminus S) - |S|)[/math] |
