Теория графов при решении логических и вероятностных задач

«Теория графов при решении

логических и вероятностных задач»

Эйлер вычислял без всякого видимого усилия,

как человек дышит или как орёл парит над землёй.

Доминик Араго

Любая точная наука изучает не сами явления, протекающие в природе, в обществе, а их математические модели, т. е. описание явлений при помощи набора строго определенных символов и операций над ни­ми. В математике и смежных с ней дисциплинах существует класс задач, которые наиболее просто и понятно решаются с применением теории графов. Это замечательные математические объекты, применяя которые можно решать математические и логические задачи.

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). История возникновения этой теории начинается со знаменитой задачи про Кенигсбергские мосты и уходит в 1736 год. (Можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Р)

Основные определения и теоремы теории графов

Графом в математике называется конечная совокупность точек, именуемых вершинами; некоторые из них соединены друг с другом линиями, называемых ребрами графа.

При взгляде на географическую карту сразу бросается в глаза сеть железных дорог. Это типичный граф: кружочки обозначают станции - вершины графа, а соединяющие их пути - ребра.

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

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

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

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями. Теперь нам видно, что долететь с Земли до Марса на рейсовых ракетах нельзя.

Задача 2. В одном городе шесть станций метро: Алмазная, Золотая, Лесная, Парковая, Садовая, Серебряная. Поезда следуют по маршрутам Алмазная – Золотая, Золотая – Серебряная, Серебряная – Алмазная. Лесная – Садовая, Садовая – Парковая, Парковая – Лесная. Можно ли с помощью этих поездов добраться со станции Парковая до станции Алмазная?

Решение: Нарисуем картинку, на которой будем отмечать станции точками, а соединяющие их маршруты – непересекающимися линиями.

Ответ: добраться со станции Парковая до станции Алмазная нельзя.

Мы рассмотрели три непохожие задачи. Однако решения этих двух задач объединяет общая идея – графическое представление решения. При этом и картинки, нарисованные для каждой задачи, оказались похожими: каждая картинка – это несколько точек, некоторые из которых соединены линиями. Такие картинки и называются графами. Точки при этом называются вершинами, а линии – ребрами графа. Заметим, что не каждая картинка такого вида будет называться графом. Например. если нарисовать в тетради пятиугольник, то такой рисунок графом не будет.

Граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными

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

Обозначать граф будем буквой Г. При изображении графов на рисунках или схемах отрезки могут быть прямолинейными и криволинейными; длины отрезков и расположение точек произвольны. Например, все три фигуры на рисунке изображает один и тот же граф.

1.3.Виды графов.

1.Ориентированный граф (кратко орграф) — рёбрам которого присвоено направление.

2.Неориентированный граф - это граф, в котором нет направления линий.

3.Взвешенный граф – дуги или ребра имеют вес.

4. Связный граф.Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.

Д ве вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их.

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

Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф.

Задачи, решаемые при помощи графов

Знаменитые задачи

Задача коммивояжера является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё обламывали зубы лучшие математики.

Постановка задачи следующая. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,4,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Метод решения задачи коммивояжера

Жадный алгоритм “иди в ближайший (в который еще не входил) город”.“Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность. Рассмотрим для примера сеть на рис.. , представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди в ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

Задача о Кенигсбергских мостах.

З адача формулируется следующим образом.
Город Кенигсберг расположен на берегах реки Прегель и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу. Вопрос: можно ли совершить прогулку таким образом,  чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту. Мосты через реку Прегель расположены как на рисунке .

Рассмотрим граф, соответствующий схеме мостов

Чтобы ответить на вопрос задачи, достаточно выяснить, является ли граф эйлеровым. (Хотя бы из одной вершины должно выходить четное число мостов). Нельзя, прогуливаясь по городу, пройти по одному разу все мосты и вернуться обратно.

Несколько интересных задач

1. "Маршруты".

Задача 1

Как вы помните, охотник за мертвыми душами Чичиков побывал у известных помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжолго, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их. Установите, какое имение кому принадлежит, если ни одной из дорог Чичиков не проезжал более одного раза.

Решение:

По схеме дорог видно, что путешествие Чичиков начал с имения Е, а окончил имением О. Замечаем, что в имения В и С ведут только две дороги, поэтому по этим дорогам Чичиков должен был проехать. Отметим их жирной линией. Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их. Отметим жирной линией ЕD ; перечеркнем DK . Перечеркнем МО и МН; отметим жирной линией MF; перечеркнем FO; отметим жирной линией FH, НК и КО. Найдем единственно возможный при данном условии маршрут. И получаем: имение Е – принадлежит Манилову, D- Коробочке, С – Ноздреву, А – Собакевичу, В – Плюшкину, М – Тентетникову, F - Бетрищеву, Н – Петуху, К – Констанжолго, О – Кошкареву.

Задача 2 На рисунке изображена схема местности

Передвигаться можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? Какой маршрут самый короткий и какой — самый длинный.

Решение:

Последовательно "расслаиваем" схему в дерево, начиная с вершины 1. Получим дерево. Число возможных способов попадания из 1 в 9 равно числу "висячих" вершин дерева (их 14). Очевидно, кратчайший путь-1-5-9; самый длинный - 1-2-3-6-5-7-8-9.

2 "Группы, знакомства"

Задача 1

Однажды Андрей, Борис, Володя, Даша и Галя договорились вечером пойти в кино. Выбор кинотеатра и сеанса они решили согласовать по телефону. Было также решено, что если с кем-то созвониться не удастся, то поход в кино отменяется. Вечером у кинотеатра собрались не все, и поэтому посещение кино сорвалось. На следующий день стали выяснять, кто кому звонил. Оказалось, что Андрей звонил Борису и Володе, Володя звонил Борису и Даше, Борис звонил Андрею и Даше, Даша звонила Андрею и Володе, а Галя звонила Андрею, Володе и Борису. Кто не сумел созвониться и поэтому не пришёл на встречу?

Р ешение:

Нарисуем пять точек и обозначим их буквами А, Б, В, Г, Д.

Это первые буквы имён. Соединим те точки, которые

соответствуют именам созвонившихся ребят. Из рисунка видно,

что каждый из ребят – Андрей, Борис и Володя - созвонились со всеми

остальными. Поэтому эти ребята и пришли к кинотеатру. А Галя

и Даша не сумели созвониться между собой (точки Г и Д не соединены отрезком) и поэтому в соответствии с договорённостью в кино не пришли.

Применение графов в различных областях жизни людей

Кроме приведенных примеров, графы широко используются в строительстве, электротехнике, менеджменте, логистике, географии, машиностроении, социологии, программировании, автоматизации технологических процессов и производств, психологии, рекламе.

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

Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.

Обычно у дерева, представляющего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. Каждая вершина дерева (кроме корня) имеет только одного предка – обозначенный ею объект входит в один класс верхнего уровня. Любая вершина дерева может порождать несколько потомков – вершин, соответствующих классам нижнего уровня.

Для каждой пары вершин дерева существует единственный путь, их соединяющий. Этим свойством пользуются при нахождении всех предков, например, по мужской линии, любого человека, чья родословная представлена в виде генеалогического дерева, которое является «деревом» и в смысле теории графов.

Применим эту теорию и для практико-ориентированной задачи.

Транспортная задача. Пусть в городе Краснодаре находится база с сырьём, которое нужно развести по городам Крымск, Темрюк, Славянск-на-Кубани и Тимашевск одним заездом, затратив при этом как можно меньше времени и топлива и вернувшись обратно в Краснодар.

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

Для удобства решения обозначаем

города цифрами: Краснодар – 1,

Крымск – 2, Темрюк – 3, Славянск – 4,

Тимашевск – 5.В результате вышло 24

решения, но нам нужны только

кратчайшие пути. Из всех решений

удовлетворяют только два, это 350 км.

Подобно этому можно и, я думаю,

нужно рассчитывать реальные

перевозки из одного населенного

пункта в другие.

Л огическая задача на переливание. В ведре 8 л воды,

и имеется две кастрюли емкостью 5 и 3 л. требуется

отлить в пятилитровую кастрюлю 4 л воды и оставить

в ведре 4 л, т. е. разлить воду поровну в ведро и

большую кастрюлю.

Решение:

Ситуацию в каждый момент можно описать

тремя числами. В результате получаем два решения:

одно в 7 ходов, другое в 8 ходов.

 Итак, для того чтобы школьникам научиться решать задачи, надо помочь им разобраться в том, что собой они представляют, как они устроены, из каких составных частей они состоят, каковы инструменты, с помощью которых производится решение задач.

Решая практические задачи с помощью теории графов необходимо в каждом шаге, в каждом этапе их решения применить творчество.

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

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

Спасибо за внимание.

Рис. 5

3