Приводятся определения трансверсали. Используя эти понятия, дается еще
одно доказательство теоремы Холла. Описывается несколько приложений в
лексике
Если $$E$$ — непустое конечное множество и $$\varphi
=(S_{1}\dts
S_{m})$$ — семейство (не обязательно различных) непустых его
подмножеств,
Общие трансверсали. Если $$E$$ — непустое конечное
множество, а $$\varphi =(S_{1} \dts S_{m})$$ и $$\tau =(T_{1}\dts
T_{m})$$ — два
семейства его непустых подмножеств, то интересно знать, когда существует
общая трансверсаль для $$\varphi$$ и $$\tau$$, то есть
множество, состоящее из $$m$$ различных элементов множества $$E$$ и являющееся
Рассмотрим пример. Предположим, что $$E=\{ 1,2,3,4,5,6\}$$,
а $$S_{1}
=S_{2} =\{ 1,2\}$$, $$S_{3} =S_{4} =\{ 2,3\}$$, $$S_{5} =\{
1,4,5,6\}$$.
Подсемейство $$\varphi' =(S_{1},S_{2},S_{3},S_{5})$$ имеет
трансверсаль, например $$\{ 1,2,3,4\}$$. Трансверсаль произвольного подсемейства
семейства $$\varphi$$ будем называть
Естественно спросить: при каких условиях данное семейство подмножеств
некоторого множества имеет трансверсаль? Легко увидеть связь между
этой задачей и
Теорема Пусть $$E$$ — непустое конечное множество и $$\varphi =(S_{1} \dts S_{m})$$ — семейство непустых его подмножеств; тогда $$\varphi$$ имеет трансверсаль в том и только в том случае, если для любых $$k$$ подмножеств $$S_{i}$$ их объединение содержит, по меньшей мере, $$k$$ элементов $$(1\le k\le m)$$.
Доказательство Необходимость этого условия очевидна. Для доказательства достаточности установим, что если одно из подмножеств (скажем, $$S_{1}$$ ) содержит более одного элемента, то можно удалить один элемент из $$S_{1}$$, не нарушив условия теоремы. Повторением этой процедуры мы добьемся сведения задачи к тому случаю, когда каждое подмножество содержит только один элемент. Тогда утверждение станет очевидным.
Осталось обосновать законность этой "процедуры сведения". Предположим, что $$S_{1}$$ содержит элементы $$x$$ и $$y$$, удаление каждого из которых нарушает условие теоремы. Тогда существуют подмножества $$A$$ и $$B$$ множества $$\{ 2,3\dts m\}$$, обладающие тем свойством, что$$\begin{align*} \left|\bigcup _{j\in A}S_{j} \bigcup (S_{1} -\{ x\} ) \right| \le \left|A\right|\\ \left|\bigcup_{j\in B}S_{j} \bigcup (S_{1} -\{ y\} )\right| \le \left|B\right|. \end{align*}$$
Но эти два неравенства приводят к противоречию, поскольку
$$\begin{aligned} \left|A\right|+\left|B\right|+1 =\left|A\bigcup B \right|+\left|A\bigcap B \right|+1\le\\ \le \left|\bigcup _{jA\bigcup B }S_{j} \bigcup S_{1} \right|+\left|\bigcup _{j\in A\bigcap B }S_{j} \right|\le \quad \t{(по условию)}\\ \le \left|\bigcup _{j\in A}S_{j} \bigcup (S_{1} -\{ x\} ) \right|+\left|\bigcup _{j\in B}S_{j} \bigcup S_{1} -\{ y\} ) \right|\le\\ \qquad \qquad \qquad\qquad\qquad \qquad\le \quad \t{(так как $\left|S_{1} \right|\ge 2)$}\\ \le \left|A\right|+\left|B\right| \quad \t{(по предположению)}. \end{aligned}$$Прелесть этого доказательства в том, что оно проводится, по существу, лишь в один шаг, в отличие от доказательства Халмоша-Вогена, которое предполагает исследование двух отдельных случаев. (Однако доказательство Радо труднее перевести на весьма наглядный матримониальный язык!).
Следствие В тех же обозначениях, что и выше, $$\varphi$$ имеет частичную трансверсаль мощности $$t$$ тогда и только тогда, если для любых $$k$$ подмножеств $$S_{i}$$ их объединение содержит, по меньшей мере, $$k+t-m$$ элементов.
Доказательство
Требуемый результат можно получить, применив теорему Холла в
лексике
Следствие Если $$E$$ и $$\varphi$$ такие же, как и прежде, а $$X$$ — любое подмножество из $$E$$, то $$X$$ содержит частичную трансверсаль мощности $$t$$ для $$\varphi$$ тогда и только тогда, если для каждого подмножества $$A$$ множества $$\{1\dts m\}$$$$\left|(\bigcup _{j\in A}S_{j} )\bigcap X \right|\ge \left|A\right|+t-m.$$
Доказательство Достаточно применить предыдущее следствие к семейству $$\varphi_{x} =(S_{1} \bigcap X\dts S_{m} \bigcup X)$$.
Используются понятия
Теорема
Пусть $$M$$ латинский $$m\times n$$ -прямоугольник,
причем, $$m < n$$ ; тогда $$M$$ можно расширить до
Доказательство Докажем, что $$M$$ можно расширить до латинского $$(m+1)\times n$$ -прямоугольника; повторяя эту процедуру, мы придем к латинскому квадрату.
Пусть $$E=\{1,2\dts n\}$$ и $$\varphi =(S_{1}\dts S_{n})$$, где через $$S_{i}$$ обозначено множество, состоящее из тех элементов множества $$E$$, которые не встречаются в $$i$$ -м столбце матрицы $$M$$. Если мы сможем доказать, что $$\varphi$$ имеет трансверсаль, то тем самым мы докажем теорему, поскольку элементы этой трансверсали и образуют дополнительную строку. По теореме Холла достаточно доказать, что объединение любых $$k$$ множеств $$S_{i}$$ содержит по меньшей мере $$k$$ различных элементов. А это очевидно, ибо любое такое объединение содержит $$(n-m)\times k$$ элементов (включая повторения), значит, по крайней мере, один из них повторялся бы более чем $$n-m$$ раз, что невозможно.
Определение
Определение
Теорема (Кенига-Эгервари, 1931)
Замечание
В качестве иллюстрации этой теоремы рассмотрим
матрицу$$\begin{aligned} \,\,\,\,\,\begin{matrix} e_{1}\,\,
e_{2}\,\, e_{3}\,\, e_{4}\,\, e_{5}\,\, e_{6}
\end{matrix}\\
\begin{matrix}
S_1 \\
S_2 \\
S_3 \\
S_4 \\
S_5 \\
\end{matrix} \left(
\begin{matrix}
1\phantom{1} 1\phantom{1}
0\phantom{1} 0\phantom{1} 0\phantom{1} 0\phantom{1}\\
1\phantom{1} 1 0\phantom{1}
0\phantom{1} 0\phantom{1} 0\phantom{1}\\
0\phantom{1} 1\phantom{1} 1\phantom{1} 0\phantom{1}
0\phantom{1} 0\phantom{1}\\
0\phantom{1} 1\phantom{1} 1\phantom{1} 0\phantom{1} 0\phantom{1}
0\phantom{1}\\
1\phantom{1} 0\phantom{1} 0\phantom{1} 1\phantom{1} 1\phantom{1} 1\phantom{1}
\end{matrix}
\right)\!,
\end{aligned}$$
которая является матрицей семейства $$\varphi
=(S_{1} \dts S_{5})$$.
Ясно, что и ее
Доказательство. Очевидно, что
Если $$i\le r$$, то определим $$S_{i}$$ как множество целых
чисел $$j\le
n-s$$, таких, что $$a_{ij} =1$$. Нетрудно проверить, что
объединение любых $$k$$ множеств $$S_{i}$$ содержит по меньшей
мере $$k$$ целых чисел;
поэтому семейство $$\varphi =(S_{1} \dts S_{r})$$ имеет трансверсаль.
Отсюда следует, что подматрица $$M$$ из $$A$$ содержит
множество из $$r$$ единиц, никакие две из которых не принадлежат одной
и той же строке или
одному и тому же столбцу. Аналогично, матрица $$N$$ содержит множество
из $$s$$ единиц, обладающих тем же свойством. Таким образом,
матрица $$A$$ содержит множество из $$r+s$$ единиц, никакие
две из которых не принадлежат одной и той же строке или одному и тому же столбцу. Тем самым
показано, что $$\mu$$ не превосходит
Мы только что доказали теорему Кенига-Эгервари с помощью теоремы
Холла, а доказательство теоремы Холла с помощью теоремы
Кенига-Эгервари и того проще. Следовательно, эти две теоремы в некотором
смысле эквивалентны. В лекции 17 мы докажем теорему о
Сформулируем необходимое и достаточное условие для того, чтобы два семейства $$\varphi$$ и $$\tau$$ имели общую трансверсаль; заметим, что эта теорема сводится к теореме Холла, если положить $$T_{j}-E$$ для $$1\le j\le m$$.
Теорема Пусть $$E$$ — непустое конечное множество, а $$\varphi =(S_{1} \dts$$ $$S_{m})$$ и $$\tau =(T_{1} \dts T_{m})$$ — два семейства его непустых подмножеств. Тогда $$\varphi$$ и $$\tau$$ имеют общую трансверсаль в том и только в том случае, если для всех подмножеств $$A$$ и $$B$$ множества $$\{1\dts m\}$$
$$\left|(\bigcup _{i\in A}S_{i} )\bigcap (\bigcup _{j\in B}T_{j} \right|\ge \left|A\right|+\left|B\right|-m.$$Набросок доказательства. Рассмотрим семейство $$U=\{ U_{i}\}$$ подмножеств множества $$E\bigcup \{1\dts m\} $$ (считаем, что $$E$$ и $$\{1\dts m\}$$ не пересекаются), где множеством индексов также является $$E\bigcup \{ 1 \dts m\}$$ и где $$U_{i} =S_{i}$$, если $$i\in \{1\dts m\}$$, и $$U_{i} =\{ i\} \bigcup \{ i\} \bigcup \{ j:i\in T_{j} \}$$, если $$i\in E$$.Нетрудно проверить, что $$\varphi $$ и $$\tau $$ имеют общую трансверсаль тогда и только тогда, если семейство $$U$$ имеет трансверсаль. Применяя затем теорему Холла к семейству $$U$$, получим нужный результат.
Условия, при которых существует общая трансверсаль для трех семейств
непустых подмножеств некоторого множества, пока что не известны, и задача
нахождения таких условий кажется очень трудной. Многие попытки решения
этой задачи используют теорию матроидов; и действительно, некоторые
задачи теории
Приводятся определения трансверсали. Используя эти понятия, дается еще
одно доказательство теоремы Холла. Описывается несколько приложений в
лексике
Если $$E$$ — непустое конечное множество и $$\varphi
=(S_{1}\dts
S_{m})$$ — семейство (не обязательно различных) непустых его
подмножеств,
Общие трансверсали. Если $$E$$ — непустое конечное
множество, а $$\varphi =(S_{1} \dts S_{m})$$ и $$\tau =(T_{1}\dts
T_{m})$$ — два
семейства его непустых подмножеств, то интересно знать, когда существует
общая трансверсаль для $$\varphi$$ и $$\tau$$, то есть
множество, состоящее из $$m$$ различных элементов множества $$E$$ и являющееся
Рассмотрим пример. Предположим, что $$E=\{ 1,2,3,4,5,6\}$$,
а $$S_{1}
=S_{2} =\{ 1,2\}$$, $$S_{3} =S_{4} =\{ 2,3\}$$, $$S_{5} =\{
1,4,5,6\}$$.
Подсемейство $$\varphi' =(S_{1},S_{2},S_{3},S_{5})$$ имеет
трансверсаль, например $$\{ 1,2,3,4\}$$. Трансверсаль произвольного подсемейства
семейства $$\varphi$$ будем называть
Естественно спросить: при каких условиях данное семейство подмножеств
некоторого множества имеет трансверсаль? Легко увидеть связь между
этой задачей и
Теорема Пусть $$E$$ — непустое конечное множество и $$\varphi =(S_{1} \dts S_{m})$$ — семейство непустых его подмножеств; тогда $$\varphi$$ имеет трансверсаль в том и только в том случае, если для любых $$k$$ подмножеств $$S_{i}$$ их объединение содержит, по меньшей мере, $$k$$ элементов $$(1\le k\le m)$$.
Доказательство Необходимость этого условия очевидна. Для доказательства достаточности установим, что если одно из подмножеств (скажем, $$S_{1}$$ ) содержит более одного элемента, то можно удалить один элемент из $$S_{1}$$, не нарушив условия теоремы. Повторением этой процедуры мы добьемся сведения задачи к тому случаю, когда каждое подмножество содержит только один элемент. Тогда утверждение станет очевидным.
Осталось обосновать законность этой "процедуры сведения". Предположим, что $$S_{1}$$ содержит элементы $$x$$ и $$y$$, удаление каждого из которых нарушает условие теоремы. Тогда существуют подмножества $$A$$ и $$B$$ множества $$\{ 2,3\dts m\}$$, обладающие тем свойством, что$$\begin{align*} \left|\bigcup _{j\in A}S_{j} \bigcup (S_{1} -\{ x\} ) \right| \le \left|A\right|\\ \left|\bigcup_{j\in B}S_{j} \bigcup (S_{1} -\{ y\} )\right| \le \left|B\right|. \end{align*}$$
Но эти два неравенства приводят к противоречию, поскольку
$$\begin{aligned} \left|A\right|+\left|B\right|+1 =\left|A\bigcup B \right|+\left|A\bigcap B \right|+1\le\\ \le \left|\bigcup _{jA\bigcup B }S_{j} \bigcup S_{1} \right|+\left|\bigcup _{j\in A\bigcap B }S_{j} \right|\le \quad \t{(по условию)}\\ \le \left|\bigcup _{j\in A}S_{j} \bigcup (S_{1} -\{ x\} ) \right|+\left|\bigcup _{j\in B}S_{j} \bigcup S_{1} -\{ y\} ) \right|\le\\ \qquad \qquad \qquad\qquad\qquad \qquad\le \quad \t{(так как $\left|S_{1} \right|\ge 2)$}\\ \le \left|A\right|+\left|B\right| \quad \t{(по предположению)}. \end{aligned}$$Прелесть этого доказательства в том, что оно проводится, по существу, лишь в один шаг, в отличие от доказательства Халмоша-Вогена, которое предполагает исследование двух отдельных случаев. (Однако доказательство Радо труднее перевести на весьма наглядный матримониальный язык!).
Следствие В тех же обозначениях, что и выше, $$\varphi$$ имеет частичную трансверсаль мощности $$t$$ тогда и только тогда, если для любых $$k$$ подмножеств $$S_{i}$$ их объединение содержит, по меньшей мере, $$k+t-m$$ элементов.
Доказательство
Требуемый результат можно получить, применив теорему Холла в
лексике
Следствие Если $$E$$ и $$\varphi$$ такие же, как и прежде, а $$X$$ — любое подмножество из $$E$$, то $$X$$ содержит частичную трансверсаль мощности $$t$$ для $$\varphi$$ тогда и только тогда, если для каждого подмножества $$A$$ множества $$\{1\dts m\}$$$$\left|(\bigcup _{j\in A}S_{j} )\bigcap X \right|\ge \left|A\right|+t-m.$$
Доказательство Достаточно применить предыдущее следствие к семейству $$\varphi_{x} =(S_{1} \bigcap X\dts S_{m} \bigcup X)$$.
Используются понятия
Теорема
Пусть $$M$$ латинский $$m\times n$$ -прямоугольник,
причем, $$m < n$$ ; тогда $$M$$ можно расширить до
Доказательство Докажем, что $$M$$ можно расширить до латинского $$(m+1)\times n$$ -прямоугольника; повторяя эту процедуру, мы придем к латинскому квадрату.
Пусть $$E=\{1,2\dts n\}$$ и $$\varphi =(S_{1}\dts S_{n})$$, где через $$S_{i}$$ обозначено множество, состоящее из тех элементов множества $$E$$, которые не встречаются в $$i$$ -м столбце матрицы $$M$$. Если мы сможем доказать, что $$\varphi$$ имеет трансверсаль, то тем самым мы докажем теорему, поскольку элементы этой трансверсали и образуют дополнительную строку. По теореме Холла достаточно доказать, что объединение любых $$k$$ множеств $$S_{i}$$ содержит по меньшей мере $$k$$ различных элементов. А это очевидно, ибо любое такое объединение содержит $$(n-m)\times k$$ элементов (включая повторения), значит, по крайней мере, один из них повторялся бы более чем $$n-m$$ раз, что невозможно.
Определение
Определение
Теорема (Кенига-Эгервари, 1931)
Замечание
В качестве иллюстрации этой теоремы рассмотрим
матрицу$$\begin{aligned} \,\,\,\,\,\begin{matrix} e_{1}\,\,
e_{2}\,\, e_{3}\,\, e_{4}\,\, e_{5}\,\, e_{6}
\end{matrix}\\
\begin{matrix}
S_1 \\
S_2 \\
S_3 \\
S_4 \\
S_5 \\
\end{matrix} \left(
\begin{matrix}
1\phantom{1} 1\phantom{1}
0\phantom{1} 0\phantom{1} 0\phantom{1} 0\phantom{1}\\
1\phantom{1} 1 0\phantom{1}
0\phantom{1} 0\phantom{1} 0\phantom{1}\\
0\phantom{1} 1\phantom{1} 1\phantom{1} 0\phantom{1}
0\phantom{1} 0\phantom{1}\\
0\phantom{1} 1\phantom{1} 1\phantom{1} 0\phantom{1} 0\phantom{1}
0\phantom{1}\\
1\phantom{1} 0\phantom{1} 0\phantom{1} 1\phantom{1} 1\phantom{1} 1\phantom{1}
\end{matrix}
\right)\!,
\end{aligned}$$
которая является матрицей семейства $$\varphi
=(S_{1} \dts S_{5})$$.
Ясно, что и ее
Доказательство. Очевидно, что
Если $$i\le r$$, то определим $$S_{i}$$ как множество целых
чисел $$j\le
n-s$$, таких, что $$a_{ij} =1$$. Нетрудно проверить, что
объединение любых $$k$$ множеств $$S_{i}$$ содержит по меньшей
мере $$k$$ целых чисел;
поэтому семейство $$\varphi =(S_{1} \dts S_{r})$$ имеет трансверсаль.
Отсюда следует, что подматрица $$M$$ из $$A$$ содержит
множество из $$r$$ единиц, никакие две из которых не принадлежат одной
и той же строке или
одному и тому же столбцу. Аналогично, матрица $$N$$ содержит множество
из $$s$$ единиц, обладающих тем же свойством. Таким образом,
матрица $$A$$ содержит множество из $$r+s$$ единиц, никакие
две из которых не принадлежат одной и той же строке или одному и тому же столбцу. Тем самым
показано, что $$\mu$$ не превосходит
Мы только что доказали теорему Кенига-Эгервари с помощью теоремы
Холла, а доказательство теоремы Холла с помощью теоремы
Кенига-Эгервари и того проще. Следовательно, эти две теоремы в некотором
смысле эквивалентны. В лекции 17 мы докажем теорему о
Сформулируем необходимое и достаточное условие для того, чтобы два семейства $$\varphi$$ и $$\tau$$ имели общую трансверсаль; заметим, что эта теорема сводится к теореме Холла, если положить $$T_{j}-E$$ для $$1\le j\le m$$.
Теорема Пусть $$E$$ — непустое конечное множество, а $$\varphi =(S_{1} \dts$$ $$S_{m})$$ и $$\tau =(T_{1} \dts T_{m})$$ — два семейства его непустых подмножеств. Тогда $$\varphi$$ и $$\tau$$ имеют общую трансверсаль в том и только в том случае, если для всех подмножеств $$A$$ и $$B$$ множества $$\{1\dts m\}$$
$$\left|(\bigcup _{i\in A}S_{i} )\bigcap (\bigcup _{j\in B}T_{j} \right|\ge \left|A\right|+\left|B\right|-m.$$Набросок доказательства. Рассмотрим семейство $$U=\{ U_{i}\}$$ подмножеств множества $$E\bigcup \{1\dts m\} $$ (считаем, что $$E$$ и $$\{1\dts m\}$$ не пересекаются), где множеством индексов также является $$E\bigcup \{ 1 \dts m\}$$ и где $$U_{i} =S_{i}$$, если $$i\in \{1\dts m\}$$, и $$U_{i} =\{ i\} \bigcup \{ i\} \bigcup \{ j:i\in T_{j} \}$$, если $$i\in E$$.Нетрудно проверить, что $$\varphi $$ и $$\tau $$ имеют общую трансверсаль тогда и только тогда, если семейство $$U$$ имеет трансверсаль. Применяя затем теорему Холла к семейству $$U$$, получим нужный результат.
Условия, при которых существует общая трансверсаль для трех семейств
непустых подмножеств некоторого множества, пока что не известны, и задача
нахождения таких условий кажется очень трудной. Многие попытки решения
этой задачи используют теорию матроидов; и действительно, некоторые
задачи теории
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.