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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов книги