Тема 3. Теория графов

В этой теме рассматриваются основные понятия, связанные с конечными графами.

Даются определения ориентированных и неориентированных графов, способы их задания и представления. Рассматриваются теоремы, связанные с путями на графе, понятия связности, изоморфизма и планирности графов. Изучаются числа, характеризующие граф: цикломатическое, хроматическое число, числа внутренней и внешней устойчивости.

Далее излагаются операции над графами: объединение, пересечение, прямое произведение графов. Рассматриваются матрицы для графов и выполнение с помощью матриц смежности основных операций над графами.

Значительная часть темы рассматривает графы типа – дерево. Необходимо изучить свойства деревьев, теоремы о них. Рассматривается задача нахождения кратчайшего дерева и её экономическая интерпретация. Для отыскания кратчайшего дерева используется алгоритм Краскала.

Отдельный раздел посвящен некоторым экстремальным задачам на графах: нахождению путей минимальной и максимальной длины на графе. Дается экономическая интерпретация каждой из этих задач. Рассматривается алгоритм Форда для их решения. Для задачи нахождения пути максимальной длины на графе рассматривается её применение в сетевом планировании.

Изучив данную тему студент должен:

· Знать:

– определения основных понятий, теоремы и их доказательства;

– рассматриваемые в теории задачи и методы их решения.

· Уметь:

– применять язык, методы и средства теории графов в дисциплинах прикладного характера.

Планы практических занятий по теме 3:

1. Способы представления графов.

2. Числа, характеризующие граф.

3. Операции над графами.

4. Деревья, их свойства.

5. Задачи нахождения кратчайшего дерева, её технико-экономическая интерпретация.

6. Задача нахождения пути максимальной длины на графе, её применении в сетевом планировании.

Рекомендации по выполнению конкретных заданий, вопросы и тесты для самопроверки содержатся в учебно-практическом пособии:

Дискретная математика. – М. : МГУЭСИ, 2009 (авторы Э.Л. Балюкевич, Л.Ф. Ковалёва, А.Н. Романников). / Литература 1 /

Список литературы

1. Балюкевич Э.Л., Ковалёва Л.Ф., Романников А.Н. Дискретная математика : учебно-практическое пособие. – М. : МГУЭСИ, 2009.

2. Балюкевич Э.Л., Ковалёва Л.Ф. Математическая логика и теория алгоритмов : учебно-практическое пособие. – М. : МГУЭСИ, 2009 (гриф УМО Минобрнауки РФ).

(Расширенные списки литературы с указанием интернет-ресурсов имеются в указанных выше учебно-практических пособиях.)