Неделя 28: теория 1 класс (с 27 марта по 3 апреля)

Графы.

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

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

Бывает так, что две вершины графа соединены несколькими рёбрами или одна вершина соединена ребром сама с собой. Мы будем пока рассматривать и рисовать только простые графы, в которых таких ребер нет.

1. Рисуем граф.

Задача 1.
В 1 «а» классе некоторые мальчики при встрече здороваются за руку (обмениваются рукопожатиями). Сегодня Антон пожал руку Боре, Ване и Грише, Гриша пожал руку Ване и Дане, Даня обменялся рукопожатиями с Борей. Сколько всего рукопожатий было сегодня в 1″а» классе? Сколько раз поздоровался за руку Гриша?

Решение.
Нарисуем граф, в котором вершинами будут мальчики Антон, Боря, Ваня, Гриша и Даня. Если два мальчика пожали друг другу руки, то соединим соответствующие им вершины ребром.

Теперь, чтобы узнать общее количество рукопожатий, нужно просто сосчитать все рёбра графа. Их 6.
А чтобы узнать, во скольких рукопожатиях участвовал Гриша, нужно посчитать рёбра, выходящие из соответствующей вершины.  Их 3: Гриша поздоровался за руку с Антоном, Ваней и Даней.

Ответ: Всего 6 рукопожатий. Гриша поздоровался за руку 3 раза.

Задача 2.
В королевском дворце есть 5 парадных залов: Золотой, Серебряный, Бриллиантовый, Рубиновый и Янтарный. Из каждого зала выходят коридоры, каждый коридор соединяет два зала, и между каждыми двумя залами есть не больше одного коридора. Из Золотого зала выходят 4 коридора, из Серебряного — 3, из Бриллиантового — 2, из Рубинового — 1. Сколько коридоров выходит из Янтарного зала?

Решение.
Начнем рисовать граф, в котором вершинами будут залы, а рёбрами — коридоры между залами. В вершинах графа напишем количество коридоров, выходящих из соответствующих залов.
Всего залов 5, из Золотого зала выходит 4 коридора, значит, Золотой зал соединён коридорами со всеми остальными залами:

Теперь проведем коридоры, выходящие из Серебряного зала. Один коридор, соединяющий этот зал с Золотым, уже есть, нужно провести еще два коридора. В Рубиновый зал коридор из Серебряного зала провести нельзя, так как из Рубинового выходит только 1 коридор, и он уже указан на графе. Значит, мы можем провести из Серебряного зала коридоры только в Бриллиантовый и в Янтарный зал:

Теперь можно увидеть, что полученный граф — это полная схема залов и коридоров: всего коридоров 6 и из каждого зала, кроме Янтарного, выходит столько коридоров, сколько указано в условии задачи. По-другому мы расположить коридоры не могли. Значит, найденные коридоры для Янтарного зала — это единственное решение задачи. Из Янтарного зала выходит 2 коридора.

Ответ: 2 коридора.

2. Ищем пути на графе.

Два ребра графа называются соседними, если они выходят из одной вершины.
Путь в графе от вершины А до вершины Б — это последовательность соседних рёбер, соединяющих вершины А и Б.

На рисунке показаны примеры путей из вершины А в вершину Б. Часто бывает так, что из одной вершины графа в другую ведут несколько разных путей (в последнем графе разные пути показаны разными цветами):

Задача 3.
В Цветочном городе проложили метро. Сейчас в нем 7 станций: Васильковая, Ромашковая, Одуванчиковая, Ландышевая, Незабудковая, Колокольчиковая, Подснежниковая. Часть пути метро, соединяющая две соседние станции, называется перегоном. В метро Цветочного города 9 перегонов:

• Васильковая — Ромашковая
• Ландышевая — Ромашковая
• Васильковая — Ландышевая
• Незабудковая — Подснежниковая
• Подснежниковая — Одуванчиковая
• Колокольчиковая — Подснежниковая
• Ландышевая — Одуванчиковая
• Одуванчиковая — Колокольчиковая
• Ландышевая — Незабудковая

Можно ли на метро добраться от станции Подснежниковая до станции Васильковая? Сколькими способами это можно сделать?

Решение.
В этой задаче без графа не обойтись. Нарисуем граф — карту метро Цветочного города. Вершины графа — станции, рёбра графа — перегоны. Обозначим вершины графа первыми буквами названий соответствующих станций:

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

Пути из Подснежниковой в Одуванчиковую можно обозначить так:

1. П-Н-Л-Р-В
2. П-Н-Л-В
3. П-О-Л-В
4. П-К-О-Л-В
5. П-О-Л-Р-В
6. П-К-О-Л-Р-В

Ответ: можно, 6 способами.

Задача 4.
На 1 мая в метро Цветочного города (см. задачу 3) запланированы профилактические работы. В этот день перегоны Подснежниковая-Незабудковая и Одуванчиковая-Ландышевая будут закрыты. Можно ли будет 1 мая добраться со станции Подснежниковой до станции Васильковой?

Решение.
1 мая карта метро Цветочного города будет выглядеть так (обозначим запрещающими знаками неработающие перегоны):

То есть фактически в графе будут отсутствовать рёбра, соответствующие этим перегонам:

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

Ответ: нельзя.

3. Одинаковые графы.

Графы называются одинаковыми, если в них одинаковое количество вершин, а рёбра изображают одинаковые связи между вершинами.

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

Задача 5.
Богатыри Илья Муромец и Добрыня Никитич сражались один на один с тремя злодеями: Соловьем-Разбойником, Тугарином-Змеем и Змеем Горынычем. Каждый богатырь провел не более одного боя с каждым из злодеев. У Ильи Муромца были бои со всеми тремя злодеями. Соловей-Разбойник и Тугарин-Змей боролись и с Ильёй, и с Добрыней. А Змей Горыныч померился силами только с одним из богатырей. Сколько всего боёв было? С какими злодеями сражался Добрыня Никитич?

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

В зависимости от расположения вершин и рёбер, могут получиться такие графы:

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

Общее количество боёв — это количество рёбер графа. Их 5.
Чтобы узнать, с какими злодеями сражался Добрыня Никитич, нужно посмотреть, с какими вершинами соединена рёбрами вершина ДН. Это вершины СР (Соловей-Разбойник) и ТЗ (Тугарин-Змей).

Ответ: Всего проведено 5 боёв. Добрыня сражался с Соловьём и Тугарином.

4. Ориентированные графы.

В рассмотренных выше задачах связи между персонажами были симметричные:

• если Гриша пожимал руку Дане, то и Даня пожимал руку Грише;
• если богатырь сражался со злодеем, то и злодей сражался с богатырем;
• если есть коридор, соединяющий Золотой зал с Серебряным, то этот же коридор соединяет Серебряный зал с Золотым.

Но бывают и несимметричные связи между объектами:

• если число А больше числа Б, то число Б меньше числа А;
• если Иван старше Фёдора, то Фёдор младше Ивана;
• если Маша выиграла у Саши партию в шашки, то Саша Маше эту партию проиграл.

Такие связи в графах изображаются стрелками, а граф называется ориентированным.

Задача 6.
Среди шести подружек Аня младше Даши, но старше Кати и Вали; Галя старше Вали и Жени, но младше Даши; Женя младше Кати, а Катя и Валя близнецы. Кто старше: Женя или Даша?

Решение.
Нарисуем граф, в котором вершины — это девочки, обозначим вершины первыми буквами имен девочек. А связи между девочками изобразим стрелками, ведущими от старшей девочки к младшей. Например, выражению «Аня старше Вали» в графе будет соответствовать стрелка:

Получится такой граф:

По этой схеме хорошо видно, что есть путь по стрелкам в направлении от Даши к Жене: Даша старше Гали, Галя старше Жени.
Есть и другой путь: Даша старше Ани, Аня старше Кати, Катя старше Жени.
Значит, Даша старше Жени.

Ответ: Даша старше Жени.