Бояринцева, А. А. Мастихина Теория графов Методические указания к выполнению домашнего задания по курсу «Дискретная математика» Москва 2014 УДК 519.17 ББК 22.176 Б86 Издание доступно в электронном виде на портале ebooks.bmstu.ru по адресу: http://ebooks.bmstu.ru/catalog/109/book218.html Факультет «Фундаментальные науки» Кафедра «Высшая математика» Рекомендовано Учебно-методической комиссией Научно-учебного комплекса «Фундаментальные науки» МГТУ им. <...> Для студентов факультета «Робототехника и комплексная автоматизация», изучающих курс «Дискретная математика». <...> Указания написаны по материалам лекций и семинаров курса «Дискретная математика», читаемого авторами в МГТУ им. <...> ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ Графом называют совокупность элементов (вершин графа) V = {v1, v2, …, vn} и связей между ними E = {e1, e2, …, em} (ребер), причем каждое ребро ek является парой {vi, vj} различных элементов из множества V, обозначая наличие связи между ними, т. е. это пара конечных множеств G = (V, E), где каждый элемент E — пара вершин из множества V. <...> Ориентированным графом (орграфом) называют пару G = (V, E) множества вершин V = {v1, v2, …,vn} и множества дуг E = {e1, e2, … …, em}, где каждая дуга ek является упорядоченной парой (vi, vj) различных элементов из множества V. <...> Граф называют взвешенным, если каждому ребру приписано некоторое число, обозначающее длину, вес или какую-либо другую величину. <...> Ясно, что различные геометри ческие графы могут быть изоморфны одному графу: геометрический граф, показанный на рис. <...> Две соединенные между собой вершины называют смежными (т. е. {v, u} ∈ E). <...> Ребро e называют инцидентным вершине v, если e = {v, u}, uV . <...> Степенью вершины d(v) неориентированного графа называют число ребер, инцидентных этой вершине: d(v) = |{u: {u, v} ∈ E}|. <...> 4 5 v4 Для ориентированных графов определены понятия полустепени захода d+(v) и полустепени исхода d–(v) — как число дуг, входящих в вершину d+(v) = |{u: (u, v) ∈ E}| и количество выходящих из нее <...>
Теория_графов.pdf
УДК 519.17
ББК 22.176
Б86
Издание доступно в электронном виде на портале ebooks.bmstu.ru
по адресу: http://ebooks.bmstu.ru/catalog/109/book218.html
Факультет «Фундаментальные науки»
Кафедра «Высшая математика»
Рекомендовано Учебно-методической комиссией
Научно-учебного комплекса «Фундаментальные науки»
МГТУ им. Н. Э. Баумана
Рецензент: канд. физ.-мат. наук, доцент О. В. Пугачев
Б86
Бояринцева Т. И.
Теория графов : метод. указания / Т. И. Бояринцева, А. А. Мастихина.
— М. : Изд-во МГТУ им. Н. Э. Баумана, 2014. — 37,
[3] с. : ил.
ISBN 978-5-7038-3994-2
Изложены основные понятия и теоретические результаты применения
теории графов. Приведены примеры, рассмотрены типовые
задачи.
Для студентов факультета «Робототехника и комплексная автоматизация»,
изучающих курс «Дискретная математика».
УДК 519.17
ББК 22.176
ISBN 978-5-7038-3994-2
2
© МГТУ им. Н. Э. Баумана, 2014
© Оформление. Издательство
МГТУ им. Н. Э. Баумана, 2014
Стр.2
ОГЛАВЛЕНИЕ
Предисловие .................................................................................................... 3
1. Основные определения и понятия ............................................................. 4
2. Способы задания графа ............................................................................ 11
3. Задачи об обходах графа .......................................................................... 14
4. Дерево. Минимальное остовное дерево .................................................. 20
5. Фундаментальная система циклов ........................................................... 23
6. Построение дерева кратчайших путей .................................................... 26
7. Конденсация и база. Потоки в сетях ....................................................... 31
8. Планарность. Вершинная раскраска ........................................................ 34
Литература ..................................................................................................... 38
39
Стр.39