Файл: 9. Гамильтоновы графы. Достаточные условия гамильтоновости графа. 17.docx

1. Основные понятия теории графов. Задачи, послужившие основой теории графов.

Граф —  пара двух множеств (V, E), где V={v, … , v_n} – множество вершин, где E={(v_i, v_j)| v_i, v_jV} – множество ребер, т.е. неупорядоченных пар, если граф неориентированный или упорядоченных пар, если граф ориентированный.

---

Ориентированный граф Неориентированный графПетля - ребро, концы которого совпадают.Подграф - граф, все вершины и ребра которого содержатся среди вершин и ребер исходного графа.Смежные вершины – соединены ребром. Если граф ориентированный, то первая вершина – начало ребра, последняя – конец ребра.Степеньвершины - число выходящих из нее концов ребер. Вершина степени 0 называется изолированной.Теорема о рукопожатиях – в любом графе сумма степеней всех вершин равна удвоенному числу ребер. В любом графе число вершин нечетной степени – четно.Простой граф - граф без петель и кратных ребер.Полный граф – простой граф, в котором каждая пара различных вершин – смежна [K_n]. Связный граф – граф, у которого нет изолированного ребра (точки).Изоморфные графы – графы, между множеством вершин которых существует взаимно однозначное соответствие, сохраняющее отношение инцидентности (для ориентированных графов сохраняется начало и конец каждого ребра).Двудольный граф – граф, в котором множество его вершин V можно разбить на два подмножества V₁ и V₂ так, что концы любого ребра принадлежат разным подмножествам.Цепь – маршрут, у которого все ребра различны.Простая цепь – цепь, у которого все содержимое кроме крайних различны.Маршрут – маршрут, содержащий вершины Х₁ и X_n – чередующаяся последовательность х1, u1, x2, u2, … , где х – вершины, u – ребра.Длина маршрута – количество ребер в нем.Расстояние между двумя вершинами – длина кратчайшей простой цепи.В теории графов на систематической основе изучаются их особенности и свойства. Граф представляет собой множество точек и линий, соединяющих эти точки. Родоначальником теории графов является Леонард Эйлер, который решил популярную в те времена задачу о мостах Кёнигсберга.Одной из первых работ по практическому применению теории графов считается задача с Кёнигсбергскими мостами. В условии заданы река, омываемые рекой острова, и некоторое количество мостов. Требуется дать ответ, есть ли возможность при выходе из заданной точки, перейти каждый из мостов только один раз и возвратиться в исходный пункт.

---

Задача может быть смоделирована так: ко всем участкам на берегу надо прикрепить одну точку, а две точки можно соединить линией лишь в случае, когда участки суши соединяются мостом. Эйлер сформулировал такой ответ на данную задачу.Если бы эта задача имела решение, то в сформированном графе должен существовать замкнутый маршрут, который проходит по рёбрам и который сдержит каждое ребро лишь единожды. Если есть такой маршрут, то все вершины должны иметь чётное число рёбер, что в данном случае не выполняется.

---

2. Ориентированные и неориентированные графы. Изоморфизм графов.

Неориентированные графы – графы, в которых все ребра являются звеньями, то есть порядок двух концов ребра графа не существенен.Ориентированные графы – графы, в которых все ребра являются дугами, то есть порядок двух концов ребра графа существенен.Неориентированный граф можно представить в виде ориентированного графа, если каждое его звено заменить на две дуги с противоположным направлением. Изоморфные графы – графы, между множеством вершин которых существует взаимно однозначное соответствие, сохраняющее отношение инцидентности (для ориентированных графов сохраняется начало и конец каждого ребра).Два графа называются изоморфными, если между множествами их ребер и множествами их вершин установлено взаимно однозначное соответствие, сохраняющее инцидентность, то есть соответствующие ребра соединяют соответствующие вершины. Изоморфные графы можно считать различными представлениями одного и того же графа.

1. 
   Изоморфны ли графы, изображенные на рисунках 4 и 5?
   

Решение. Графы на рисунке 4 изоморфны. Для доказательства этого обозначим соответствующие вершины одинаковыми буквами, см. рис. 6. Нетрудно заметить, что инцидентность соответствующих вершин и ребер сохраняется.Графы на рисунке 5 не изоморфны. Хотя между их вершинами и ребрами можно установить взаимно однозначное соответствие так, чтобы вершины одинаковой степени соответствовали друг другу, но у первого графа вершины степени 2 соединены ребром, а у второго нет.

3. Способы задания графов. Метрические характеристики графа.

Рассмотрим три способа задания графов: графический, аналитический и матричный.1) Графический способ.Вершины изображают точками на плоскости, а ребра – линиями, соединяющими соответствующие точки. Для изображения дуги используется линия со стрелкой, указывающей направление от начала к концу дуги.

---

 2) Аналитический способ.Граф задают перечислением элементов множества вершин и множества ребер. Для графа, изображенного на рисунке 12, эти множества: V={v₁, v₂, v₃, v₄, v₅, v₆} и Е={e₁, e₂, e₃, e₄, e₅}, где e₁=(v₁, v₂), e₂=(v₁, v₃), e₃=(v₁, v₃), e₄=(v₄, v₅), и e₅=(v₄, v₄).3) Матричный способ.Имеется несколько вариантов задать граф матрицей. Наиболее употребимыми являются матрица инциденций и матрица смежности.а) Матрица инциденций – это прямоугольная матрица, число строк которой равно числу вершин, а число столбцов – числу дуг (ребер) графа. Элементы этой матрицы определяются следующим образом:б) Матрица смежности вершин – это квадратная матрица, размер которой определяется числом вершин в графе. Элементы этой матрицы определяются так:   . Если в графе имеются параллельные ребра, то соответствующий элемент матрицы смежности полагают равным числу этих ребер. Метрическими (или числовыми) характеристиками называют параметры графа, определяемые через кратчайшие расстояния между вершинами: центр, радиус и диаметр. Диаметр определяется как самое длинное из всех кратчайших расстояний между вершинами графа, центр - как вершина, максимальное расстояние от которой до всех остальных вершин графа минимально, а это максимальное расстояние от центра есть радиус графа.

---