КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Преобразование графа в остовное связное дерево минимального веса
Алгоритм Крускала (Kruscal) XIV. ДЕРЕВЬЯ Дерево – это граф, в котором нет циклов, то есть граф, в котором нельзя из некоторой вершины пройти по нескольким различным ребрам, и вернутся в ту же вершину. Остовным связным деревом называется подграф, включающий в себя все вершины исходного графа G, каждая вершина которого (дерева) достижима из любой другой, и не содержащий циклов.
Пусть G=(V,R) – связный взвешенный неориентированный граф (матрицу смежности см. на стр.). Цикломатическое число равно разности между количеством ребер и количеством вершин графа, увеличенной на единицу. у=т-п+1 Для графа G у =8-5+1=4. это значит, что для получения остовного связного дерева в графе G необходимо удалить 4 ребра, тогда в нем не останется ни одного цикла. Пример остовного связного дерева:
V2
V5
V3 V4
Для построения остовного связного дерева минимального веса используется алгоритм Крускала: 1. каждая вершина исходного графа помещается в одноэлементное подмножество, где все вершины изолированы: 2. ребра сортируются по возрастанию веса; 3. ребра последовательно включаются в остовное дерево. Существуют четыре случая: а) обе вершины ребра не принадлежат пока ни одному из множеств, тогда они объединяются в новое множество; б) одна из вершин принадлежит множеству, а другая – нет, тогда включаем вторую во множество первой; в) обе вершины принадлежат разным множествам, тогда эти множества объединяются; г) обе вершины принадлежат одному множеству, тогда данное ребро исключаем; 4. алгоритм заканчивает работу, когда все вершины объединяются в одно множество, при этом оставшиеся ребра не включаются в остовное дерево.
Остальные ребра в граф включать не надо, так как все их вершины уже принадлежат одному связному множеству. Получен граф, который: - является остовным, так как включает все вершины, - является связным, так как вершины в нем можно соединить маршрутом, - является деревом, так как в нем отсутствуют циклы, - обладает минимальным весом: R15 +R45 +R23 +R25= 10+15+25+30=80.
Дата добавления: 2014-01-20; Просмотров: 1310; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |