Утверждение состоит в том,
что в множестве M нет рёбер,
то есть множество M является независимым множеством вершин в нашем графе G.
Ну давайте доказывать это утверждение.
Предположим… Сейчас
придётся рисовать новую картину, я уже к той старой картине не пойду.
Ну что поделать?
Придётся нарисовать.
Значит, предположим, что какие-то вершины
x(i + 1) и x(j + 1),
принадлежащие M, образуют ребро в графе G.
Образуют ребро.
Вот есть две вершины из множества M, которые всё-таки образуют ребро.
Предположим, что такие есть и докажем, что будет некое противоречие.
Тогда, конечно, утверждение о том, что в M отсутствую рёбра, будет доказано.
Ну давайте в очередной раз нарисуем наш замечательный цикл.
Вот в нём есть x(i + 1).
Э, сначала я xi нарисую, виноват.
Сначала я нарисую xi, потом я, собственно, нарисую x(i + 1),
то есть ту самую вершину, которая вместе с неким x(j + 1) образуют ребро,
потом пройдусь вот так, дойду до x с индексом j, нарисую рёбрышко,
идущее в x(j + 1), ну а дальше уже двинусь до конца цикла.
Естественно, без ограничений общности я могу считать,
что i строго меньше чем j, это понятно.
Вот такая вот картина.
Ну и, конечно, есть W.
Тут уж деваться некуда, есть W.
Смотрите, что мы знаем?
Во-первых, мы предполагаем, что вот эта x(i +
1) соединена с x(j + 1), во-вторых, мы знаем,
что у вершины xi есть какая-то соседка внутри множества W потому,
что xi по определению принадлежит множеству Nw (G).
То же самое мы знаем про xj.
У xj тоже есть какая-то соседка в множестве W,
и между этими соседками есть какая-то цепь,
которую можно по-прежнему обозначать p, и которая вполне себе может оказаться
пустой, то есть эти вершины вполне могут совпасть.
Это нам опять никак не повредит для того, чтобы получить противоречие.
Ну, я думаю, вы догадываетесь, как мы теперь хотим получить противоречие,
товарищи.
Как? Наверное, мы хотим найти цикл,
который длиннее исходного, то есть рассуждение совершенно стандартное,
сейчас мы будем искать цикл, который длиннее исходного.
Ну я думаю, понятно, как его искать.
Давайте сейчас попробуем пробежаться.
Вот стартовали отсюда, прошли по этой цепочке, может быть, сразу сюда попали,
это уж как посчастливится, да?
Вот двинулись сюда, сейчас мы куда-нибудь туда пойдём.
Так, как нам дальше действовать?
Как нам дальше действовать, чтобы нам вернуться, да?
Мы, наверное, отсюда пойдём сюда,
потом пойдём вот так, вот так, вот так, сейчас… Или это плохо?
Какой самый длинный цикл-то?
Где длинный цикл появился?
Надо ещё сообразить, от какого ребра-то избавиться.
От какого ребра избавиться, надо сообразить.
Ну я могу, товарищи, сказать так — ну посмотрите просто на этот цикл и увидите,
что он длиннее получается, но всё-таки не худо бы нарисовать какой-нибудь.
Путаюсь, какой здесь подлиннее-то будет очевидно?
Так.
От какого-то ребра надо избавиться,
а по всем остальным пройти.
Так, вот так пойдём,
вот так пойдём, вот так пойдём.
А всё понятно!
Я нашёл!
Ну вы уж извините, что я в этом месте притормаживаю, ну пойди на таком рисунке,
я ведь художник-то тот ещё, пойди на таком рисунке разыщи нужный цикл.
Давайте вот отсюда стартуем.
Я думаю, что слушатели уже сами всё нашли.
Пройдём вот сюда, потом перейдём вот так, двинемся обратно,
пройдём по всему исходному циклу досюда и вернёмся.
То есть мы из исходного цикла выкинули вот это ребро и вот это ребро.
Видите, мы вот так пошли?
Шлёп! Шлёп!
Шлёп! Шлёп!
Шлёп! Шлёп!
Шлёп и вернулись.
Простой цикл получился, да, но мы действительно вот этим ребром
пренебрегли и вот этим ребром тоже пренебрегли в исходном цикле.
Ну судьба у них такая, они вылетели,
но зато появилось вот это новое ребро, существование которого мы, собственно,
и предположили, появилось вот это новое ребро и вот это новое ребро.
Итого три новых ребра взамен двух потерянных старых.
Ну и, возможно, тут ещё что-то, но даже если ничего,
всё равно три новых ребра — это больше, чем два потерянных старых.
Мы нашли более длинный цикл и это противоречие.
Следовательно есть более длинный цикл,
что приводит нас к противоречию.
Таким образом, мы действительно доказали, что в множестве M нет рёбер,
то есть множество M является, в наших предположениях, независимым.
Но это такой очередной шах, и вот сейчас будет нанесён, собственно, мат.
Поставлен мат в этой задаче, мы докажем окончательно теорему.
Смотрите, раз в множестве M нет рёбер, давайте сделаем ещё
одну дополнительную штучку, давайте добавим,
добавим к множеству M любую
вершину из W.
Мы с вами знаем, что M,
пересечённая с Nw (G), пусто,
то есть в множестве M нету соседок вершин из W.
Если мы добавим к M любую вершину из W,
то всё равно получится независимое множество.
Снова получится независимое множество вершин.
Независимое множество вершин.
Его размер, то есть количество вершин в нём,
то есть количество вершин в нём не меньше, как мы показали,
нежели æ(G), поскольку размер M не меньше, чем æ(G),
+ 1, где вот это + 1 за счёт того, что мы добавили любую вершину из W.
То есть получается,
что α (G) — число независимости
нашего графа, оно, конечно, больше либо равняется
мощности вот этого независимого множества, давайте я даже писать это не буду.
Ну число независимости, оно, конечно, не меньше,
чем мощность конкретного независимого множества.
Ну, значит, она больше либо равняется æ(G) + 1.
Больше либо равняется æ(G) + 1.
Но мы-то знаем, по условию теоремы,
что α (G) не превосходит æ(G).
Это по условию теоремы, так теорема формулировалась.
И вот, наконец, катарсис, то есть мы понимаем, зачем же было это условие.
А затем, чтоб в этом месте сказать: «Мы опять ошиблись,
мы опять пришли к противоречию».
И это уже мат, потому что это противоречие с изначальным
предположением о том, что длина нашего самого длинного цикла, вот это число M,
меньше, чем количество вершин в нашем графе, то есть чем число n.
Следовательно, противоречие с
предположением о том,
о том,
что цикл x₁, ...,