2014 dxdy logo

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

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




 
 Центр и диаметр графа
Сообщение20.12.2013, 22:03 
Аватара пользователя
Добрый вечер! Не знаю как подступиться к такой задаче:верно ли, что хотя бы один центр графа лежит на диаметральной цепи(диаметре)?Пробовал строить много графов, пришел к выводу, что, скорее всего, это так, однако как это доказать?

 
 
 
 Re: Центр и диаметр графа
Сообщение20.12.2013, 22:19 
Среди построенных вами графов есть такие, у которых диаметр не равен двум радиусам?

 
 
 
 Re: Центр и диаметр графа
Сообщение20.12.2013, 22:27 
Аватара пользователя
helgui в сообщении #804049 писал(а):
Среди построенных вами графов есть такие, у которых диаметр не равен двум радиусам?

Безусловно

 
 
 
 Re: Центр и диаметр графа
Сообщение22.12.2013, 00:36 
Аватара пользователя
Неужели никто не знает?

 
 
 
 Re: Центр и диаметр графа
Сообщение22.12.2013, 00:56 
Собирался подумать над этим и забыл. Ну доказательство для ацикликлического графа простое. Может стоит как-то идти от него. Или приводить к нему, например, сжимая циклы. Да, я речь веду только о неориентированных связных графах.

 
 
 
 Re: Центр и диаметр графа
Сообщение22.12.2013, 11:49 
Аватара пользователя
Да, речь идет только о неориентированных. А каким образом мы будем избавляться от циклов, чтобы придти к ациклическому?

 
 
 
 Re: Центр и диаметр графа
Сообщение22.12.2013, 13:26 
Enot2 в сообщении #804408 писал(а):
Неужели никто не знает?
Давайте строить цепь с середины.
Сначала рассмотрим случай $D=2R$.
Пусть $a$ и $b$ - диаметральные вершины.
Возьмем какую-нибудь центральную вершину и рассмотрим все вершины, удаленные от нее на $R$. Если среди них есть $a$ и $b$, то все доказано.
Если расстояние хотя бы до одной меньше $R$, то вершины $a$ и $b$ не диаметральные - противоречие. Если расстояние же хотя бы до одной больше $R$, наша вершина не центральная - противоречие.
Остался случай $D=2R-1$ :-)

 
 
 
 Re: Центр и диаметр графа
Сообщение22.12.2013, 14:41 
VAL в сообщении #804602 писал(а):
Enot2 в сообщении #804408 писал(а):
Неужели никто не знает?
Давайте строить цепь с середины.
Сначала рассмотрим случай $D=2R$.
Пусть $a$ и $b$ - диаметральные вершины.
Возьмем какую-нибудь центральную вершину и рассмотрим все вершины, удаленные от нее на $R$. Если среди них есть $a$ и $b$, то все доказано.
Если расстояние хотя бы до одной меньше $R$, то вершины $a$ и $b$ не диаметральные - противоречие. Если расстояние же хотя бы до одной больше $R$, наша вершина не центральная - противоречие.
Остался случай $D=2R-1$ :-)

Я уже говорил про случай $D=2R$, тут все очевидно.

 
 
 
 Re: Центр и диаметр графа
Сообщение22.12.2013, 15:07 
VAL в сообщении #804602 писал(а):
Сначала рассмотрим случай $D=2R$.
<...>
Остался случай $D=2R-1$ :-)

а как быть со случаями $D=2R-2$ и $D=R$ (к примеру)? :D

 
 
 
 Re: Центр и диаметр графа
Сообщение22.12.2013, 15:58 
patzer2097 в сообщении #804652 писал(а):
VAL в сообщении #804602 писал(а):
Сначала рассмотрим случай $D=2R$.
<...>
Остался случай $D=2R-1$ :-)

а как быть со случаями $D=2R-2$ и $D=R$ (к примеру)? :D
Ой! Отвлекли меня звонком. Когда вернулся, про смайлик не забыл, а вместо $D<2R$ написал что-то другое :shock: (Наверное, подсознательно из случая дерева.)

 
 
 
 Re: Центр и диаметр графа
Сообщение22.12.2013, 21:41 
Аватара пользователя
Я долго вникал, почему же только $D=2R-1$ :D
Может, для оставшегося случая, нужно постепенно идти от вершины $a$ до $b$?

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


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