Лекция 21

ТЕМА: ПЛОСКИЕ ГРАФЫ

ПЛАН:

1. Задача о плоской укладке графа

2. Основные определения

3. Алгоритм плоской укладки графа

Главная

1. Задача о плоской укладке графа

Имеется много приложений задачи о плоской укладке графа. Одним из характерных является проблема размещения на печатных платах приборов различных радиоэлектронных устройств. Приборы (резисторы, трансформаторы, конденсаторы и т.д. ) должны быть размещены на плате таким образом, чтобы гальванические соединения, осуществляемые с помощью частей проводящего слоя платы, полностью соответствовали принципиальной схеме устройства. При этом должно быть соблюдено требование: проводники пересекаются лишь в контактах платы.

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

При большом числе приборов и гальванических соединений между ними задача представляется довольно сложной.

2. Содержание

   • Лекция 2
   • Лекция 3
   • Лекция 4
   • Лекция 5
   • Лекция 13
   • Лекция 14
   • Лекция 16
   • Основные понятия
   • Понятие множества. Способы задания множеств.
   • Понятие множества. Способы задания множеств.
   • Отношения между множествами.
   • 3, Операции над множествами.
   • Алгебра множеств.
   • Теорема о количестве подмножеств конечного множества.
   • Формула включений и исключений.
   • Лекция 2
   • 1.Понятие вектора. Прямое произведение множеств.
   • 2.Теорема о количестве элементов прямого произведения.
   • Понятие вектора. Прямое произведение множеств.
   • Теорема о количестве элементов прямого произведения.
   • Лекция 3
   • 2. Понятие высказывания.
   • 3. Логические операции над высказываниями
   • 4.Формулы алгебры логики.
   • Лекция 4
   • 2. Важнейшие равносильности алгебры логики.
   • 3.Равносильные преобразования формул.
   • Задачи для самостоятельного решения
   • Лекция 5
   • Дизъюнктивная нормальная форма.
   • Конъюнктивная нормальная форма.
   • Проблема разрешимости.
   • Лекция 6
   • Функции алгебры логики.
   • 3. Представление произвольной функции алгебры логики в виде формулы алгебры логики.
   • 4.Приложения алгебры логики в технике (релейно-контактные схемы).
   • Контрольные вопросы
   • Лекция 7
   • Совершенная дизъюнктивная нормальная форма.
   • Совершенная конъюнктивная нормальная форма.
   • Совершенная дизъюнктивная нормальная форма.
   • 2.Совершенная конъюнктивная нормальная форма.
   • Лекция 8
   • 2.Понятие минимальной днф. Метод минимизирующих карт.
   • 3.Метод Квайна.
   • 4.Метод Карно.
   • 5.Постановка задачи минимизации в геометрической форме.
   • 6.Сокращенная днф.
   • 7.Тупиковая днф. Днф Квайна.
   • Лекция 9
   • Некоторые логические операции. Двоичное сложение.
   • Полином Жегалкина.
   • Некоторые логические операции. Двоичное сложение.
   • Полином Жегалкина.
   • Лекция 10
   • Полная система . Достаточное условие полноты.
   • Критерий полноты системы булевых функций.
   • Независимые системы. Базис замкнутого класса.
   • Полная система. Достаточное условие полноты.
   • Критерий полноты системы булевых функций.
   • 3. Независимые системы. Базис замкнутого класса.
   • Лекция 11
   • Понятие предиката.
   • Логические операции над предикатами.
   • 1. Понятие предиката
   • 2. Логические операции над предикатами
   • Лекция 12
   • 2. Формулы логики предикатов.
   • Значение формулы логики предикатов.
   • 4. Равносильные формулы логики предикатов.
   • Лекция 13
   • Построение противоположных утверждений.
   • 3. Прямая, обратная и противоположная теоремы.
   • 4. Необходимые и достаточные условия.
   • 5. Доказательство методом от противного.
   • Задачи для самостоятельного решения
   • Лекция 14
   • 2. Использование метода математической индукции для нахождения сумм конечного числа слагаемых
   • 3. Использование метода математической индукции для доказательства неравенств и делимости выражений, зависящих от n на некоторое число
   • 4. Обобщение метода математической индукции
   • Контрольные вопросы
   • Лекция 15
   • Операции над бинарными отношениями.
   • 3. Свойства бинарных отношений.
   • 4. Специальные бинарные отношения.
   • Контрольные вопросы
   • Лекция 16
   • Функция
   • 1. 4. Отображение
   • Обратная функция
   • 2. Свойства отображений и функций
   • 3.Операции над функциями. Свойства операций
   • Контрольные вопросы
   • Лекция 17
   • Основные понятия .
   • 2. Смежность, инцидентность, степени вершин.
   • 3. Способы задания графов
   • Маршруты в неориентированном графе
   • Операции над графами.
   • Связность. Компоненты связности
   • Контрольные вопросы
   • Лекция 18
   • 2. Метрические характеристики неориентированного графа
   • Минимальные маршруты в нагруженных графах
   • Задачи на деревьях
   • Цикловой ранг графа. Цикломатическое число
   • Контрольные вопросы
   • Лекция 19
   • Эйлеровы цепи и циклы
   • Гамильтоновы циклы и цепи
   • Эйлеровы цепи и циклы
   • Гамильтоновы циклы и цепи.
   • Контрольные вопросы
   • Лекция 20
   • Двудольный граф. Условие существования двудольного графа
   • Паросочетания . Реберные покрытия
   • Двудольный граф. Условие существования двудольного графа
   • Паросочетания. Реберные покрытия
   • Контрольные вопросы
   • Лекция 21
   • Основные определения
   • Алгоритм плоской укладки графа
   • Контрольные вопросы
   • Лекция 22
   • Способы задания ориентированного графа
   • Путь в ориентированном графе
   • 4. Связность. Компоненты связности в орграфе
   • Контрольные вопросы
   • Лекция 23
   • 2. Минимальные пути в нагруженных орграфах
   • 3. Порядковая функция орграфа без контуров
   • Контрольные вопросы