Тема: Графы в математике
Цель
Изучить определение и свойства графа
Рассмотреть применение теории к решению задач различных
областей окружающей жизни
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.
Три простейшие задачи
Голодная лиса вышла из вырытой под деревом норы и начала бродить по лесу от дерева к дереву в поисках добычи. Чёрной линией изображён путь лисы. Наконец она устала и легла отдохнуть под одним из деревьев (дерево загораживает лису и её не видно). Где сейчас лиса? Под каким деревом находится её нора? Сколько решений имеет задача?
2. Обведите нарисованную здесь фигуру одним росчерком, т.е. не отрывая карандаша от бумаги и не проводя дважды по одной линии.
3. Вы, наверное, знаете, что есть такой город Калининград. Через город протекает река, она делится на два рукава и огибает остров. В 18 веке в городе было семь мостов, расположенных так, как показано на рисунке. Однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка?
Эти три задачи на первый взгляд кажутся совершенно разными, и человек, не знающий того, о чём пойдёт речь дальше, будет пытаться их решить методом перебора, т. е. работая карандашом, перебирая различные варианты.
Понятие графа
Решить проблему удалось знаменитому математикуЛеонарду Эйлеру. Причём, он решил не только эту конкретную задачу, но и придумал общий метод решения подобных задач.
Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в линии. В результате получилась вот такая фигура (см. рис.)
Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют графом. Точки называют вершинами графа, а линии, которые соединяют вершины, -рёбрами графа. Вершины, из которых выходит нечётное число рёбер, называются нечётными вершинами, а вершины, из которых выходит чётное число рёбер, называются – чётными.
Свойства графа
Решая задачу про Кенигсбергские мосты, Эйлер установил следующие свойства графа:
Если все вершины графа чётные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф.
Граф с двумя нечётными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечётной вершины, а заканчивать на другой нечётной вершине.
Граф с более чем двумя нечётными вершинами, невозможно начертить одним росчерком.
В задаче о Кенигсбергских мостах все четыре вершины соответствующего графа – нечётные, значит, нельзя пройти по всем мостам ровно один раз и закончить путь там же.
В задаче про лису две нечётные вершины, значит, нора лисы находится в одной из них, а сама лиса – во второй, или наоборот, т.е. задача имеет два решения.
Во второй задаче, подсчитав, сколько линий выходит из каждой вершины, тоже можно сделать вывод о возможности её решения.
Граф получить на листе бумаги очень просто. Надо взять карандаш и нарисовать на этом листке, не отрывая карандаша от бумаги и не проводя дважды по одной линии, что угодно. Отметить точками «перекрёстки» и начальную и конечную точки, если они не совпадают с «перекрёстками». Получившуюся фигуру можно назвать графом. Если начальная и конечная точки рисунка совпадают, то все вершины окажутся чётными, если же начальная и конечная точки не совпадают, то они окажутся нечётными вершинами, а все остальные будут чётными.
Льюис Кэрролл, автор книги «Алиса в стране чудес», любил давать своим знакомым следующую головоломку. Он просил обвести фигуру, изображённую на рисунке, не отрывая карандаша от бумаги и не проводя дважды по одной линии. Подсчитав чётность вершин, убеждаемся, что эта задача легко решается, причём начинать обход можно с любой вершины, т. к. они все чётные. Однако, он усложнял задачу тем, что требовал, чтобы при обводке линии не пересекались. Справиться с этой проблемой можно следующим способом. Раскрасим фигуру так, чтобы её граничащие части оказались разного цвета. Затем разъединим пересекающиеся линии таким образом, чтобы закрашенная часть представляла из себя единый кусок. Теперь остаётся обвести по краю одним росчерком закрашенную область – это и будет искомая линия
