Основы теории и алгоритмы на графах

ОСНОВЫ ТЕОРИИ 

И АЛГОРИТМЫ 

НА ГРАФАХ

Н.И. ГДАНСКИЙ

Москва
ИНФРА-М

2020

УЧЕБНОЕ ПОСОБИЕ

Рекомендовано Межрегиональным учебно-методическим советом 

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

для студентов высших учебных заведений, обучающихся 

по укрупненной группе направлений подготовки 

09.03.00 «Информатика и вычислительная техника» 

(квалификация (степень) «бакалавр») 

(протокол № 17 от 11.11.2019)

УДК 519.17(075.8)
ББК 22.176я73
 
Г26

Гданский Н.И.
Г26 
 
Основы теории и алгоритмы на графах : учебное пособие / Н.И. Гданский. — Москва : ИНФРА-М, 2020. — 206 с. — (Высшее образование: 
Бакалавриат). — DOI 10.12737/978686.

ISBN 978-5-16-014386-6 (print)
ISBN 978-5-16-106890-8 (online)
В учебном пособии изложены основные теоретические положения 
теории графов, основные задачи, решаемые с использованием графовых 
структур, а также общие методы их решения и конкретные алгоритмы 
с оценками их сложности. Рассмотрено множество примеров, приведены 
вопросы для проверки уровня знаний и задачи для самостоятельного решения. Наряду с контрольными заданиями для проверки теоретической 
подготовки указаны варианты практических заданий на разработку прог-
рамм по изучаемым разделам теории графов.
Соответствует требованиям федеральных государственных образовательных стандартов высшего образования последнего поколения.
Рассчитано на студентов бакалавриата и магистратуры, изучающих 
информационные технологии, для углубленной подготовки в области анализа и проектирования систем сложной структуры. Также пособие может 
быть полезно специалистам IT-сферы при изучении алгоритмических аспектов теории графов.

УДК 519.17(075.8)
ББК 22.176я73

Р е ц е н з е н т ы:
Кораблин Ю.П., доктор технических наук, профессор, профессор 
кафедры математического обеспечения и стандартизации информационных технологий МИРЭА — Российского технологического университета;
Мокрова Н.В., доктор технических наук, доцент, профессор кафедры автоматизации и электроснабжения Национального исследовательского Московского государственного строительного университета 

ISBN 978-5-16-014386-6 (print)
ISBN 978-5-16-106890-8 (online)
© Гданский Н.И., 2020

Посвящается
Гарию Петровичу Гаврилову

Введение

При анализе и проектировании сложных систем их модели представляют в виде набора некоторых объектов, соединенных между 
собой связями, которые могут иметь определенные свойства. Такая 
геометрическая интерпретация, с одной стороны, позволяет адекватно моделировать многие свойства исходных систем, с другой 
стороны, дает возможность представить данные свойства в наглядной визуальной форме, что значительно упрощает понимание 
их структуры, а также сущность применяемых методов их анализа 
и синтеза. Теория графов посвящена изучению общих свойств 
таких моделей.
Как научная дисциплина теория графов прошла довольно длительный путь развития. Ее истоки лежат в различных головоломках 
и развлекательных задачах геометрического содержания, которые 
известны еще с древности. Однако начало теории графов как самостоятельной математической дисциплины было положено Л. Эйлером только в 1736 г. в решении задачи о кенигсбергских мостах, 
которая была сформулирована ему в письме И. Кантом. В XIX в. 
развитие науки (химия, электротехника, логические методы и др.), 
а также потребности решения практических задач вызвали существенное возрастание интереса к графовым методам исследования. 
В XX столетии мощным стимулом к дальнейшему развитию теории 
стало появление многих новых направлений в науке и технике, существенно учитывающих системные свойства объектов изучения 
и проектирования, допускающих их наглядную геометрическую 
интерпретацию. Помимо традиционных областей это следующие 
направления — теория игр, информатика, программирование, экономика, логистика, теория передачи сообщений, разнообразные 
сети, психология и биология и др.
В настоящее время теория графов является одним из разделов 
дискретной математики, главной особенностью которого является 
применение геометрических методов к исследованию объектов. 
Своеобразие рассматриваемых в ней задач приводит к тому, что 
для их решения применяются не только специальные методы самой 
теории, но и методы теории множеств, комбинаторики, математи

ческой логики, линейной алгебры, геометрии, теории игр и других 
дисциплин. Сегодня это сложившаяся научная дисциплина со 
своим кругом задач и проблем, методами их решения, а также связями с другими научными направлениями и областями информационных технологий.
Теоретическая и практическая значимость графовых структур 
для алгоритмизации и программирования, с одной стороны, заключается в том, что они являются основой двух базовых структур 
данных — иерархического и сетевого типов. Также активно развивается теория графических баз данных, которые предпочтительны 
при моделировании как геоинформационных, так и других сильно 
связанных систем. С другой стороны, сами задачи теории графов стимулируют разработку новых эффективных алгоритмов их решения.
Поэтому современный уровень изложения теории графов нераздельно связан с вопросами практического решения ее задач 
при помощи компьютерной техники. В своем развитии она уже 
прошла начальный этап, на котором ее представляли как своеобразную теорию с необычным предметом исследования. Сегодня 
теория графов превратилась в мощный инструмент решения большого ряда актуальных прикладных задач.
Знание основ теории графов и их алгоритмической реализации не только закладывает базовый уровень инженерных знаний 
и умений в области информационных технологий, но и подготавливает учащегося к овладению специальными дисциплинами, в которых применяются ее методы. Таким образом, изучение теории 
графов закладывает общую основу для формирования необходимых 
знаний, умений и общей компетентности. Их понимание позволяет 
уже на ранних этапах предотвратить принципиальные ошибки как 
при построении информационных структур, так и при их последующей обработке.
В пособии изложены все основные разделы теории графов, дано 
пояснение смысла вводимых понятий и теоретических результатов 
дисциплины. Отдельно рассмотрены основные методы решения 
задач на графовых структурах, а также их применение для решения 
конкретных задач. Для повышения уровня самостоятельной работы 
учащихся дополнительно даны вопросы для самопроверки изучаемых теоретических положений.
Наряду с теорией большое внимание уделено практическим аспектам ее применения. Для этого рассмотрены базовые алгоритмы 
решения основных задач теории графов, а также примеры их применения на типовых графовых структурах. Даны задачи для самостоятельного решения, позволяющие определить реальный уровень 

получаемых практических навыков. Изучение базовых алгоритмов 
решения графовых задач позволяет легко освоить их современные 
усложненные модификации, имеющие оптимальную вычислительную сложность.
Глава 1 является вводной. В ней изложены основные виды графовых структур, их характеристики; введены ориентированные 
и неориентированные псевдографы, мультиграфы, графы, даны понятия маршрута, цикла. Особое внимание здесь уделено способам 
задания графов и орграфов. Отдельно рассмотрены гиперграфы. 
Также проанализированы основные типы задач на графовых структурах и общие методы их решения.
В главе 2 сначала рассмотрены свойства связности и достижимости для графовых моделей. Также проанализированы основные 
виды покрытий графов и возможные алгоритмы их определения, 
рассмотрены реберные графы.
Глава 3 посвящена такому распространенному типу графов, как 
деревья. Дано основное и альтернативные определения дерева, его 
основные свойства. Отдельно рассмотрены остовные деревья (каркасы) для связных графов. Даны основные характеристики и классификация однокорневых деревьев как основных моделей для 
иерархических структур. Особое внимание уделено двоичным (бинарным) деревьям, решению с их помощью логических уравнений, 
систем и задач.
В главе 4 описаны основные свойства полных, двудольных 
графов, единичных n-мерных кубов и сетей. Особое внимание в ней 
уделено характерным задачам, решаемым с их помощью.
В главе 5 рассмотрены операции и отображения на графах, в том 
числе гомеоморфизм и изоморфизм графов, изложено построение 
вершинных (гамильтоновых) и реберных (эйлеровых) обходов 
графов, мультиграфов и псевдографов.
Глава 6 посвящена оптимальным маршрутам во взвешенных 
графах. Здесь рассмотрены две основные задачи — определение 
кратчайших расстояний между всеми парами вершин (алгоритмы 
Шимбелла, Флойда — Уоршалла) и определение кратчайших расстояний от заданной вершины ко все остальным (алгоритмы Дейкстры, Беллмана — Форда).
В главе 7 показаны основные виды раскрасок графов (вершинных, реберных и тотальных), причем как их самых важных 
типов, так и произвольных. Также описана планарность графов.
Для усвоения материала пособия достаточно базовых знаний 
по курсу средней школы, математическому анализу, линейной алгебре и основам программирования.

Значительное внимание в пособии отведено проверке уровня 
теоретических знаний и практических навыков. В конце изученных 
тем приведены вопросы для проверки знаний, помогающие самостоятельно выяснить уровень подготовки, а также задачи для самостоятельного решения. Содержание задач, с одной стороны, максимально приближено к прикладным приложениям теоретических 
разделов, с другой — помогает усвоению учебного материала. 
Их решение составляет основу семинарских занятий. Для промежуточного и итогового контроля усвоения теоретических знаний 
разработаны варианты контрольных заданий по двум основным 
разделам курса. Дополнительно к ним для практического освоения 
материала в пособии даны задания по алгоритмизации и программированию, в которых необходимо разработать конкретную программу по тематике теории графов.
Основная компетенция, формируемая при изучении предлагаемого пособия, может быть сформулирована в следующем виде: способность к владению основами теории графов и методами решения 
основных задач на графовых структурах.
Кроме того, после изучения материала книги студенты будут:
знать общие положения теории графов и ее основные теоретические результаты;
уметь решать основные типы задач по теории графов;
владеть методами анализа и синтеза графовых структур.
Помимо учащихся высшей школы пособие может быть полезно 
специалистам из IT-сферы, самостоятельно изучающим теоретические и практические вопросы теории графов, а также учащимся 
средних школ с углубленным изучением математики и информатики.
Автор с большой благодарностью вспоминает своего университетского учителя Гария Петровича Гаврилова, который еще в студенческие годы ввел его в необычный мир теории графов и на всю 
жизнь привил интерес к ней.

Глава 1. 
ОСНОВНЫЕ ВИДЫ ГРАФОВЫХ СТРУКТУР, 
ИХ ХАРАКТЕРИСТИКИ И СПОСОБЫ ЗАДАНИЯ. 
ЗАДАЧИ НА ГРАФОВЫХ СТРУКТУРАХ

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

1.1. ПСЕВДОГРАФЫ, МУЛЬТИГРАФЫ, ГРАФЫ. 
МАРШРУТЫ, ЦИКЛЫ

Определение. Рассмотрим в качестве базового конечное множество элементов вида Vi (i = 1, …, n), а также бинарное отношение 
на нем — множество Х пар элементов из V вида (Vi, Vj), где (1 ≤ i, 
j ≤ n).
Элементы базового множества V называют вершинами. Еcли отношение на нем симметрично, вхождение в Х пары (vi, vj) (1 ≤ i, 
j ≤ n) автоматически означает вхождение в Х обратной пары (vj, vi), 
то такие пары называют ребрами, а всю совокупность G = (V, X) — 
неориентированным псевдографом. При этом прилагательное «неориентированный» в названии обычно опускается.
Если все пары Х упорядочены, то их называют дугами, а совокупность G = (V, X) — ориентированным псевдографом.
Ребра (дуги) X вида (Vi, Vi ), соединяющие одну и ту же вершину, называют петлями. Если в множестве ребер (дуг) X есть одинаковые элементы, то их называют кратными.
Когда элементам — ребрам (дугам) Хij  = (vi, vj) (1 ≤ i, j ≤ n) псевдографа G = (V, X) присвоены числовые значения dij , которые называются весами ребер (дуг) и задаются матрицей весов D размером n × n, 
весь псевдограф называют взвешенным и обозначают так: G = (V, X, D).
На изображениях вершины показывают точками или окружностями малого диаметра, ребра — линиями, дуги — однонаправленными стрелками. Веса указывают непосредственно на ребрах 
(дугах).
Пример 1.1. Псевдограф, показанный на рис. 1.1, задан множествами V = (1, 2, 3, 4); X = ((1, 1), (1, 1), (1, 2), (2, 3), (2, 3), (2, 3), 
(2, 4), (2, 4), (4, 4), (4, 4)). Ориентированный псевдограф (рис. 1.2) 

задан множествами V = (1, 2, 3, 4); X = ((1, 1), (1, 1), (2, 1), (2, 3), 
(3, 2), (4, 2), (4,3)).
Определение. Если в псевдографе отсутствуют петли (но могут 
быть кратные ребра (дуги)), то его называют мультиграфом.

Рис. 1.1. Псевдограф к примеру 1.1

Рис. 1.2. Ориентированный 
псевдограф к примеру 1.1

Пример 1.2. На рис. 1.3 приведен мультиграф, имеющий множества вершин и ребер V = (1, 2, 3, 4); Х = ((1, 2), (1, 3), (2, 3), (2, 3), 
(2, 4), (2, 4), (3, 4)).

Рис. 1.3. Мультиграф к примеру 1.2

Определение. Мультиграф без кратных ребер называют графом. 
Ориентированный граф для краткости называют также орграфом.
Пример 1.3. На рис. 1.4 показаны граф с множествами V = (1, 2, 
3, 4); X = ((1, 2), (2, 3), (2, 4), (3, 4)) и орграф с множествами V = (1, 2, 
3, 4); X = ((1, 2), (1, 4), (2, 3), (3, 4)).

1

2
4

3
1

2
4

3

Рис. 1.4. Граф и орграф к примеру 1.3

Для каждого графа всегда можно построить эквивалентный 
ему по наличию связей в системе оргаф путем замены всех ребeр 
вида (vi, vk) парой дуг (vi, vk), (vk, vi). Обратный переход от орграфа 
к графу в общем случае невозможен.

Определение. Если вершины ориентированного или неориентированного мультиграфа vi и vj соединены ребром (дугой) Хk = (vi, vj), 
то их называют смежными. Вершина vi и ребро (дуга) Хk = (vi, vj), 
образованные данной вершиной, называют инцидентными. Степенью вершины v называют число d(v) ребер (дуг), инцидентных ей. 
Если d(v) = 0, то вершину называют изолированной, если d(v) = 1, то 
висячей.
У рассмотренного в примере 1.2 мультиграфа d(v1) = 2, d(v2) = 3, 
d(v3) = 1, вершина v3 — висячая.
Определение. В орграфах полная степень каждой вершины d(v) 
складывается из числа выходящих дуг, которое называют полустепенью исхода и обозначают через d–(v), и числа входящих дуг, 
которое называют полустепенью захода и обозначают через d+(v): 
d(v) = d–(v) + d+(v).
Степень вершин приведенного в примере 1.3 орграфа:
d(v1) = 1, d–(v1) = 1, d+(v1) = 0;
d(v2) = 2, d–(v2) = 1, d+(v2) = 1;
d(v3) = 1, d–(v3) = 0, d+(v3) = 1.
Определение. Рассмотрим граф G = (V, X). Граф G1 = (V1, X1) 
в общем случае называют подграфом графа G, если V1 ⊆ V, Х1 ⊆ Х, 
причем ребра входят в Х1 только тогда, когда обе составляющие его 
вершины входят в V1.
В зависимости от обязательности включения в подграф вершин 
или ребер выделяют следующие виды подграфов.
Определение. Рассмотрим в графе G = (V, X) подмножество 
вершин V1 ⊆ V. Вершинно-порожденным подграфом графа G называют такой его подграф G1 = (V1, X1), в который входят наряду с вершинами V1 все ребра из множества X, у которых обе составляющие 
их вершины входят в V1, т.е. максимально возможное число ребер 
из X.
Рассмотрим в графе G = (V, X) подмножество ребер X1 ⊆ X. Реберно-порожденным подграфом графа G называют такой его подграф G1 = (V1, X1), в который входят наряду с ребрами X1 все вершины из множества V, которые инцидентны им, т.е. максимально 
возможное число вершин из V.
Пример 1.4. Рассмотрим граф G = (V, X); V = {1—8}; X = {(1, 2), 
(1, 3), (1, 5), (1, 6), (1, 7), (2, 3), (2, 4), (2, 7), (3, 4), (3, 8), (4, 5), 
(4, 6), (4, 8), (5, 6), (5, 8), (6, 7), (7, 8)}, показанный на рис. 1.5, а. 
На рис. 1.5, б приведен его подграф, содержащий вершины {1—6} 
и часть инцидентных им в G ребер (нет, например, ребер (1, 3), 
(2, 4)). На рис. 1.5, в показан вершинно-порожденный подграф 
графа G, содержащий вершины {1, 4—8}. На рис. 1.5, г приведен ре

берно-порожденный подграф графа G; порождающие ребра показаны на нем штриховыми линиями.

а 
 
 б 
 
   в 
 
     г

Рис. 1.5. Граф к примеру 1.4 и его подграфы

Определение. Последовательность вершин и ребер (дуг), связывающих их в графе (орграфе), называется маршрутом (путем). 
В орграфе ориентация всех дуг должна быть одинаковой — от конца 
предыдущей — к началу следующей. Число ребер в маршруте называется длиной маршрута. Маршрут, в котором все ребра попарно 
различны, называется цепью. Цепь, в которой все вершины попарно 
различны, называется простой цепью. Маршрут, начальная и конечная вершины которого совпадают (V1 = Vn), называется циклом. 
Цикл, в котором кроме вершин V1 и Vn все вершины различны, называется простым.
В примере 1.2 последовательность (v1 х1 v2 х3 v3) — маршрут 
из вершины v1 в вершину v3.
Пример 1.5. Граф V = {1, 2, 3, 4}; X = {х1 = (1, 2), х2 = (2, 3), х3 = (1, 3), 
х4 = (1, 4), х5 = (3, 4)}. Его изображение приведено на рис. 1.6.

4

1

2
3

x1

x4

x5

x3

x2

Рис. 1.6. Граф к примеру 1.5

В графе выделены следующие циклы:
(v1 х1 v2 х2 v3 х5 v4 х4 v1 х1 v2 х2 v3 х5 v1) — цикл длины 7;
(v1 х1 v2 х2 v3 х5 v4 х4 v1) — простой цикл длины 4.
Пример 1.6. Орграф V = {1, 2, 3, 4}; X = {х1 = (1, 2), х2 = (3, 2), 
х3 = (1, 3), х4 = (1, 4), х5 = (4, 3)}. Изображение приведено на рис. 1.7. 
В нем (v1 х4 v4 х5 v3 х2 v2) — маршрут длины 3 из вершины V1 в вершину V2. Циклов в орграфе нет.