Графы.
Есть много разных задач, которые удобно решать, нарисовав граф. Граф — это несколько точек, некоторые из которых соединены линиями. Графы могут выглядеть так:
Точки в графе называются вершинами и чаще всего обозначаются жирными точками, кружками или другими фигурками, чтобы можно было отличить вершины от точек пересечения линий. Линии, соединяющие вершины графа, называются рёбрами графа. Рёбра графа могут быть прямыми или кривыми, могут пересекаться друг с другом.
Степенью вершины графа называется количество рёбер, выходящих из этой вершины, то есть для которых эта вершина является одним из концов. На рисунке числа обозначают степени вершин графов:
Бывает так, что две вершины графа соединены несколькими рёбрами или одна вершина соединена ребром сама с собой. Мы будем пока рассматривать и рисовать только простые графы, в которых таких ребер нет.
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.
Среди шести подружек Аня младше Даши, но старше Кати и Вали; Галя старше Вали и Жени, но младше Даши; Женя младше Кати, а Катя и Валя близнецы. Кто из девочек самая старшая, а кто самая младшая?
Решение.
Нарисуем граф, в котором вершины — это девочки, обозначим вершины первыми буквами имен девочек. А связи между девочками изобразим стрелками, ведущими от старшей девочки к младшей. Например, выражению «Аня старше Вали» в графе будет соответствовать стрелка:
Получится такой граф:
Если мы сможем дорисовать стрелки так, чтобы они соединяли каждую девочку с каждой из остальных (то есть сделать граф полным), то самой старшей девочке будет соответствовать вершина, из которой стрелки только выходят, а самой младшей — вершина, в которую вершины только входят.
Мы можем дорисовать стрелки, основываясь на том, что если А старше Б, а Б старше В, то А старше В. То есть, если в графе есть, например, стрелка из вершины А в вершину К, а из вершины К в вершину Ж, то мы можем провести стрелку из вершины А в вершину Ж, не нарушив условий задачи:
Кроме того, мы можем провести стрелки, учитывая, что Катя и Валя близнецы (то есть одного возраста). Например, если есть стрелка из вершины К в вершину Ж (Катя старше Жени), то можем провести и стрелку из вершины В в вершину Ж (Валя старше Жени, так как Валя с Катей близнецы):
В этой задаче дорисовать граф до полного не получится, поскольку Катя и Валя близнецы, мы не можем нарисовать между ними стрелки. Кроме того, из условия задачи невозможно сделать вывод о том, кто старше — Аня или Галя. Дорисовав все возможные стрелки, получаем такой граф:
Но и этого рисунка достаточно, чтобы ответить на вопрос задачи.
Вершина Д — единственная, из которой стрелки только выходят и ведут они ко всем остальным вершинам, значит Даша — самая старшая из девочек. Вершина Ж — единственная, в которую стрелки только входят, причем из всех остальных вершин. Значит, Женя — самая младшая из девочек.
Ответ: Самая старшая — Даша, самая младшая — Женя.