КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Пояснение к работеВремя выполнения практического задания – 2 часа. Последовательность выполнения 1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы: В чем состоит алгоритм поиска путей с минимальным числом дуг? Какой цикл называется эйлеровым? Каков критерий существования эйлерова цикла в графе? Каков критерий существования эйлеровой цепи в графе? 2. Дать определение следующих понятий: – маршрут в графе (привести пример); – цепь и простая цепь в графе; – цикл и простой цикл в графе; – эйлеровой цепь; – матрица смежности графа; – степень вершины графа. 3. Выполнить задания для аудиторных занятий. 4. Выполнить задания для самостоятельной работы. 6.1. Маршруты, цепи, циклы Маршрутом в графе G = (V, E) (путем в графе D = (V, E)) называется последовательность вершин и рёбер (дуг) вида v 0, e 1, v 1, e 2,..., v n-1, e n, v n, где v i Î V, i Î [0, n ], e i Î E, (v i-1, e i), (v i, e i) Î I, i Î [1, n ]. Вершины v 0, v n называются связанными данным маршрутом (или просто связанными). Вершину v 0 называют началом, а v n – концом маршрута. Если v 0 = v n, то маршрут называют замкнутым. Число n называется длиной маршрута. Маршрут, в котором все рёбра попарно различны, называется цепью. Замкнутый маршрут, являющийся цепью, называется циклом (контуром). Цепь, в которой все вершины попарно различны, называется простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом. Примеры: 1. Последовательность v 1, e 1, v 2, e 3, v 4, e 4, v 3 – маршрут длины 3, соединяющий вершины v 1, v 3 в графе G (рис. 11); это простая цепь, так как все ребра и вершины попарно различны. 2. v 2, e 3, v 2 – простой контур длины 1 в ориентированном псевдографе D (рис. 10). 3. v 1, e 2, v 2, e 4, v 3 – путь из v 1 в v 3 длины 2 в ориентированном псевдографе D (рис. 10); это простая цепь, так как все дуги и вершины попарно различны. Рис. 10 Рис. 11 6.2. Поиск путей (маршрутов)с минимальным числом дуг При решении некоторых прикладных задач нередко возникает необходимость найти минимальный маршрут, соединяющий заданные вершины в графе. Приведем алгоритм решения этой задачи. Путь в орграфе D из вершины v в вершину w (v ¹ w) называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из вершины v в вершину w. Аналогично определяется минимальный маршрут в графе G. Алгоритм нахождения минимального маршрута состоит из следующих шагов: Шаг 1. Помечаем вершину v индексом 0. Затем помечаем вершины, принадлежащие образу вершины v, индексом 1. Множество вершин с индексом 1 обозначаем FW1(v). Полагаем k = 1. Шаг 2. Если FWk(v) = Æ или выполняется k = n – 1, w Ï FWk(v), то вершина w не достижима из v и работа алгоритма на этом заканчивается. В противном случае переходим к шагу 3. Шаг 3. Если w Ï FWk(v), то переходим к шагу 4. В противном случае существует путь из v в w длины k, и этот путь является минимальным. Последовательность вершин v w1w2 …wk-1w, где wk-1 Î FWk-1(v) Ç D-1(w); wk-2 Î FWk-2(v) Ç D-1(wл-1); … w1 Î FW1(v) Ç D-1(w2) и есть искомый минимальный путь из v в w. На этом работа алгоритма заканчивается. Шаг 4. Помечаем индексом k + 1 все непомеченные вершины, которые принадлежат образу множества вершин с индексом k. Множество вершин с индексом k + 1 обозначаем FWk+1(v). Присваиваем k:= k + 1 и переходим к шагу 2. Пример. Используя предложенный алгоритм, определим минимальный путь из v 1 в v 6 в орграфе D, заданном матрицей смежности, представленной в табл. 1.
Таблица 1
Действуя согласно алгоритму, последовательно определяем FW1(v1) = { v4, v5 }; FW2(v1) = D(FW1(v1))\{ v1, v4, v5 } ={ v2, v3 }; FW3(v1) = D(FW2(v1))\{ v1, v2, v3, v4, v5 } = { v6 }. Таким образом, v6Î FW3(v1), а значит (см. шаг 3) существует путь из v1 в v6 длины 3 и этот путь является минимальным. Найдем теперь минимальный путь из v1 в v6. Определим множество FW2(v1) Ç D-1(v6) = { v2, v3 } Ç { v2, v3 } = { v2, v3 }. Выберем любую вершину из найденного множества, например вершину v3. Определим далее множество FW1(v1) Ç D-1(v3) = { v4, v5 } Ç { v4, v5, v6 = { v4, v5 }. Выберем любую вершину из найденного множества, например, вершину v5. Тогда v1 v5 v3 v6 – искомый минимальный путь из v1 в v6 длины 3 в орграфе D. 6.3. Эйлеровы графы Пусть G – псевдограф. Цепь (цикл) в G называется эйлеровой, если она (он) проходит по одному разу через каждое ребро псевдографа G.
щий эйлеров цикл, тоже будем называть эйлеровым. В любом эйлеровом графе степени всех вершин чётные. Пусть по некоторой вершине v цикл проходит k раз. Но так как перед этой вершиной и после неё цикл должен проходить по инцидентным ей рёбрам, то количество рёбер, инцидентных данной вершине, по которым проходит цикл – 2 k. Так как цикл эйлеров – рёбер, по которым цикл не проходит, нет, значит 2 k – степень вершины v. Если в связном графе степени всех вершин чётные, то в графе существует эйлеров цикл. В ходе доказательства мы дадим алгоритм построения такого цикла. Начнём с произвольной вершины v и будем строить из неё цепь, пока есть возможность её продолжить. Пусть в какой-то момент построения мы находимся в вершине u (не совпадающей с v). Тогда цепь, которую мы построили, проходит по нечётному числу рёбер, инцидентных данной вершине. Степень вершины u чётная, следовательно, есть хотя бы одно ребро, инцидентное вершине u, по которому цепь не прошла – значит её можно продолжить. Следовательно, цепь может закончится только в вершине v. Получим цикл. В задачах часто возникает необходимость нахождения цепи, проходящей по каждому ребру ровно один раз (снимается требование замкнутости). Такие цепи будем называть эйлеровыми цепями. Задания Для аудиторных занятий 1. Задан граф G (рис. 13 а). Найти путь с минимальным числом ребер из вершины v 1 в вершину v 6 графа G.
а б в
а б в Рис. 13 2. Для графа G (рис. 13 б) записать матрицу смежности и найти путь с минимальным числом ребер из вершины v 2 в вершину v 9. 3. Для орграфа D (рис. 13 в) записать матрицу смежности и найти путь с минимальным числом ребер из вершины v 1 в вершину v 7. 4. Определить, содержит ли граф на рис. 13 а эйлеров цикл или эйлерову цепь. 5. Может ли вершина, входящая в цикл графа, иметь степень, меньшую двух? 6. Как называется путь, у которого начало первой дуги совпадает с концом последней? 7. Как называется маршрут, у которого первая вершина совпадает с последней? 8. Показать, что в любом графе количество вершин нечетной степени четно. 9. Показать, что из всякого замкнутого маршрута нечетной длины можно выделить простую цепь. 10. Показать, что ребро, входящее в цикл графа, входит в некоторый его простой цикл. Для самостоятельной работы 1. Задан граф G (рис. 13 а). Найти путь с минимальным числом ребер из вершины v 1 в вершину v 7 графа G. 2. Для графа G (рис. 13 б) записать матрицу смежности и найти путь с минимальным числом ребер из вершины v 1 в вершину v 8. 3. Для графа G (рис. 13 б) записать матрицу инцидентности. 4. Для орграфа D (рис. 13 в) записать матрицу смежности и найти путь с минимальным числом ребер из вершины v 1 в вершину v 6. 5. Показать, что любая вершина, входящая в цикл, не является висячей. 6. Доказать, что если в орграфе отсутствуют вершины с нулевой полустепенью исхода (захода), то в орграфе имеется простой контур. 7. Доказать, что удаление из орграфа вершины v с d+(v) ≤ 1 (d-(v) ≤ 1) приводит к орграфу, контуры которого совпадают с контурами исходного орграфа. 8. Привести определение простой цепи: а) цепь, в которой вершины и ребра повторяются; б) чередование вершин и ребер; в) цепь, в которой все вершины попарно различны. 9. В чем заключается понятие смежности? а) сежными являются вершины, инцидентные одному ребру; б) смежными являются два ребра, не имеющие общих вершин; в) смежными являются вершины, соединенные некоторым маршрутом. 10. Задан псевдограф G. Цепь в G называется эйлеровой, если… а) она проходит по одному разу через каждую точку псевдографа; б) она проходит по одному разу через каждое ребро псевдографа; в) она проходит по одному разу через вершины и ребра. Литература 1. Новиков, Ф. А. Дискретная математика для программистов: учебник для вузов / Ф. А. Новиков. – СПб.: Питер, 2001. – 304 с. 2. Акимов, О. Е. Дискретная математика. Логика, группы, графы. – 2-е изд., доп. / О. Е. Акимов. – М.: Лаборатория базовых знаний, 2001. – 367 с.
Дата добавления: 2017-02-01; Просмотров: 148; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |