Связность графов - Курсовая работа

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. "Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов.Пара (V(G), Е(G)) называется простым графом, если V(G) - непустое конечное множество элементов, называемых вершинами (или узлами, или точками), а Е(G) - конечное множество неупорядоченных пар различных элементов из V(G), называемых ребрами (или линиями). Кроме того, часто бывает удобно снять ограничение, состоящее в том, что ребро должно соединять две различные вершины, и допустить существование петель, т. е. ребер, соединяющих вершину с ней самой. Более точно, графом G называется пара (V(G), Е(G)), где V(G) - непустое конечное множество элементов, называемых вершинами, а Е(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами. Орграфом D называется пара (V(D), A (D)), где V(D) - непустое конечное множество элементов, называемых вершинами, а А (D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Две вершины v и w графа G называются смежными, если существует соединяющее их ребро (т. е. ребро вида {v, w}); при этом вершины v и w называются инцидентными этому ребру (а ребро - инцидентным этим вершинам).Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом. Если степень каждой вершины равна r, то граф называется регулярным степени r. Регулярные графы степени 3, называемые также кубическими (или трехвалентными) графами (см., например, Рис. Пусть даны два графа G1= (V(G1), Е(G1) и G2 - (V(G2), Е(G2)), причем множества V(G1) и V(G2) не пересекаются; тогда объединением G1?G2 графов G1 и G2 называется граф с множеством вершин V(G1) U V(G2) и семейством ребер E(G1) U E(G2) (Рис.Граф называется связным, если для любых его вершин u и v существует цепь, соединяющая эти вершины. Числом вершинной связности графа G [обозначение a(G)] наз. наименьшее число вершин, удаление к-рых (вместе с инцидентными им ребрами) приводит к несвязному графу или к графу, состоящему из одной изолированной вершины. В теории графов изучаются способы установления Г. с, условия, при к-рых граф является k-связным или k-реберно связным, соотношения между различными видами связности, зависимость чисел связности от других параметров графа и т. п. Говорят, что множество S вершин, ребер или вершин и ребер разделяет вершины u и v, если u и v принадлежат разным компонентам связности графа G-S, полученного из G удалением элементов множества S. Зафиксируем некоторую вершину v графа и обозначим через V1 множество, состоящее из вершины v и всех тех вершин из V, которые соединены цепями с вершиной v.Маршрут называется цепью, если все его ребра различны, и простой цепью, если все вершины v0, v1 ..., vm различны (кроме, может быть, v0= vm). Цепь называют путем, полупростым путем; простую цепь - цепью, путем, дугой, простым путем, элементарной цепью; замкнутую цепь - циклической цепью, контуром; цикл - контуром, контурной цепью, простым циклом, элементарным циклом. Граф G называется связным, если для любых двух его вершин v и w существует простая цепь из v в w. Любой граф можно разбить на непересекающиеся связные подграфы, называемые компонентами (связности), задав следующее отношение эквивалентности на множестве его вершин: две вершины эквивалентны (или связаны), если существует простая цепь из одной в другую. Оставим читателю доказательство того, что связанность вершин действительно является отношением эквивалентности и что вершины, принадлежащие одному классу эквивалентности, вместе с инцидентными им ребрами образуют компоненты (связности) графа.Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро; такая цепь называется эйлеровой цепью. Название «эйлеров» возникло в связи с тем, что Эйлер первым решил знаменитую задачу о кенигсбергских мостах, в которой нужно было узнать, имеет ли граф, изображенный на Рис. 4, эйлерову цепь (не имеет!).Сразу же возникает вопрос: можно ли найти необходимые и достаточные условия для того, чтобы граф был эйлеровым? Пусть v - произвольная вершина графа G; построим по индукции маршрут v> v1> v2>…, выбирая вершину v1 смежной вершине v, а для i ? 1 - выбирая vi 1 смежной vi и отличной от vi-1(существование такой вершины vi 1 гарантировано условием леммы). В силу связности графа G, каждая компонента в Н имеет по крайней мере одну общую вершину с циклом С, поэтому искомую эйлерову цепь графа G можно получить так: идем по ребрам цикла С до тех пор, пока не встретим неизолированную вершину графа H, затем следуем по эйлеровой цепи той компоненты в H, которая содержит указанную вершину; далее продолжаем путь по ребрам цикла С, пока не встретим

Содержание

Введение

Глава 1. Понятие графа

§1. Определения

§2. Примеры графов

§3. Связность графов

Глава 2. Цепи и Циклы

§4. Новые определения

§5. Эйлеровы графы

§6. Гамильтоновы графы

§7. Бесконечные графы

Глава 3. ДЕРЕВЬЯ

§8. Элементарные свойства деревьев

Практическая часть

Заключение

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года.

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