В этой теме рассматриваются основные понятия, связанные с конечными графами.
Даются определения ориентированных и неориентированных графов, способы их задания и представления. Рассматриваются теоремы, связанные с путями на графе, понятия связности, изоморфизма и планирности графов. Изучаются числа, характеризующие граф: цикломатическое, хроматическое число, числа внутренней и внешней устойчивости.
Далее излагаются операции над графами: объединение, пересечение, прямое произведение графов. Рассматриваются матрицы для графов и выполнение с помощью матриц смежности основных операций над графами.
Значительная часть темы рассматривает графы типа – дерево. Необходимо изучить свойства деревьев, теоремы о них. Рассматривается задача нахождения кратчайшего дерева и её экономическая интерпретация. Для отыскания кратчайшего дерева используется алгоритм Краскала.
Отдельный раздел посвящен некоторым экстремальным задачам на графах: нахождению путей минимальной и максимальной длины на графе. Дается экономическая интерпретация каждой из этих задач. Рассматривается алгоритм Форда для их решения. Для задачи нахождения пути максимальной длины на графе рассматривается её применение в сетевом планировании.
|
|
Изучив данную тему студент должен:
· Знать:
– определения основных понятий, теоремы и их доказательства;
– рассматриваемые в теории задачи и методы их решения.
· Уметь:
– применять язык, методы и средства теории графов в дисциплинах прикладного характера.
Планы практических занятий по теме 3:
1. Способы представления графов.
2. Числа, характеризующие граф.
3. Операции над графами.
4. Деревья, их свойства.
5. Задачи нахождения кратчайшего дерева, её технико-экономическая интерпретация.
6. Задача нахождения пути максимальной длины на графе, её применении в сетевом планировании.
Рекомендации по выполнению конкретных заданий, вопросы и тесты для самопроверки содержатся в учебно-практическом пособии:
Дискретная математика. – М.: МГУЭСИ, 2009 (авторы Э.Л. Балюкевич, Л.Ф. Ковалёва, А.Н. Романников). / Литература 1 /
Список литературы
1. Балюкевич Э.Л., Ковалёва Л.Ф., Романников А.Н. Дискретная математика: учебно-практическое пособие. – М.: МГУЭСИ, 2009.
2. Балюкевич Э.Л., Ковалёва Л.Ф. Математическая логика и теория алгоритмов: учебно-практическое пособие. – М.: МГУЭСИ, 2009 (гриф УМО Минобрнауки РФ).
(Расширенные списки литературы с указанием интернет-ресурсов имеются в указанных выше учебно-практических пособиях.)