Элементы теории графов.
Предмет: Математика, 5 класс
Автор: Вольфсон Георгий Игоревич

Всем привет!

Вы никогда не задумывались, почему в детстве (да и не только) мы предпочитаем книжки с картинками? Пожалуй, главное: с помощью картинок информация становится нагляднее и зачастую – понятнее. Именно поэтому даже на самых важных встречах люди очень часто используют проектор и показывают картинки, на которых изображены графики, таблицы и схемы, подтверждающие слова рассказчика.

Примерно за этим в математике и нужна теория графов. Но позвольте, при чём тут вообще графы? Это ж титул такой, вроде маркиза или барона. На самом деле, речь здесь идёт о графе, однокоренном с «графический», то есть, от английского graph (график, диаграмма). Так что сегодня мы увидим один из способов графического представления данных задачи, который существенно упрощает решение, делая его более наглядным. Но начнем мы не с задач, а с небольшой теории – не зря же урок назван «Теория графов». Но не бойтесь, всё пройдёт быстро и безболезненно.

Итак, графом называют совокупность вершин (их может быть сколько угодно, но не 0), а также набора рёбер, связывающих пары вершин. Вот несколько примеров графов:

Точки на данных рисунках – вершины, а отрезки, которые их соединяют – рёбра. Формально, не запрещено проводить два ребра из одной вершины в другую, а также не запрещены «дуги» – рёбра, соединяющие вершину с самой собой. Какие бывают примеры графов в реальной жизни? Да сколько угодно! Например, карта метро – типичный граф. Смотрите: станции – это вершины, а рёбра – «перегоны» между станциями.

Кстати, заметьте: на метро, как видно по данной карте, можно проехать с одной станции на любую другую. Если в графе можно из любой вершины добраться до любой другой, такой граф называют связным. Если же нельзя – несвязным. Соответственно, метро – связный граф. Если же рассмотреть автомобильную карту всего мира, где города – вершины, а дороги между ними – рёбра, то граф получится несвязным, ведь в Рио-де-Жанейро из Москвы добраться не получится, через океан нет дороги! Что ж, пока вы ещё не совсем уснули, пора срочно переходить к задачам!

Задача 1. Между девятью планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам (все маршруты – двусторонние): Земля – Меркурий, Плутон – Венера, Земля – Плутон, Плутон – Меркурий, Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер, Юпитер – Марс и Марс – Уран. Можно ли добраться с Земли до Марса?

Решение. Ответить на вопрос задачи сходу трудно – слишком много данных. Зато если нарисовать – всё будет легко! Итак, пусть планеты будут вершинами, а рёбрами мы соединим те из них, между которыми есть ракетные маршруты. И тогда задача сводится к вопросу, есть ли путь в графе от вершины «Земля» до вершины «Марс»? Путём в графе, как нетрудно догадаться, называют путь от одной вершины к другой, идущий по рёбрам графа.

Итак, что же получилось? Вот такая картинка:

А здесь ответ очевиден: от Земли до Марса не добраться! Кстати, такие части графа, как мы видим на картинке, называются компонентами связности – в них мы из каждой вершины можем добраться до каждой, но вне этой компоненты – никуда. Ну а исходный граф, разумеется, не является связным. Заодно, ещё одно важное определение. Если в графе существует такой путь из вершины в неё же саму, такой путь называется циклом – вполне логично. В такие моменты возникает ощущение, что те, кто это придумал, были не такими уж глупыми людьми!

Кстати, заметили в условии задачи указание, что маршруты идут в обе стороны? А если бы это было не так? Логично было бы как-то учесть это при рисовании графа. И для этого существуют специальные понятия и обозначения. Графы, которые мы рассматривали до этого, называют неориентированными: на них нет указания направления рёбер. А если указать направление – получаем ориентированный граф, где направления указывают вполне разумно – стрелочками. Так что карта автодорог – ориентированный граф, ведь по некоторым дорогам есть только одностороннее движение.

Ориентированные графы также полезны при решении задач. Разберём это на таком несложном примере:

Задача 2. Из лагеря вышли четыре туриста: Вася, Галя, Толя и Лена. Вася идёт впереди Лены, Толя впереди Гали, а Лена – впереди Толи. В каком порядке идут дети?

Решение. Опять же, разобраться без картинки можно, но не так просто. А если нарисовать граф – всё станет легко! Пусть вершины – это ребята, а ребром со стрелочкой отметим пары, про которые мы знаем, кто идёт впереди. При этом если Вася впереди Лены, то проведем ребро, которое ведёт из вершины «Лена» в вершину «Вася». Получим такой граф:

А здесь никаких сомнений: первым шел Вася, второй – Лена, третьим – Толя, четвёртой – Галя.

И ещё одно важное понятие в теории графов – дерево. Деревом называют связный граф без циклов. То есть, например, граф из первой задачи – не дерево аж по двум причинам (несвязный, есть циклы), а из второй – дерево. Подробно о деревьях говорить мы сегодня не будем, обсудим лишь очень важное для нас применение деревьев – деревья возможностей. Я покажу их использование на примере.

Задача 3. В столовой на горячее можно заказать щуку, грибы и баранину, на гарнир – картофель и рис. Сколько различных вариантов обедов можно составить из указанных блюд?

Решение. Уверен, сиди вы сейчас на моём уроке, некоторые бы уже завопили: «Конечно, 5!» А другие бы столь же громко: «Конечно, 6!» (меня как учителя всегда радуют эти уверенные «конечно», раздающиеся при абсолютно несовместимых ответах). Не буду пока комментировать, чей ответ верен (возможно, ничей!), задам лишь один вопрос: а почему? Почему 5? Почему 6? Вы можете мне ответить: 3 горячих, 2 гарнира, 2 напитка, значит 3 + 2 = 5. А другие скажут: . А почему мы складываем? Почему умножаем? Загадка. Можно, конечно, попытаться перебрать все варианты, но как при этом не пропустить что-то? И вот тут на помощь снова приходят графы.

Допустим, некто Антон пришёл в столовую. Первым делом он заказывает горячее – у него три способа это сделать. Изобразим это так:

Далее, в каждом из этих трёх случаев Антон может взять любой из двух гарниров: картофель или рис. Проведём по два ребра от каждой из трёх вершин:

Получили мы нечто, отдалённо напоминающее ветку дерева – отсюда и название! А теперь ответить на вопрос задачи проще простого: все варианты у нас указаны на самом нижнем уровне – их там 6 штук. Так что правильно – 6. Кстати, а что было бы, если в столовой предлагали бы ещё на выбор чай или кофе? Именно, к каждой из 6 вершин мы дорисовали бы по 2 ребра вниз, и в нижнем уровне стало бы = 12 вершин. Так что вариантов обеда было бы 12.

Напоследок – важное замечание. Конечно, в этих довольно простых задачах можно было бы обойтись и без графов. Про первые две даже не говорю, а в последней можно было бы провернуть такое рассуждение из области комбинаторики: основное блюдо – 3 варианта, а для каждого из них есть 2 варианта гарнира, значит, по правилу произведения, получается 6 вариантов обеда. Согласен, разумеется, можно и так. Но, во-первых, графы сделали данные решения нагляднее и проще, а во-вторых, сегодня вы познакомились с очень важным инструментом, без которого некоторые гораздо более сложные задачи будет просто не решить! Всё равно, что, например, велосипед: можно ли обойтись без него, когда нужно проехать 10 метров? Конечно, пешком даже проще. А если нужно проехать 10 км? Тогда пешком сложнее и намного дольше. Но учиться-то мы начинаем именно с проезжания 10 метров! Так и с графами – мы ещё увидимся с ними не раз!

До встречи!

1. Дополнительная информация

Рекомендуемые тренажёры:

1. Докажите, что не существует графа с пятью вершинами, степени которых равны 4, 4, 4, 4, 2 (степенью вершины в графе называют количество выходящих из неё рёбер).

2. В детском лагере отдыха в одной комнате живут четыре девочки: Маша, Валя, Таня и Галя. Две из них ровесницы. Известно, что Таня старше Маши, которая моложе Гали. Таня моложе Вали, которая старше Гали. Кто ровесницы? Ответ: Таня и Галя

3. В шахматном турнире участвовали 4 человека. Каждый спортсмен сыграл со всеми другими участниками соревнований по одному разу. Сколько всего было сыграно партий? Ответ: 6

Рекомендуемые тесты:

1. В стране алфавит 8 городов: А, Б, В, Г, Д, Е, Ж, З и восемь непересекающихся дорог между городами А и Б, Е и Д, Б и Ж, З и А, В и Г, Г и Д, Ж и З, В и Е. Можно ли по этим дорогам проехать из А в Г? Ответ: нет.

2. У Серёжи есть 5 пиджаков, 4 пары брюк и 7 рубашек. Сколько вариантов выбрать сочетание рубашки, брюк и пиджака есть у Серёжи? Ответ: 140.

3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединён ровно с пятью другими? Ответ: Нет.