Курсовая: Нахождение кротчайшего остова ориентированного графа, используя алгоритмы Краскала и Прима - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

Нахождение кротчайшего остова ориентированного графа, используя алгоритмы Краскала и Прима

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 4049 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

20 Министерство образования и науки Российской Федерации Воронежский Институт Высоких Технологий Факультет Информационных технологий Курсовая работа По дисциплине “ Дискретная математика ” По теме : « Нахождение кротчайшего остова ориентированного графа, используя алгоритмы Краскала и Прима” Выполнил: Студент группы ИН-044 Рязанцев А.В. Руководитель: доцент Белецкая С.Ю. Воронеж 2007 Содержание Введение 1. Исторические сведения Правило Эйлера 2. Основные термины и теоремы теории графов Свойства связных графов Эквивалентные определения дерева. 3. Ориентированный граф 4 . Нахождение кратчайших путей в графе Начальные понятия Алгоритм нахождения кратчайшего пути 5 . Алгоритмы Краскала и Прима Алгоритм Краскала Алгоритм Прима Задача Прима– Краскала. 6 . Листинг программы Заключение Литература Введение Теория графов представляет собой интересный предмет, связанный со многими аспектами науки и техники, находящий широкое практическое применение. Наше столетие было свидетелем неуклонного развития теории графов. В этом процессе явно заметно влияние запросов новых областей приложений: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем в области психологии и биологии, электрики, моделей кристаллов и структур молекул и др. В наше насыщенное событиями время в любой области деятельности востребован человек, который равноценно владеет не только теорией, но и практикой, в то время как статистические исследования показали, что умение учащихся интегрировать знания и применять их для получения новых знаний и объяснения явлений, происходящих в окружающем мире получили достаточно низкую оценку специалистов. Изучение теории графов в немалой степени способствует разрешению этой проблемы благодаря своей специфике, а то, что этот предмет еще недостаточно изучен и представляет собой огромное поле для исследований и интересных открытий способно стимулировать интерес учащихся к познанию и самообучению, что так необходимо в нашем обществе. 1 . Исторические сведения ТЕОРИЯ ГРАФОВ - это область дискретной матема тики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов-граф и его обобщения. Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и другие). Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторе ний, полученный Л. Эйлером при реше нии задачи о Кенигсбергских мостах. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может“. Кенигсбергские мосты схематически можно изобразить так. Правило Эйлера 1. В графе, не имеющем вершин нечетных степеней, существует обход всех рёбер (причем каждое ребро проходится в точности один раз) с началом в любой вершине графа. 2. В графе, имеющем две и только две вершины с нечетными степенями, существует обход с началом в одной вершине с нечетной степенью и концом в другой. 3. В графе, имеющим более двух вершин с нечетной степенью, такого обхода не существует. Существует еще один вид задач, связанных с путешествиями вдоль графов. Речь идёт о задачах, в которых требуется отыскать путь, проходящий через все вершины, причем не более одного раза через каждую. Цикл, проходящий через каждую вершину один и только один раз, носит название гамильтоновой линии( в честь Уильяма Роуэна Гамильтона, знаменитого ирландского математика прошлого века, который первым начал изучать такие линии). К сожалению, пока еще не найден общий критерий, с помощью которого можно было бы решить, является ли данный граф гамильтоновым, и если да, то найти на нём все гамильтоновы линии. Другая старая топологическая задача, которая особенно долго не поддавалась решению и будоражила умы любителей головоломок, известна как “задача об электро -, газо - и водоснабжении”. В 1917 году Генри Э.Дьюдени дал ей такую формулировку. В каждый из трёх домов, изображенных на рисунке, необходимо провести газ, свет и воду. Свет вода газ Можно ли так проложить коммуникации, чтобы они, нигде не пересекаясь друг с другом, соединяли каждый дом с источниками электричества, газа и воды? Иначе говоря, можно построить плоский граф с вершинами в шести указанных точках? Оказывается, такой граф построить нельзя. Об этом говорится в одной очень важной теореме – так называемой теореме Куратовского. Теорема утверждает, что каждый граф, не являющийся плоским, содержит в качестве подграфа один из двух простейших пространственных графов: В середине 19 в. появились работы, в которых при решении практических задач были получены результаты, относящиеся к теории графов. Так, например, Г. Кирхгоф при составлении полной системы уравнений для токов и напряжений в электрической схеме предложил по существу представлять такую схему графом и находить в этом графе остовные де ревья, с помощью которых выделяются линейно независи мые системы контуров. А. Кэли, исходя из задач подсчета числа изомеров предельных углеводородов, пришел к задачам перечисления и описания деревьев, обладающих заданными свойствами, и решил некоторые из них. 2. Основные термины и теоремы теории графов 1. Граф - Пара объектов G = ( X , Г ) ,где Х - конечное множество ,а Г – конечное подмножество прямого произведения Х*Х . При этом Х называется множеством вершин , а Г - множеством дуг графа G . 2. Любое конечное множество точек (вершин), некоторые из которых попарно соединены стрелками , (в теории графов эти стрелки называются дугами), можно рассматривать как граф. 3. Если в множестве Г все пары упорядочены, то такой граф называют ориентированным . 4. Дуга - ребро ориентированного графа. 5. Граф называется вырожденным , если у него нет рёбер. 6. Вершина Х называется инцидентной ребру G , если ребро соединяет эту вершину с какой-либо другой вершиной. 7. Подграфом G(V 1 , E 1 ) графа G(V, E) называется граф с множеством вершин V 1 Н V и множеством ребер (дуг) E 1 Н E, - такими, что каждое ребро (дуга) из E 1 инцидентно (инцидентна) только вершинам из V 1 . Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф). 8. Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого – U , содержащий те и только те рёбра, оба конца которых входят в U . 9. Подграф называется остовным подграфом , если множество его вершин совпадает с множеством вершин самого графа. 10. Вершины называются смежными , если существует ребро , их соединяющее. 11. Два ребра G 1 и G 2 называются смежными , если существует вершина, инцидентная одновременно G 1 и G 2 . 12. Каждый граф можно представить в пространстве множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам (или дугам - в последнем случае направление обычно указывается стрелочками). - такое представление называется укладкой графа. 13. Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежные . 14. Конечная последовательность необязательно различных рёбер E 1 ,E 2 ,...E n называется маршрутом длины n, если существует последовательность V 1 , V 2 , ... V n необязательно различных вершин, таких, что E i = (V i-1 ,V i ). 15. Если совпадают, то маршрут замкнутый . 16. Маршрут, в котором все рёбра попарно различны, называется цепью . 17. Замкнутый маршрут, все рёбра которого различны, называется циклом . Если все вершины цепи или цикла различны, то такая цепь или цикл называются простыми . 18. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом . 19. Граф называется связным , если для любых двух вершин существует путь, соединяющий эти вершины. 20. Степень вершины - число ребер, которым инцидентна вершина V, обозначается D(V). Э квивалентные определения дерева 1. Связный граф называется деревом, если он не имеет циклов. 2. Содержит N-1 ребро и не имеет циклов. 3. Связный и содержит N-1 ребро. 4. Связный и удаление одного любого ребра делает его несвязным. 5. Любая пара вершин соединяется единственной цепью. 6. Не имеет циклов и добавление одного ребра между любыми двумя верши- нами приводит к появлению одного и только одного цикла. 3. Ориентированный граф Определение. Ориентированным графом (сокращенно: орграфом ) называется множество точек и соединяющих эти точки ориентированных непрерывных линий. Точки будем называть вершинами , ориентированные линии – дугами графа. Орграф часто будем обозначать парой (V,E), где V – множество вершин, Е – множество дуг графа. При изображении орграфа ориентацию будем указывать стрелкой на дуге (см. рис. 6.1). Если дуга е, соединяющая вершины x и y, ориентирована от х и y, то будем говорить, что х – начало дуги и х – конец дуги е, или что дуга е выходит из х и заходит в y. Такую дугу е будем иногда называть (x,y)– дугой . Например, дуга е 2 выходит из вершины а и заходит в вершину b (см. рис. 3 .1). Вершины x и y будем называть смежными , если существует (x,y)– дуга или (y,x)– дуга. Если дуга е соединяет вершины x и y, то будем говорить, что е инцидентна вершинам x и y. Рис. 3 .1 Дугу, выходящую из некоторой вершины и заходящую в ту же вершину, будем называть петлей , а дуги, выходящие из одной и той же вершины и заходящие в одну и ту же вершину, будем называть кратными . Так, дуги е 5 и е 6 являются кратными, а дуга е 1 – петлей (см. рис. 3 .1). Вершину, из которой не выходит и в которую не заходит ни одна дуга, будем называть изолированной . Например, i – изолированная вершина. Обобщим понятие степени вершины для орграфов. Определение . Пусть G – орграф. Полустепенью исхода r – (v) вершины v графа G называется число дуг, выходящих из v, полустепенью захода r + (v) – число дуг, заходящих в v. Например, для графа, изображенного на рис. 6.1, имеем, что r – (b)=2, r + (b)=1, r – (c)=0, r + (c)=3. Следующее утверждение достаточно очевидно. Предложение . Сумма полустепеней исхода всех вершин графа равна суммe полустепеней захода всех вершин . Определение . Вершина v ориентированного графа называется источником , если r + (v) № 0 и r – (v) № 0, и стоком , если r + (v) № 0 и r – (v)=0. Так для графа на рис. 3 .1 вершина с является стоком, а источника этот граф не имеет. Ясно, что орграф может иметь несколько источников и стоков. Ориентированные графы возникают в различных областях. Так, например, блок– схема алгоритма решения задачи является ориентированным графом, где вершинами являются блоки. Схема различных коммуникаций с односторонним движением, эйлеров граф с указанным направлением обхода ребер, схема маршрутов движения на местности – примеры ориентированных графов. Как и в неориентированном случае, мы будем задавать орграф, изображая на рисунке соответствующую геометрическую фигуру. Однако для решения задач, связанных с графами на компьютере, такое задание графа является неудобным. Для задания графа в этих случаях используются фактически те же способы, что и в неориентированном случае. Пусть n – число вершин, m – число ребер орграфа G=(V,E), V= v 1 ,v 2 ,…,v n и E= e 1 ,e 2 ,…e m . Матрица инцидентности графа G – это матрица A=(a ij ) размера nяm такая, что Матрица смежности графа G – это квадратная матрица B=(b ij ) порядка n такая, что b ij есть число дуг с началом в вершине v i и концов в v j . На рис. 3.2 и 3 .3 приведены примеры задания графов соответственно матрицами инцидентности и смежности. Рис. 3 .2 Рис. 3 .3 Для задания орграфов используются также списки смежностей и список ду г. В первом случае для каждой вершины v формируется список вершин, в которые заходят дуги, выходящие из v. В списке дуг каждая дуга е представляется парой вершин (x,y), где х – начало, y – конец дуги е. Введем понятие изоморфизма для орграфов. Определение . Орграфы G 1 =(V 1 ,E 1 ) и G 2 =(V 2 ,E 2 ) изоморфны , если существует биекция j: V 1 ® V 2 такая, что для любых вершин x,y О V 1 число (x,y)– дуг из Е 1 равно числу ( j (x), j (y)) – дуг из Е 2 . Графы G 1 и G 2 , изображен ные на рис. 3 .4, изоморфны; биекция я определяется нумерацией вершин. Нам понадобится также понятие подграфа. Определение . Орграф G
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Дапох - древнерусский бог спокойствия.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, курсовая по математике "Нахождение кротчайшего остова ориентированного графа, используя алгоритмы Краскала и Прима", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru