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

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

Свойства связных графов Эквивалентные определения дерева. 3. Ориентированный граф 4. Нахождение кратчайших путей в графе Начальные понятия Алгоритм нахождения кратчайшего пути 5. Алгоритмы Краскала и Прима Алгоритм Краскала Алгоритм Прима Задача Прима–Краскала. 6. Листинг программы Заключение

Литература Введение Теория графов представляет собой интересный предмет, связанный со многими аспектами науки и техники, находящий широкое практическое применение. Наше столетие было свидетелем неуклонного развития теории графов. В этом процессе явно заметно влияние запросов новых областей приложений: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем в области психологии

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

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

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

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

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

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

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

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

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

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

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

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