Теорема Холла

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Теорема Холла(також відома як теорема про одруження)— комбінаторне твердження, що дає достатні і необхідні умови існування вибору різних елементів з деякого набору скінченних множин. Теорема названа на честь англійського математика Філіпа Холла.

Твердження[ред.ред. код]

Теорема Холла може бути сформульована кількома способами, зокрема за допомогою мови теорії графів і теорії трансверсалів.

Твердження у теорії графів[ред.ред. код]

Нехай G=(V, E)\; — деякий граф, і A \subseteq V, B \subseteq V\; підмножини його вершин, такі що A \cup B = V\;, і для довільного ребра e\; такого що e= \lbrace  v, u \rbrace\;, справедливе твердження

(v \in A \and u \in B) \or (v \in B \and u \in A)\;,

тобто граф G\; є дводольним. Тоді для даного графа існує набір ребер, що з'єднують вершини A\; з різними вершинами B\; тоді й лише тоді коли для кожної підмножини елементів K\subseteq A\; виконується

|W| \geqslant |K|,\;

де:

W=\{w \in B\colon (\exists k\in K) \lbrace k,w\rbrace \in E\}\;

множина елементів з B,\; що з'єднані ребрами хоча б з одним елементом підмножини K\; Остання умова також називається умовою одружень.

Твердження у теорії трансверсалів[ред.ред. код]

Нехай S = {S1, S2, ... } - деяка сім'я скінченних множин. Трансверсалем для S, називається множина X = {x1, x2, ...} різних елементів (де |X| = |S|) з властивістю, що для всіх i, xiSi.

Теорема Холла стверджує, що трансверсаль для S існує тоді й лише тоді, коли виконується умова


|T| \le \Bigl|\bigcup_{t \in T} t\Bigr|

Доведення[ред.ред. код]

Доведення 1[ред.ред. код]

Доведення здійснюватимемо методом математичної індукції щодо кількості елементів S.

Теорема очевидно справедлива для \vert S\vert=0. Припустимо твердження теореми справедливе для \left\vert S\right\vert<n, доведемо її для випадку \left\vert S\right\vert=n.

Спершу розглянемо випадок коли виконується  \left\vert\cup T \right\vert \ge \left\vert T\right\vert+1 для всіз власних підмножин T of S. Виберемо довільний елемент x\in S_n представником S_n. Якщо існує трансверсаль для  S' = \left\{S_1\setminus\{x\},\ldots,S_{n-1}\setminus\{x\}\right\}, тоді R' \cup \{x\} є трансверсаллю для S. Але якщо взяти  \{S_{j_1}\setminus\{x\},...,S_{j_k}\setminus\{x\}\} = T'\subseteq S' то за припущенням,  \left\vert\cup T'\right\vert \ge \left\vert\cup_{i=1}^{k} S_{j_i}\right\vert-1 \ge k. Згідно з припущенням індукції для S' і як наслідок для S існує трансверсаль.

В іншому випадку для деякої \emptyset\ne T \subset S виконується рівність  \left\vert\cup T\right\vert=\left\vert T\right\vert. Для T маємо, що для кожної T'\subseteq T\subset S виконується  \left\vert\cup T'\right\vert\ge\left\vert T'\right\vert, і за припущенням індукції для T існує трансверсаль.

Для завершення доведення достатньо знайти представників для множин S\setminus T що не містять елементів \cup T. Для цього достатньо довести, що для довільної множини T'\subseteq S\setminus T, виконується

 \left\vert\cup T' \setminus \cup T\right\vert \ge \left\vert T'\right\vert

і скористатися припущенням індукції.

Маємо

\left\vert\cup T' \setminus \cup T\right\vert

 = \left\vert\bigcup(T\cup T')\right\vert - \left\vert\cup T\right\vert \ge \left\vert T\cup T'\right\vert - \left\vert T\right\vert

 = \left\vert T\right\vert + \left\vert T'\right\vert - \left\vert T\right\vert = \left\vert T'\right\vert,

зважаючи на відсутність спільних елементів у T і T', і той факт, що  \left\vert\cup T\right\vert=\left\vert T\right\vert. Тому за припущенням індукції, S\setminus T має трансверсаль, що не містить елементів \cup T.

Доведення 2[ред.ред. код]

Позначимо через H\; підграф графа G=(V, E)\; такий, що

  • кожна вершина інцидентна деякому ребру графа H\;
  • граф H\; задовольняє умову одружень і є мінімальним за включенням ребер графом, що задовольняє цю вимогу.

Позначимо d_H(a)\; — степінь вершини a в графі H\;. Очевидно, що d_H(a) \geq 1. Для доведення теореми Холла достатньо довести, що d_H(a) = 1\;.

Для цього спершу позначимо : N_H(K)=\{w \in B\colon (\exists k\in K) \lbrace k,w\rbrace \in E\}\;

Припустимо, що деяка вершини a \in A з'єднується більш ніж з однією вершиною і нехайb_1,b_2 \in N_H(a).\; Тоді згідно з вибором H\; графи H-\{ab_1\}\; і H-\{ab_2\}\; не задовольняють умови одружень. Тому для i=1,2\; існують такі A_i \subset A що містять a і |A_i| > |B_i|\; де B_i:=N_{H-\{ab_i\}}(A_i)\;. Звідси одержуємо:

|N_H(A_1 \cap A_2 \smallsetminus \{a\} )|\leq|B_1 \cap B_2|
=|B_1|+|B_2|-|B_1 \cup B_2|=|B_1|+|B_2|-|N_H(A_1 \cup A_2)
\leq |A_1|-1+|A_2|-1-|A_1 \cup A_2|=|A_1 \cap A_2 \smallsetminus \{a\} |-1

Тобто H не задовольняє умови одружень, що суперечить припущенню і доводить теорему.

Посилання[ред.ред. код]