Введение
Теория графов – область дискретной математики, особенностью которой является геометрический подход к изучению объектов.
Дискретная математика для программистов относится к числу общепрофессиональных предметов, формирующих базовый уровень знаний, необходимых для изучения других дисциплин, таких, как «Программирование», «Архитектура ЭВМ», «Компьютерное моделирование» и других. Теория графов, как один из разделов дискретной математики, и связанные с ней методы исследования, используются на разных уровнях не только во всей современной математике, но и нашли широкое примениние в областях не связанных непосредственно с математикой.
Данная методическая разработка предназначена для студентов, обучающихся на третьем курсе по специальности 050202 «Информатика».
Целью методической разработки является помощь студентам в самостоятельной работе над теоретическим материалом для более успешной подготовки к выполнению практических упражнений, проверка знаний и практических навыков решения задач по указанным разделам данного курса, а также в качестве закрепления теоретического материала и осуществления качественного самоконтроля. Но также может быть использована как задачник для выполнения домней контрольной работы или просто для отработки полученных знаний умений и навыков.
В работе даны необходимые теоретические сведения, рассмотрено подробное решение наиболее показательных задач;
выделен необходимый для полного раскрытия темы круг контрольных вопросов, составленный в соответствии с государственными требованиями к минимуму содержания и уровню подготовки студентов по данной теме.
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой.
Указана учебная литература, рекомендуемая для успешного изучения материала.
История развития теории графов
На самом западе России есть город Калининград, раньше он назывался Кенигсберг. Через город протекает река Преголя. Она делится на два рукава и огибает остров. В XVIII веке в городе было семь мостов, расположенных так, как показано на рисунке 1.
Рис 1. Кенигсберг
Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка. Многие горожане заинтересовались этой задачей, однако придумать решение никто не смог. Этот вопрос привлек внимание ученых разных стран. Разрешить проблему удалось известному математику Леонарду Эйлеру. Причем он не только решил эту конкретную задачу, но и придумал общий метод решения
подобных задач. Поэтому, родоначальником теории графов принято считать Леонарда Эйлера.
По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал "Это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением, и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Итак, я не знаю, каким образом получается, что вопросы,имеющие совсем мало отношения к математике, скорее разрешаются математиками, чем другими".
Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?
Эйлер поступил следующим образом: он «сжал» берега в точки, а мосты «вытянул» в линию. В результате получилась фигура изображенная на рисунке 2.
Рис 2. Схема мостов Кенигсберга
Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, что если из всех точек или вершин выходит четное количество линий, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии), пройти по всем линиям только по одному разу. При этом движение можно начать с любой вершины и окончить в той же вершине.
Если схема содержит только две нечетные вершины, то задача тоже имеет решение, то есть можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине.
Схему с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
В задаче о семи кенигсбергских мостах все четыре вершины соответствующего графа нечетные, т.е. нельзя пройти по всем мостаодин раз и закончить путь там, где он был начат.
Это была первая работа по теории графов великого русского математика швейцарского происхождения Леонарда Эйлера.
Задача о Кенигсбергских мостах и подобные ей задачи вместе с совокупностью методов их исследования составляют очень важный в практическом отношении раздел математики, называемый теорией графов. Первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков К. Берж, О. Оре, А. Зыков.
|
