Связность графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
Тюменский государственный нефтегазовый университет
Филиал: Тобольский индустриальный институт
Кафедра математики и информатики
КУРСОВАЯ РАБОТА
по дисциплине Дискретная математика
на тему Связность графов
Выполнил студент группы ИВТ(б)-10
Гарюткин А.Е.
Руководитель курсового проекта:
Татьяненко С.А
Тобольск, 2011г.
Содержание
Введение
Глава 1. Понятие графа
1. Определения
2. Примеры графов
3. Связность графов
Глава 2. Цепи и Циклы
4. Новые определения
5. Эйлеровы графы
6. Гамильтоновы графы
7. Бесконечные графы
Глава 3. ДЕРЕВЬЯ
8. Элементарные свойства деревьев
Практическая часть
Заключение
Введение
Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года.
"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Множество самых разнообразных задач естественно формулируется в терминах графов. Так, например, могут быть сформулированы задачи составления расписаний в исследовании операций, анализа сетей в электротехнике, установления структуры молекул в органической химии, сегментации программ в программировании, анализа цепей Маркова в теории вероятностей. В задачах, возникающих в реальной жизни, соответствующие графы часто оказываются так велики, что их анализ неосуществим без ЭВМ. Таким образом, решение прикладных задач с использованием теории графов возможно в той мере, в какой возможна обработка больших графов на ЭВМ, и поэтому эффективные алгоритмы решения задач теории графов имеют большое практическое значение.
Глава 1. Понятие графа
1. Определения
Дадим сначала определение простого графа G. Пара (V(G), Е(G)) называется простым графом, если V(G) - непустое конечное множество элементов, называемых вершинами (или узлами, или точками), а Е(G) - конечное множество неупорядоченных пар различных элементов из V(G), называемых ребрами (или линиями). Иногда V(G) называют множеством вершин, а Е(G) - множеством ребер графа G. Например, на Рис. 1 изображен простой граф G, у которого множеством вершин V(G) является множество {u, v, w, z}, а множество ребер Е(G) состоит из пар {u, v}, {v, w}, {u, w} и {w, z}. Говорят, что ребро {v, w} соединяет вершины v и w. Отметим, что так как Е(G) является множеством, а не семейством, то в простом графе данную пару вершин может соединять не более чем одно ребро.
Оказывается, многие результаты, полученные для простых графов, без труда можно перенести на более общие объекты, в которых две вершины могут быть соединены более чем одним ребром. Кроме того, часто бывает удобно снять ограничение, состоящее в том, что ребро должно соединять две различные вершины, и допустить существование петель, т. е. ребер, соединяющих вершину с ней самой.
Рис. 1.Рис. 2
Получающийся при этом объект, в котором могут быть петли и кратные ребра, называется общим графом, или просто графом (Рис. 2). Подчеркнем тот факт, что каждый простой граф является графом, но не каждый граф является простым графом.
Более точно, графом G называется пара (V(G), Е(G)), где V(G) - непустое конечное множество элементов, называемых вершинами, а Е(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами. Заметим, что употребление слова семейство говорит о том, что допускаются кратные ребра. Будем называть V(G) множеством вершин, а Е(G) - семейством ребер графа G; на Рис. 2 V(G) - это множество {u, v, w, z}, а Е(G) - это семейство, состоящее из ребер {u, v}, {v, v), {v, v), {v, w}, {v, w}, (v, w}, {u, w}, {u, w} и {w, z}. О каждом ребре вида {v, w} говорят, что оно соединяет вершины v и w; значит, каждая петля {v, v} соединяет вершину v саму с собой. Предметом изучения в теории графов являются также ориентированные графы (называемые иногда орграфами или сетями; однако мы будем употреблять слово сеть в несколько ином смысле). Орграфом D называется пара (V(D), A (D)), где V(D) - непустое конечное множество элементов, называемых вершинами, а А (D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или