Простой путь, Гамильтонов путь, Гамильтонов цикл

Пример. Пусть Вася выберет какую-то карточку и задаст вопросов, в каждом из которых он спросит про и одну из карточек, отличных от Общее количество чисел, не соседних с числом, написанным на не превосходит если на написано или и если на написаны числа от до Тогда либо в одном из ответов будет дан положительный ответ, и Вася нашёл нужную пару соседних чисел, либо все эти карточки содержат числа, не соседние с числом на Следовательно, оставшаяся карточка содержит число, соседнее с числом на Таким образом, Васе достаточно вопросов.

Оценка. Докажем, что, если Вася задаст всего любых вопросов, он может не найти ни одной пары карточек с соседними числами. Предположим противное, что задав некоторые вопросов он смог точно указать на пару карточек с соседними числами. Переведём задачу на язык теории графов. Карточки будем считать вершинами графа а заданные Васей вопросы – рёбрами (синими рёбрами), соединяющими соответствующие пары карточек. К этим рёбрам нужно добавить ещё одно, соответствующее той паре карточек, на которых написана пара соседних, по версии Васи, чисел. Теперь нужно доказать, что вершины могут быть занумерованы в таком порядке, что ни одно ребро не соединяет две вершины с соседними номерами. То есть, нужно дорисовать в графе путь из рёбер, проходящий последовательно по всем вершинам, и не содержащих ни одного из «Васиного» синего ребра. Это будет означать, что Васина догадка не верна. Назовём такой путь красным и будем строить его методом математической индукции по числу вершин графа

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

1) Пусть в есть «крайняя» вершина из которой выходит ровно одно ребро В графе полученном из удалением вершины и ребра число вершин равно а рёбер – не больше выполнено предположение индукции, поэтому в можно построить красный путь длины с началом в вершине и концом в вершине Тогда ребро не соединяет вершину с одной из или проведя красное ребро из в эту вершину, получим красный путь длины в

2) Пусть в нет вершин, из которых выходит ровно одно ребро. В таком случае все синие рёбра инцидентны в сумме вершинам степени не меньше каждая, следовательно, среди них не больше различных. Следовательно, в не меньше двух вершин из которых не выходит ни одного синего ребра. Удалим из вершины и два ребра, выходящие из некоторой четвёртой вершины (но не саму вершину). Полученный граф снова удовлетворяет предположению индукции и в нём можно построить красный путь длины с началом в вершине и концом в вершине Если он не проходит через или проходит, но не проходит через удалённые рёбра, соединим с и с и получим красный путь в длины 99. В оставшихся случаях, обозначим за и вторые концы удалённых рёбер. Если красный путь в проходит через заменим этот фрагмент на Если он проходит только через одно удалённое ребро, скажем, через заменим его на В обоих случаях получится красный путь в

База индукции - случаи графов с 3 и 4 вершинами - очевидна.