рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Работа сделанна в 2007 году

Нахождение кротчайшего остова ориентированного графа, используя алгоритмы Краскала и Прима - раздел Математика, - 2007 год - «Нахождение Кротчайшего Остова Ориентированного Графа, Используя Алгоритмы Кр...

«Нахождение кротчайшего остова ориентированного графа, используя алгоритмы Краскала и Прима” Выполнил: Студент группы ИН-044 Рязанцев А.В. Руководитель: доцент Белецкая С.Ю. Воронеж 2007 Содержание Введение 1. Исторические сведения Правило Эйлера 2. Основные термины и теоремы теории графов Свойства связных графов Эквивалентные определения дерева. 3. Ориентированный граф 4. Нахождение кратчайших путей в графе Начальные понятия Алгоритм нахождения кратчайшего пути 5. Алгоритмы Краскала и Прима Алгоритм Краскала Алгоритм Прима Задача Прима–Краскала. 6. Листинг программы Заключение Литература Введение Теория графов представляет собой интересный предмет, связанный со многими аспектами науки и техники, находящий широкое практическое применение.

Наше столетие было свидетелем неуклонного развития теории графов.В этом процессе явно заметно влияние запросов новых областей приложений: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем в области психологии и биологии, электрики, моделей кристаллов и структур молекул и др. В наше насыщенное событиями время в любой области деятельности востребован человек, который равноценно владеет не только теорией, но и практикой, в то время как статистические исследования показали, что умение учащихся интегрировать знания и применять их для получения новых знаний и объяснения явлений, происходящих в окружающем мире получили достаточно низкую оценку специалистов. Изучение теории графов в немалой степени способствует разрешению этой проблемы благодаря своей специфике, а то, что этот предмет еще недостаточно изучен и представляет собой огромное поле для исследований и интересных открытий способно стимулировать интерес учащихся к познанию и самообучению, что так необходимо в нашем обществе. 1. Исторические сведения ТЕОРИЯ ГРАФОВ - это область дискретной матема¬тики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете.

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

Основной объект теории графов-граф и его обобщения.

Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и другие). Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторе¬ний, полученный Л. Эйлером при реше¬нии задачи о Кенигсбергских мостах.

Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов.

Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно.Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство.

После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может“. Кенигсбергские мосты схематически можно изобразить так. Правило Эйлера 1. В графе, не имеющем вершин нечетных степеней, существует обход всех рёбер (причем каждое ребро проходится в точности один раз) с началом в любой вершине графа. 2. В графе, имеющем две и только две вершины с нечетными степенями, существует обход с началом в одной вершине с нечетной степенью и концом в другой. 3. В графе, имеющим более двух вершин с нечетной степенью, такого обхода не существует. Существует еще один вид задач, связанных с путешествиями вдоль графов. Речь идёт о задачах, в которых требуется отыскать путь, проходящий через все вершины, причем не более одного раза через каждую.

Цикл, проходящий через каждую вершину один и только один раз, носит название гамильтоновой линии( в честь Уильяма Роуэна Гамильтона, знаменитого ирландского математика прошлого века, который первым начал изучать такие линии). К сожалению, пока еще не найден общий критерий, с помощью которого можно было бы решить, является ли данный граф гамильтоновым, и если да, то найти на нём все гамильтоновы линии.

Другая старая топологическая задача, которая особенно долго не поддавалась решению и будоражила умы любителей головоломок, известна как “задача об электро газо - и водоснабжении”. В 1917 году Генри Э.Дьюдени дал ей такую формулировку.

В каждый из трёх домов, изображенных на рисунке, необходимо провести газ, свет и воду. Свет вода газ Можно ли так проложить коммуникации, чтобы они, нигде не пересекаясь друг с другом, соединяли каждый дом с источниками электричества, газа и воды? Иначе говоря, можно построить плоский граф с вершинами в шести указанных точках? Оказывается, такой граф построить нельзя.

Об этом говорится в одной очень важной теореме – так называемой теореме Куратовского. Теорема утверждает, что каждый граф, не являющийся плоским, содержит в качестве подграфа один из двух простейших пространственных графов: В середине 19 в. появились работы, в которых при решении практических задач были получены результаты, относящиеся к теории графов.Так, например, Г. Кирхгоф при составлении полной системы уравнений для токов и напряжений в электрической схеме предложил по существу представлять такую схему графом и находить в этом графе остовные де¬ревья, с помощью которых выделяются линейно независи¬мые системы контуров.

А. Кэли, исходя из задач подсчета числа изомеров предельных углеводородов, пришел к задачам перечисления и описания деревьев, обладающих заданными свойствами, и решил некоторые из них.

– Конец работы –

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

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

Алгоритм и требования к алгоритму свойства алгоритма
Object Inspector Options goEditing True... StringGrid FexedCols Rows n... Var I J integer Begin...

АЛГОРИТМЫ ВЫПОЛНЕНИЯ ПРАКТИЧЕСКИХ НАВЫКОВ, НЕОБХОДИМЫХ ДЛЯ ОКАЗАНИЯ ПЕРВОЙ ВРАЧЕБНОЙ ПОМОЩИ ПРИ НЕОТЛОЖНЫХ АЛГОРИТМЫ ВЫПОЛНЕНИЯ ПРАКТИЧЕСКИХ НАВЫКОВ, СОСТОЯНИЯХ И ЗАБОЛЕВАНИЯХ
АЛГОРИТМЫ ВЫПОЛНЕНИЯ ПРАКТИЧЕСКИХ НАВЫКОВ НЕОБХОДИМЫХ ДЛЯ ОКАЗАНИЯ ПЕРВОЙ ВРАЧЕБНОЙ ПОМОЩИ ПРИ СОСТОЯНИЯХ И ЗАБОЛЕВАНИЯХ...

Эксцентриситет вершины. Релейно-контактные (переключательные) схемы. Алгебра высказываний. Операции над множествами. Графы и Способы задания графов. Релейно-контактные схемы
также однозначно определяет структуру графа... Весьма важным видом графа является связный граф не имеющий циклов он... Рассмотрим связный граф пусть и две его вершины Длина кратчайшего маршрута называется расстоянием между...

Алгоритм поиска кратчайших расстояний в графе
Алгоритм поиска кратчайших расстояний в графе... Алгори тм Де йкстры... Задача о кратчайшем пути...

Введение в теорию графов 1. Лекция: Графы и способы их представления
Введение в теорию графов Лекция Графы и способы их представления... Приводятся начальные сведения о графах и основные понятия и определения такие как орграф смешанный граф дубликат графа дуга петля полустепени...

Понятие алгоритма, его свойства. Описание алгоритмов с помощью блок схем на языке Turbo Pascal
Каким же образом компьютер решает сложнейшие задачи обработки информации Для решения этих задач программист должен составить подробное описание… В разных ситуациях в роли исполнителя может выступать электронное или… Составление алгоритмов и вопросы их существования являются предметом серьзных математических исследований. Свойства…

Раскраска графа. Хроматические полиномы. Алгоритм раскраски
Вершинная К раскраска графа присвоения его вершинам К различных цветов...

Понятие и её свойства алгоритма. Способы записи алгоритмов.
Способы записи алгоритмов... Оформить записать алгоритмы можно несколькими способами... Словесный способ записи алгоритмов основан на использовании средств обычного языка но с жестко ограниченным...

Ориентированные графы
Особое значение с практической точки зрения имеет теория графов, использующаяся при проектировании интегральных схем и схем управления, исследовании… В приложениях часто приходится рассматривать гра¬фы с ориентированными… Примерами таких графов являются сети автомобильных дорог с односторонним дви¬жением или схемы программ для ЭВМ.…

Остовы графов
тема quot Элементы теории графов Виды и способы задания графов quot... Даны населенные пункты расстояния между которыми известны Требуется найти маршрут проходящий через все пункты по...

0.027
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам