Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

об индукции

Эта запись может быть интересна людям, любящим математику.

Есть один довольно частый способ использования доказательства по индукции, в котором индукция используется, чтобы установить какие-то дополнительные свойства общего случая, облегчающие доказательство, а потом о ней забывают и продолжают доказывать общий случай напрямую. Мы хотим доказать какое-то утверждение P(n) для всех n, и глядя на общий случай, мы видим, что если выполняется некое X, тогда P(n) можно легко свести к P(k) для k меньших, чем n. Ага, говорим мы, в этом случае - "по индукции", поэтому продолжим теперь обсуждать общий случай, предполагая, что X неверно, и доказываем его, уже не рассматривая другие значения n, напрямую.

Формально все доказательство выходит обернутым в индукцию, но по сути дела индукция помогла нам, "бесплатно" подарив информацию "не-X", а потом ушла в сторону. Мавр сделал свое дело, мавр может уходить. Этакое доказательство по полу-индукции.

Вчера попался хороший пример, опять из веблога по теории сложности, на который я несколько раз в последнее время ссылался. Рассмотрим связный граф без циклов, т.е. дерево; у него есть n вершин и n-1 ребер. Если мы добавим еще одно ребро, то обязательно получится цикл, но, вообще говоря, он может быть очень длинный. Однако если мы станем еще и еще добавлять ребра, то рано или поздно в графе появятся довольно короткие циклы - мы не сможем удерживать связанные циклами вершины далеко друг от друга. Сколько ребер надо добавить, чтобы получить очень короткие циклы, например, логарифмической длины от размера графа?

Утверждение: если в графе из n вершин есть 2n или более ребер, в нем есть цикл длиной 2log(n) или меньше.



Предположим, что в графе есть вершина с степенью (кол-вом ребер) 2 или меньше. Тогда, удаляя эту вершину и все связанные с ней ребра, мы сохраняем условие - в новом графе кол-во ребер тоже будет в два раза или более превышать кол-во вершин. Значит, "по индукции", в нем есть короткий цикл, который тем более будет достаточно коротким для исходного графа.

Поэтому мы можем предположить, что в графе у каждой вершины степень 3 или больше. Все, на этом индукция выполнила свою роль и уходит в сторону.

Пусть X - длина самого короткого цикла. Зафиксируем какую-то вершину v и пометим ее числом 0. Все вершины, с которыми соединена v, пометим 1. Все вершины, к которым можно перейти из тех, что помечены 1 (и у которых еще нет числа), пометим 2. И продолжим так обходить граф, помечая на k-м шагу числом k все вершины, к которым можно перейти из k-1-х, и у которых нет еще числа. Утверждение: первые X/2 шагов число вершин, помеченных на каждом шаге, как минимум удваивается. Почему? Потому что у любой вершины k-1-го шага есть степень не меньше трех, и все ее ребра, кроме того, по которому мы пришли к ней на предыдущем шаге, ведут к новым, еще не помеченным (и не соединенным ни с кем других из k-1-х) вершинам. Иначе мы бы получили вершину, к которой есть два разных пути длиной менее X/2 из v, и соединив их вместе, получили бы цикл короче X, что невозможно.

Итак, в течение первых X/2 шагов кол-во вершин на каждом шаге как минимум удваивается, значит общее число найденных вершин после них не меньше равно примерно 2^(X/2) (я опускаю некоторые подробности - нетрудно доказать, что оно точно не меньше 2^(X/2), если аккуратно просуммировать, и еще учесть, что из самой первой вершины v выходят три "новых" ребра, а не два). Но это число не может быть больше общего числа вершин n. Отсюда следует, что X/2 <= log(n), и длина самого короткого цикла X меньше или равна 2log(n), что и требовалось доказать.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 5 comments