Поиск максимального количества рёбер графа

@IG2 · Регистрация: 16.04.2020

Author24 — интернет-сервис помощи студентам

Здравствуйте, помогите, пожалуйста, решить такую задачу:
Какое максимальное количество ребер может быть в графе с 2022 вершинами, если в этом графе нет циклов длины 4? Петли и кратные ребра запрещены.

@3D Homer · 03.07.2022, 00:05

Я не специалист по теории графов, но это кажется непростой задачей. Откуда она взялась? Могут ли в этом графе быть циклы длины 3?

В этой статье (PDF) на с. 41 приводится такая верхняя оценка: количество ребер графа на n вершинах, не содержащего цикла длины 2k, не превосходит (k − 1)n^1+(1/k) + 16(k − 1)n. Также говорится, что при k = 2 это число растет как Θ(n^3/2).

Если циклы длины 3 тоже запрещены, то теорема 4.1 на с. 39 в той же статье говорит, что число ребер в графе на n вершинах без циклов длины 3, ..., 2k есть строго меньше (1/2)n^1+(1/k) + n/2. Также говорится, что более высокую верхнюю оценку n^1+(1/k) легко доказать индукцией по n.

См. также этот вопрос на MathOverflow и ссылки в нем. Можно также поискать фразу "the maximal number of edges in a graph with n vertices and girth g".

@IG2 28 / 21 / 8 Регистрация: 16.04.2020 Сообщений: 87
		1
	Поиск максимального количества рёбер графа 02.07.2022, 20:19. Показов 873. Ответов 1 Метки нет (Все метки) Здравствуйте, помогите, пожалуйста, решить такую задачу: Какое максимальное количество ребер может быть в графе с 2022 вершинами, если в этом графе нет циклов длины 4? Петли и кратные ребра запрещены. 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,661
	03.07.2022, 00:05	2
	Я не специалист по теории графов, но это кажется непростой задачей. Откуда она взялась? Могут ли в этом графе быть циклы длины 3? В этой статье (PDF) на с. 41 приводится такая верхняя оценка: количество ребер графа на n вершинах, не содержащего цикла длины 2k, не превосходит (k − 1)n^1+(1/k) + 16(k − 1)n. Также говорится, что при k = 2 это число растет как Θ(n^3/2). Если циклы длины 3 тоже запрещены, то теорема 4.1 на с. 39 в той же статье говорит, что число ребер в графе на n вершинах без циклов длины 3, ..., 2k есть строго меньше (1/2)n^1+(1/k) + n/2. Также говорится, что более высокую верхнюю оценку n^1+(1/k) легко доказать индукцией по n. См. также этот вопрос на MathOverflow и ссылки в нем. Можно также поискать фразу "the maximal number of edges in a graph with n vertices and girth g". 1