Автор работы: Пользователь скрыл имя, 14 Ноября 2011 в 01:21, курсовая работа
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.Эйлеру, появилась в 1736г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались при построении схем.
Введение
Глава 1. Основные понятия теории графов
1.1.Понятие графа
1.2.Маршруты, пути и циклы в графах
1.3.Подграфы
1.4.Степень вершины графа
Глава 2. Эйлеровы графы
2.1.Эйлеров путь. Полуэйлеров граф. Эйлерова цепь
2.2.Признак Эйлеровости графа
2. 3.Решение задач о лабиринтах
Глава 3. Гамильтоновы графы.
3.1.Гамильтонов путь. Полугамильтонов граф
3.2. Задача о «Кругосветном путешествии»
3.3.Необходимое условие гамильтоновости графа
Теорема Дирака
Список литературы
Как
было сказано выше, в отличии от
эйлеровых графов, где имеется
критерий для графа быть эйлеровым,
для гамильтоновых графов такого критерия
нет. Приведём одно из достаточных условий
гамильтоновости.
Теорема Дирака. Если в графе G(V,E) c n вершинами (n ≥ 3) выполняется условие deg(v) ≥ n/2 для любой вершины v V, то граф G является гамильтоновым.
Доказательство. Будем проводить доказательство методом от противного. Пусть G — не гамильтонов граф. Добавим к G минимальное количество новых вершин u1, … ,un, соединяя их со всеми вершинами G так, чтобы граф := G + u1 + … + un был гамильтоновым.
Пусть v, u1, w, … ,v — гамильтонов цикл в графе G’, причем v G, u1 G’, u1 G. Такая пара вершин v и u1 в гамильтоновом цикле обязательно найдется, иначе граф G был бы гамильтоновым. Тогда w G, w {u1,…,un}, иначе вершина u1 была бы не нужна. Более того, вершина v несмежна с вершиной w, иначе вершина u1 была бы не нужна.
Далее, если в цикле v,u1,w, … ,u’,w’, … ,v есть вершина w’, смежная с вершиной w, то вершина v’ несмежна с вершиной v, так как иначе можно было бы построить гамильтонов цикл v,v’, … ,w,w’, … ,v без вершины u1, взяв последовательность вершин w, … ,v’ в обратном порядке. Отсюда следует, что число вершин графа G’, не смежных с v, не менее числа вершин, смежных с w. Но для любой вершины w графа G имеем deg (w) ≥ p/2+n по построению, в том числе deg (v) ≥ p/2+n. Общее число вершин (смежных и не смежных с v) составляет n+p-1. Таким образом, имеем:
n+p-1 = deg (v)+d(V) ≥ deg (w)+ deg (v) ≥ p/2+n+p/2+n = 2n+p.
Следовательно,
0 ≥ n+1, что противоречит тому, что n >
0.
Список литературы