Читать онлайн «Применение графов для проектирования дискретных устройств»

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТЕХНИЧЕСКОЙ КИБЕРНЕТИКИ Издательство «наука» главная редакция физико-математической литературы МОСКВА 1974 A. H. МЕЛИХОВ, Л. С. БЕРШТЕЙН, В. М. КУРЕЙЧИК ПРИМЕНЕНИЕ ГРАФОВ ДЛЯ ПРОЕКТИРОВАНИЯ ДИСКРЕТНЫХ УСТРОЙСТВ лй ;•*¦;?-. '. ¦; v . ¦} л . ¦¦¦ ¦:$ . -*'. '. ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1974 бф. 6. 5 М 47 УДК 62-50 Применение графов для проектирования ди- дискретных устройств, А. Н. Мелихов, Л. С. Б е р- штейн, В. М. Курейчик, Главная редак- редакция физико-математической литературы изд-ва «Наука», М. , 1974, 304 стр. В книге рассматриваются основные этапы технического проектирования дискретных уст- устройств с помощью теории графов. Основное внимание уделяется решению задач разрезания графа схемы на заданное и произ- произвольное число подграфов, размещения графа схе- схемы па плоскости с минимизацией суммарной дли- длины и внутрисхемных пересечений ребер. Иссле- Исследуются вопросы планарности схем и трассировки соединений. Приводятся программы основных ал- алгоритмов проектирования дискретных устройств, представленные на языке ЛЯПАС. Книга рассчитана на специалистов в области вычислительной техники и кибернетики и может быть полезна студентам и аспирантам соответ- соответствующих специальностей. Илл. 150. Библ. 217 назв. Издательство «Наука», 1974 г. 30501-022 \,v*! 053{01)-74 ОГЛАВЛЕНИЕ Предисловие 7 Введение 9 Глава I. Основные определения и понятия теории графов 13 § 1, Способы задания, основные типы и части графов . 13 § 2. Связность графов 18 § 3. Основные числа графов 21 § 4. Метрика графов 30 § 5, Пленарные графы 33 § 6. Изоморфизм и изоморфное вложение графов ... 37 § 7. Переход от модульных схем к графам 40 § 8. Метод ветвей и границ . 43 Глава II. Компоновка элементов схем дискретных устройств 48 § 1. Покрытие функциональных схем схемой соединения модулей . 48 § 2. Постановка задачи разрезания графа схемы ... 57 • § 3. Последовательные алгоритмы разрезания 60 § 4. Итерационные алгоритмы разрезания 67 § 5. Разрезание графа схемы па произвольное число ча- частей ... . ¦... ... -. . 86 Глава III. Размещение графа схемы на плоскости ... . 106 § 1. Постановка задачи размещения модулей ... . 106 §2. Последовательные алгоритмы размещения . . . . 112 § 3. Итерационные алгоритмы размещения 122 § 4. Алгоритм размещения элементов методом ветвей и границ ... ... 150 Глава IV. Минимизация внутрисхемных пересечений дискрет- дискретных устройств ... 156 § 1. О числе пересечений ребер полных и кубичных гра- графов 166 6 ОГЛАВЛЕНИЕ § 2. Подсчет пересечений ребер произвольных графов при фиксированном расположении вершин на плоскости 171 § 3, Подсчет пересечений ребер произвольных графов при отображении в прямоугольную решетку 181 § 4. Минимизация числа пересечений ребер графя схемы 187 Глава V. Некоторые вопросы планарности графов схем . . 205 § 1. Методы определения планарности графа ... . . 205 ' § 2. О числе планарности графа ... ... ... . 207 § 3. Алгоритм определения планарности графа, имеющего гамильтонов цикл ... ... ... ... . 215 § 4.