Решение задач Алгоритм Крускала




НазваниеРешение задач Алгоритм Крускала
Дата конвертации23.02.2013
Размер445 b.
ТипРешение


Графы

  • Введение в теорию графов

  • Решение задач

  • Алгоритм Крускала


ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ

  •     Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783).      Через город протекает река Преголя. Она делится на два рукава, огибает остров и имеет семь мостов.     



Свойства графа(Эйлер):

  • Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.      Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине.      Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.

  • Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ?



Задача

  • Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?



Задача

  • На урок в танцкласс пришли слон, волк и лев. Партнершами для них были выбраны мышка, белочка и лисичка. Помогите учителю расставить их в пары, если белочка боится, что ее съест волк, а слон – что он раздавит мышку. Сколько вариантов составления пар есть у учителя танцев? Перечислите их.



Задача

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

  • Винни-Пух – Кролик – 60

  • Иа-Иа – Пятачок – 55

  • Иа-Иа - Винни-Пух – 30

  • Винни-Пух - Пятачок – 40

  • Кролик – Пятачок - 50

  • Кролик – Иа-Иа – 45



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

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



Основные понятия теории графов

  • Граф задается парой множеств G(V,R)

  • Вершины называются смежными, если их соединяет ребро

  • Количество вершин и ребер – мощность множеств V,R

  • Ребро и любая из двух вершин называются инцидентными

  • Степень вершины – количество инцидентных ей ребер

  • Вершины, не имеющие инцидентных ребер, называются изолированными



Основные понятия теории графов

  • Маршрут графа – последовательность чередующихся вершин и ребер

  • Замкнутый маршрут – маршрут, в котором начальная и конечная вершины совпадают

  • Простая цепь – маршрут, в котором все ребра и вершины различны

  • Связный граф – граф, в котором каждая вершина достижима из любой другой



Основные понятия теории графов

  • Ориентированный граф (орграф) имеет направленные ребра – дуги

  • Входящая степень вершины – количество входящих дуг

  • Исходящая степень вершины - количество исходящих дуг

  • Взвешенный граф – граф, ребрам или дугам которого поставлены в соответствие числовые величины

  • Вес сети равен сумме весов ее ребер



Способы задания графа

  • Явное задание графа как алгебраической системы {a,b,c,d}: {(a,b), (b,a),(b,c),(c,b),(a,c),(c,a),(c,d),(d,c)}

  • Геометрический

  • Матрица смежности

  • Матрица инцидентности



Составить матрицы смежности для графов



Составить матрицы смежности для графов



Основные понятия теории графов(продолжение)

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

  • Остовной связный подграф – подграф графа G, который содержит все его вершины и каждая вершина достижима из любой другой

  • Дерево – граф без циклов

  • Остовное связное дерево – подграф, включающий вершины исходного графа G, не содержащего циклы, каждая вершина которого достижима из любой другой.



Основные понятия теории графов

  • Цикломатическое число γ показывает, сколько ребер нужно удалить из графа, чтобы в нем не осталось циклов

  • γ =m-n+1,

  • m- количество ребер

  • n-количество вершин



Алгоритм Крускала построения остовного связного дерева минимального веса

  • Построение остовного подграфа с изолированными вершинами

  • Упорядочить ребра по возрастанию

  • Ребра последовательно, по возрастанию их весов, включаются в остовное дерево до тех пор, пока не включены все вершины

    • Обе вершины включаемого ребра принадлежат одноэлементным множествам, тогда они объединяются в новое, связное подмножество
    • Одна из вершин принадлежит связному подмножеству, другая нет, тогда включаем вторую в то мн-во, которому принадлежит первая
    • Обе вершины принадлежат разным подмножествам, тогда объединяем подмножества
    • Обе вершины принадлежат одному подмножеству – исключаем ребро


Задание

  • Применить алгоритм Крускала для графов



Компьютерный практикум: создать проект «Построение остовного связного дерева графа» (на языке Visual Basic или Turbo Delfi – по выбору)

  • Компьютерный практикум: создать проект «Построение остовного связного дерева графа» (на языке Visual Basic или Turbo Delfi – по выбору)

  • Д/з: §1.10.1, 1.10.2(1.10.3)



Похожие:

Решение задач Алгоритм Крускала iconРешение задач Алгоритм решения задач Задачи на сравнение величин

Решение задач Алгоритм Крускала iconПлан урока: 1 значение теоремы Пифагора; 2 решение задач по готовым чертежам; 3 решение исторических задач

Решение задач Алгоритм Крускала iconРешение арифметических задач
Римская система счисления. Представление чисел в ней и решение арифметических задач
Решение задач Алгоритм Крускала iconЛекции Определить место генетических алгоритмов в Data Mining
Генетический алгоритм (англ genetic algorithm) это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования...
Решение задач Алгоритм Крускала iconРешение ряда задач: Для устранения сложившейся ситуации необходимо решение ряда задач
Формирование и совершенствование теоретических знаний и практических навыков обучающихся в области технической защиты информации...
Решение задач Алгоритм Крускала iconУрока Линейный алгоритм Разветвляющийся алгоритм Циклический алгоритм Конкурс

Решение задач Алгоритм Крускала iconРешение психолого-педагогических задач
Педагогические технологии дополнительного образования детей должны быть ориентированы на решение психолого-педагогических задач
Решение задач Алгоритм Крускала iconПлан урока : Организационный момент + домашнее задание. Повторение материала устный опрос. Решение задач работа в группах. Самостоятельное решение задач.
Организационный момент + домашнее задание. Повторение материала устный опрос. Решение задач работа в группах. Самостоятельное решение...
Решение задач Алгоритм Крускала iconРешение задач Урок геометрии в 11 классе
Отработка навыков и умений решения простейших задач в координатах и решения задач на скалярное произведение векторов
Решение задач Алгоритм Крускала iconУрок проект: Комбинаторика и ее применение Проблемный вопрос: Может ли нам комбинаторика помочь в реальной жизни?
Решение комбинаторных задач развивает творческие способности, помогает при решении олимпиадных задач, задач из егэ
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница