|
|
Кроме того существует алгоритм Дейкстры - Прима построения минимального остовного дерева.
Шаг 1. Выбрать произвольную вершину v с V и считать её ребром нулевой длины.
Шаг 2. Упорядочить рёбра графа в порядке возрастании весов. Пусть 0=wfv)Шаг 3. Включить ребро v с минимальным нулевым весом в строящееся дерево Т.
Шаг 4. Включить дерево Т ребра ei минимального веса, образующее связной граф без циклов с уже включёнными ребрами. Исключить из дальнейшего рассмотрения всякое просмотренное ребро е, образующее цикд с уже включенными ребрами. Повторять-шаг 4, пока не будут выбраны р — [ ребер ненулевого веса.
Отметим, что в данном алгоритме отбрасываются не все просмотренные рёбра, а только те, которые образуют цикл с уже включёнными рёбрами. Рёбра не образующие цикла с уже включёнными рёбрами, но и не образующие связного графа (дерева) с этими рёбрами, алгоритм «откладывает в сторону», возвращаясь к их просмотру при очередных возобновлениях шага 4.
Пусть al, а2,....ар-1 - рёбра дерева Т ненулевого веса в там порядке, в котором их выбрал алгоритм Дейкстры — Прима. Пусть к - наибольшее целое число, такое, что al, а2, ...,ак (к < р - 1) принадлежат минимальному остовному дереву Tmin. Тогда ребро а к+1 дереву Tmin уже не принадлежит, а рёбрам/,
а2.....ok образуют дерево Тк. Добавим ребро а к+1 в дерево Tmin. В графе
Tmin о { а к+1 } содержится единственный цикл, проходящий через ребро а к+1. Среди ребер этого цикла, не принадлежащих дереву ТА, есть ребро е, которое, как и ребро а к+ /, имеет роено одну общую вершину с деревом Тк. В соответствии с правилом выбора ребра ак+1 w(el ) > w(a к+1). Удалим ребро е из графа Tmin o{ а к+1 }. Мы получим дерево Т\ вес которого меньше или равен весу дерева Tmin, так что дерево Т^ - минимальное остовное дерево, содержащее рёбра al, a2,..., а к+1 , но это противоречит определению к. Значит, к=р — / и Т- минимальное остовное дерево графа G.
ПОСТАНОВКА ПРОБЛЕМЫ БОРСУКА В ПРОСТРАНСТВЕ (R*)
Вильданова Д. А., группа 17-11 (ЗариповаЗ. Ф.)
Проблема Борсука: найти минимальное число частей меньшего ди g на которое может быть разбита произвольное ограниченное мноЖ_ае1кс» пространстве. Пусть дано какое-то множество Лс/?".тгде п<3- П°п . дЛЯ представить А в виде А—Ах \J...[}A г, предполагая, что diam А < oia
f пля кот°™ каждого i, / такое представление имеет место. Понятно, что f(A) - это и есть м есТВоу<-число частей меньшего диаметра, на которые может быть разбито м дь. на
Определим f(n) как максимум по всем AaR" величин f(A). В сво нИченИ°^ f(n) частей меньшего диаметра разбивается уже произвольное F"
194
|
