zhChinese    enEnglish
  ПМ-ПУ  » Образование  » Программы курсов  » Дисциплины специализаций » Управление дискретными системами

Управление дискретными системами

Специальный курс

Лектор: д.ф.-м.н., проф. Горьковой В.Ф.

Глава I. Общие сведения.

Бинарные отношения. Матрица отношений. Алгебра отношений. Частичное упорядочение. Верхние и нижние грани. Бинарные отношения и графы. Способы задания графов. Группы, подгруппы. Перестановки. Теоремы Кэли и Лагранжа. Изоморфизмы и автоморфизмы для дискретных систем.

Глава II. ИЗОМОРФИЗМ.

О проблеме изоморфизма для графов. Графы Бержа. Представление графов. Разбиения и факторизация графов. Теорема о изоморфизме графов Бержа. Автоматы без выходов. Автоморфизмы автоматов и графов. Теоремы о автоморфизмах автоматов и графов. Гиперграфы. Изоморфизм гиперграфов. Декомпозиция сети связи и автоморфизмы графов.

Глава III. ДЕКОМПОЗИЦИЯ.

Операции над дискретными системами: умножение, сумма и композиция. Операции над графами и представлениями. Матрицы бинарных отношений. Операции над матрицами отношений. Теоремы о разложении представлений графов по различным операциям. Сведение разложения графов к разложению представлений. Обратная задача. Условие разложимости графов. Алгоритмы разложения. Алгебраические операции над автоматами. Декомпозиция автоматов. Алгоритмы декомпозиции автоматов. Восстановление графов по совокупности графов меньшей размерности.

Глава IV. Экстремальные задачи для дискретных систем.

Общие понятия и определения. Раскраски графов. Хроматическое число. Критические графы. Реберно-критические графы. Преобразования над множеством раскрасок. Элементарные преобразования. Приведенные раскраски. Z и R связность.Общие системы на графах. Инвариантные множества раскрасок. Устойчивые множества. 4-критические графы. Необходимый вид 4-критических графов. 5-критические графы. Необходимый вид 5-критических графов. Необходимый вид m-критических графов. Теорема о хроматическом числе произведения, суммы и композиции графов. Критические, реберно-критические и максимально-критические графы. Теоремы о реберно-критических и максимально-критических графах. Гамильтоновы графы и циклы. Задача об оптимальной загрузке оборудования.

ЛИТЕРАТУРА

  1. Холл М. Теория групп.- М.,1962.- 468 с.
  2. Биркгоф Т., Барти Т. Современная прикладная алгебра.- М.,1976.- 400 с.
  3. Зубов В.И. Устойчивость движения.- М., 1973.- 272 с.
  4. Харари Ф. Теория графов.- М.,1973.- 300 с.
  5. Берж К. Теория графов и ее применение.- М.,1962.- 319 с.
  6. Зыков А.А. Основы теории графов.- М., 1987.- 382 с.
  7. Горьковой В.Ф. Графы Бержа: изоморфизм, декомпозиция, раскраски.- СПб.: Изд-во СПбГУ, 1994.- 180 с.
  8. Мелихов А.Н. Ориентированные графы и конечные автоматы.- М.,1979.- 416 с.