Центр и диаметр графа

[Enot2]

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

[helgui]

Среди построенных вами графов есть такие, у которых диаметр не равен двум радиусам?

[Enot2]

helgui в сообщении #804049 писал(а):

Среди построенных вами графов есть такие, у которых диаметр не равен двум радиусам?

Безусловно

[Enot2]

Неужели никто не знает?

[helgui]

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

[Enot2]

Да, речь идет только о неориентированных. А каким образом мы будем избавляться от циклов, чтобы придти к ациклическому?

[VAL]

Enot2 в сообщении #804408 писал(а):

Неужели никто не знает?

Давайте строить цепь с середины.
Сначала рассмотрим случай $D=2R$.
Пусть $a$ и $b$ - диаметральные вершины.
Возьмем какую-нибудь центральную вершину и рассмотрим все вершины, удаленные от нее на $R$. Если среди них есть $a$ и $b$, то все доказано.
Если расстояние хотя бы до одной меньше $R$, то вершины $a$ и $b$ не диаметральные - противоречие. Если расстояние же хотя бы до одной больше $R$, наша вершина не центральная - противоречие.
Остался случай $D=2R-1$

[helgui]

VAL в сообщении #804602 писал(а):

Enot2 в сообщении #804408 писал(а):

Неужели никто не знает?

Давайте строить цепь с середины.
Сначала рассмотрим случай $D=2R$.
Пусть $a$ и $b$ - диаметральные вершины.
Возьмем какую-нибудь центральную вершину и рассмотрим все вершины, удаленные от нее на $R$. Если среди них есть $a$ и $b$, то все доказано.
Если расстояние хотя бы до одной меньше $R$, то вершины $a$ и $b$ не диаметральные - противоречие. Если расстояние же хотя бы до одной больше $R$, наша вершина не центральная - противоречие.
Остался случай $D=2R-1$

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

[patzer2097]

VAL в сообщении #804602 писал(а):

Сначала рассмотрим случай $D=2R$.
<...>
Остался случай $D=2R-1$

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

[VAL]

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

VAL в сообщении #804602 писал(а):

Сначала рассмотрим случай $D=2R$.
<...>
Остался случай $D=2R-1$

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

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

[Enot2]

Я долго вникал, почему же только $D=2R-1$
Может, для оставшегося случая, нужно постепенно идти от вершины $a$ до $b$?