Теорема Холла: відмінності між версіями

[неперевірена версія][неперевірена версія]
Вилучено вміст Додано вміст
м Заміна застарілого математичного синтаксису відповідно до mw:Extension:Math/Roadmap
Немає опису редагування
Рядок 1:
'''Теорема Холла''' (також відома як '''теорема про одруження''')— [[комбінаторика|комбінаторне]] твердження, що дає достатні і необхідні умови існування вибору різних елементів з деякого набору скінченних множин. Теорема названа на честь англійського математика [[Філіп Холл|Філіпа Холла]].
 
== Твердження ==
Теорема Холла може бути сформульована кількома способами, зокрема за допомогою мови [[теорія графів|теорії графів]] і теорії трансверсалів.
 
=== Твердження у теорії графів ===
Нехай <math>G=(V, E)\;</math> &nbsp;— деякий [[граф (математика)|граф]], і <math>A \subseteq V, B \subseteq V\;</math> підмножини його вершин, такі що <math>A \cup B = V\;</math>, і для довільного ребра <math>e\;</math> такого що <math>e= \lbrace v, u \rbrace\;</math>, справедливе твердження
: <math>(v \in A \land u \in B) \lor (v \in B \land u \in A)\;</math>,
тобто граф <math>G\;</math> є [[дводольний граф|дводольним]]. Тоді для даного графаграфу існує набір ребер, що з'єднують вершини <math>A\;</math> з ''різними'' вершинами <math>B\;</math> тоді й лише тоді коли для кожної підмножини елементів <math>K\subseteq A\;</math> виконується
: <math>|W| \geqslant |K|,\;</math>
де:
: <math>W=\{w \in B\colon (\exists k\in K) \lbrace k,w\rbrace \in E\}\;</math>
[[множина]] елементів з <math>B,\;</math> що з'єднані ребрами хоча б з одним елементом підмножини <math>K\;</math>
Остання умова також називається умовою одружень.
 
=== Твердження у теорії трансверсалів ===
Нехай ''S'' = {''S''<sub>''1''</sub>, ''S''<sub>''2''</sub>, ... } -&nbsp;— деяка сім'я скінченних множин. Трансверсалем для ''S'', називається множина ''X'' = {''x''<sub>''1''</sub>, ''x''<sub>''2''</sub>, ...} різних елементів (де |''X''| = |''S''|) з властивістю, що для всіх ''i'', ''x''<sub>''i''</sub>∈''S''<sub>''i''</sub>.
 
Теорема Холла стверджує, що трансверсаль для ''S'' існує тоді й лише тоді, коли виконується умова
 
 
: <math>|T| \le \Bigl|\bigcup_{t \in T} t\Bigr|</math>
 
== Доведення ==
 
=== Доведення 1 ===
Доведення здійснюватимемо [[метод математичної індукції|методом математичної індукції]] щодо кількості елементів ''S''.
 
Рядок 32:
Спершу розглянемо випадок коли виконується
<math> \left\vert\cup T \right\vert \ge \left\vert T\right\vert+1</math>
для всіз власних підмножин ''T'' of ''S''. Виберемо довільний елемент <math>x\in S_n</math> представником <math>S_n.</math> Якщо існує трансверсаль для
<math> S' = \left\{S_1\setminus\{x\},\ldots,S_{n-1}\setminus\{x\}\right\}</math>, тоді <math>R' \cup \{x\}</math> є трансверсаллю для S.
Але якщо взяти
Рядок 47:
 
Для завершення доведення достатньо знайти представників для множин <math>S\setminus T</math> що не містять елементів <math>\cup T</math>. Для цього достатньо довести, що для довільної множини <math>T'\subseteq S\setminus T</math>, виконується
: <math> \left\vert\cup T' \setminus \cup T\right\vert \ge \left\vert T'\right\vert</math>
і скористатися припущенням індукції.
 
Рядок 60:
зважаючи на відсутність спільних елементів у <math>T</math> і <math>T'</math>, і той факт, що <math> \left\vert\cup T\right\vert=\left\vert T\right\vert</math>. Тому за припущенням індукції, <math>S\setminus T</math> має трансверсаль, що не містить елементів <math>\cup T</math>.
 
=== Доведення 2 ===
Позначимо через <math>H\;</math> підграф графаграфу <math>G=(V, E)\;</math> такий, що
* кожна вершина інцидентна деякому ребру графаграфу <math>H\;</math>
* граф <math>H\;</math> задовольняє умову одружень і є мінімальним за включенням ребер графом, що задовольняє цю вимогу.
Позначимо <math>d_H(a)\;</math> &nbsp;— степінь вершини ''a'' в графі <math>H\;</math>. Очевидно, що <math>d_H(a) \geq 1</math>. Для доведення теореми Холла достатньо довести, що <math>d_H(a) = 1\;</math>.
 
Для цього спершу позначимо : <math>N_H(K)=\{w \in B\colon (\exists k\in K) \lbrace k,w\rbrace \in E\}\;</math>
Рядок 70:
Припустимо, що деяка вершини <math>a \in A</math> з'єднується більш ніж з однією вершиною і нехай<math>b_1,b_2 \in N_H(a).\;</math> Тоді згідно з вибором <math>H\;</math> графи <math>H-\{ab_1\}\;</math> і <math>H-\{ab_2\}\;</math> не задовольняють умови одружень. Тому для <math>i=1,2\;</math> існують такі <math>A_i \subset A</math> що містять ''a'' і <math>|A_i| > |B_i|\;</math> де <math>B_i:=N_{H-\{ab_i\}}(A_i)\;</math>.
Звідси одержуємо:
: <math>|N_H(A_1 \cap A_2 \smallsetminus \{a\} )|\leq|B_1 \cap B_2|</math>
 
: <math>=|B_1|+|B_2|-|B_1 \cup B_2|=|B_1|+|B_2|-|N_H(A_1 \cup A_2)</math>
 
: <math>\leq |A_1|-1+|A_2|-1-|A_1 \cup A_2|=|A_1 \cap A_2 \smallsetminus \{a\} |-1</math>
 
Тобто H не задовольняє умови одружень, що суперечить припущенню і доводить теорему.
 
== Посилання ==
* [http://www.cut-the-knot.org/arithmetic/elegant.shtml Теорема Холла на сайті cut-the-knot]
* [http://www.cut-the-knot.org/arithmetic/marriage.shtml Теорема і алгоритм]
 
[[Категорія:Парування]]