Дороги между городами

[daogiauvang]

Дано 20 город - 2 города любые соединены одной дорогой с односторонним движением. Пример: А -> Б т.е. только есть прямая дорога от А до Б, а нет прямой дороги от Б до А. Доказать, что существует один город, из которого можно доехать до всех других городов.

[DeBill]

Индукция. Удалим город $A$. Среди оставшихся есть город $B$, из которого можно доехать до всех. Если изначально была дорога $BA$, то искомый - $B$, иначе - $A$

[daogiauvang]

DeBill в сообщении #1207659 писал(а):

Индукция. Удалим город $A$. Среди оставшихся есть город $B$, из которого можно доехать до всех. Если изначально была дорога $BA$, то искомый - $B$, иначе - $A$

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

[slavav]

Индукция по $n$ - числу вершин в графе. База очевидна.
Пусть верно индукционное предположение для $n$. Рассмотрим граф с $n + 1$ вершиной. Удалим одну вершину $A$. В оставшемся графе есть вершина $B$ из которой радиус графа равен $2$. Разберём случаи:
1. $B \to A$ - вершина $B$ останется центром для большего графа.
2. $A \to B, \exists C: B \to C, C \to A$ - вершина $B$ останется центром для большего графа.
3. $A \to B, \forall C: B \to C \Rightarrow A \to C$ - вершина $A$ становится центром для большего графа. Рассмотрим $D: D \to B$. Из индукционного предположения $\exists C: B \to C, C \to D$. Тогда верно что $A \to C, C \to D$.

[Skeptic]

Условиям задачи удовлетворяет наличие нескольких тупиковых городов, т.е. не имеющих выездных дорог. С тупиковыми городами задача не имеет решения.

[slavav]

Skeptic в сообщении #1207877 писал(а):

Условиям задачи удовлетворяет наличие нескольких тупиковых городов, т.е. не имеющих выездных дорог. С тупиковыми городами задача не имеет решения.

В условиях задачи не может быть более одного тупикового города. Если их хотя бы два, то куда ведёт дорога между ними?

[ET]

daogiauvang в сообщении #1207800 писал(а):

DeBill в сообщении #1207659 писал(а):

Индукция. Удалим город $A$. Среди оставшихся есть город $B$, из которого можно доехать до всех. Если изначально была дорога $BA$, то искомый - $B$, иначе - $A$

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

Возьмем любой город A, у которого максимальное количество исходящих путей (и, следователно, минимальное число входящих). Теперь возьмем любой город B , для которого дорога ведет из B->A Число входящих путей для города B будет больше или равно числу входящих путей города A. но, как минимум 1 входящий путь города A - это A->B. Следовательно, Дирихле