Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Бурков В.Н. Элементы теории графов
 
djvu / html
 

В.Н. Бурков, Д.А. Новиков
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Теория графов в качестве теоретической дисциплины1 может
рассматриваться как раздел дискретной математики, исследующий
свойства конечных множеств (бесконечные графы рассматривать
мы не будем) с заданными отношениями между их элементами.
Как прикладная дисциплина теория графов позволяет описывать и
исследовать многие технические, экономические, биологические и
социальные системы.
Задача настоящего материала заключается в том, чтобы, сле-
дуя, в основном [8], изложить основные понятия и результаты
теории графов, необходимые для постановки и решения задач
управления организационными системами.
Изложение материала имеет следующую структуру. В первом
разделе вводятся основные понятия, во втором рассматриваются
задачи о максимальных путях и контурах на графах, в третьем -
свойства псевдопотенциальных графов, в четвертом - задачи о
максимальном потоке, в пятом - задачи сетевого планирования и
управления.
1. Основные понятия теории графов
Граф - система, которая интуитивно может быть рассмотрена
как множество кружков и множество соединяющих их линий
(геометрический способ задания графа — см. рисунок 1). Кружки
называются вершинами графа, линии со стрелками - дугами, без
стрелок -ребрами. Граф, в котором направление линий не выделя-
ется (все линии являются ребрами), называется неориентирован-
ным; граф, в котором направление линий принципиально (линии
являются дугами) называется ориентированным.
Теория графов может рассматриваться как раздел дискретной
математики (точнее - теории множеств), и формальное определе-
1 Начало теории графов датируют 1736 г., когда Л. Эйлер решил популярную в
то время «задачу о кенигсбергских мостах». Термин «граф» впервые был введен
спустя 200лет (в 1936г.) Д. Кенигом.
1

 

1 2 3 4 5 6 7 8 9 10 20


Математика