Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Введение в теорию графов

Покупка
Основная коллекция
Артикул: 788063.01.99
Доступ онлайн
188 ₽
В корзину
В учебно-методическом пособии излагаются основные понятия теории графов, матричные подходы к описанию графов, а также основные типы графов и их свойства. Рассматриваются различные способы решения задач теории графов, приводятся содержательные примеры. Предполагается предварительное знакомство студента с началами математического анализа и алгебры. Пособие нацелено на прививание учащимся навыков самостоятельного решения прикладных задач инженерной практики.
Захаров, Д. Д. Введение в теорию графов : учебно-методическое пособие к практическим занятиям по математике / Д. Д. Захаров. - Москва : РУТ (МИИТ), 2018. - 49 с. - Текст : электронный. - URL: https://znanium.ru/catalog/product/1896868 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
 
МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ 
ФЕДЕРАЦИИ 
Федеральное государственное бюджетное образовательное 
учреждение высшего образования 
«РОССИЙСКИЙ УНИВЕРСИТЕТ ТРАНСПОРТА (МИИТ)»  
_________________________ 
 
Кафедра «Математический анализ» 
 
Д.Д. Захаров  
  
 
 
ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ 
 
Учебно-методическое пособие к практическим занятиям  
по дисциплине  
«ВЫСШАЯ МАТЕМАТИКА» 
 
 
 
 
 
 
Москва – 2018 
 


 
 
МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ 
Федеральное государственное бюджетное образовательное 
учреждение высшего образования 
«РОССИЙСКИЙ УНИВЕРСИТЕТ ТРАНСПОРТА (МИИТ)»  
_________________________ 
 
Кафедра «Математический анализ» 
 
Д.Д. Захаров  
  
 
 
ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ 
 
 
 
 
  Учебно-методическое пособие для студентов 
 всех строительных специальностей 
 
 
 
Москва – 2018 
 
 


 
-2УДК 517 
З-38 
 
Захаров 
Д.Д. 
Введение 
в 
теорию 
графов: 
Учебнометодическое пособие к практическим занятиям по математике. – 
М.: РУТ (МИИТ), 2018. –49 с. 
 
 
В учебно-методическом пособии излагаются основные 
понятия теории графов, матричные подходы к описанию 
графов, а также основные типы графов и их свойства.  
Рассматриваются различные способы решения задач теории 
графов, 
приводятся 
содержательные 
примеры. 
Предполагается предварительное знакомство студента с 
началами математического анализа и алгебры. Пособие 
нацелено на прививание учащимся навыков самостоятельного решения прикладных задач инженерной практики.  
 
Рецензент: зав. кафедрой «Высшая и вычислительная математика» РУТ (МИИТ)     к.ф.-м.н. Платонова О.А. 
 
 
                                              ©РУТ (МИИТ), 2018 
 
 
 
 
 
 


 
 
ОГЛАВЛЕНИЕ 
 
 
Оглавление................................................................................. 
3 
 
Введение..................................................................................... 
4 
1. 
Орграфы и бинарные отношения: основные понятия и 
определения............................................................................... 
 
5 
2. Применение матриц к анализу простейших свойств 
графов......................................................................................... 
 
15 
3. Неографы. Полные, двудольные и эйлеровы графы. 
Изоморфизм............................................................................... 
 
22 
4. Деревья и леса........................................................................... 
27 
5. Задачи оптимизации: алгоритм ближайшего соседа и 
алгоритм Дейкстры................................................................... 
 
31 
6. Плоские и планарные графы.................................................... 
39 
7. Раскраски графов....................................................................... 
43 
 
Заключение………..................................................................... 
48 
 
Список литературы.................................................................... 
49 
 
 
 
 
 
 
 
 
 
 
 


 
-4Введение 
 
Начало теории графов как самостоятельного раздела 
математики обычно относят к 18-веку и связывают с именами 
таких классиков математического знания как Л. Эйлер, Г. Монж, 
Д. Кениг, Д. Сильвестр, А. Кэли, У. Гамильтон, Г. Кирхгоф и 
многих  других. К настоящему времени теория графов стала 
развитой 
и 
востребованной 
дисциплиной 
дискретной 
математики с огромным количеством приложений. Графы 
используют в задачах анализа и синтеза электрических цепей, 
для моделирования сложных молекул химических соединений, в 
генетике, при создании многопроцессорных компьютеров и 
сетей, различных систем коммуникации, в задачах транспорта, 
экономического планирования, финансах, в логистике и т.д.  
Теория 
графов 
широко 
использует 
матричные 
и 
комбинаторные методы, но в то же время имеет собственную 
специфику, 
конструктивно 
дополняющую 
родственные 
математические дисциплины.  
Ниже приводятся базовые сведения из теории графов, 
позволяющие сначала моделировать (и программировать) графы 
общего вида с помощью двоичных матриц и анализировать их 
фундаментальные свойства. Затем рассматриваются некоторые 
основные виды неориентированных графов, методы их изучения 
и типичные задачи. В каждом параграфе сначала приводятся 
основные теоремы и свойства графов, а потом рассматривается 
ряд примеров для развития навыков самостоятельного решения 
прикладных задач инженерной практики. 
 
 
 
 
 


 
-51. Орграфы и бинарные отношения: основные понятия 
и определения 
 
Пусть X  есть некоторое конечное множество, состоящее 
из n  различных элементов:  


1
2
,
,
,
n
X
x x
x

. Любое 
множество , такое, что  
2
X
X
X



назовем бинарным 
отношением на множестве X .  
Таким образом,  есть любое множество упорядоченных 
пар вида 
                




,
  
,
ij
i
j
i
j
x x
x
X x
X





,   
для каких-то возможных номеров i  и j  элементов на первых и 
вторых местах в паре. Характеризовать его можно следующей 
квадратной матрицей бинарного отношения или матрицей 
смежности 
 




если
если
0,  
  
,
1,   
  
,
i
j
ij
i
j
x x
x x







,      
1
2
1
11
12
1
2
21
22
2
1
2
        
  
    
      
0,1
n
n
n
ij
n
n
n
nn
x
x
x
x
x
x

























. 
На пересечении строки i  и столбца j  ставим символ 
принадлежности пары 

,
i
j
x x
 отношению .  
Сохраним обозначение матрицы той же буквой 
ij


Γ
, 
что и для отношения . 
 Назовем величину r  булевой, если она может принимать 
только значения 0 и 1. 


Доступ онлайн
188 ₽
В корзину