100 городов и два мегаполиса

[jrock]

Здравствуйте, использую этот форум что бы проверить следующее доказательство. Вообще эта задача - мое ДЗ, но я слышал что ее школьники на олимпиаде решают.

Задача.
В стране 100 городов, некоторые пары городов соединены дорогами. Для любых четырех городов существует хотя бы две дороги между ними. Известно, что не существует маршрута, проходящего по каждому городу ровно один раз.
Докажите, что можно выбрать два города таким образом, чтобы любой из оставшихся городов был соединен дорогой хотя бы с одним из двух выбранных городов.

Доказательство.
Города - это вершины. Ребра - это дороги.

Выясним, может ли быть граф несвязен. Если компонент больше, чем 3, то тогда выберем 2 вершины из одной, одну из другой и еще одну из третей. Получится, что они могут быть соединены максимум одним ребром. Условие задачи нарушается.
Пусть будет две компоненты, каждая состоит больше, чем из одной вершины. Тогда они должны быть все полными. Если это не так, то возьмем две несмежные вершинки из первой, любые две из другой. В таком наборе может быть соединены только два города. Противоречие. Тоже самое для другой компоненты. Значит, обе полные. Ну тогда берем любую одну вершину из первой и любую одну из второй компоненты. Условие задачи выполнено.
Пусть теперь одна компонента - это просто одна вершина степени 0. Тогда получается, что другая компонента будет из 99 вершин. Если у любой вершины убрать больше, чем два ребра, то сразу нарушение условия: возьмем вершину степени 0, вершину без двух ребер и вершины, к которым ребер от нее нет (1 ребро будет). Значит, у каждой вершины можно убрать только одно ребро. Но если так сделать, то у каждой вершины будет нечетная степень (до этого у каждой было 98). А нечетных степеней может быть только четное число, поэтому либо убираем где-то два ребра и нарушается ограничение о 4-х городах, либо оставляем все ребра и тогда полная вершина.

Города, от которых есть дороги ко всем остальным городам назовем q и p.

Далее доказываем по индукции, что для любого связного графа с ограничением о 4-х городах и г.путем условие будет выполняться.
База. из 4-х вершин очевидна: возьмем любое остовное дерево и в нем выберем вершину, отличную от листа, а вторую - лист.

Переход. Пусть есть граф из $n+1 \ge 5$ вершин. Тогда для всех графов меньше размера, для которых выполнено условие задачи, все доказано.

Необходимо доказать, что можно пользоваться индукционным предположением.
Назовем вершину, которая будет выкинута как $e$.
Если есть граф из $n+1$ вершины, где для любых 4-х городов должны быть две дороги, то и для $n$ городов это тоже должно выполняться: будем рассматривать все города без одного. Главное, что бы граф не потерял связность, а это всегда можно делать, удаляя только висячую вершину, если таковая имеется.

Если получилось так, что в $G$ образовался г.путь, то $e$ не могла быть связна с одним из его концов (иначе г.путь в графе $G+e$). Значит, $e$ для удаления - это висячая вершина в остовном дереве. Если же получилось так, что так все еще нельзя: $e$ была соединена через одну вершину с концом, который удалили, то уберем другую. Одновременно не могло получиться так, что вершина $e$ соединена через одну вершину с обоими из концов: это был бы граф на 3-х вершинах (а если есть второй путь до конца, то в $G+e$ есть г.путь), а доказывается для графов, более чем для 4-х вершин.
Очевидно, что от удаления висячей вершины в остовном дереве, связность не теряется.

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

Теперь есть $e$, соединенная с графом $G$ из $n$ вершин, в этой стране из $n$ городов есть свои p и q. Ясно, что если есть ребро от $e$ до p или q, то доказывать ничего не нужно. Тогда пусть нет дорог от $e$ до p и до q.
Множество, в которые есть дороги из p назовем A, а множество, в которые есть дороги из q, назовем B.
Пусть нет дороги из p в q. Тогда пусть город $e$ не соединен дорогой с городом $u \in A - B$. Но тогда $u$ должен иметь дороги и в p и в q, иначе возьмем вершины $u$, $e$, p и q.
Тогда получается, что город $e$ не может быть не соединен дорогами с городами из $(A \cup B) - (A \cap B)$
Но тогда можно сделать город $e$ новым p, а q оставить прежней (или наоборот).

Значит, остался один случай: p и q соединены дорогой.
Названия множеств оставим теми же.
По предположению индукции: граф $G$ не имеет гамильтонова пути.
Еще раз, если есть дороги от $e$ до всего множества $A\B$ или до всего $B\A$, то уже все доказано.

Теперь есть пара вершин $u \in A$ и $v \in B$, от которых нет ребер к $e$.
Если есть только $v$, то $e$ кроет все, что не кроет q, $u$ - то p. Тогда $e$ - новый большой город.
Если $(A \cup B) - (A \cap B)$ пусто, то $e$ связна с $A \cap B$ и все доказано.

Если между $u$ и $v$ нет ребра, то берем $e$, $u$, $v$ и p - будет одно ребро. Значит оно есть. Теперь получается, что $A\B$ - полный подграф, впрочем, как и $B\A$ (иначе берем $u$ или $v$, p или q по необходимости и несоединенные вершины).
Теперь расмотрим подграф на вершинах из $A \cap B$. Попробуем покрыть все множество веришин простыми путями.
Пусть получилось покрытие только из $\ge$ 4-х простых путей. Возьмем по крайней вершине от каждого: если есть ребро, то можно было соединить две крайние вершины и получить более длинный путь. Получилась антиклика на четырех вершинах. Противоречие.
Теперь известно, что множество $A \cap B$ покрывается не более чем 3-мя простыми путями. Будем рассматривать каждый простой как одну вершину: если можно прийти в любой из концов, то можно и пройти по каждой вершине внутри него один раз - он же простой, а так можно сделать, т.к. в каждую вершину из $A \cap B$ можно попасть и через p и через q. Теперь есть только не более 3-х вершин.
Путь может состоять из одной вершины или более. Если более, то отождествляем весь путь его одной крайней вершиной.
Назовем левое множество - $A\B$ , правое - $B\A$, среднее - $A \cap B$ (пути сжаты в вершины).
Про вершину $e$ можно забыть: если получилось, что $G$ имеет г.путь, то уже будет противоречие с индукционным предположением.
Случай 1. Среднее множество пусто. Тогда просто (по вершинам просто) обходим левое множество, ничаная с любой вершины, отличной от $u$, заканчиваем в $u$, потом в p , потом сразу q, потом в $v$ и просто обходим правое множество. Получился г.путь.
Случай 2. В среднем множестве одна вершина. Все тоже самое, но из p в q проходим через эту вершину.
Случай 3. Теперь есть в среднем множестве вершины $a$ и $b$, напомню, что они несмежны. Теперь одна из них, пусть это $a$ должна быть соединена с $u$ или $v$. Иначе возьмем $a$, $b$, $u$, $v$ и будет одно ребро между $u$ и $v$. Пусть теперь есть ребро $u$ - $a$. Обойдем правое множество, далее из $v$ в q, потом через $b$ в p, потом в $a$ и потом в $u$ и там обойдем левое множество. Снова г.путь.
Случай 4. Есть три вершины в среднем множестве. Теперь есть три пары несмежных вершин.
Нужны два ребра в $u$ из этих трех вершин- иначе берем эти три и $u$. Тоже самое для $v$.
Значит, есть ребра из $u$ в $a$ и из $v$ в $b$, где еще осталась $c$ и $a \ne b$.
Теперь идем по маршруту $uapcqv$ где вначале обходим, как обычное, левое множество, а в конце правое.
Снова г.путь.

Перефразируем доказанное:
Дан граф, удовлетворяющий условию задачи. Если выбрать в нем вершину для удаления определенным способом, который всегда существует, то будет выполняться либо что выбранная вершина будет иметь дорогу к большим городам, либо будет являться сама большим городом, покрывая вместе с другим все вершины.
Во всех других случаях были доказаны противоречия.

Значит, всегда есть два необходимых города.

[jrock]

Еще попытка

Пусть в графе $G$ две вершины, которые вместе имеют дороги не во все города и они соединены. Ясно, что в стране есть хотя бы два соединенных города. Иначе в графе вообще нет ни одной дороги.

Назовем эти два города $p$ и $q$, город, в который от этих двух городов нет дороги - $e$. Смежные с $p$ - $A$, а соседей $q$ - B.
Теперь от $e$ должны быть дороги во все города, с которыми несмежны $p$ и $q$, иначе берем $e$, $p$, $q$ и эту вершину, будет одно ребро.

Если есть дороги от $e$ до всего множества $A -B$ или до всего $B - A$, то уже все доказано: $e$ будет новым городом, который вместе с $p$ или $q$ покроет все города.

Теперь есть пара вершин $u \in (A - B)$ и $v \in (B - A)$, от которых нет ребер к $e$.
Если есть только $v$, то $e$ кроет все, что не кроет q, $u$ - то p. Тогда $e$ - новый большой город.
Если $(A \cup B) - (A \cap B)$ пусто, то $e$ связна с $A \cap B$ и все доказано.

Если между $u$ и $v$ нет ребра, то берем $e$, $u$, $v$ и p - будет одно ребро. Значит оно есть. Теперь получается, что $A\B$ - полный подграф, впрочем, как и $B\A$ (иначе берем $u$ или $v$, p или q по необходимости и несоединенные вершины).
Теперь расмотрим подграф на вершинах из $A \cap B$. Попробуем покрыть все множество веришин простыми путями.
Пусть получилось покрытие только из $\ge$ 4-х простых путей. Возьмем по крайней вершине от каждого: если есть ребро, то можно было соединить две крайние вершины и получить более длинный путь. Получилась антиклика на четырех вершинах. Противоречие.
Теперь известно, что множество $A \cap B$ покрывается не более чем 3-мя простыми путями. Будем рассматривать каждый простой как одну вершину: если можно прийти в любой из концов, то можно и пройти по каждой вершине внутри него один раз - он же простой, а так можно сделать, т.к. в каждую вершину из $A \cap B$ можно попасть и через p и через q. Теперь есть только не более 3-х вершин.
Путь может состоять из одной вершины или более. Если более, то отождествляем весь путь его одной крайней вершиной.
Назовем левое множество - $A\B$ , правое - $B\A$, среднее - $A \cap B$ (пути сжаты в вершины).
Про вершину $e$ можно забыть: если получилось, что $G$ имеет г.путь, то уже будет противоречие с индукционным предположением.
Случай 1. Среднее множество пусто. Тогда просто (по вершинам просто) обходим левое множество, ничаная с любой вершины, отличной от $u$, заканчиваем в $u$, потом в p , потом сразу q, потом в $v$ и просто обходим правое множество. Получился г.путь.
Случай 2. В среднем множестве одна вершина. Все тоже самое, но из p в q проходим через эту вершину.
Случай 3. Теперь есть в среднем множестве вершины $a$ и $b$, напомню, что они несмежны. Теперь одна из них, пусть это $a$ должна быть соединена с $u$ или $v$. Иначе возьмем $a$, $b$, $u$, $v$ и будет одно ребро между $u$ и $v$. Пусть теперь есть ребро $u$ - $a$. Обойдем правое множество, далее из $v$ в q, потом через $b$ в p, потом в $a$ и потом в $u$ и там обойдем левое множество. Снова г.путь.
Случай 4. Есть три вершины в среднем множестве. Теперь есть три пары несмежных вершин.
Нужны два ребра в $u$ из этих трех вершин- иначе берем эти три и $u$. Тоже самое для $v$.
Значит, есть ребра из $u$ в $a$ и из $v$ в $b$, где еще осталась $c$ и $a \ne b$.
Теперь идем по маршруту $uapcqv$ где вначале обходим, как обычное, левое множество, а в конце правое.
Снова г.путь.

Перефразируем доказанное:
Дан граф, удовлетворяющий условию задачи. Если выбрать в нем вершину для удаления определенным способом, который всегда существует, то будет выполняться либо что выбранная вершина будет иметь дорогу к большим городам, либо будет являться сама большим городом, покрывая вместе с другим все вершины.
Во всех других случаях были доказаны противоречия.

Значит, всегда есть два необходимых города.

[jrock]

Есть опечатка в случае 4.
Там путь, очевидно, $uapcqbv$

[jrock]

Еще я забыл сказать, что, очевидно, подграф, любая вершина которого не имеет дороги к q и p будет полным: если нашлись две вершины, которые не имеют дороги, то берем p, q и эти две вершины - получится одно ребро. Такой граф содержит г.цикл, в который можно приходить в любую вершину, выйти из любой вершины в $e$ и вернуться в любое место.
Если левое множество содержит вершину, отличную от $u$ и $v$, то ее можно использовать для выхода из г.путь внутри (иначе берем p или q по необходимости, $e$, эту вершину и любую вершину оставшегося графа. ). Если в правом и левом множестве есть только вершины $u$ и $v$ , то хотябы одна должна иметь ребро в оставшийся граф, иначе $v$, $u$, $p$ и любая вершина из оставшегося графа. Значит, можно $u$ или $v$ использовать для выхода из г.пути.