Эйлеровы циклы. Задача "Китайского почтальона"
2 ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОСТОЧНО - СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ» ЭЛЕКТРОТЕХНИЧЕСКИЙ ФАКУЛЬТЕТ Кафедра систем информатики Курсовая работа (Д.669.2.1.12.13.006.09.ПЗ) по дисциплине «Дискретная математика в программировании» Тема: «Эйлеровы циклы. Задача «Китайского почтальона» Выполнил: студентка гр. 669 Хохлова А.М. Руководитель: Доцент кафедры Си Данилова С.Д Улан-Удэ,2010 ВОСТОЧНО-СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ ЭЛЕКТРОТЕХНИЧЕСКИЙ ФАКУЛЬТЕТ Кафедра систем информатики ЗАДАНИЕ на курсовую работу |
Дисциплина: Дискретная математика | | Тема: Эйлеровы циклы. Задача «Китайского почтальона» | | Исполнитель: Хохлова А.М | | Руководитель: Данилова С.Д | | Краткое содержание проекта: Курсовая работа посвящена исследованию Эйлеровых циклов | | И способу решения «Задачи Китайского почтальона» | | 1. Теоретическая часть: Анализ предметной области : | | Цикломатическое число и фундаментальные циклы. Разрезы. Матрицы циклов и разрезов. Эйлеровы циклы и задача китайского почтальона. | | и фундаментальные циклы. Разрезы. Матрицы циклов и разрезов. чтальона.расширенная постановка задачи.,, | | Эйлеровы циклы и задача китайского почтальона | | 2. Практическая часть: Математическаяпостановка,алгоритм,программная | | реализация, вычислительный эксперимент. | | Сроки выполнения работы по графику: | | Обзор литературы и исследование предметной области - 30 % к 10 неделе. Разработка постановки задачи и модели - 30% к 13 неделе. Разработка программы - 30%к 16 неделе Оформление отчета - 10% к 17 неделе. Защита проекта - 17 неделя. | | 2.Разработка постановки задачи и модели - 30% к 13 неделе. | | 3.Разработка программы - 30%к 16 неделе | | 4.Оформление отчета - 10% к 17 неделе. | | 5.Защита проекта - 17 неделя. | | Требования к оформлению: | | 1. Расчетно-пояснительная записка курсовой работы должна быть представлена в электронной и твердой | | электронной и твердой копиях | | 2. Объем РПЗ должен быть не менее 20 машинописных страниц без учета приложений | | 3.Отчет должен быть оформлен по ГОСТу 7.32-2001. | | |
Оглавление Глава 1: теоретическая часть Аннотация 1.1 Задача Эйлера 1.2 Цикломатическое число и фундаментальные циклы 1.3 Разрезы 1.4 Матрицы циклов и разрезов 1.5 Эйлеровы циклы и задача китайского почтальона 1.5.1 Основные понятия и определения 1.5.2 Критерий существования эйлерова цикла 1.5.3 Алгоритмы построения эйлерова цикла 1.6 Алгоритм для задачи китайского почтальона 1.6.2 Алгоритм Дейкстры 1.6.3 Венгерский алгоритм 2.Проектный раздел 2.1 Словесная постановка задачи 2.2 Формальная постановка задачи 2.3 Алгоритм решения задачи в графическом виде 3. Программный раздел 4. Экспериментальный раздел Заключение Приложения 1 Список использованной литературы Аннотация Целью моей курсовой работы является описание методов нахождения и построения эйлеровых циклов в графах. Разобраться с такими понятиями как, цикломатическое число и фундаментальные циклы. Разрезы. Матрицы циклов и разрезов. Так же было необходимо решить задачу « задачу китайского почтальона». Для достижения поставленной цели в работе рассмотрены теоретические вопросы в данной предметной области, предложен способ решения «задачи китайского почтальона». И разработано программное обеспечение, реализующее предложенный способ. Предмет исследований: Задача «Китайского почтальона» Цель работы: Изучение таких понятий как: Цикломатическое число и фундаментальные циклы. Разрезы. Матрицы циклов и разрезов. Эйлеровы циклы и задача китайского почтальона. Задачи: 1)Узнать, что такое Цикломатическое число и фундаментальные циклы. Разрезы. Матрицы циклов и разрезов. Эйлеровы циклы и задача китайского почтальона. 2)изучить алгоритм решения «задачи китайского почтальона» 3)Разработать программу решающую данную задачу на языке программирования. Си Методы исследования: Теоретические методы:теоретический анализ (выделение и рассмотрение отдельных сторон, признаков, особенностей, свойств явлений), индуктивные и дедуктивные методы обобщения полученных данных, математические методы, статические методы и практические. 1. Теоритический раздел 1.1 Задача ЭйлераС именем Эйлера, связана задача о трех домиках и трех колодцах. Задача: Три соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу. Дорожки не могут проходить через колодцы и домики (рис.1).
Рис. 1. К задаче о домиках и колодцах.Для решения этой задачи воспользуемся теоремой, доказанной Эйлером в 1752 году, которая является одной из основных в теории графов. Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых. Теорема. Если многоугольник разбит на конечное число многоугольников так, что любые два многоугольника разбиения или не имеют общих точек, или имеют общие вершины, или имеют общие ребра, то имеет место равенство где - общее число вершин, - общее число ребер, - число многоугольников (граней). Доказательство. Докажем, что равенство (*) не изменится, если в каком-нибудь многоугольнике данного разбиения провести диагональ (рис. 2, а). Рис. 2. Действительно, после проведения такой диагонали в новом разбиении будет вершин, ребер и количество многоугольников увеличится на единицу. Следовательно, имеем Пользуясь этим свойством, проведем диагонали, разбивающие входящие многоугольники на треугольники, и для полученного разбиения покажем выполнимость соотношения (*) (рис. 2, б). Для этого будем последовательно убирать внешние ребра, уменьшая количество треугольников. При этом возможны два случая: · для удаления треугольника ABC требуется снять два ребра, в нашем случае AB и BC; для удаления треугольника MKN требуется снять одно ребро, в нашем случае MN. В обоих случаях равенство (*) не изменится. Например, в первом случае после удаления треугольника граф будет состоять из вершин, ребер и многоугольника: Таким образом, удаление одного треугольника не меняет равенства (*). Продолжая этот процесс удаления треугольников, в конце концов мы придем к разбиению, состоящему из одного треугольника. Для такого разбиения , , и, следовательно, Значит, равенство (*) имеет место и для исходного разбиения, откуда окончательно получаем, что для данного разбиения многоугольника справедливо соотношение (*). Соотношение Эйлера не зависит от формы многоугольников. Многоугольники можно деформировать, увеличивать, уменьшать или даже искривлять их стороны, лишь бы при этом не происходило разрывов сторон. Соотношение Эйлера при этом не изменится. Решениезадачи о трех домиках и трех колодцах.. Предположим, что это можно сделать. Отметим домики точками Д1, Д2, Д3, а колодцы - точками К1, К2, К3 (рис. 1). Каждую точку-домик соединим с каждой точкой-колодцем. Получим девять ребер, которые попарно не пересекаются. Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение Эйлера Добавим к рассматриваемым граням еще одну - внешнюю часть плоскости по отношению к многоугольнику. Тогда соотношение Эйлера примет вид , причем и Следовательно Каждая из пяти граней имеет по крайней мере четыре ребра, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро лежит ровно в двух гранях, то количество ребер должно быть не меньше , что противоречит условию, по которому их число равно 9. Полученное противоречие показывает, что ответ в задаче отрицателен - нельзя провести непересекающиеся дорожки от каждого домика к каждому колодцу. 1.2 Цикломатическое число и фундаментальные циклы.Мультиграф -- граф, где между двумя заданными вершинами может быть несколько дуг. Дуги, соединяющие одну и ту же пару вершин, принято называть параллельными. Мультиграф, у которого максимальное число параллельных дуг -- , называют-графом.Рассмотрим неориентированный мультиграф (s-граф) , n -- вершин, -- ребёр, -- связных компонент. -- цикломатическое число (число ребер в остовах всех p связных компонент графа). -- коцикломатическое число. Если граф отождествить с электрической цепью, то определенные числа приобретают физический смысл. -- наибольшее число независимых круговых токов в электрической цепи. -- наибольшее число независимых разностей потенциалов в электрической цепи. Рассмотрим, например, электрическую цепь, показанную на рисунке 3а. Неориентированный граф G этой цепи состоит из единственной связной компоненты и изображен на рис. 3б ,где остов Т показан жирной линией .Добавление любого ребра из , не принадлежащего, к ребрам дерева приводит к образованию точно одного (простого) цикла, состоящего из ребер остова , лежащих на (единственной) цепи из в, и только что добавленного ребра. Например, добавляя ребро, получаем цикл .Так как в графе имеется ребер, из которых лежат в , то число всех циклов, построенных таким способом, равно , что совпадает с цикломатическим числом графа . В примере на рисунке 3 число таких циклов равно , они изображены на рисунке 3б пунктирными линиями и обозначены через Все эти циклы, очевидно, независимы между собой, так как каждый из них имеет по крайней мере одно ребро, не принадлежащее никакому другому циклу. В общем случае циклов, получаемых добавлением какого-либо ребра из , не лежащего в , к ребрам , называются фундаментальными циклами. Если семейство этих циклов обозначить черезв нашем примерето любой другой цикл в графе, не принадлежащий к , может быть выражен в виде линейной комбинации циклов из , если принять следующее соглашение :Пусть каждый фундаментальный цикл представлен -мерным вектором, в котором j-я компонента равна 1 или 0 в зависимости от того, принадлежит лиj-е ребро данному циклу. Тогда, используя как символ сложения по модулю 2, любой цикл можно представить как сумму по модулю 2 фундаментальных циклов. Так, цикл на рисунке 3б может быть представлен в виде Отметим, что обращение вышеприведенного утверждения неверно, а именно некоторая сумма по модулю 2 фундаментальных циклов не обязательно дает единственный цикл, но может представлять два и более циклов. Например, сумма соответствует двум циклам () и Таким образом, для порождения всех циклов графа не надо брать все комбинаций фундаментальных циклов и складывать их но модулю 2: некоторые из этих сумм на самом деле не будут циклами.
Страницы: 1, 2, 3, 4
|
