Статьи
Теория графов
Решение задач методом Графов.
Во многих ситуациях удобно изображать объекты точками, а связи между ними - линиями или стрелками. Такой способ предоставления называется графом . Например схема метро - это граф. Точки называют вершинами графа, а линии - ребрами. Вершину называют четной, если из нее выходит четное число ребер и нечетной в противном случае. Граф называют связным, если между любыми вершинами существует путь, состоящий из ребер графа, ориентированным - если на каждом ребре указано направление, плоским - если он нарисован на плоскости и его ребра не пересекаются (во внутренних точках). При решении многих олимпиадных задач используются следующие утверждения, относящиеся к обходу ребер графа:
Если в графе больше двух нечетных вершин, то его правильный обход (т.е. обход, при котором каждое ребро приходится ровно один раз) невозможен;
Для всякого четного связного графа существует правильный обход, который можно начать с любой вершины и который обязательно кончается в той же вершине, с которой начался.
Если в связном графе ровно две нечетные вершины, то существует правильный обход, причем в одной из них он начинаеться, а в другой - заканчивается;
В любом графе количество нечетных вершин четно.
В углах шахматной доски 3х3 стоят 4 коня: 2 белых и 2 черных (смотрите рисунок). Можно ли за несколько ходов (по шахматным правилам, конь ходит буквой "Г") поставить коней так, что бы во всех соседних углах стояли кони разного цвета?
Решение.Отметим центры клеток доски и соединим отрезками пары отмеченных точек, если из одной в другую можно перейти ходом коня. Мы получим граф (смотри рисунок), содержащий цикл из восьми точек и одну изолированную точку (центральная точка). Перемещение коней по доске соответствует движению по ребрам этого цикла. Проследив за перемещениями коней, становиться ясно, что при движении по циклу нельзя попасть в соседний угол. Вот так, просто и красиво решаются при помощи графов на первый взгляд сложные задачи.
.
