Перейти к полному списку специальных курсов кафедры

Программа специального курса "Теория графов и синтез БИС"

2013/14 учебный год.

1. Планарная технология. Фотолитография. Принцип работы МОП-транзистора. КМОП реализация базовых логических элементов. Реализация автоматных функций КМОП-схемами.
2. Основные понятия теории графов. Дерево. Критерии, определяющие свойство графа быть деревом. Минимальное остовное дерево (м.о.д.) в связном взвешенном графе. Алгоритмы Краскала и Прима нахождения м.о.д. в связном взвешенном графе.
3. Формализация понятия большой интегральной схемы (БИС). Логическая схема. Укладка логической схемы. Гиперребра и граф противоречий. Определение БИС. Задача укладки элементов БИС и задача трассировки проводников.
4. Прямоугольная задача Штейнера. Теорема о существовании решения. Алгоритм нахождения минимального прямоугольного Штейнерова дерева.
5. Число вершинной связности и число реберной связности для графа. Связь этих характеристик графа между собой и с минимумом степеней вершин. Критерии двусвязности графа. Блоковый граф для данного графа, его свойства. Теорема о существовании в 3-связном графе двух вершин, удаление которых приводит к графу, не содержащему точек сочленения. Теорема Менгера.
6. Плоские графы. Грань плоского графа. Планарные графы. Теорема Эйлера. Доказательство непланарности графов K₅ и K_3,3. Критерий двусвязности плоского графа. Сведение задачи укладки графа к задачи укладки его блоков. Плоский граф, как подграф плоской триангуляции. Максимальный плоский граф и плоская триангуляция. Связь между числом вершин и числом ребер в плоской триангуляции. Сведение проверки планарности графа к аналогичному вопросу для трехсвязных графов. Теорема Понтрягина-Куратовского. Теорема Вагнера. Гамма-алгоритм для проверки планарности графа и укладки графа на плоскости (в случае его планарности ).
7. Степенная последовательность графа, n-последовательность, графическая последовательность. Теорема о возможности перехода от одной реализации графической последовательности к другой с использованием операции переключения. Критерии графичности последовательности: теоремы Гавела-Хакими и Эрдеша-Галлаи.
8. Хроматическое число графа. Критерий бихроматичности графа. Сведение задачи определения хроматического числа графа к определению хроматических чисел его блоков. Теорема Брукса. Достижимость оценки, доставляемой теоремой Брукса. Теорема Зыкова. Неравенства, связывающие число вершин графа, число его независимости и хроматическое число. Точность этих неравенств. Представление хроматической функции графа суммой хроматических функций полных графов. Хроматическая функция дерева. Теорема о возможности раскраски планарного графа не более чем в 5 цветов. Проблема 4-х красок. Теорема Крола.
9. Сортирующие сети. Правило нуля и единицы. Битонический сортировщик. Сортирующая сеть с глубиной равной по порядку квадрату логарифма от числа входов.
10. Реализация схем сложения и умножения n-разрядных двоичных чисел с глубиной O(log n). Метод Уолеса.
11. Задача отыскания кратчайшего пути между двумя заданными вершинами во взвешенном графе. Алгоритм Дийкстры. Корректность алгоритма Дийкстры, оценка времени его работы на графе с n вершинами. Применение алгоритма Дийкстры при решении задачи поиска кратчайшего пути на плоскости с многоугольными препятствиями между двумя заданными точками, а также к решению дискретной геодезической задачи.
12. Двудольные графы. Критерий двудольности графов. Алгоритм поиска наибольшего паросочетания в двудольном графе и оценка времени его работы на графах с n вершинами. Алгоритм построения совершенного паросочетания минимального веса во взвешенном графе K_n,n и оценка времени его работы.
13. Потоки в сетях. Максимальный поток, минимальный разрез. Теорема Форда-Фалкерсона. Алгоритмы Эдмондса-Карпа и «проталкивания предпотока» поиска максимального потока, оценки времени работы этих алгоритмов.
14. Алгоритмы Кернигана-Лина и Федосия-Матеуса для нахождения минимального сбалансированного разреза в графе, оценки времени работы этих алгоритмов.
15. Гордиан-алгоритм для приближенного поиска наилучшей укладки графа.

Литература.

1. В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. Лекции по теории графов. – М.: Наука Гл. Ред. Физ.-мат. Лит., 1990. – 384 с.

2. А.Ф. Сидоренко. О минимальных прямоугольных штейнеровых деревьях. Журнал «Дискретная математика». Том 1, вып. 2, 1989 г., с. 28 – 37.

3. Дискретная математика и математические вопросы кибернетики. Под общей редакцией С.В. Яблонского и О.Б. Лупанова. Том 1. – М.: Наука Гл. Ред. Физ.-мат. Лит., 1974. – 312 с.

4. В.Н. Нефедов, В.А. Осипов. Курс дискретной математики. Учеб. пособие. – М.: Изд-во МАИ, 1992. – 264 с.

Наверх