об индукции
Nov. 20th, 2008 12:40 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaЭта запись может быть интересна людям, любящим математику.
Есть один довольно частый способ использования доказательства по индукции, в котором индукция используется, чтобы установить какие-то дополнительные свойства общего случая, облегчающие доказательство, а потом о ней забывают и продолжают доказывать общий случай напрямую. Мы хотим доказать какое-то утверждение 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), что и требовалось доказать.
Есть один довольно частый способ использования доказательства по индукции, в котором индукция используется, чтобы установить какие-то дополнительные свойства общего случая, облегчающие доказательство, а потом о ней забывают и продолжают доказывать общий случай напрямую. Мы хотим доказать какое-то утверждение 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), что и требовалось доказать.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2008-11-19 11:33 pm (UTC)no subject
Date: 2008-11-20 06:11 am (UTC)no subject
Date: 2008-11-20 09:59 am (UTC)no subject
Date: 2008-11-20 02:48 pm (UTC)Вторая половина подсказывает, что надо бы ту же оценку доказывать не для 2n, а для 3n/2 ребер (как в регулярном графе степени 3). Но тут первая половина не работает.
При 3n/2 первая половина дает, что в минимальном контрпримере нет двух соседних вершин степени 2, но этого не хватает для того, чтобы простое копирование второй половины дало нужную оценку.
Короче, надо думать дальше.
no subject
Date: 2008-11-20 02:53 pm (UTC)