Лекция 12: Графы - 2 (стр. 12 )

(!) Заметим, что в последних 4-х задачах мы не рисовали никаких картинок. На самом деле, к использованию картинок в задачах про графы следует подходить с большой осторожностью. С одной стороны, можно не заметить какой-либо случай из-за того, что не хватило фантазии нарисовать картинку, где он возникает (так обычно и делаются ошибки в задачах на графы!!!). С другой стороны, именно новая, оригинальная картинка (и рассмотрение на ее примере старой идеи) может помочь выловить новый случай ;-)

Эйлеровы графы.
Понятие эйлерова графа связано со следующей задачей: можно ли нарисовать данный граф, не отрывая карандаш от бумаги и проводя каждое ребро ровно по разу? А можно ли так сделать, чтобы в конце карандаш вернулся в первую нарисованную вершину? Оказывается, как установил в XVIII веке Леонард Эйлер, существует очень простой критерий разрешимости этой задачи.
(?) А можно ли нарисовать, не отрывая карандаша, два графа на рисунке внизу?

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

Критерий Эйлера: В связном графе существует эйлеров путь тогда и только тогда, когда в нем не более 2-х нечетных вершин, а эйлеров цикл - тогда и только тогда, когда в нем все вершины четные. В несвязном графе очевидно, что эйлерова пути существовать не может (но он существует в тех компонентах связности, которые удовлетворяют критерию).
Доказательство: В сторону необходимости критерия все довольно просто: в любую вершину эйлеров путь несколько раз заходит и каждый раз, уже по другому ребру, выходит (при этом каждый новый заход идет уже по новым, не пройденным ранее ребрам). Объединим такие 2 ребра в пару - тогда все ребра, выходящие из одной вершины, разобьются на пары. Поэтому этих ребер четное число - и вершина четная. Возникают еще два исключения: первое ребро, выходящее из начальной вершины пути и последнее ребро, входящее в конечную вершину пути, ни с кем не объединяются в пару (но если путь является циклом, их можно объединить в пару друг с другом, т. к. они выходят из одной вершины). Таким образом, в графе, где есть эйлеров цикл, все вершины - четные (мы про любую вершины доказали, что она четная), а в графе, где есть эйлеров путь (не являющийся циклов), четные все вершины, кроме двух - начала и конца этого пути.

(!)На самом деле, вместе с необходимостью критерия Эйлера мы доказали еще ряд попутных фактов:
- начало и конец эйлерова пути, если они разные, всегда вершины нечетной степени;
- поэтому в графе, где все вершины четные, любой эйлеров путь будет эйлеровым циклом;
- а в графе, где есть 2 нечетные вершины, только они могут быть началом и концом эйлерова пути;
- графы же с одной нечетной вершиной мы не рассматриваем, потому что их нет в природе (см. выше в этой же лекции).

Достаточность критерия Эйлера доказать проще всего как частный случай (при n=1 и n=0) более общего "утверждения 2", которое будет сформулировано ниже.

Упражнение: На следующем рисунке изображена схема мостов города Кенингсберга. Можно ли прогуляться по городу, пройдя ровно 1 раз по каждому мосту? (именно размышляя над этой задачей, Леонард Эйлер придумал свой критерий для графов)

А за какое наименьшее число прогулок можно в общей сложности пройти ровно 1 раз по каждому мосту? (следующая прогулка может, конечно, начинаться не с того места, где закончилась предыдущая).

Утверждение 1: Связный граф с 2n нечетными вершинами нельзя нарисовать, отрывая карандаш от бумаги меньше n-1 раза и не проводя линий дважды.
Доказательство: От противного: пусть можно так нарисовать - тогда по ребрам графа проходит не более n-1 пути, в общей сложности проходящих ровно 1 раз по каждому ребру. Возьмем нечетную вершину и будем объединять выходящие из нее ребра в пары, как в док-ве необходимости критерия Эйлера. Обязательно окажется ребро (хотя бы одно!), оставшееся без пары. Значит, оно - крайнее в каком-то из путей, и наша вершина - один из концов этого пути. Таким образом, все нечетные вершины - концы каких-то путей. Но не могут же n-1 (или меньше) путей иметь 2n концов! ч. т.д.

На рисунке изображен граф с 4-мя нечетными вершинами, нарисованный ровно с 1 отрывом карандаша. Тонкие линии - это первый путь, проходящий по ребрам (порядок обхода указан цифрами). Жирные линии - второй путь, обход которого в пояснениях не нуждется. Можно легко увидеть, что каждая нечетная вершина - конец одного из путей, и еще раз понять, почему это происходит.

Утверждение 2: Связный граф с 2n нечетными вершинами можно нарисовать, отрывая карандаш от бумаги ровно n-1 раз и не проводя линий дважды.
Доказательство: Сначала нарисуем какие угодно пути, в общей сложности проходящие 1 раз по каждому ребру. Теперь начнем их сокращать. Если из одной вершины выходят 2 конца разных путей, то эти 2 пути можно слить в один (второй - продолжение первого). Повторяя эти операции, пока возможно, мы получим в итоге разбиение, где в каждой вершине заканчивается максимум 1 путь. Поскольку в любой четной вершине всегда есть четное число концов путей, а в нечетной - нечетное (так как это соответствует четности числа ребер, оставшихся без пары! - см. док-во утв-ния 1), то в четныхвершинах будет теперь ровно 0 концов путей, а в нечетных - ровно 1 конец. Значит, концов путей получилось 2n, откуда самих путей - ровно n, ч. т.д. (при n=0 получится, что имеется 0 концов путей, т. е. 1 большой цикл - как раз эйлеров цикл графа!)

Пример слияния двух путей в один изображен на рисунке. Путь из тонких сплошных линий (помеченных цифрами от 1 до 5) и путь из пунктирных линий (помеченных цифрами от 6 до 11) имеют общий конец (вершину А). Тогда их сливаем в один путь, который был показан тонкими линиями на предыдущем рисунке.

Упражнение: (на умение использоваь критерий Эйлера и утверждения после него) На какое минимальное число кусков нужно разрубить проволоку, чтобы сделать из нее каркас кубика? (ответ - 4)

Лекция 3: Комбинаторика.

Комбинаторика - это математическая наука, грубо говоря, о подсчете числа способов сделать что-либо. Несмотря на узость предмета изучения, наука эта весьма глубока. Кроме того, в олимпиадных задачах комбинаторика используется настолько часто, что ее знание (хотя бы в объеме данной лекции!) совершенно необходимо каждому математику-олимпиаднику.

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

Основные комбинаторные формулы и соображения:

1. Аддитивность взаимоисключающих случаев. Если в комбинаторной задаче имеется (возможно, на каком-то внутреннем этапе) нескольковзаимоисключающих случаев/вариантов выбора, то общее число способов равно сумме количеств способов в каждом из этих случаев.
Это действительно очевидно. Настолько, что в решении задач можно даже не формулировать ;-)

2. Мультипликативность независимых случаев. Если способ (количество которых надо посчитать) полностью определяется несколькиминезависимыми друг от друга этапами выбора (на каждом этапе выбор вариантов - взаимоисключающий!), то общее число способов равно произведениюколичеств вариантов выбора на каждом этапе.
Доказательство: Пусть у нас всего есть k этапов. Обозначим количество вариантов выбора на первом этапе - n1, на втором этапе - n2... на последнем - nk. На первом этапе у нас есть n1 вариантов выбора, т. е. образуется n1 случаев. На втором этапе в каждом из этих случаев мы может выбрать любой (т. к. этапы независимы) из n2 вариантов, образовав n2 подслучаев. Таким образом, после двух этапов будет уже n1*n2 случаев. На третьем этапе в каждом из них мы можем выбрать любой из n3 вариантов... и после трех этапов будет n1*n2*n3 случаев. Продолжая этот процесс, мы получаем после всех этапов n1*n2*...*nk случаев - и это будут уже окончательные способы. Их количество как раз равно произведению количеств вариантов выбора, ч. т.д.
Опять же, в решении задач это свойство можно даже не формулировать... если вы уверены, что применили его в правильной ситуации ;-)

(!) На самом деле, доказывая п.2, мы пользуемся утверждением п.1. Например, как подробнее объяснить, почему после двух этапов есть n1*n2 случаев? У нас есть взаимоисключающие случаи - варианты выбора на первом этапе, которых n1 штук. В каждом из них есть n2 способов сделать выбор на двух этапах (на первом этапе вариант уже известен, осталось выбрать n2 вариантов на втором этапе). А чтобы найти общее число способов сделать выбор на первых двух этапах, надо (в соответствии с п.1) сложить n1 чисел, равных n2, т. е. умножить n1 на n2, ч. т.д.

2'. Общее правило мультипликативности подслучаев. Если способ полностью определяется несколькими, возможно зависимыми друг от друга, этапами выбора, но количество вариантов выбора на каждом этапе не зависит от того, как был сделан выбор на предыдущих этапах, то общее число способов равно произведению количеств вариантов выбора на каждом этапе.
Доказательство: Ничем не отличается от доказательства п.2, т. к. там мы пользовались независимостью от предыдущих этапов выбора только количества вариантов на данном этапе.

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