Введение в теорию графов
Покупка
Основная коллекция
Издательство:
Российский университет транспорта
Автор:
Захаров Дмитрий Дмитриевич
Год издания: 2018
Кол-во страниц: 49
Дополнительно
Вид издания:
Учебно-методическая литература
Уровень образования:
ВО - Бакалавриат
Артикул: 788063.01.99
В учебно-методическом пособии излагаются основные понятия теории графов, матричные подходы к описанию графов, а также основные типы графов и их свойства. Рассматриваются различные способы решения задач теории
графов, приводятся содержательные примеры. Предполагается предварительное знакомство студента с началами математического анализа и алгебры. Пособие нацелено на прививание учащимся навыков самостоятельного решения прикладных задач инженерной практики.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 08.03.01: Строительство
- ВО - Специалитет
- 08.05.01: Строительство уникальных зданий и сооружений
- 08.05.02: Строительство железных дорог, мостов и транспортных тоннелей
- 08.05.03: Строительство, эксплуатация, восстановление и техническое прикрытие автомобильных дорог, мостов и тоннелей
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «РОССИЙСКИЙ УНИВЕРСИТЕТ ТРАНСПОРТА (МИИТ)» _________________________ Кафедра «Математический анализ» Д.Д. Захаров ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ Учебно-методическое пособие к практическим занятиям по дисциплине «ВЫСШАЯ МАТЕМАТИКА» Москва – 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.