ВСЯ теория по графам для олимпиад

[@shkolkovo_olymp]

Тайм-коды! 0:00 Будет БАЗА по графам! Никаких сложных теорем, а только выжимка обязательных вещей! 0:35 Граф. Вершины и рёбра. Степень вершины. Определения. Кратные рёбра и петли - то, чего обычно не бывает! 2:29 Лемма о рукопожатиях. Количество вершин нечётной степени чётно! Сумма степеней вершин = 2 * кол-во рёбер! 4:19 Путь, простой путь. Цикл, простой цикл. Компоненты связности и связный граф! 7:39 Какое минимальное количество рёбер нужно провести, чтобы связать n вершин? 9:26 В графе с n вершинами и n-1 ребром нет циклов! Дерево - связный граф без циклов! Лес - несвязный граф без циклов! 11:18 Ранжированный граф. Располагаем все вершины графа по рангам! Упражнение: выделите остовное дерево в связном графе! 12:46 Двудольный граф. Критерий двудольности: граф двудольный тогда и только тогда, когда все циклы в графе имеют чётную длину! 18:03 Раскраска вершин графа правильным образом! Разбиение графа на доли 18:52 Полный граф. Сколько рёбер в полном графе на n вершинах?

[@gerpol1005]

ООО прям то что нужно!! Только собирался изучить перед олимпиадами, огромное спасибо!

[@ФорменноеБезобразие-т6е]

Ооо теория графов. А будет планиметрия в комплексных числах? Или комбинаторная геометрия...

[@shkolkovo_olymp]

комплексные в геоме -- уж больно специфично и для перечневых не особо нужно. Комбинаторная геометрия -- ды не очень понятно пока, какую там теорию рассказывать, лемма Хелли -- слишком жестко!

[@lokiff7834]

Спасибо, ДА !!!

[@zetytkit3599]

Как будто бы "ВСЯ теория по графам" и вся БАЗА немного разные вещи, по названию пришёл сюда как раз за Теоремой Турана и т.п.

[@x_xp9259]

Так а где все? Деревья, компоненты сильной связности, мосты, двусвязность, точки сочленения, двудольность, потоки, lca, центройды, хэви лайт декомпазиция и тому подобное

[@anon_commentator]

Нарешано у меня задач достаточно, а вот теории - ноль. Перед регионом надо будет основательно пройти по всем вашим разделам "вмя теория". Если закрепить её на соответствующих задачах, то даже такой интернетный червь как я может чего-то добиться. Хотя, честно, эти роли ну слишком детские. В них стоит добавить в раза 2-3 больше теорем

[@qwq7459]

ты уже прошел на рег?

[@anon_commentator]

@@qwq7459 так а хер знает. На Эйлере меня не было, а результатов до сих пор нет. Муницип написал на 26, в mosreg пишет что побед, + проходные прошлых лет ни разу не были больше, скорее всего должен пройти. А у тебя как, пришли результаты уже?

[@qwq7459]

@@anon_commentator Эйлер? Ты в 7 классе? Я просто в 11, и в тюменской области еще даже не было муниципального этапа

[@anon_commentator]

@@qwq7459 "Эйлер? Ты в седьмом классе?" Чеего. Эйлер для 8ого класса, я пишу "на Эйлере меня не было", типа меня не было на реге прошлого года. Т е я девятый. П с я в московской, и у нас он был уже больше месяца назад. А на офиц сайте проходные так и не скинули 😵‍💫

[@qwq7459]

@@anon_commentator аааа, понял. Я прост уже забыл когда писал его, все смешалось. И кстати, всош для Москвы очень отличается от всоша регионов, даже структурой работы

[@MiChAeLLo_10_06]

учись р говорить

[@arthur4157]

Ооо круто! Будет ли теоиря по параметрам и геоме?

[@shkolkovo_olymp]

что такое геометрия

[@АлексРоманенко-з3х]

Здравствуйте очень вы хорошо обьясняете спасибо вам надеюсь новый ролик скоро

[@agegon8514]

Последнюю задачу можно решить геометрией. Соединим все пограничные точки так, чтобы получился n-угольник (все остальные вершины внутри остались) получается n ребер, дальше мы в этой фигуре проводим диагонали, а их количество n(n-3)/2 (n вершин, от каждой проводим к n-3 другим вершинам диагонали 1 точка это наша 2 другие соседние, к ним нельзя провести диагонали + мы каждую диагональ посчитали дважды). Тогда ответ n+n(n-3)/2

[@blazik4206]

Спасибо большое!