Разработка алгоритмов оценки и построения минимальных связывающих деревьев в САПР электронной аппаратуры

Содержание.
Введение.
Глава 1. Определения и понятия
1.1 Элементы теории графов, используемые в работе.
1.2 Место минимальных связывающих деревьев в задачах САПР электронной аппаратуры.
1.3 Задача КраскалаПрима
1.4 Выводы.
Глава 2. Задача Штейнера.
2.1 Свойства деревьев Штейнера в прямоугольной метрике.
2.2 Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для задач ограниченной размерности.
2.3 Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для общего случая
2.4 Приближенные алгоритмы построения деревьев Штейнера в прямоугольной
. метрике .
2.5 Алгоритм выборки перспективных дополнительных точек
2.6 Оптимизация конфигурации дерева Штейнера.
2.7 Выводы.
Глава 3. Глобальная трассировка
3.1 Постановка задачи и стандартная методика глобальной трассировки 1
3.2 Первый этап i. Построение леса деревьев с учетом текущего распределения цепей по ребрам глобального графа.
3.3 Второй этап i. Оптимизация распределения цепей по ребрам глобального графа.
3.4 Третий этап i. Волновая трассировка
3.5 Сравнение результатов i с результатами других программ глобальной трассировки.
3.6 Выводы
Заключение.
Благодарности
Литература