Графы.
Есть много разных задач, которые удобно решать, нарисовав граф. Граф — это несколько точек, некоторые из которых соединены линиями. Графы могут выглядеть так:
Точки в графе называются вершинами и чаще всего обозначаются жирными точками, кружками или другими фигурками, чтобы можно было отличить вершины от точек пересечения линий. Линии, соединяющие вершины графа, называются рёбрами графа. Рёбра графа могут быть прямыми или кривыми, могут пересекаться друг с другом.
Бывает так, что две вершины графа соединены несколькими рёбрами или одна вершина соединена ребром сама с собой. Мы будем пока рассматривать и рисовать только простые графы, в которых таких ребер нет.
1. Рисуем граф.
Задача 1.
В 1 «а» классе некоторые мальчики при встрече здороваются за руку (обмениваются рукопожатиями). Сегодня Антон пожал руку Боре, Ване и Грише, Гриша пожал руку Ване, Дане и Антону, а Даня обменялся рукопожатиями с Борей и Гришей. Сколько всего рукопожатий было сегодня в 1″а» классе? Сколько раз поздоровался за руку Боря?
Решение.
Нарисуем граф, в котором вершинами будут мальчики Антон, Боря, Ваня, Гриша и Даня. Если два мальчика пожали друг другу руки, то соединим соответствующие им вершины ребром.
Теперь, чтобы узнать общее количество рукопожатий, нужно просто сосчитать все рёбра графа. Их 6.
А чтобы узнать, во скольких рукопожатиях участвовал Боря, нужно посчитать рёбра, выходящие из соответствующей вершины. Их 2: Боря поздоровался за руку с Антоном и Даней.
Ответ: Всего 6 рукопожатий. Боря поздоровался за руку 2 раза.
Задача 2.
В королевском дворце есть 5 парадных залов: Золотой, Серебряный, Бриллиантовый, Рубиновый и Янтарный. Из каждого зала выходят коридоры, каждый коридор соединяет два зала, и между каждыми двумя залами есть не больше одного коридора. Из Золотого зала выходят 4 коридора, из Серебряного — 3, из Бриллиантового — 2, из Рубинового — 1. Сколько коридоров выходит из Янтарного зала?
Решение.
Начнем рисовать граф, в котором вершинами будут залы, а рёбрами — коридоры между залами. В вершинах графа напишем количество коридоров, выходящих из соответствующих залов.
Всего залов 5, из Золотого зала выходит 4 коридора, значит, Золотой зал соединён коридорами со всеми остальными залами:
Теперь проведем коридоры, выходящие из Серебряного зала. Один коридор, соединяющий этот зал с Золотым, уже есть, нужно провести еще два коридора. В Рубиновый зал коридор из Серебряного зала провести нельзя, так как из Рубинового выходит только 1 коридор, и он уже указан на графе. Значит, мы можем провести из Серебряного зала коридоры только в Бриллиантовый и в Янтарный зал:
Теперь можно увидеть, что полученный граф — это полная схема залов и коридоров: всего коридоров 6 и из каждого зала, кроме Янтарного, выходит столько коридоров, сколько указано в условии задачи. По-другому мы расположить коридоры не могли. Значит, найденные коридоры для Янтарного зала — это единственное решение задачи. Из Янтарного зала выходит 2 коридора.
Ответ: 2 коридора.
2. Ищем пути на графе.
Два ребра графа называются соседними, если они выходят из одной вершины.
Путь в графе от вершины А до вершины Б — это последовательность соседних рёбер, соединяющих вершины А и Б.
На рисунке показаны примеры путей из вершины А в вершину Б. Часто бывает так, что из одной вершины графа в другую ведут несколько разных путей (в последнем графе разные пути показаны разными цветами):
Задача 3.
В Цветочном городе проложили метро. Сейчас в нем 7 станций: Васильковая, Ромашковая, Одуванчиковая, Ландышевая, Незабудковая, Колокольчиковая, Подснежниковая. Часть пути метро, соединяющая две соседние станции, называется перегоном. В метро Цветочного города 9 перегонов:
- Васильковая — Ромашковая
- Ландышевая — Ромашковая
- Васильковая — Ландышевая
- Незабудковая — Подснежниковая
- Подснежниковая — Одуванчиковая
- Колокольчиковая — Подснежниковая
- Ландышевая — Одуванчиковая
- Одуванчиковая — Колокольчиковая
- Ландышевая — Незабудковая
Можно ли на метро добраться от станции Подснежниковая до станции Васильковая? Сколькими способами это можно сделать?
Решение.
В этой задаче без графа не обойтись. Нарисуем граф — карту метро Цветочного города. Вершины графа — станции, рёбра графа — перегоны. Обозначим вершины графа первыми буквами названий соответствующих станций:
Требуется узнать, есть ли в этом графе путь от вершины П до вершины В. Такой путь есть, и не один. На рисунке отмечены 6 разных путей от Подснежниковой до Васильковой:
Пути из Подснежниковой в Одуванчиковую можно обозначить так:
- П-Н-Л-Р-В
- П-Н-Л-В
- П-О-Л-В
- П-К-О-Л-В
- П-О-Л-Р-В
- П-К-О-Л-Р-В
Ответ: можно, 6 способами.
Задача 4.
На 1 декабря в метро Цветочного города (см. задачу 3) запланированы профилактические работы. В этот день перегоны Подснежниковая-Незабудковая и Одуванчиковая-Ландышевая будут закрыты. Можно ли будет 1 декабря добраться со станции Подснежниковой до станции Васильковой?
Решение.
1 декабря карта метро Цветочного города будет выглядеть так (обозначим запрещающими знаками неработающие перегоны):
То есть фактически в графе будут отсутствовать рёбра, соответствующие этим перегонам:
Можно увидеть, что в этом случае граф распадается на две отдельные части, не связанные между собой. И вершина П находится в одной из этих частей, а вершина В — в другой. Следовательно, в графе нет пути, соединяющего вершины П и В, добраться от Подснежниковой до Васильковой на метро будет невозможно.
Ответ: нельзя.
3. Ориентированные графы.
В рассмотренных выше задачах связи между персонажами были симметричные:
- если Гриша пожимал руку Дане, то и Даня пожимал руку Грише;
- если есть коридор, соединяющий Золотой зал с Серебряным, то этот же коридор соединяет Серебряный зал с Золотым.
- если есть в метро перегон «Васильковая — Ромашковая», то этот же перегон является перегоном «Ромашковая — Васильковая».
Но бывают и несимметричные связи между объектами:
- если число А больше числа Б, то число Б меньше числа А;
- если Иван старше Фёдора, то Фёдор младше Ивана;
- если Маша выиграла у Саши партию в шашки, то Саша Маше эту партию проиграл.
Такие связи в графах изображаются стрелками, а граф называется ориентированным.
Задача 5.
Среди шести подружек Аня младше Даши, но старше Кати и Вали; Галя старше Вали и Жени, но младше Даши; Женя младше Кати, а Катя и Валя близнецы. Кто старше: Женя или Даша?
Решение.
Нарисуем граф, в котором вершины — это девочки, обозначим вершины первыми буквами имен девочек. А связи между девочками изобразим стрелками, ведущими от старшей девочки к младшей. Например, выражению «Аня старше Вали» в графе будет соответствовать стрелка:
Получится такой граф:
По этой схеме хорошо видно, что есть путь по стрелкам в направлении от Даши к Жене: Даша старше Гали, Галя старше Жени.
Есть и другой путь: Даша старше Ани, Аня старше Кати, Катя старше Жени.
Значит, Даша старше Жени.
Ответ: Даша старше Жени.