Теория графов. Основные понятия

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

История возникновения теории графов
Математические графы с дворянским титулом "граф" связывает общее происхождение от лат. слова "графио" - пишу.
Впервые основы теории графов появились в работе члена Петербургской академии наук, выдающегося математика Леонардо Эйлера, где он описывал решение головоломок и математических развлекательных задач.
Среди них знаменитая задача о Кенигсбергских мостах. Философ Иммануил Кант, гуляя по городу Кенигсбергу, поставил задачу: можно ли пройти по всем семи мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз.
В 1736 году задача о семи мостах заинтересовала Леонарда Эйлера. Он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них.

Существует задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Возможно ли провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена польским математиком Куратовским в 1930 году.
В 1859 г. английский математик Уильям Гамильтон выпустил в продажу головоломку. Она представляла собой деревянный додекаэдр(12-гранник), в вершинах которого вбиты гвоздики. Каждая из 20 вершин была помечена названием одного из крупных городов мира – Дели, Брюссель и т.д. Требовалось найти замкнутый путь, проходящий по ребрам додекаэдра и позволяющий побывать в каждой его вершине по одному разу. Путь следовало отмечать с помощью шнура, зацепляя его за гвоздики.
В 1975 году преподавателем архитектуры Будапешта Эрне Рубиком для развития пространственного воображения у студентов изобрел головоломку Кубик Рубика.
Примеры задач

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом
Граф – это набор точек, каждые из которых соединены линиями. Точки – называются вершинами, а соединяющие их линии ребрами.
Графы, в которых не построены все возможные ребра, называются неполными графами
Графы, в которых построены все возможные ребра, называются полными графами
Основные понятия теории графов

Основные понятия теории графов
Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

Маршрутом в графе называется последовательность рёбер, в которой соседние рёбра имеют общую вершину. Первая вершина называется нача­лом маршрута, последняя — концом.
Путём (или цепью) в графе называется маршрут, в котором нет повто­ряющихся рёбер. Если в пути нет повторяющихся вершин, его называют простым путём. Длина маршрута равна количеству рёбер в порядке их про­хождения. Расстоянием между вершинами в графе называют длину крат­чайшего пути от одной вершины до другой.
Основные понятия теории графов
Цикл — это путь, у которого совпадают начало и конец. Если в цик­ле все вершины разные, его называют простым циклом. Если в цикле все рёбра разные, то такой цикл называется эйлеровым. Маршрут, содержа­щий все рёбра или все вершины графа, называется обходом графа.

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

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

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

Задача о трех домах и трех колодцах
Если проложить 8 тропинок, то 9 никак не проложить, чтобы она не пересеклась. Решая задачу с помощью теоремы Эйлера, получили противоречие, которое показало, что ответ в задаче отрицателен: нельзя провести непересекающиеся дорожки от каждого домика к каждому колодцу.
Предположим, что эти 9 тропинок можно проложить. Обозначим домики точками Д1, Д2, Д3, колодцы - точками К1, К2, К3. Каждую точку-дом соединим с каждой точкой-колодцем.
Как видно, нам удалось провести только восемь тропинок, а девятая должна пересечься хотя бы с одной.
Полученное доказывает, что ответ в задаче о 3-х колодцах отрицателен.
Задачи

Задача о рукопожатиях друзей
Одинец Иван, Бояркин Миша, Захаров Паша, Хартуев Костя и Цацукевич Данил при встрече в школе обменялись рукопожатиями (каждый пожал руку каждому по одному разу).
Вопрос: Сколько всего рукопожатий было сделано?
Решение: В данном случае применяется построение полного графа.
Ответ: Всего 10 рукопожатий было сделано.
Задачи

Самостоятельная работа

Рефлексия
Подведем итоги работы на уроке.
Какую цель мы ставили?
Назовите тему урока.
Скажите, что нового вы узнали на уроке?

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