Связность в орграфах.

7. Раскраски карт. Планарные графы. Критерии планарности. Формула Эйлера. Геометрически двойственный граф. Правильная раскраска карты. Теорема Хивуда. Теорема о четырѐх красках.

8. Рѐберные раскраски графов. Хроматический индекс. Теорема Кѐнига. Теорема Визинга.

9.Деревья. Двоичные деревья. Код Прюффера.

10. Потоки в сетях. Задача о максимальном потоке.

11. Алгоритмы проверки планарности графов.

12.

13. Связность. Вершинная и реберная связность. Двусвязные графы. Теорема Менгера.

Поиск на графе.

Независимые множества. Клики. Вершинные покрытия.

Паросочетания и реберные покрытия..

Задача почтальона.

 

 

Порядок и сроки выдачи заданий на курсовое проектирование

- Техническое задание на проектирование, выдаваемое руководителем студенту, является исходным документом для разработки курсового проекта.

- Студент обязан в двухнедельный срок после начала семестра получить задание на проектирование.

- Задание оформляется на специальном бланке, подписывается руководителем курсового проекта, студентом и заведующим кафедрой.

- Задание подшивается в пояснительную записку по курсовому проектированию после титульного листа. Студент не допускается к защите курсового проекта при отсутствии технического задания.

 

Содержание курсового проекта

 

В курсовом проекте требуется

1) изучить соответствующий раздел теории графов;

2) разработать и реализовать алгоритм по теме курсового проекта;

3) провести тестирование программы;

4) использовать соответствующий алгоритм при решении практической задачи.

 

Более подробно остановимся на пункте 4. Рассмотрим пример решения практической задачи.

 

 

 

 

 

 

Далее перечислим некоторые типовые задачи теории графов и их приложения:

- Задача о кратчайшей цепи

замена оборудования

составление расписания движения транспортных средств

размещение пунктов скорой помощи

размещение телефонных станций

 

- Задача о максимальном потоке

анализ пропускной способности коммуникационной сети

организация движения в динамической сети

оптимальный подбор интенсивностей выполнения работ

синтез двухполюсной сети с заданной структурной надежностью

задача о распределении работ

 

- Задача об упаковках и покрытиях

оптимизация структуры ПЗУ

размещение диспетчерских пунктов городской транспортной сети

 

- Раскраска в графах

распределение памяти в ЭВМ

проектирование сетей телевизионного вещания

 

- Связность графов и сетей

проектирование кратчайшей коммуникационной сети

синтез структурно-надежной сети циркуляционной связи

анализ надежности стохастических сетей связи

 

- Изоморфизм графов и сетей

структурный синтез линейных избирательных цепей

автоматизация контроля при проектировании БИС

 

- Автоморфизм графов

конструктивное перечисление структурных изомеров для

производных органических соединений

синтез тестов цифровых устройств

 

 

Пояснительная записка должна быть оформлена согласно ГОСТ 7.32-2001 и содержать следующие обязательные структурные единицы:

- титульный лист

- реферат;

- содержание;

- введение;

- основная часть;

- заключение;

- список использованных источников.

 

Образец титульного листа пояснительной записки приведен в приложении А. Красным цветом в шифре работы выделен порядковый номер студента в списке группы.

Объем пояснительной записки 25-40 страниц машинописного текста без учета приложений.

 

Основная часть должна обязательно содержать следующие 4 раздела.

1. Постановка задачи курсового проектирования

2. Теоретический анализ

3. Схемы алгоритмов

4. Результаты тестирования

5. Решение практической задачи

Основная литература для выполнения курсового проекта

1. Оре, О. Теория графов [Текст] / О. Оре; пер. с англ. И. Н. Врублевской; под ред. Н. Н. Воробьева. - М.: ЛИБРОКОМ, 2009. – 352 с..

2. Кузнецов, О.П. Дискретная математика для инженера [Текст] / О.П. Кузнецов. – 4-е изд., стер. – СПб.: Лань, 2005. – 394 с.

3. Шапорев, С.Д. Дискретная математика [Текст]: курс лекций и практ. занятий: учеб. пособие для вузов по специальностям 220200 "Автоматизированные системы обработки информации и управления", 071900 "Информационные системы в технике и технологиях" / С.Д. Шапорев. - СПб.: БХВ-Петербург, 2009. - 396 с. (Гриф)..

4. Степанов, В.Н. Дискретная математика: графы и алгоритмы на графах [Текст]: учеб. пособие / В.Н. Степанов; ОмГТУ. – Омск: Изд-во ОмГТУ, 2010. – 118 с.

5. Иванов, Б. Н.. Дискретная математика. Алгоритмы и программы [Текст]: учеб. пособие / Б. Н. Иванов. - М.: Лаб. Базовых Знаний, 2010. - 288 с.