графы

[cyb12]

Имеется такая задача: показать, что граф с диаметром $d$ и минимальной длиной простого цикла $2d+1$ регулярен.
В статье Р.Синглтона доказывается следующим образом. В начале можно показать, что степень противоположных вершин (т.е. находящихся на расстоянии диаметра) одинакова. Затем доказывается, что степень любой вершины в графе не меньше 2: пусть есть висячая вершина $u,$ а $v$ -- смежная с ней. Тогда расстояние от любой отличной от этих вершины до $v$ не больше $d-1.$ В графе имеется цикл длины $2d+1,$ пусть $w_1$ и $w_2$ -- любые смежные вершины в нём. Тогда, в силу связности графа, существует путь из $v$ в $w_1,$ и из $v$ в $w_2,$ т.е. имеем цикл, имеющий длину меньшую, чем $2(d-1)+1=2d-1,$ противоречие. Почему путь из $v$ в $w_2$ не может проходить по пути из $v$ в $w_1$?

[bnovikov]

cyb12 в сообщении #458714 писал(а):

Тогда, в силу связности графа, существует путь из $v$ в $w_1,$ и из $v$ в $w_2,$ т.е. имеем цикл, имеющий длину меньшую, чем $2(d-1)+1=2d-1,$ противоречие. Почему путь из $v$ в $w_2$ не может проходить по пути из $v$ в $w_1$?

Потому что если путь из $v$ в $w_2$ будет проходить по пути из $v$ в $w_1$, то получим цикл еще меньшей длины.

[cyb12]

bnovikov в сообщении #458895 писал(а):

Потому что если путь из $v$ в $w_2$ будет проходить по пути из $v$ в $w_1$, то получим цикл еще меньшей длины.

Никак не пойму, какой цикл это будет?

[bnovikov]

Цикл $v-w_1-w_2$ имеет длину $<2d$. Если он не простой, то он содержит простой цикл МЕНЬШЕЙ длины.

[cyb12]

bnovikov в сообщении #459361 писал(а):

Цикл $v-w_1-w_2$ имеет длину $<2d$. Если он не простой, то он содержит простой цикл МЕНЬШЕЙ длины.

А почему $v-w_1-w_2$ -- это цикл?

[bnovikov]

Вы же сами пишете:

"...существует путь из $v$ в $w_1,$ и из $v$ в $w_2,$..."

[cyb12]

А если путь из $v$ в $w_2$ единственный и проходит только через $w_1$? Нет же тут цикла....

[bnovikov]

Тогда я неправ. Прошу прощения.

[Circiter]

2cyb12
Скорее всего я вам ничем не помогу, но есть такая идея. Допустим у вас вот эта вот неудобная ситуация все-таки возникла, т.е. $w_1$ оказалась на единственном пути от $v$ до $w_2$. Тогда мы можем заменить $w_1$ на $w_2$ (увеличив тем самым расстояние от $w_1$ до $v$ на единицу), а в качестве $w_2$ выбрать ещё неиспользованную соседку. Если до этой соседки есть более короткий путь, не проходящий через новую $w_1$, то мы приходим к ситуации из стартового сообщения (т.е. получаем более короткий простой цикл, что нарушает условие минимальности уже имеющегося), в противном же случае продолжаем процесс "передвигания" $w_1$ вдоль содержащего её минимального цикла длины $2d+1$ пока расстояние от $w_1$ до $v$ не превысит $d-1$, т.е. пока не нарушится условие, по которому расстояние от любой вершины до $v$ не больше $d-1$ (длина минимального цикла при этом обеспечивает это запасное расстояние).

В общем тут как-то должна использоваться принадлежность $w_1$ и $w_2$ минимальному циклу, и в тоже время эти вершины могут выбираться не обязательно произвольно... Может быть там в статье есть какие-то дополнительные детали? Нельзя ли процитировать (особенно про то, что $w_1$ и $w_2$ -- любые смежные из цикла)?

[cyb12]

2Circiter
Да, я думаю, так можно...

Тут кусок из статьи: http://rghost.ru/11568671.view