2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Про общую вершину наидлиннейших путей в связном графе
Сообщение09.08.2014, 23:33 


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


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

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

 Профиль  
                  
 
 Re: Про общую вершину наидлиннейших путей в связном графе
Сообщение10.08.2014, 02:16 
Заслуженный участник


14/03/10
867
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 


14/03/14
112
$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 
Заслуженный участник


14/03/10
867
Теперь все отлично! Чтобы завершить доказательство, достаточно проверить, что один из путей $\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 


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

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

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


14/03/10
867
ghetto в сообщении #895431 писал(а):
Доказательтсво неполное пока не докажем :
...что $u$ лежит на $P$, а $v$ лежит на $Q$ и ни одна внутренняя вершина $P'$ не лежит на $P$ или $Q$.

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

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


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

 Профиль  
                  
 
 Re: Про общую вершину наидлиннейших путей в связном графе
Сообщение12.08.2014, 00:02 
Заслуженный участник


14/03/10
867
ghetto в сообщении #895449 писал(а):
Честно признаться, понятия не имею.
а-а :-(
ну, может надо просто удалить какие-то ребра из $P'$?

 Профиль  
                  
 
 Re: Про общую вершину наидлиннейших путей в связном графе
Сообщение12.08.2014, 01:19 


14/03/14
112
patzer2097 в сообщении #895450 писал(а):
ghetto в сообщении #895449 писал(а):
Честно признаться, понятия не имею.
а-а :-(
ну, может надо просто удалить какие-то ребра из $P'$?

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

 Профиль  
                  
 
 Re: Про общую вершину наидлиннейших путей в связном графе
Сообщение12.08.2014, 02:03 
Заслуженный участник


14/03/10
867
ghetto в сообщении #895461 писал(а):
Можно поподробнее?
можно, рассмотрите минимальный путь, соединяющий $P$ с $Q$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group