В
Все
М
Математика
О
ОБЖ
У
Українська мова
Х
Химия
Д
Другие предметы
Н
Немецкий язык
Б
Беларуская мова
М
Музыка
Э
Экономика
Ф
Физика
Б
Биология
О
Окружающий мир
У
Українська література
Р
Русский язык
Ф
Французский язык
П
Психология
О
Обществознание
А
Алгебра
М
МХК
Г
География
И
Информатика
П
Право
А
Английский язык
Г
Геометрия
Қ
Қазақ тiлi
Л
Литература
И
История
Wanemid
Wanemid
30.09.2022 20:24 •  Математика

(это лемма турана) в графе 2n вершин и n^2+1 ребро. доказать, что в графе есть хотя бы один треугольник.можно подробно и понятно,

Показать ответ
Ответ:
анксунамун1
анксунамун1
08.10.2020 21:11
Построим таблицу 2n×2n (см. рис). Столбцы и строки обозначают вершины (они занумерованы числами от 1 до 2n). Если какие-то вершины соединены ребром, то на соответствующем пересечении столбца и строки напишем 1. Например, если вершины 4 и 2 соединены ребром, то на пересечении 4 столбца и 2 строки напишем 1. Поскольку 4 столбец и четвертая строка отвечают за одну и ту же вершину, можем обрезать таблицу пополам (по линии диагонали). Заметим, если три вершины образуют треугольник, то единицы, соответствующие этим соединениям образуют прямоугольный треугольник (если мысленно их соединить в таблице). Также, любой двойке единиц в конкретном столбце соответствует единственная единица в соответствующей строке, такая что они втроем образуют треугольник. Например, на рисунке красные единицы образуют треугольные, а синие - нет. При этом двойке красных единиц в 4-ом столбце соответствует единственная 1-ца, такая, что они вместе образуют треугольник (если бы третья единица была в 3-ем столбце, 1 строке, то треугольник не образовывался). Значит общее число треугольников в графе соответствует сумме комбинаций двоек в каждом столбце. Пусть в первом столбце n₁ единиц, во втором n₂ и т.д. Значит общее число треугольников равно \frac{n_{1}(n_{1}-1)}{2}+ \frac{n_{2}(n_{2}-1)}{2}+...+ \frac{n_{2n}(n_{2n}-1)}{2}= \frac{n_{1}^{2}+n_{2}^{2}+...+n_{2n}^{2}-n^{2}-1}{2}(*); Заметим, что минимальное значение выражения A²-A для натуральных чисел равно 1. Раз  n_{1}^{2}+n_{2}^{2}+...+n_{2n}^{2}-n_{1}-n_{2}-...-n_{2n}=2n, то с учетом (*), минимальное количество треугольников равно 2n/2 = n; То есть ясно, что хотя бы один треугольник образуется
(это лемма турана) в графе 2n вершин и n^2+1 ребро. доказать, что в графе есть хотя бы один треуголь
(это лемма турана) в графе 2n вершин и n^2+1 ребро. доказать, что в графе есть хотя бы один треуголь
0,0(0 оценок)
Популярные вопросы: Математика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота