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


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

ние графа таково: задано конечное множество X, состоящее из п
элементов (Х= {1, 2, ..., п}), называемых вершинами графа, и
подмножество V декартова произведения X хХ, то есть V<^X2,
называемое множеством дуг, тогда ориентированным графом G
называется совокупность (X, V) (неориентированным графом назы-
вается совокупность множества X и множества неупорядоченных
пар элементов, каждый из которых принадлежит множеству X).
Дугу между вершинами z и у, i,j e X, будем обозначать (г, у). Число
дут графа будем обозначать т (V = (v/, \2, •••, vm)).
Г
Рис. 1. Пример графа
Язык графов оказывается удобным для описания многих фи-
зических, технических, экономических, биологических, социаль-
ных и других систем.
Приведем ряд примеров приложений теории графов.
1. «Транспортные» задачи, в которых вершинами графа явля-
ются пункты, а ребрами - дороги (автомобильные, железные и др.)
и/или другие транспортные (например, авиационные) маршруты.
Другой пример - сети снабжения (энергоснабжения, газоснабже-
ния, снабжения товарами и т.д.), в которых вершинами являются
пункты производства и потребления, а ребрами - возможные
маршруты перемещения (линии электропередач, газопроводы,
дороги и т.д.). Соответствующий класс задач оптимизации потоков
грузов, размещения пунктов производства и потребления и т.д.,
иногда называется задачами обеспечения или задачами о размеще-
нии. Их подклассом являются задачи о грузоперевозках [7, 12].
2. «Технологические задачи», в которых вершины отражают
производственные элементы (заводы, цеха, станки и т.д.), а дуги -
2

 

1 2 3 4 5 6 7 8 9 10 20


Математика