Про общую вершину наидлиннейших путей в связном графе

[ghetto]

Докажите, что если $P$ и $Q$ две самые длинные пути в связном графе, то $P$ и $Q$, по крайней мере имеют
одну общую вершину.


Предположим, напротив, что существует связный граф $G$, содержащий две наидлиннейших пути $P$ и $Q$, не имеющих общую вершину. В силу связности $G$, существует $u - v$ путь $P'$, где $u$ находится на $P$, $v$ находится на $Q$.

Что здесь еще можно придумать?

[patzer2097]

ghetto в сообщении #894792 писал(а):

Что здесь еще можно придумать?

Если я правильно понял Ваше рассуждение, то решения оно не дает. Чтобы решение получить, рассмотрите минимальный путь $l$, соединяющий какую-нибудь вершину $P$ с какой-нибудь вершиной $Q$ (назовем их $u$ и $v$, соответственно). Попробуйте теперь построить путь большей длины, чем $P$ и $Q$.
А именно, если обозначить через $p_1$ и $p_2$ начало и конец пути $P$, и через $q_1$ и $q_2$ начало и конец пути $Q$, - что можно будет сказать про пути $p_i\rightarrow u\rightarrow v\rightarrow q_j$?

[ghetto]

$d(p_i, q_j) > d(p_1, p_2)$ и $d(p_i, q_j) > d(q_1, q_2)$ ?

-- 10.08.2014, 04:18 --

Если $P$ есть $a - b$ путь, а $Q$ есть $c - d$ путь, и они не имеют общую вершину, то существует $u - v$ путь $P'$, так что $u$ лежит на $P$, а $v$ лежит на $Q$ и ни одна внутренняя вершина $P'$ не лежит на $P$ или $Q$. Это следует из связности графа. Тогда $u$ разбивает $P$ на $a - u$ и $u - b$ пути. Аналогично $v$ разбивает $Q$ на $c - v$ и $v - d$ пути. Если мы выберем длинную из этих путей от каждой $P$ и $Q$, скажем, $a - u$ и $c - v$, то объединение путей $a - u, u - v, v - c$ будет длиннее чем $P$ или $Q$. Надо это еще доказать.

[patzer2097]

Теперь все отлично! Чтобы завершить доказательство, достаточно проверить, что один из путей $\pi(i,j)=p_i\rightarrow u\rightarrow v\rightarrow q_j$ будет длиннее, чем $P$ и чем $Q$.
А для этого ответьте на вопрос: чему равна сумма длин путей $\pi(1,1)$, $\pi(1,2)$, $\pi(2,1)$, $\pi(2,2)$? И как можно оценить снизу длину самого длинного из них?

[ghetto]

Доказательтсво неполное пока не докажем :

...что $u$ лежит на $P$, а $v$ лежит на $Q$ и ни одна внутренняя вершина $P'$ не лежит на $P$ или $Q$.

[patzer2097]

ghetto в сообщении #895431 писал(а):

Доказательтсво неполное пока не докажем :
...что $u$ лежит на $P$, а $v$ лежит на $Q$ и ни одна внутренняя вершина $P'$ не лежит на $P$ или $Q$.

Ну вот у Вас есть какой-то $P'$, сколько-то вершин которого лежат на $P$ и сколько-то на $Q$. Как сделать из него путь, концы которого лежат на $P$ и $Q$ соответственно, а внутренние вершины - там не лежат?

[ghetto]

Честно признаться, понятия не имею.

[patzer2097]

ghetto в сообщении #895449 писал(а):

Честно признаться, понятия не имею.

а-а
ну, может надо просто удалить какие-то ребра из $P'$?

[ghetto]

patzer2097 в сообщении #895450 писал(а):

ghetto в сообщении #895449 писал(а):

Честно признаться, понятия не имею.

а-а
ну, может надо просто удалить какие-то ребра из $P'$?

Можно поподробнее?

[patzer2097]

ghetto в сообщении #895461 писал(а):

Можно поподробнее?

можно, рассмотрите минимальный путь, соединяющий $P$ с $Q$