Кировская ЛМШ, Профи-7, 2000 г.

Графы-1

Задачи на минимальное число рёбер в связном графе и лемму о рукопожатиях. Но самая главная идея, конечно – это идея схемы: надо суметь увидеть граф и нарисовать его!

Школа "Математика у моря", 6-7, 2014 г.

Графы. Cчет ребер

В графе без циклов есть равенство Р=В–С (где Р – рёбра, В – вершины, С – компонеты связности). В произвольном графе это превращается в неравенство Р≥В–С. Увидев подходящий граф, можно доказать или использовать соответствующие равенства и неравенства.

Кировская ЛМШ, Профи-7, 2000 г.

Графы-2: определения, лемма о рукопожатиях, связность

Даны явные определения и приведен богатый список примеров графов, покрывающий большинство задач для начинающих. Большинство кружковцев не догадываются применить факты о графах к шахматной доске, а это просто: вершины клетки, рёбра – ходы той или иной фигуры.

Школа "Математика у моря", 6-7, 2014 г.

Деревья

Деревом называется связный граф без циклов. В дереве вершин на одну больше чем рёбер. Из любого графа можно выкинуть часть рёбер, оставив остовное дерево.

Кировская ЛМШ, Профи-7, 2000 г.

Графы-3

Деревья. Число рёбер в связном графе и в дереве.

Кировская ЛМШ, Профи-7, 2000 г.

Эйлеровы пути и обходы

Несложен критерий существования пути или обхода графа, проходящий по каждому ребру графа ровно раз. Неожиданно то, что из критерия бывают нетривиальные следствия.

Сириус, 7 класс, 2016 г., май

Эйлеровы пути и обходы

doc    pdf

Связь существования путей и обходов по всем ребрам с четностью кружковцам хорошо известна, необходимость очевидна. В процессе обсуждения неожиданно выясняется, что у них есть средства доказать и достаточность. Более того, "игрушечный" факт о рисовании одним росчерком пера помогает решать серьезные задачи, включая минимальную последовательность нажатий для раскрытия кода!

Школа "Математика у моря", 6-7, 2014 г.

Увидеть двудольный граф

В двудольном графе вершины двух цветов, а концы всех рёбер разноцветны. Пример: любое дерево. При движении по двудольному графу цвета вершин строго чередуются, поэтому вернуться в исходную вершину можно только за чётное число ходов.
С игрой всегда связан граф: позиции — вершины, ходы — рёбра. Полезно знать, когда этот граф — двудольный.

Онлайн-кружок, Набережные Челны, 7 класс, 2013-14 г.

Увидеть двудольный граф

Двудольный граф даёт чередование цветов, и гарантирует равенство цветов на замкнутом маршруте и отличие не более чем на 1 на незамкнутом. Часто удается раскрасить явно, выделив два свойства (например, чётность).

Кировская ЛМШ, Профи-7, 2000 г.

Двудольные графы

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

Школа "Математика у моря", 6-7, 2014 г.

Графы: разбиение на циклы и цепочки

Поняв, что задача сводится к графу, можно его удобно нарисовать. Если в конечном графе степени всех вершин не больше 2, то его можно разбить на непересекающиеся циклы и цепочки.

Онлайн-кружок, Набережные Челны, 7 класс, 2013-14 г.

Опять увидеть граф: циклы и цепочки

«Разделяй и властвуй», то есть разбей на удобные части, и разберись с каждой частью по отдельности. Граф, у которого степень каждой вершины не более 2, распадается на циклы и цепочки.

Школа "Математика у моря", 6-7, 2014 г.

Графы. Четность, связность

Граф связен, если между любыми двумя его вершинами есть путь по ребрам (как по дорогам). Любой граф можно разбить на связные куски-компоненты. Если в графе всего две вершины нечетной степени, между ними есть путь по рёбрам.

Сириус, 7 класс, 2016 г., май

Подсчет двумя способами в графах

doc    pdf

В дискретных задачах запись соотношений в виде уравнений и неравенств чаще всего возникает для таблиц и графов. Для сильных учеников пунктиром проходит идея нагруженных графов.

Сириус, 7 класс, 2016 г., май

Свяжитесь с графом

doc    pdf

Широко известно, что число рёбер в связном графе может быть меньше числа вершин не более чем на 1: Р<В-1. Это неравенство часто помогает найти нетривиальную оценку, стоит только увидеть за конструкцией связный граф.

Кировская ЛМШ, Профи-7, 2000 г.

Король и ладья

Если клетки шахматной доски n×n раскрашены в синий и желтый цвета, то либо ладья может пройти по синим клеткам с нижнего края на верхний, либо король может пройти с левого края на правый по желтым клеткам (то есть из двух возможностей всегда есть ровно одна!)

Онлайн-кружок, Набережные Челны, 7 класс, 2013-14 г.

Увидеть граф-3: счёт рёбер, вершин и компонент связности

В графе без циклов есть равенство Р=В–С (где Р – рёбра, В – вершины, С – компонеты связности). В произвольном графе это превращается в неравенство Р≥В–С. Увидев подходящий граф, можно доказать или использовать соответствующие равенства и неравенства.

Московские сборы, 9 класс

Увидеть граф

2013 осень: группа 9-1,
группа 9-2

В задачах на графы важно научиться строить подходящий граф из объектов любой природы. Далее часто хватает применения простейших фактов о графах. Важный пример графа: вершины – позиции, рёбра – ходы. Если граф окажется двудольным, то применима идея чередования.

Московские сборы, 9 класс

Увидеть граф-2

2013 осень: группа 9-1,
группа 9-2

При подсчетах и оценках помогает разбиение на компоненты связности, в частности – разбиение на циклы и цепочки. Считаем компоненты, выписываем неравенство между числом вершин и рёбер в графе без циклов.