Участник:Masha — различия между версиями

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

Текущая версия на 22:34, 13 июня 2021

Формула Бержа

Определение:
[math]\mathrm{odd}({G})[/math] — число нечетных компонент связности в графе [math]{G}[/math], где нечетная компонента (англ. odd component) — это компонента связности, содержащая нечетное число вершин.



Лемма:
[math](n + |S| + odd(G \setminus S)) \; \equiv \; 0 \; ( mod \; 2) \; [/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|\; + \; \sum_{i=1}^{k}k_i) \; \equiv \; 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|) \; \equiv \; n \; (mod \; 2) \;[/math].
[math]\triangleleft[/math]


Теорема:
[math]def G = \max\limits_{S \in V} (odd(G \setminus S) - |S|)[/math]
Доказательство:
[math]\triangleright[/math]

[math] \forall S \in V : \; (odd(G \setminus S) + |S|) \; \equiv \; n ( mod \; 2) \;[/math]


Рассмотрим несколько случаев:


1. Если [math] \max\limits_{S \in V}(odd(G \setminus S) \; - \; |S|) \; = 0 \; [/math], тогда для любых [math]S \in V: \; odd(G \setminus S) \leq |S| \; [/math], следовательно выполнено условие теоремы Татта, значит, в графе есть совершенное паросочетание, то есть его дефицит равен нулю.

2. Если [math] \max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \; [/math], тогда рассмотрим исходный граф [math]G[/math] и полный граф [math]K_k[/math] с [math]k[/math] вершинами, [math]W[/math] - вершины [math]K_k[/math]. Каждую вершину [math]K_k[/math] соединим с каждой вершиной [math]G[/math]. Получим граф [math]H \; = \; K_k + G \;[/math], докажем, что для него выполнено условие теоремы Татта. Докажем, что для любых [math]S \in V_{H}: odd(H \setminus S) \; \leq \; |S| \; [/math]. Рассмотрим [math]S \; \subset \; V_H\;[/math]:

  • Если [math]W \not\subset S[/math], тогда поскольку граф [math]K_k[/math] полный и все его вершины связаны с каждой вершиной графа [math]G[/math], то граф [math]H[/math] связный и [math]odd(H \setminus S) \; = \; 0 \;[/math] или [math]odd(G \setminus S) \; = \; 1 \;[/math].
    • В случае [math]odd(H \setminus S) \; = \; 0 \; [/math] условие очевидно выполняется, так как для любых [math]S \in G : 0 \; \leq \; |S| \;[/math].
    • Рассмотрим случай [math]odd(H \setminus S) \; = \; 1 \;[/math], [math]|V_H| \; = \; n \; + \; k \; = \; n \; + \; odd(G \setminus A) \; - \; |A| \; [/math], где [math]A \; = \; arg \max\limits_{S \in V}(odd(G \setminus S) \; - \; |S|) \; [/math]. Разность [math]odd(G \setminus A) \; - \; |A| \; [/math] имеет ту же четность, что и [math]n[/math], и [math]odd(H \setminus S) \; = \; 1 \;[/math], поэтому [math]|V_H|[/math] четно, значит, по лемме, мощность [math]S[/math] нечетна, следовательно она не равна нулю, значит, [math] 1 \leq |S| [/math].


  • Если [math]W \subset S \;[/math], то [math]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| \; [/math], так как [math] \max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \; [/math]. Таким образом, для графа [math]H[/math] выполнено условие теоремы Татта, следовательно в нём есть полное паросочетание. Рассмотрим полное паросочетание в графе [math]H[/math], удалим вершины [math]W[/math] из графа [math]H[/math]. Количество непокрытых вершин после удаления не больше, чем количество удаленных вершин [math]k[/math], значит, [math]def(G) \; \leq \; k[/math]. Удалим множество вершин [math]A \; = \; arg \max\limits_{S \in V}(odd(H \setminus S) \; - \; |S|) \; [/math] из графа [math]G\;[/math]. Заметим, что после удаления в графе осталось [math]odd(G \setminus A)\; [/math] нечетных компонент и образовались новые непокрытые вершины, но при этом число нечетных компонент больше числа удаленных на [math]k[/math]. Значит, хотя бы [math]k[/math] нечетных компонент содержали исходно непокрытую вершину, следовательно [math]def(G) \; \geq \; k \; [/math]. Из [math]def(G) \; \leq \; k[/math] и [math]def(G) \; \geq \; k \; [/math] следует [math]def(G) \; = \; k \; [/math].
[math]\triangleleft[/math]

См. также

Источники информации

— Лекция А.С. Станкевича