Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
Аннотация к работе
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.Эйлеру, появилась в 1736г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками.Граф G - пара (V,X), где V конечное непустое множество, содержащее p вершин, а множество Х содержит q неупорядоченных пар различных вершин из V. Граф с р вершинами и q ребрами называется (p;q)-графом. Маршрутом в графе G называется чередующаяся последовательность вершин и ребер v0,x1,v1,…vn-1,xn,vn; эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Задачу об обходе мостов можно обобщить и получить следующую задачу теории графов: можно ли найти в данном графе G цикл, содержащий все вершины и все ребра? Теорема 1(критерий): Граф с более чем одной вершиной имеет эйлеров цикл тогда и только тогда, когда он связный и каждая его вершина имеет четную степень.Решение: А) Так как каждая вершина имеет четную степень, то по критерию в этом графе существует эйлеров цикл: 1,4,6,9,10,8,5,3,2,4,7,10,11,8,6,5,2,1 Решение: а) Т.к. этот граф связный и каждая его вершина имеет четную степень, то по критерию эйлерова графа, данный граф имеет эйлеров цикл: a b e j i f c b d h j g f a c d e h g i a б) Этот граф связный, но т.к. все его вершины имеют нечетную степень, то он не имеет эйлерова цикла. в) Этот граф связный, но т.к. все его вершины имеют степень 3, то есть нечетную, то он не имеет эйлерова цикла. г) Данный граф связный, степени вершин а и с имеют нечетную степень, значит, этот граф не имеет эйлерова цикла. Решение: а) Граф не является связным, то есть не выполняется первое условие критерия, значит, он не имеет эйлерова цикла. б) Этот граф является связным и все его вершины имеют четную степень, значит, по критерию эйлерова графа, он имеет эйлеров цикл: a c f h I j k g d c b f I l j g e d a в) Данный граф связный, но степени вершин а и е нечетные, следовательно по критерию, этот граф не имеет эйлерова цикла. г) Граф является связным, но так как все его вершины имеют нечетную степень, то граф не имеет эйлерова цикла. Решение: а) Граф связный, и только две его вершины (a и f) имеют нечетную степень, следовательно, то по теореме 3, граф имеет собственный эйлеров путь. б) Граф связный; deg(a)=3, deg(b)=3, deg(c)=3, то есть более двух вершин имеют нечетную степень, значит, не имеет эйлерова пути. в) Этот граф связный и только две вершины (с и j) имеют нечетную степень, значит, граф имеет собственный эйлеров путь. г) Граф связный; deg(a)=3, deg(b)=4, deg(c)=1, deg(d)=3, то есть более двух вершин имеют нечетную степень, следовательно, в этом графе нет эйлерова пути. Ровно две вершины имеют нечетную степень, значит, по теореме 3, граф имеет собственный эйлеров путь. б) Граф является связным и ровно две его вершины (е и f) имеют нечетную степень, значит, данный граф имеет собственный эйлеров путь. в) Граф связный, найдем степени вершин: deg(d)=5, deg(b)=5, deg(e)=5, нашлись три вершины, степень которых нечетная, значит, граф не имеет эйлерова пути. г) Данный граф связный и только две его вершины (а и b) имеют нечетную степень, значит, этот граф имеет собственный эйлеров путь.Большое внимание уделили вопросу существования в них эйлеровых цепей и циклов, рассмотрели ряд теорем и свойств. Описали алгоритм нахождения эйлерова цикла в произвольном графе, а в практической части показали его применение на конкретных примерах.
План
Оглавление
Введение 3
Глава 1. Теоретическая часть. 4
Основные понятия теории графов 4
Маршруты и связность 6
Задача о кенигсбергских мостах. 7
Эйлеровы графы 9
Оценка числа эйлеровых графов 13
Алгоритм построения эйлеровой цепи в данном эйлеровом графе. 14
Глава 2. Практическая часть 15
Заключение 24
Литература 25
Введение
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.Эйлеру, появилась в 1736г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно ее приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались при построении схем.
В настоящее время эта теория находит многочисленное применение в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов, в программировании и теории игр, теории передачи сообщений. Теория графов теперь применяется и в таких областях, как экономика, психология и биология.
В этой работе мы подробнее рассмотрим эйлеровы графы, основные сведения и теоремы, связанные с этим понятием. А также задачи, которые решаются с помощью эйлеровых графов.
Вывод
В данной работе были рассмотрены основные понятия теории графов, их виды. Большое внимание уделили вопросу существования в них эйлеровых цепей и циклов, рассмотрели ряд теорем и свойств. Описали алгоритм нахождения эйлерова цикла в произвольном графе, а в практической части показали его применение на конкретных примерах.
Известно, что эйлеровы графы получили широкое распространение и популярность благодаря тому, что многие головоломки и задачи можно решить с использованием знаний теории графов. Частные примеры таких головоломок и сюжетных задач были приведены в практической части. Задачи на отыскание путей через лабиринты, близкие к задачам на эйлеровы графы, находят применение в современной психологии и при конструировании вычислительных машин. Также с практической точки зрения, сейчас графы применяют во многих других областях науки таких как: программирование, физика, химия, биология, экономика и т.д.
Список литературы
1. Андерсон, Джеймс А. Дискретная математика и комбинаторика: пер. с англ. - М.: Издательский дом «Вильямс», 2003. - 960с.
2. Березина Л. Ю. Графы и их применение. - М.: Просвещение, 1979.
3. Новиков С.А. Дискретная математика для программистов - СПБ.: Питер, 2001. - 304с.
4. Оре о. Графы и их применение. - М.: Мир,1973.
5. Уилсон Р. Введение в теорию графов. - М.: Мир, 1977.