Методические указания к выполнению расчетных работ по теории графов и сетей

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)________________________________________________________ФАКУЛЬТЕТ «ПРИКЛАДНАЯ МАТЕМАТИКА И ФИЗИКА»Учебно-методические комплексы кафедры «Математическая кибернетика»В.Н. НЕФЕДОВМЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮРАСЧЕТНЫХ РАБОТ ПО ТЕОРИИ ГРАФОВ И СЕТЕЙПечатается по рекомендации Редакционного совета факультета«Прикладная математика и физика» Московского авиационного института(национального исследовательского университета)МоскваИздательство «Доброе слово»2015ББК 517УДК 512Н 58Нефедов В.Н.

Методические указания к выполнению расчетных работ по теорииграфов и сетей: Учебное пособие. – М.: Издательство «Доброе слово», 2015. – 59 с.: ил.ISBN 978-5-89796-528-5Пособие предназначено для подготовки студентов к выполнению расчетных работ по следующимтемам: связность, сильная связность, орграф конденсации; матричное задание графов, матрицы смежности, достижимости, связности; поиск маршрутов (путей) в графах (орграфах); деревья и циклы; внутренняя и внешняя устойчивость в графах, ядра графа; функции на вершинах орграфа, порядковая функция,функция Гранди; хроматическое число графа, задача об оптимальном раскрашивании вершин графа; цикломатическая матрица, электрические цепи, уравнения Кирхгофа; транспортные сети, поток в сети, максимальный поток. В каждой из тем приведены краткие теоретические сведения, необходимые для решениязадач, а также приводится решение типового варианта расчетной работы по этой теме.

Пособие предназначено для студентов специальностей «Прикладная математика», «Прикладная математика и информатика», а также для студентов других специальностей, изучающих курс «Дискретная математика».Корректура: Яковлева С.Ю.Издательство «Доброе слово»www.dobroeslovo.infoПодписано в печать: 07.04.2015П.л. 7,5. Формат 60х90/8© Нефедов В.Н., 2015© Издательство «Доброе слово», 2015ПРЕДИСЛОВИЕПособие предназначено для студентов специальностей «Прикладная математика»,«Прикладная математика и информатика», а также для студентов других специальностей,изучающих курс «Дискретная математика» и выполняющих расчетные работы по теорииграфов и сетей.

В методических указаниях рассматриваются следующие темы: связность,сильная связность, орграф конденсации; матричное задание графов, матрицы смежности,достижимости, связности; поиск маршрутов (путей) в графах (орграфах); деревья и циклы; внутренняя и внешняя устойчивость в графах, ядра графа; функции на вершинах орграфа, порядковая функция, функция Гранди; хроматическое число графа, задача об оптимальном раскрашивании вершин графа; цикломатическая матрица, электрические цепи,уравнения Кирхгофа; транспортные сети, поток в сети, максимальный поток. В методических указаниях приведены краткие теоретические сведения по перечисленным темам,подробное изложение которых можно найти в учебном пособии [1].

Настоящее пособиедополняет учебное пособие [2], поскольку в нем рассматривается семь новых тем.3Тема 1. Элементы теории графов. Задача об оповещенииПод графом G  (V , X ) понимается пара, состоящая из конечного непустого множества V  {v1 ,..., vn }, элементы которого называются вершинами графа, и конечногомножества пар вершин X  {x1 ,..., xn }. Если пары в X являются неупорядоченными, тограф G называется неориентированным графом (или просто графом). Если пары в X являются упорядоченными, то граф называется ориентированным, кратко орграфом.Элементы множества X называются ребрами, если G – неориентированный граф, и дугами, если G – орграф.

Ребра неориентированного графа обозначаются в виде двухэлементных множеств {v, w}, где v, w V . При этом {v, w}  {w, v}. Дуги орграфа обозначаются ввиде упорядоченных пар вида (v, w) (или  v, w  ), где v, w V . Иногда в множестве Xдопускается существование нескольких одинаковых пар.

В этом случае граф называетсямультиграфом. Иногда также допускаются пары с одинаковыми элементами, которые называются петлями. В последнем случае граф называется псевдографом. Одинаковые парыв X называются кратными (или параллельными). Количество одинаковых ребер (дуг) называется кратностью этого ребра (этой дуги). Все вводимые в этой теме понятия одинаково применимы к графам, мультиграфам, псевдографам. Поэтому чаще всего будем говорить просто о графах (ориентированных или неориентированных).

Неориентированныеграфы будем обозначать буквой G или G с индексами (например, G0 , G1 ,... ), а ориентированные – буквой D или D с индексами (например, D0 , D1 ,... ). Кроме того, договоримсяобозначать вершины буквами v, w, u (без индексов или с индексами), а ребра и дуги – буквами x, y, z (без индексов или с индексами). Для графа G  (V , X ) в случае v V ( x  X )будем иногда кратко писать v  G ( x  G). Аналогично будем поступать и для орграфов.Графы принято изображать на плоскости в виде множества точек (маленьких кружков),соответствующих вершинам, и множества линий, соединяющих некоторые пары вершин,соответствующих ребрам. В случае орграфа на линиях, соответствующих дугам, указываются стрелки, указывающие направления дуг (от первой вершины пары до второй).

Нарис. 1.1 приведено изображение неориентированного псевдографа, а на рис. 1.2 – ориентированного.Рис. 1.14Рис. 1.2Замечание 1.1. Для упрощения изображения графов вместо указания вершиныоколо кружка, соответствующего этой вершине, будем иногда указывать номер этой вершины в центре этого кружка (см., например, рис.

1.8). Кроме того, будем иногда вместоизображений видаиспользовать изображение.Если x  {v, w} – ребро неориентированного графа, то говорят, что (а) вершиныv, w – смежные; (б) вершины v, w – концы ребра x ; (в) ребро x соединяет вершиныv, w; (г) ребро x инцидентно вершинам v, w; (д) вершины v, w инцидентны ребру x.Если x  (v, w) – дуга орграфа, то говорят, что (а) вершина v – начало дуги x, w –конец дуги x ; (б) дуга x исходит из вершины v и заходит в вершину w ; (в) дуга x инцидентна вершинам v, w; (г) вершины v, w инцидентны дуге x.Степень вершины. Степенью вершины v графа G называется число  (v ) реберграфа G , инцидентных вершине v.

Вершина графа, имеющая степень 0, называется изолированной, а имеющая степень 1 – висячей. В случае псевдографа вклад петли {v, v} в (v ) равен 2.Полустепенью исхода (захода) вершины v орграфа D называется число   (v )(  (v) ) дуг орграфа D, исходящих из вершины v (заходящих в вершину v ). В случаеориентированного псевдографа вклад петли (v, v ) в   (v ) и в   (v ) равен 1.Пример 1.1.(а) Для графа, изображенного на рис.

1.1,  (v1 )  5,  (v4 )  2,  (v5 )  1, (v6 )  0 ; (б) для орграфа, изображенного на рис. 1.2,   (v2 )  2,   (v2 )  5.Будем количества вершин и ребер в графе G обозначать через n(G), m(G) соответственно, а количества вершин и дуг в орграфе D – через n( D), m( D) соответственно.Утверждение 1.1. Для любого псевдографа G  (V , X ) выполняется равенство (v)  2m(G).(1.1)vVДоказательство. Равенство (1.1) является очевидным следствием того, что каждоеребро дает вклад, равный двум, в сумму из левой части равенства (1.1).Приведем также соответствующее утверждение для орграфов.5Утверждение 1.2. Для любого ориентированного псевдографа D  (V , X ) выполняетсяvV(v)    (v) m( D).(1.2)vVМаршруты, пути.

Последовательность(1.3)v1 x1v2 x2 ...vk xk vk 1 ,где vi V , xi  {vi , vi 1} X , называется маршрутом, соединяющим вершины v1 , vk 1 вграфе G  (V , X ). Аналогично определяется путь в орграфе D  (V , X ). Последовательность (1.3), где vi V , xi  (vi , vi 1 )  X , называется путем из v1 в vk 1 в орграфеD  (V , X ). Вершина v1 называется начальной, а vk 1 – конечной вершиной маршрута (пу-ти), а остальные вершины – внутренними. Длиной маршрута (пути) называется количество ребер (дуг) в нем.

Маршрут называется замкнутым, если его начальная вершина совпадает с конечной. Незамкнутый маршрут (путь), в котором ребра (дуги) попарно различны, называется цепью. Цепь, в которой все вершины попарно различны, называется простой. Замкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется циклом (контуром). Цикл (контур), в котором все вершины попарно различны, называется простым. Если ребро (дуга) x входит в некоторый маршрут (путь)  , то будемкратко писать x .Замечание 1.2. Последовательность (1.3) можно однозначно восстановить по последовательности x1 x2 ... xk , а следовательно, ее можно использовать как сокращеннуюформу записи маршрута или пути.

Отметим далее, что в случае, когда в последовательности (1.3) x1 , ... , xk имеют кратности, равные 1, ее можно однозначно восстановить по последовательности вершин v1v2 ...vk 1 , а следовательно, вместо (1.3) можно использовать иэту сокращенную форму записи маршрута или пути.Говорят, что вершина w орграфа D (графа G ) достижима из вершины v, еслилибо v  w, либо существует путь из v в w (маршрут, соединяющий v, w ).Подграфом графа G называется граф, все вершины и ребра которого содержатсясреди вершин и ребер графа G.