Конструкторско-технологическое обеспечение производства ЭВМ. Классификация интегральных схем, страница 4

Функциональный	Алгоритмический	Конструкторский	Технологический
Системный	Программных систем	Шкафа/стойки	Схем технических процессов
		Панели
Логический
	Программных модулей	Типовых элементов замены	Маршрутных технологий
Схемотехнический		Модуля
			Технологических операций
	Микропрограмм	Кристалла
Компонентов
		Ячейки

13.  Характеристические числа графов

13.1.  Цикломатическое число – число ребер, которые необходимо удалить из графа, чтобы он стал деревом.

n(G) = кол_ребер_графа – кол_ребер_дерева = кол_ребер_графа – (кол_вершин - 1)

13.2.  Хроматическое число – наименьшее число непересекающихся подмножеств, на которое можно разбить вершины графа, чтобы ребра графа соединяли вершины только разных подмножеств; количество красок для раскраски графа

13.3.  Число планарности – минимальное количество ребер, которое необходимо удалить из графа, чтобы он стал планарным, т.е. который можно расположить на плоскости так, чтобы избежать пересечения ребер.

Q(G); для полного графа Kn: Q(Kn) = (n-3)(n-4)/2

13.4.  Число внутренней устойчивости – максимальное количество несмежных вершин

a(G)

13.5.  Число внешней устойчивости – наименьшее количество вершин графа такое, чтобы все остальные вершины были с ними смежны

14.  Планарность графов

14.1.  Плоский граф – это граф, расположенный на плоскости так, что ребра имеют общие точки только в вершинах

14.2.  Изоморфные графы: у них одинаковое количество вершин и каждой паре вершин, соединенной в первом графе, соответствует пара вершин, соединенных во втором.

14.3.  Планарный граф – граф, изоморфный плоскому.

15.  Раскраска графов

15.1.  Алгоритм Вейсмана

15.1.1.  Построение всех максимальных внутренне устойчивых множеств

15.1.1.1.  Для каждого элемента xi рассчитываем количество ненулевых связей ri

15.1.1.2.  Выбираем максимальное ri

Ci = xi U xa xb xc…, где xa… - вершины, смежные xi

15.1.1.3.   Удаляем из графа вершины Ci и повторяем до тех пор, пока граф не станет пустым.

15.1.1.4.  Составляем произведение Ci:

П = C1 C2 … = (после минимизации) V Kj

15.1.1.5.  Для каждого Kj строится Yj, в который входят все вершины, не вошедшие в Kj – внутренне устойчивые множества.

15.1.2.  Выбор минимального количества внутренне устойчивых множеств

15.1.2.1.  Для каждой вершины строится ti=VYj, Yj – множества, в которые входит вершина

15.1.2.2.  П = t1 t2 … = (после минимизации) V(LYj)

15.1.2.3.  Выбираем терм с минимальным количеством сомножителей (это количество – хроматическое число графа). Каждое Yj, вошедшее в этот терм – множество вершин, которое может быть окрашено одним цветом.

15.2.  Приближенный алгоритм раскраски с упорядочиванием

15.2.1.  Цвет j=1

15.2.2.  Для каждой вершины xi подсчитываем число связей ri.

15.2.3.  Вершины упорядочиваются по невозрастанию ri.

15.2.4.  Просматривая последовательность в цвет j окрашивают вершины, несмежные с уже окрашенными

15.2.5.  Если не все вершины окрашены, из графа удаляются окрашенные вершины, j=j+1, повторить с п. 15.2.2

16.  Этапы компоновки, размещения элементов и трассировки межсоединений

16.1.  Компоновка

16.1.1.  Определение функции критерия

16.1.2.  Получение начального варианта решения

16.1.3.  Вычисление функции критерия

16.1.4.  Выбор лучшего варианта. Получение очередного варианта решения.

16.1.5.  Срабатывание правила останова (время, число итераций, улучшение становится меньше фиксированной величины, перебор всех вариантов)