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

Московский государственный технический университет 
имени Н. Э. Баумана 
 
 
Т. Е. Бояринцева, А. А. Мастихина  
 
 
 
Теория графов 
 
 
 
 
Методические указания к выполнению домашнего задания  
по курсу «Дискретная математика» 
 
 
 
 
 
 
 
 
 
 
Москва  
2014 

УДК 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 
 
 
 
 
 
 
 
 
© МГТУ им. Н. Э. Баумана, 2014 
© Оформление. Издательство 
ISBN 978-5-7038-3994-2 
 
 
       МГТУ им. Н. Э. Баумана, 2014 
 
2 

 
 
ПРЕДИСЛОВИЕ 
Данные методические указания предназначены для студентов 
МГТУ им. Н.Э. Баумана, выполняющих типовой расчет по теории 
графов. Задачи типового расчета приведены в конце работы. 
Теория графов является разделом дискретной математики. С 
помощью графов решается ряд оптимизационных задач. Указания 
написаны по материалам лекций и семинаров курса «Дискретная 
математика», читаемого авторами в МГТУ им. Н.Э. Баумана. 
В методических указаниях изложены основные понятия теории 
графов, рассмотрены типовые задачи, которые решаются средствами данной теории, и представлены алгоритмы их решения. 
 
 
3 

 
1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ 
4 
3 
5 
1 
2 
6 
Графом называют совокупность элементов (вершин графа) 
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. 
По умолчанию графом называют неориентированный граф. 
Граф называют взвешенным, если каждому ребру приписано 
некоторое число, обозначающее длину, вес или какую-либо другую величину. 
Поставим в соответствие вершинам графа точки на плоскости 
или в трехмерном пространстве, а каждому ребру — линию, соединяющую точки, соответствующие вершинам, каждой дуге — 
такую же линию, но с указанием направления (стрелкой). Получившееся изображение будем называть геометрическим графом. 
Граф 
G = (V, E), 
V = {1, 2, 3, 
4, 5, 6}, 
E = {{1, 2}, {2, 3}, {2, 4}, 
{2, 5}, {5, 6}}, изображен на рис. 1. 
Два графа называют изоморфными, 
если 
существует 
взаимнооднозначное отображение множеств 
их вершин, сохраняющее связи между 
ними. Ясно, что различные геометриРис. 1 
 
4