Автор: Пользователь скрыл имя, 01 Апреля 2013 в 17:02, реферат
Теория графов – это раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие технические, экономические, биологические и социальные системы.
Граф называется плоским, если на плоскости его можно изобразить так, что все пересечения его рёбер являются вершинами графа .
В качестве характеристики плоского представления графа вводится понятие грани.
Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.
Рассмотрим графы и
а) Дополнением графа называется граф множеством вершин которого является множество а множеством его рёбер является множество
б) Объединением графов и при условии, что называется граф множеством вершин которого является множество а множеством его рёбер является множество
в) Пересечением графов и называется граф множеством вершин которого является множество а множеством его рёбер является множество
г) Суммой по модулю два графов и при условии, что называется граф множеством вершин которого является множество а множеством его рёбер – множество Т. е. этот граф не имеет изолированных вершин и состоит только из рёбер, присутствующих либо в первом графе, либо во втором графе, но не в обоих графах одновременно.
Существуют
три эквивалентных способа
Аналитический способ задания графов
Граф задан, если задано множество элементов V и отображение E множеств V в V. Отображение Е может быть как однозначным, так и многозначным.
Пусть дано множество которое имеет мощность
Для того чтобы задать отображение Е на V , необходимо каждому элементу поставить в соответствие некоторое подмножество множества V, которому соответствует отображение Е. Это подмножество обозначают через Поэтому Совокупность двух объектов: множества V и отображение Е на V задаёт некоторый граф.
Другой формой аналитического способа задания является задание графа как совокупности множества элементов V и подмножества множества упорядоченных пар
Геометрический способ задания графов
Множество элементов V графа G изображают кружками, это множество вершин. Каждую вершину соединяют линиями с теми вершинами , для которых выполняется условие Множество линий, которое соответствует множеству упорядоченных пар есть множество рёбер.
Матричный способ задания графов
Квадратная матрица элементами которой являются нули и единицы, а также некоторое число m, называется матрицей смежности графа тогда и только тогда, когда её элементы образуются по следующему правилу: элемент стоящий на пересечении й строки и го столбца, равен единице, если имеется ребро, идущее из вершины в вершину и равен нулю в противном случае. Элемент равен единице, если при вершине имеется петля, и равен нулю в противном случае. Элемент равен некоторому числу m, где m – число рёбер графа, идущее из вершины в вершину
Таким образом, если граф задан одним из указанных способов: аналитическим, геометрическим или матричным, всегда можно перейти к любому другому способу задания. Наиболее часто для задания графа используется аналитический и матричный способы, а геометрический способ служит для иллюстрации полученных результатов.
Эйлеровы графы
К задачам на Эйлеровы графы относятся головоломки, в которых требуется вычертить на плоскости одним росчерком замкнутые кривые, обводя каждый участок в точности один раз. Введём следующие понятия.
Эйлеровым путём в графе называется путь, содержащий все рёбра графа.
Эйлеровым циклом или эйлеровой цепью называется цикл, содержащий все рёбра графа и притом по одному разу.
Граф, обладающий эйлеровым циклом, называется эйлеровым графом.
Замкнутую линию, если её можно начертить, не отрывая карандаша от бумаги, проходя при этом каждый участок в точности один раз, принято называть уникурсальной.
Рисунок графа, обладающий эйлеровым путём или эйлеровым циклом, является уникурсальной линией.
Докажем следующие две теоремы
Теорема 1. Если граф обладает эйлеровым циклом, то он связный и все его вершины четные.
Доказательство. Связность графа следует из определения эйлерова цикла. Эйлеров цикл содержит каждое ребро и притом только один раз, поэтому, сколько раз эйлеров путь приведет конец карандаша в вершину, столько и выведет, причём уже по одному ребру. Следовательно, степень каждой вершины графа должна состоять из двух одинаковых слагаемых: одно – результат подсчета входов в вершину, другое – выходов.
Теорема 2. Если граф связный и все его вершины четные, то он обладает эйлеровым циклом.
Доказательство. Если начать путь из произвольной вершины графа , то найдётся цикл, содержащий все рёбра графа. Пусть - произвольная вершина. Из начнём путь по l по одному из рёбер и продолжим его, проходя каждый раз по новому ребру. Все вершины графа имеют чётные степени, поэтому если l есть «выход» из , то должен быть и «вход» в , также как и для любой вершины другой вершины. И если есть «вход» в вершину, то должен быть и «выход». Так как число ребер конечно, то это путь должен окончиться, причём в вершине . Если путь, замкнувшийся в , проходит через все рёбра графа, то мы получим искомый эйлеров цикл.
Для построения
эйлерова цикла в связном графе
со всеми вершинами чётной степени
применяется следующий
1. Выйти из произвольной вершины . Каждое пройденное ребро зачеркнуть. Если путь замыкается в и проходит через все рёбра графа, то получим искомый эйлеров цикл.
2. Если остались непройденные рёбра, то должна существовать вершина принадлежащая и ребру, не вошедшему в
3. Так как чётная, то число рёбер, которым принадлежит и которые не вошли в путь тоже чётно. Начнём новый путь из и используем только рёбра, не принадлежащие Этот путь кончится в
4. Объединим теперь оба цикла: из пройдём по пути к затем по и, вернувшись в пройдём по оставшейся части обратно в .
5. Если снова найдутся рёбра, которые не вошли в путь, то найдём новые циклы. Так как число рёбер и вершин конечно, то процесс закончится.
Таким образом, замкнутую фигуру, в которой все вершины чётные, можно начертить одним росчерком без повторений и начиная с любой точки.
На практике эйлеровым графом может быть план выставки; это позволяет расставить указатели маршрута, чтобы посетитель смог пройти по каждому залу в точности по одному разу.
Гамильтоновы графы
Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.
Гамильтоновым циклом, или путём в графе, называется цикл, или путь, проходящий через каждую вершину графа в точности по одному разу.
Эйлеровы и гамильтоновы пути сходны по способу задания. Первые содержат все рёбра, и притом по одному разу, вторые – все вершины по одному разу. Но, несмотря на внешнее сходство, задачи их отыскания резко отличаются по степени трудности. Для решения вопроса о существовании эйлерова цикла в графе достаточно выяснить, все ли его вершины чётные.
Критерий же существования гамильтонова цикла на произвольном графе ещё не найден.
Однако есть несколько достаточных условий существования гамильтоновых циклов в графе:
1. Всякий полный граф является гамильтоновым, так как он содержит простой цикл, которому принадлежат все вершины данного графа.
2. Если граф,
помимо простого цикла,
3. Если граф имеет один гамильтонов цикл, то он может иметь и другие гамильтоновы циклы.