М
Молодежь
К
Компьютеры-и-электроника
Д
Дом-и-сад
С
Стиль-и-уход-за-собой
П
Праздники-и-традиции
Т
Транспорт
П
Путешествия
С
Семейная-жизнь
Ф
Философия-и-религия
Б
Без категории
М
Мир-работы
Х
Хобби-и-рукоделие
И
Искусство-и-развлечения
В
Взаимоотношения
З
Здоровье
К
Кулинария-и-гостеприимство
Ф
Финансы-и-бизнес
П
Питомцы-и-животные
О
Образование
О
Образование-и-коммуникации
lebrov
lebrov
31.01.2023 18:34 •  Математика

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

👇
Ответ:
Lizevette
Lizevette
31.01.2023
Построим таблицу 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 ребро. доказать, что в графе есть хотя бы один треуголь
4,4(95 оценок)
Открыть все ответы
Ответ:
GangsterSkrillex
GangsterSkrillex
31.01.2023
Ацте́ки (асте́ки [1]) (самоназв. mēxihcah [meː'ʃiʔkaʔ]) — индейская народность в центральной Мексике. Численность свыше 1,5 млн человек. Цивилизация ацтеков (XIV—XVI века) обладала богатой мифологией и культурным наследием. Столицей империи ацтеков был город Теночтитлан, расположенный на озере Тескоко (Тешкоко) (исп. Texcoco), там, где сейчас располагается город Мехико. 
Племя ацтеков пришло в долину Мехико с севера — скорее всего c земель, ныне принадлежащих США. В то время вся территория долины была поделена между местными племенами и, естественно, никто из них не хотел делиться землёй с пришельцами. Посовещавшись, местные вожди решили отдать пришельцам необитаемый остров на озере Тескоко. На острове водилось много змей, поэтому местные жители ожидали, что пришельцам на острове придётся несладко. 
Прибыв на остров, ацтеки увидели, что на нём обитает много змей, и очень этому обрадовались, поскольку змеи были их пищей. Как хорошая примета был воспринят ацтеками увиденный ими орёл, держащий в своих когтях змею. 
Уже в 1325 году на острове возник город Теночтитлан — ацтекская столица. 
4,5(32 оценок)
Ответ:
sofiaryzhova
sofiaryzhova
31.01.2023
В окружность радиуса R = 2√6 вписан равносторонний треугольник
сторона треугольника a = R* корень(3) = основание треугольника

Прямая, параллельная стороне треугольника, делит высоту, проведенную к этой стороне, в отношении 3:1, считая от основания

отрезок этой прямой, заключенной между сторонами треугольника
является основанием подобного треугольника

коэффициент подобия 1:4

Длина отрезка этой прямой, заключенной между сторонами треугольника, равна b = a/4 = R* корень(3)/4 = 2√6 * корень(3)/4 = 3√2/2 = 3 / √2
4,4(54 оценок)
Это интересно:
Новые ответы от MOGZ: Математика
Полный доступ к MOGZ
Живи умнее Безлимитный доступ к MOGZ Оформи подписку
logo
Вход Регистрация
Что ты хочешь узнать?
Спроси Mozg
Открыть лучший ответ