Федеральное агентство по образованию Российской Федерации

Государственное образовательное учреждение высшего

профессионального образования

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Теория графов

ПРАКТИКУМ

по дисциплине «Дискретная математика»

Уфа  2005

Федеральное агентство по образованию Российской Федерации

Государственное образовательное учреждение высшего

профессионального образования

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра вычислительной математики и кибернетики

Кафедра проектирования средств информатики

ТЕОРИЯ ГРАФОВ

ПРАКТИКУМ

по дисциплине «Дискретная математика»

Уфа  2005

Составители: н.И. Житникова, г.И. Федорова, а.К. Галимов

УДК 519.6 (07)

ББК 22.193 (я7)

Теория графов. Практикум по дисциплине «Дискретная математика». /Уфимск. гос. авиац. техн. ун-т.; Сост.: Н.И. Житникова, Г.И. Федорова, А.К. Галимов. - Уфа, 2005 -39 с.

Предназначен для студентов направлений 010503: «Математическое обеспечение и администрирование информационных систем», 230100: «Информатика и вычислительная техника» для подготовки к практическим занятиям по дисциплине «Дискретная математика».

Ил. 15. Библиогр.: 9 назв.

Рецензенты: - зам. зав. кафедрой ВМК УГАТУ

д.ф.-м.н., проф. Бронштейн Е.М.

- зав. каф. высшей алгебры и геометрии БашГУ

д.ф.-м.н., проф. Хабибуллин Б.Н.

© Уфимский государственный

авиационный технический университет, 2005

Содержание

Введение ………………………………………………………………… 5

Цели и задачи ...…………………………………………………………. 5

1. Краткий перечень основных понятий теории графов .…………….. 6

1.1. Общие понятия ……………………………………………………... 6

1.2. Понятия смежности, инцидентности, степени …….……………... 8

1.3. Маршруты и пути ……………………………….………….………. 8

1.4. Матрицы смежности и инцидентности…..….……………………. 9

1.5. Связность. Компоненты связности……………………………….. 10

1.6. Матрицы достижимости и связности……….……………………. 10

1.7. Расстояния в графе………………………..…………….…………. 11

1.8. Образ и прообраз вершины и множества вершин …………..…... 11

1.9. Нагруженные графы ………………..……………………………... 12

1.10. Деревья и циклы ………………………….………….…………... 13

2. Решение контрольных задач …………………………...…………… 14

2.1. Компоненты сильной связности ориентированного графа..……. 14

2.2. Расстояния в ориентированном графе..…………………………... 17

2.3. Минимальный путь в нагруженном ориентированном графе...... 21

2.4. Эйлеровы циклы и цепи……………..………………………….…. 23

2.5. Минимальное остовное дерево…………………………………… 25

2. 6. Задача о коммивояжёре…………………………………………... 27

3. Задания для самостоятельного решения ……….…………...……... 35

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

Введение

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

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

Умение решать задачи на графах позволит будущему специалисту приобрести опыт разработки технологий и методов теории операций для решения задач при научных исследованиях и проектно-конструкторской деятельности

В данном практикуме рассмотрены основные типы задач на графах, подходы и методы их решения, конкретные примеры.

Цели и задачи

Цель раздела «Теория графов» состоит в формировании у студентов умений и навыков, необходимых при исследовании различных систем и проектировании технических объектов.

Для достижения указанной цели решаются следующие задачи:

- формирование знаний методов и алгоритмов эффективного решения задач дискретной оптимизации;

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