Программирование на С++ задач на графах

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ 

РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное 

учреждение высшего образования

«Южный федеральный университет»
Инженерно-технологическая академия

В.А. Литвиненко

Программирование на С++

задач на графах

Учебное пособие

Таганрог

Издательство Южного федерального университета

2016

УДК 004.438(075.8)+519.17(075.8)
Л641
ББК 32.973-018.1+22.174.2я73
Л64+

Печатается по решению редакционно-издательского совета

Южного федерального университета

Рецензенты:

доктор технических наук, профессор, заведующий кафедрой 

Таганрогского института имени А.П. Чехова (филиал) «РГЭУ (РИНХ)» 

Я. Е.  Ромм;

кандидат технических наук, доцент кафедры ИБТС Института 

компьютерных технологий и информационной безопасности ЮФУ 

С. А. Ховансков.

Литвиненко, В. А. 

Л641
Программирование на С++ задач на графах : учебное пособие / 

В. А. Литвиненко ; Южный федеральный университет. – Таганрог : 
Издательство Южного федерального университета, 2016. – 83 с.

ISBN 978-5-9275-2311-5

В работе рассмотрены основные понятия теории графов, способы

задания графов, структуры данных и особенности программирования на 
С++ задач на графах, заданных в табличной и списочной формах, 
программирование на С++ задач на графах, в том числе, определения
вершины 
с 
наибольшей 
локальной 
степенью, 
нахождения

паросочетания графа, разбиения
графов на части, размещения

мультиграфов в вершины ортогональной решетки.

Предназначено для студентов очной формы обучения по направлению

подготовки 09.03.02 «Информационные системы и технологии».

ISBN 978-5-9275-2311-5
УДК 004.438(075.8)+519.17(075.8)
ББК 32.973-018.1+22.174.2я73

© Южный федеральный университет, 2016
© Литвиненко В. А., 2016

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.............................................................................................................. 5
1. ОСНОВЫ ТЕОРИИ ГРАФОВ ......................................................................... 7
1.1. Что такое граф? ............................................................................................... 7
1.2. Симметрический граф и мультиграф ............................................................ 9
1.3. Граф – это универсальная модель ............................................................... 10

Вопросы для самоконтроля........................................................................... 12

2. ПРЕДСТАВЛЕНИЕ ГРАФОВ И ПРОГРАММИРОВАНИЕ  ...................... 13
2.1. Матрица смежности графа ............................................................................ 13
2.2. Матрица инцидентности графа..................................................................... 15
2.3. Списочная форма задания графа .................................................................. 17

Вопросы для самоконтроля........................................................................... 20

3. ПРОГРАММИРОВАНИЕ ЗАДАЧ  НА ГРАФАХ......................................... 21
3.1. Определение локальной степени заданной вершины графа...................... 21
3.2. Определение вершины с наибольшей локальной степенью...................... 22
3.3. Определение вершин графа, смежных одновременно двум заданным                 

вершинам графа............................................................................................... 24

3.4. Определение вершин графа, смежных любой из двух заданных вершин 

графа................................................................................................................. 26

3.5. Определение паросочетания графа .............................................................. 26
4. РАЗБИЕНИЕ ГРАФА НА ПОДГРАФЫ......................................................... 31
4.1. Постановка и практическое применение задачи разбиения графов на 

подграфы  ........................................................................................................ 31

4.2. Разбиение графа на части с использованием методов случайного 

разбиения ......................................................................................................... 34

4.3. Определение числа ребер между любыми двумя 

заданными элементами................................................................................... 37

4.4. Подсчет числа связей между элементами, находящихся в двух разных                   

заданных подмножествах............................................................................... 39

4.5. Случайное распределение заданного множества элементов на два 

подмножества .................................................................................................. 41

4.6. Окончательный вариант программы на С++ разбиения мультиграфа                               

на два подграфа ............................................................................................... 49

4.7. Программа разбиения мультиграфа на две части с использованием 

функций............................................................................................................ 53
Вопросы для самоконтроля............................................................................ 57

5. РАЗМЕЩЕНИЕ ВЕРШИН МУЛЬТИГРАФА В ГРАФ ОРТОГОНАЛЬНОЙ 

РЕШЕТКИ ...................................................................................................... 59

5.1. Постановка задачи размещения вершин мультиграфа в граф 

ортогональной решетки.................................................................................. 59

5.2. Методы размещения вершин мультиграфа в граф регулярной 

ортогональной решетки ................................................................................. 62

5.3. Определение расстояния между двумя любыми  вершинами графа 

ортогональной решетки  ................................................................................ 64

5.4. Определение длины ребер между двумя вершинами мультиграфа, 

размещенными в выбранные вершины графа ортогональной решетки .. 68

5.5. Определение длины ребер между вершинами мультиграфа при их 

размещении вершины графа ортогональной решетки ................................ 70

5.6. Случайное назначение вершин графа ортогональной решетки 

вершинам мультиграфа    .............................................................................. 73

5.7. Программирование общей задачи размещения вершин   мультиграфа 

в вершины графа ортогональной решетки  ............................................... 75
Вопросы для самоконтроля.......................................................................... 80

БИБЛИОГРАФИЧЕСКИЙ СПИСОК ................................................................. 82

ВВЕДЕНИЕ

Обучение по направлению 09.03.02 «Информационные системы и 

технологии» предусматривает освоение студентами программирования на 

языке 
высокого 
уровня. 
Одним 
из 
наиболее 
популярных 
языков 

программирования 
является 
С++. 
Широкое 
распространение  

инструментальных систем визуального программирования на С++, таких как 

Visual C++, C++Builder, Red Studio дало мощный толчок для дальнейшего 

использования С++. 

В качестве одного из объектов для освоения программирования графы 

выбраны не случайно.  Графы – это универсальная модель для представления 

различных объектов, в том числе и абстрактных. Графы
широко 

используются в задачах прикладного характера, например, в проектных 

процедурах систем автоматизированного проектирования. Кроме того, 

задачи на графах являются хорошим  практическим базисом для освоения 

программирования комбинаторно-логических алгоритмов. 

Пособие знакомит с основными понятиями теории графов, способами 

задания графов, структурами данных и особенностями программирования на 

С++ задач на графах, заданных в табличной и списочной формах, с 

программированием
на С++ задач на графах, таких как, например,

определение вершины с наибольшей локальной степенью, генерация 

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

части, размещение мультиграфов в вершины ортогональной решетки.

В пособии не использовались термины теории множеств при описании 

задач на графах. Это сделано специально с целью упростить работу с 

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

множеств.

Учебное пособие ориентировано на  студентов специальностей 09.03.02 

«Информационные системы и технологии» дневной формы обучения при 

изучении курсов «Основы алгоритмизации и программирования», модуля 

«Практикум по программированию» курса «Математическая логика и теория 

алгоритмов»,
модуля
«Технологии
программирования»
курса 

«Информационные и программные технологии»,  использовании при 

выполнении индивидуальных заданий по курсам «Дискретная математика». 

Материал пособия рассчитан на студентов, освоивших начальный курс 

процедурного программирования на  С++. Программы, тексты которых 

приведены в учебном пособии, разработаны с использованием открытой 

системы программирования Turbo C++. Система является открытой и 

распространяется по лицензии GPL. Тексты программ, приведенные в 

учебном пособии, можно использовать при программировании задач на 

графах и с использованием других систем программирования, например, 

Visual
C++, при соблюдении особенностей программирования
в этих 

системах программирования.

1. ОСНОВЫ ТЕОРИИ ГРАФОВ

1.1.
Что такое граф?

Граф – это   универсальная    абстрактная    модель.   Граф    состоит  

из вершин и ребер.  Вершины  моделируют объекты,  а  каждое ребро

моделирует отношение между  двумя  объектами, которые моделируются 

этими двумя вершинами. 

Рассмотрим следующий пример. Пусть объекты – это студенты.   

Каждому студенту  поставим в соответствие  вершину
графа.  По-другому 

можно сказать, что каждая вершина графа моделирует студента. Сколько    

студентов – столько и вершин. Студенты могут дружить друг с другом или 

нет.  «Дружба»  – это отношения между  студентами. Если  два  студента  

«дружат» между собой,  то   между вершинами, которые их моделируют,  

будет существовать ребро. Если  два  студента не «дружат», то между двумя 

вершинами, которые им соответствуют в графе, ребра нет.

Граф можно задать графически, таблицей или списком.  На рис. 1.1 

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

графа. Линии – это ребра, кружки – вершины. Если вершины соединены 

ребром, то говорят, что эти две вершины смежны друг другу. 

Рис. 1.1. Графическое представление графа

1

2

3

4
5

На рис. 1.2 показана одна их форм табличного представления этого 

графа – матрица смежности.  

Рис. 1.2. Матрица смежности графа

Матрица смежности состоит из строк и столбцов. Если в графе пять 

вершин, то в матрице смежности будет пять строк и пять столбцов. Каждая 

строка и столбец имеет номер. Первая строка и первый столбец 

соответствуют  вершине графа с номером «1» – Первой вершине. Вторая 

строка и второй столбец соответствуют  вершине графа с номером «2» –

Второй вершине, и т.д. Если на пересечении первой строки и второго столбца 

поставлена «1», то это означает, что первая и вторая вершины соединены 

ребром. Если стоит «0», то эти вершины ребром не соединены.

Граф отражает отношения между любыми парами вершин, т.е. 

бинарные отношения между объектами. В нашем примере объекты – это 

студенты, а отношение между каждой парой студентов  – «дружны два 

студента или нет». Граф (см. рис. 1.1) показывает, что Первый студент 

«дружит» только со Вторым, Второй студент «дружит» со всеми студентами,  

кроме Четвертого, Третий студент «дружит» со Вторым и Пятым студентами, 

а Четвертый студент «не дружит» ни с кем. 

Для того чтобы проверить – «дружат» ли два студента, нужно 

проверить, есть ли ребро между вершинами графа, которые соответствуют 

этим студентам. По графическому изображению графа (см. рис. 1.1) это 

1
2
3
4
5

1
0
0
0

0
1
0
1

1
0
0
1

0
0
0
0

0

1

0

0

0
1
1
0
0

1

2

3

4

5

можно сделать визуально. По матрице смежности это можно узнать, 

проверив значение элемента на пересечении строки и столбца, которые 

соответствуют этим вершинам. Если элемент матрицы равен 1, то студенты,

которым соответствуют вершины с номерами строки и столбца матрицы 

смежности, «дружат» между собой, если элемент матрицы равен 0, то эти 

студенты «не дружат» между собой.

1.2.
Симметрический граф и мультиграф

Граф, показанный на рис. 1.1 называют симметрическим графом.

Симметрический граф – это неориентированный граф, без петель и 

кратных ребер. 

Симметрическим граф назвали потому, что матрица его смежности 

симметрична относительно главной диагонали. 

Элементы главной диагонали матрицы смежности симметрического 

графа равны нулю, поскольку симметрический граф не должен содержать 

петель.

Петля у какой-то вершины в графе с номером i (i-ой вершины) 

означает, что эта вершина смежна сама с собой. В этом случае элемент  

главной диагонали матрицы смежности для такой вершины будет равен 1.

Другим типом графов является мультиграф.

Мультиграф – это граф, любые пары вершин которого могут быть 

соединены несколькими ребрами.

Поэтому каждый элемент матрицы смежности мультиграфа равен 

количеству ребер между соответствующей этому элементу парой вершин.

На рис. 1.3 показан мультиграф, у которого Первая и Вторая, Вторая и 

Третья вершины соединены двумя ребрами, а Третья и Четвертая вершины  –

тремя ребрами. 

На рис. 1.4 показана матрица смежности такого мультиграфа.