Задача по теории графов

[Kid Kool]

Можно ли несколько точек в пространстве соединить отрезками так, чтобы каждая точка была соединена ровно с тремя другими, а длина любого замкнутого пути была не меньше 30-и?

[Профессор Снэйп]

Kid Kool писал(а):

Можно ли несколько точек в пространстве соединить отрезками так, чтобы каждая точка была соединена ровно с тремя другими, а длина любого замкнутого пути была не меньше 30-и?

Тридцати чего? Миллиметров, километров, ангстремов, световых лет?

В пространстве каком? В $\mathbb{R}^3$, в банаховом, в гильбертовом?

Отрезки чего имеются в виду? Отрезки прямых?

Странная какая-то задача, на вид очень-очень глупая. Вот дана система точек в $\mathbb{R}^3$. Каждую соединили отрезком с каждой, получили полный граф. Если суммарная длина рёбер меньше 30-ти чего-то там, то то и любой замкнутый путь будет меньше 30-ти. А если каждое ребро больше тридцати, то любой замкнутый путь будет иметь длину больше 90... Ответ на вопрос задачи таков: смотря какие точки и как они расположены.

[Руст]

Попытаюсь угадать условие.
1. Любой замкнутый путь имеет не менее 30 узлов.
2. Каждое расстояние между узлами равно 1, а длина любого замкнутого пути не менее 30. В этом случае необходимо знать метрические свойства пространства,. По видимому автор под ним имеет в виду $R^3$ с естественной метрикой.

[Профессор Снэйп]

Мне тут через ЛС прислали такое предположение, что каждый замкнутый путь содержит не менее тридцати рёбер.

Непонятно тогда, при чём здесь вообще какое-то "пространство".

[maxal]

Если пространство не при чем, то в задаче по сути спрашивается о том, существует ли 3-регулярный граф с обхватом не менее 30. Ответ на этот положительный. Более того, существует 3-регулярный граф у которого обхват в точности равен 30. Если же рассмотреть граф с минимальным числом вершин, то такой граф называется $(3,30)$-клеткой. При этом доказано, что $(3,30)$-клетка содержит не менее $65534$ и не более $1227666$ вершин.

Регулярные графы с большим обхватом мы также обсуждали в другой теме.

[Kid Kool]

Пространство тут ни при чем, это задача по теории графов.

[maxal]

См. также статью Constructions for cubic graphs with large girth.

[CD_Eater]

Утверждение. Для любых $k$ и $g$ существует $k$-регулярный граф с обхватом не менее $g$.

Для доказательства применим нужное число раз процедуру "удвоения обхвата графа".
Пусть есть $k$-регулярный граф $G$ с обхватом $g$, в нём $V$ вершин и $E$ рёбер (рёбра пронумерованы). Построим новый граф. Вершинами в нём будут пары $(v,x)$, где $v$ - вершина исходного графа $G$, а $x$ - строка из $E$ битов. Две вершины $(v1,x1)$ и $(v2,x2)$ соединяются ребром тогда и только тогда, когда выполнены 2 условия:
1) в графе $G$ между вершинами $v1$ и $v2$ есть ребро (имеющее некоторый номер $e$), и
2) битовая строка $x2$ получается из битовой строки $x1$ инверсией бита номер $e$.
Новый граф будет $k$-регулярным и его обхват будет равен $2g$.

Начав с графа $K_{3,3}$ за три удвоения получим $g=32$.
Правда, количество вершин будет немалым - $6*2^{9*2^{4617}+4617}$