Построение остовного (покрывающего) дерева графа Преподаватель «И и ИКТ» ГБОУ лицея 1557 Куленчик Олеся Николаевна.

Презентация:

Advertisements

Похожие презентации

Введение в теорию графов. ЗАДАЧА ПРОКЛАДКИ КОММУНИКАЦИЙ

Advertisements

Теория графов. Теория графов – обширный самостоятельный раздел дискретной математики. Используется при проектировании компьютерных сетей, трубопроводов,

Теория графов: подграфы и деревья 11 класс Профиль Учитель информатики Тивякова Л.А., к учебнику автора Угриновича Н.Д.

Алгоритмы Прима и Крускала построения остовного связного дерева минимального веса Гуляева Татьяна Викторовна учитель информатики и математики МБОУ СОШ.

Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.

Раскраски графов Раскраска вершин Пусть Г (V,E,Ф) – граф, раскраска вершин Г в n цветов – отображение f : V {1,2,…,n } Правильная раскраска вершин графа.

Остовные деревья Лекция 4. Задача «Минимальное остовное дерево» Дано: Граф G, веса c: E(G) R. Найти остовное дерево в G наименьшего веса или определить,

АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ..

ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Гамильтоновы графы применяются для моделирования многих практических задач. Основой всех таких задач служит классиче.

Задача о максимальном потоке в сети Алгоритм Фалкерсона-Форда.

ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная.

Теория графов. Теория графов – обширный самостоятельный раздел дискретной математики. Используется при проектировании компьютерных сетей, трубопроводов,

Графы Кенигсбергские мосты К XVIII веку через реку, на которой стоял город Кенигсберг (ныне Калининград), было построено 7 мостов, которые связывали.

Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.

Алгоритмы на графах. Задача о максимальном потоке в сетях Требуется от источника к стоку передать максимальное количество энергии. В условиях задачи о.

Алгоритм Эдмондса Лекция 11. Идея алгоритма Эдмондса Пусть есть некоторое паросочетание M, построим M-чередующийся лес F. Начинаем с множества S вершин.

ПРАВОСЛАВНЫЙ СВЯТО-ТИХОНОВСКИЙ БОГОСЛОВСКИЙ УНИВЕРСИТЕТ (БОГОСЛОВСКИЙ ФАКУЛЬТЕТ) Презентация по математике на тему: Элементы теории графов.

Номер варианта выбирается по параметру зачетки d 10 соотв Задача Коммивояжёра Имеется n городов, занумерованных числами.

Кластерный анализ. Цель работы ознакомление с проблемой кластерного анализа при интеллектуальной обработке данных в информационных системах; изучение.

Теория графов Алгоритмы на графах. Медиана графа Медиана вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимальная возможная.

Транксрипт:

Построение остовного (покрывающего) дерева графа Преподаватель «И и ИКТ» ГБОУ лицея 1557 Куленчик Олеся Николаевна

Основные определения Остовное дерево – это подграф, не содержащий циклов, включающий все вершины исходного графа, а сумма длин ребер которого минимальна. Цикломатическое число – показывает сколько ребер надо удалить, чтобы в нем не осталось ни одного цикла. Алгоритмы построения метод Крускаламетод Прима γ=n-m+1 Куленчик О.Н.

Метод Крускала Ребра исходного графа записываются в порядке возрастания их весов, каждая вершина графа помещается в одноэлементное подмножество. Просматривая ребра исходного графа, делается вывод о включении, либо исключении ребра из остовного дерева. При этом, если ребро связывает вершины, принадлежащие разным подмножествам, то оно включается в остовное дерево, в противном случае ребро удаляется из рассмотрения. Куленчик О.Н.

Пример. Пусть дан граф (взвешенный, неориентированный). Необходимо построить остовное дерево методом Крускала Множество вершин ребровес{V 1 }, {V 2 }, {V 3 }, {V 4 }, {V 5 }, {V 6 }опер (V 1, V 2 )1{V 1, V 2 }, {V 3 }, {V 4 }, {V 5 }, {V 6 }вкл (V 1, V 3 )1{V 1, V 2, V 3 }, {V 4 }, {V 5 }, {V 6 }вкл (V 1, V 4 )2{V 1, V 2, V 3, V 4 }, {V 5 }, {V 6 }вкл (V 2, V 3 )2искл (V 3, V 4 )3искл (V 3, V 5 )3{V 1, V 2, V 3, V 4, V 5 }, {V 6 }вкл (V 3, V 6 )4{V 1, V 2, V 3, V 4, V 5, V 6 }вкл (V 4, V 6 )4искл (V 5, V 6 )4искл (V 2, V 5 )5искл Подсчитаем цикломатическое число γ=n-m+1 Проверка сошлась, надо было удалить 5 ребер и мы их удалили γ=10-6+1=5 Куленчик О.Н.

Ответ: полученное остовное дерево

Метод Прима В этом методе первоначально выбирается любая вершина для начального рассмотрения ее по отношению к другим вершинам. После чего, выбирается минимальный вес (с вершиной). Вершину с минимальным весом удаляем из дальнейшего рассмотрения и сносим ее на следующий уровень. Дальше мы начинаем рассматривать снесенную вершину относительно других, оставшихся вершин.

Пусть дан граф (взвешенный, неориентированный). Необходимо построить остовное дерево методом Прима V2V3V4V5V6 V V2125- V3234 V434 V54 На первом шаге минимальный вес был 1 и принадлежал он вершине V2, поэтому мы ее выбираем и удаляем из дальнейшего рассмотрения. На втором шаге мы рассматриваем вершину V2, т.к. ее мы удалили, относительно оставшихся вершин. Причем на втором шаге не только проставляем веса ребер, но и сравниваем их с предыдущим уровнем. Если на предыдущем уровне вес был меньше, то сносим min вес. Заполним таблицу весами ребер, которые соединяют рассматриваемые вершины. Куленчик О.Н.

Ответ: полученное остовное дерево V2V3V4V5V6 V V2125- V3234 V434 V54 Метод построения: Берем последний min вес, он равен 4 и относится к вершине V6 что вершину V6 надо соединить в V3, т.к. первый раз 4, в этом столбце, появилось напротив вершины V3. Все оставшиеся вершины соединяются по этому же принципу. Куленчик О.Н.