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

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

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

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

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

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

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

ПРАКТИКУМ

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

Уфа  2005

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

ББК 22.193 (я7)

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

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

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

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

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

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

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

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

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

Цели и задачи ...…………………………………………………………. 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

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

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

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

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

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

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

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

Графы помогают описывать и исследовать различные системы объектов и их связи. Например, в графе, изображенном на рис. 1, точки (вершины графа) можно интерпретировать как города, а линии, соединяющие вершины (ребра), как дороги, соединяющие эти города.

Рис. 1.
Формальное определение графа таково [1-9]. Графом Г=(V,X) называется пара множеств: V – множество, элементы которого называются вершинами, X – множество неупорядоченных пар вершин, называемых ребрами. Если v, w  V, x=(v,w)X, то говорят, что ребро x соединяет вершины v и w или x инцидентно v и w. Таким образом, {v,w} – обозначение ребра. Если Х представляет собой упорядоченные пары (т. Е. X – подмножество декартова произведения V×V), то граф называется ориентированным, а пары {v,w} называют дугами. Если множеству X принадлежат пары v=w, то такие ребра (v,v) называют петлями. Существование одинаковых пар {v,w} соответствует наличию параллельных или кратных ребер (дуг), а кратностью ребер называют количество таких одинаковых пар.

Например, кратность ребра {v₁, v₂} в графе, изображенном на рис. 2, равна двум, кратность ребра {v₃, v₄} − трем.

Рис.2.
Псевдограф − граф, в котором есть петли и/или кратные ребра.

Итак, используемые далее обозначения:

{v,w} − ребра неориентированного графа;

{v,v} – обозначение петли;

(v,w) − дуги в ориентированном графе;

1) Ориентированный граф D=(V, X), V={v₁, v₂, v₃, v₄},

Рис. 3.
2) Неориентированный граф, изображенный на рис. 4:

Рис. 4.

Если x={v,w} - ребро, то v и w − концы ребра x.

Если x=(v,w) - дуга ориентированного графа, то v − начало, w – конец дуги.

Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x ).

Вершины v, w называются смежными, если {v,w}X.

Степенью вершины v графа G называется число (v) ребер графа G, инцидентных вершине v.

Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.

Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в ⁺(v), так и в ^(v).

Последовательность v₁x₁v₂x₂v₃…x_kv_k+1, (где k1, v_iV, i=1,…,k+1, x_iX, j=1,…,k), в которой чередуются вершины и ребра (дуги) и для каждого j=1,…,k ребро (дуга) x_j имеет вид {v_j,v_j+1} (для ориентированного графа (v_j,v_j+1)), называется маршрутом, соединяющим вершины v₁ и v_k+1 (путем из v₁ в v_k+1).

В графе, изображенном на рис.4, v₁x₁v₂x₂v₃x₄v₄x₃v₂ – маршрут, v₂x₂v₃x₄v₄ – подмаршрут;

маршрут можно восстановить и по такой записи x₁x₂x₄x₃ ;

если кратности ребер (дуг) равны 1, можно записать и так v₁v₂v₃v₄v₂ .

Пусть D=(V,X) ориентированный граф, V={v₁,...,v_n}, X={x₁,...,x_m}.