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

Тайм-коды!
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 вершинах?

[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 вершинах?

[gerpol]

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

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

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

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

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

[agegon]

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

[arthur]

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

[zetytkit]

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

[x_xp]

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

[anon_commentator]

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