|
|
 |
Условие
а) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет треугольников?
б) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет полного подграфа из четырёх вершин?
Подсказка
Выберите вершину наибольшей степени.
Решение
а) Оценка. Выберем вершину A наибольшей степени n и рассмотрим подграф G, образованный вершинами, куда ведут рёбра из A. Ясно, что в этом подграфе рёбер нет. Каждая вершина, не входящая в G имеет степень не больше n, а выходящие из них рёбра – это все рёбра исходного графа. Таким образом, общее число рёбер исходного графа не превосходит n(30 – n) ≤ 15².
Пример. Разобьём 30 вершин на две группы по 15 и проведём все рёбра, соединяющие вершины из разных групп. Получился граф без треугольников с 225 рёбрами.
б) Оценка. Выберем вершину A наибольшей степени n и рассмотрим подграф G, образованный вершинами, куда ведут рёбра из A. Ясно, что в этом подграфе нет треугольников, поэтому, как фактически доказано в а), число его рёбер не превосходит (n/2)². Таким образом, общее число рёбер исходного графа не превосходит (n/2)² + n(30 – n) = 3/4 n(40 – n) ≤ 3/4·20² = 300.
Пример. Разобьём 30 вершин на три группы по 10 и проведём все рёбра, соединяющие вершины из разных групп. Получился граф без полных 4-подграфов с 300 рёбрами.
Ответ
а) 225; б) 300 рёбер.
Замечания
Эти задачи – частные случаи теоремы Турана (см. статью в Википедии).
Источники и прецеденты использования
| книга | |
| Автор | Иванов С.В. |
| Название | Математический кружок |
| глава | |
| Номер | 5 |
| Название | Графы |
| Тема | Теория графов |
| задача | |
| Номер | 36 |
