2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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


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

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

 
 
 
 Re: Про общую вершину наидлиннейших путей в связном графе
Сообщение10.08.2014, 02:16 
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$?

 
 
 
 Re: Про общую вершину наидлиннейших путей в связном графе
Сообщение10.08.2014, 02:41 
$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$. Надо это еще доказать.

 
 
 
 Re: Про общую вершину наидлиннейших путей в связном графе
Сообщение10.08.2014, 03:58 
Теперь все отлично! Чтобы завершить доказательство, достаточно проверить, что один из путей $\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)$? И как можно оценить снизу длину самого длинного из них?

 
 
 
 Re: Про общую вершину наидлиннейших путей в связном графе
Сообщение11.08.2014, 22:12 
Доказательтсво неполное пока не докажем :

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

 
 
 
 Re: Про общую вершину наидлиннейших путей в связном графе
Сообщение11.08.2014, 22:55 
ghetto в сообщении #895431 писал(а):
Доказательтсво неполное пока не докажем :
...что $u$ лежит на $P$, а $v$ лежит на $Q$ и ни одна внутренняя вершина $P'$ не лежит на $P$ или $Q$.

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

 
 
 
 Re: Про общую вершину наидлиннейших путей в связном графе
Сообщение11.08.2014, 23:54 
Честно признаться, понятия не имею.

 
 
 
 Re: Про общую вершину наидлиннейших путей в связном графе
Сообщение12.08.2014, 00:02 
ghetto в сообщении #895449 писал(а):
Честно признаться, понятия не имею.
а-а :-(
ну, может надо просто удалить какие-то ребра из $P'$?

 
 
 
 Re: Про общую вершину наидлиннейших путей в связном графе
Сообщение12.08.2014, 01:19 
patzer2097 в сообщении #895450 писал(а):
ghetto в сообщении #895449 писал(а):
Честно признаться, понятия не имею.
а-а :-(
ну, может надо просто удалить какие-то ребра из $P'$?

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

 
 
 
 Re: Про общую вершину наидлиннейших путей в связном графе
Сообщение12.08.2014, 02:03 
ghetto в сообщении #895461 писал(а):
Можно поподробнее?
можно, рассмотрите минимальный путь, соединяющий $P$ с $Q$

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group