Канал dead, стата в нулину, НадЭн слита, зато у меня есть печеньки>>>>

📝 ГРАФЫ. НАЧАЛО
Ну, хотите пожёстче - будут вам графы
Очень многие явления и ситуации в нашей жизни можно представить графически. Самое банальное - транспортные карты, дороги между городами и т.д.
Граф - это совокупность множества вершин и множества рёбер. При этом сами вершины являются объектами, а рёбра - связями между ними. В примере выше города будут вершинами, а дороги - рёбрами. Ну хорошо, а что если движение по дорогам исключительно одностороннее? Так мы приходим к понятию ориентированного графа (сокращённо орграфа), каждое ребро которого имеет начало и конец (в таком случае эти рёбра называются дугами).
Концевые вершины любого ребра называются инцидентными этому ребру, и наоборот, ребро инцидентно вершинам, которые оно соединяет. Вершины называются смежными, если они соединены ребром. Степень вершины - это количество инцидентных ей (проще говоря, выходящих из неё) рёбер. Вершина со степенью 0 называется изолированной (логично, ведь она ни с кем ни соединена), а со степенью 1 - висячей, или листом (об этом чуть позже).
В случае неорграфа рёбра называются кратными, если они соединяют одну и ту же пару вершин, а в случае орграфа - если их начала и концы совпадают. Петля - это ребро, у которого начало и конец совпадают (оно как бы сразу "возвращается обратно"). Графы без кратных рёбер и петель называются простыми.
Граф, в котором две любые вершины соединены ровно одним ребром, называется полным. Пусть в нём есть n вершин, тогда из каждой выходит по n-1 ребру, а значит, всего рёбер n(n-1)/2. Раз уж мы начали считать рёбра, то давайте подумаем вот о чём - если мы сложим степени всех вершин любого графа, то каждое ребро в этой сумме будет учтено дважды по очевидным причинам, т.е. сумма степеней вершин произвольного графа равна удвоенному числу его рёбер (имеет место равенство S=2k, где S - сумма степеней вершин, а k - число рёбер). Значит, S всегда чётно. Чётные слагаемые на чётность суммы не влияют, тогда получается, что нечётных слагаемых обязательно должно быть чётное число. Мы получаем утверждение, называемое леммой о рукопожатиях:

В произвольном графе количество вершин нечётной степени всегда чётно.

Вот, кстати, хороший пример применения графов - принять людей за вершины, а утверждение "А и В пожали руки" обозначать ребром между А и В. Это полезно в различных комбинаторных сюжетах про какую-нибудь дружбу, вражду и т.д., да и в целом в комбинаторике, а ещё, например, в теории игр и теории групп, не говоря уже про глобальное применение графов в других науках.
#уроки@mathbotva

Мы почему-то еще не набрали миллион подписчиков, всё, канал закрывается

Где ещё вы найдёте бесплатные пробники по профмату с проверкой🫣
Кстати, олмат в 16:00 составлял я, гляньте - надеюсь, вам понравится)))

Соревнование пробник 6 апреля (гробик). Сдача ответов до 21:00.

Ну как вам, математики? Халява же

📝 НОД И НОК. АЛГОРИТМ ЕВКЛИДА
В теории чисел часто возникает понятие НОД и НОК - наибольший общий делитель и наименьшее общее кратное соответственно.
Наибольший общий делитель чисел a и b: НОД(a,b) - это максимальное число, являющееся делителем a и b (т.е. на него одновременно делятся a и b).
Наименьшее общее кратное чисел a и b: НОК(a,b) - это минимальное число, делителями которого являются a и b (т.е. оно одновременно делится на a и b).
Давайте рассмотрим степень вхождения какого-либо простого числа p в числа a и b. Пусть a ⁝ p^n, b ⁝ p^m. Какая степень числа p пойдёт в НОД? Очевидно, та, которая меньше - min(m,n), ведь оба числа кратны НОД. Логично, что в НОК пойдёт наибольшая из двух степеней - max(m,n). Тогда если мы перемножим НОД(a,b) И НОК(a,b), то получим p^(n+m) - такую же степень, что и при перемножении a и b. Очевидно, что это справедливо для любого простого числа в разложении a и b. Только что мы вывели один симпатичный факт:

Произведение НОД и НОК двух чисел равно произведению самих этих чисел: НОД(a,b)•НОК(a,b) = ab

Хорошо, а теперь обратимся конкретно к НОД. Пусть a>b. Рассмотрим НОД(a,b) и НОД(a-b,b). Пусть НОД(a,b) ⁝ c => a⁝c, b⁝c => (a-b)⁝c => НОД(a-b,b) ⁝ c. Если же наоборот, НОД(a-b,b) ⁝ c, то (a-b)⁝c, b⁝c, => a⁝c => НОД(a,b) ⁝ c. Обобщая эти рассуждения, мы понимаем, что НОД(a,b) и НОД(a-b,b) делятся друг на друга, но это возможно тогда и только тогда, когда они равны. Поздравляю с открытием вещи под названием..

Алгоритм Евклида: НОД(a,b) = НОД(a-b,b), где a>b

Таким образом, в любом НОД из большего числа можно вычесть меньшее и заменить его на эту разность. Такое действие можно совершать, пока в одном из аргументов не получится ноль, а мы знаем, что НОД(x,0) = x.
Кроме того, можно не делать такое вычитание миллиард раз, а сразу заменить a на его остаток по модулю b: a ≡ r (mod b) => НОД(a,b) = НОД (r,b). Но более подробно об арифметике остатков мы поговорим позднее.
#уроки@mathbotva

Ну в целом ладно, лом слит, жаль не в том смысле как хотелось бы

🤔 ЛИРИЧЕСКОЕ ОТСТУПЛЕНИЕ
Вот и приближается к концу учебный год, у многих на горизонте уже ощутимо маячат экзамены. Кто-то готовился целый год, а может, и больше; кто-то только начинает (пупупу), а кто-то в состоянии варёного овоща после олимпиадного сезона, и хорошо если с дипломом, иначе овощ ещё и суицидальный.. Но не будем о грустном. Так или иначе, очень многие уже прошли долгий и непростой путь, и сейчас главное - не сдаться перед самым финишем. Вспомните, сколько всего вы уже сделали, похвалите себя, в конце концов - вы это заслужили. Вот ты, да, именно ты, послушай меня. Ты молодец, я это знаю. Твоя жизнь только начинается, и все эти егэ, всеросы, сессии ты будешь вспоминать с ностальгической улыбкой. Главное - не паникуй, всё хорошо. Выйди прогуляйся, посмотри на природу. Не забывай, конечно, про пункты из этого поста - они сейчас актуальны как никогда. Чем бы ты не занимался - продолжай в том же духе, всё у тебя получится. Спасибо за внимание.
#послушай@mathbotva