§ библиотека мастерская Помощь Контакты Вход —

Новиков А.М., Новиков Д.А. Методология

В каталоге: Педагогика
Отдельное спасибо: anovikov.ru
Стр. 238

Теория графов – раздел дискретной математики. Неформальное определение графа таково: графом называется совокупность вершин (изображаемых кружками) и связей между ними, изображаемых ориентированными дугами (со стрелками) или неориентированными ребрами (без стрелок) – см.

Рис. 18.

image070.gif

Рис. 18. Пример графа

Язык графов оказывается удобным для моделирования многих физических, технических, экономических, биологических, социальных и других систем.

Приведем ряд примеров приложений теории графов (более подробное описание перечисляемых и других задач можно найти в [26, 29]).

·         «Транспортные» задачи, в которых вершинами графа являются пункты погрузки/разгрузки, а ребрами – дороги (автомобильные, железные и др.) и/или другие транспортные (например, авиационные) маршруты. Другой пример – сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами или дугами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т.д., иногда называется задачами обеспечения или задачами о размещении. Их подклассом являются задачи о грузоперевозках.

·         «Технологические задачи», в которых вершины отражают производственные элементы (заводы, цеха, станки и т.д.), а дуги – потоки сырья, материалов и продукции между ними, заключаются в определении оптимальной загрузки производственных элементов и обеспечивающих эту загрузку потоков.

·         Обменные схемы, являющиеся моделями таких явлений как бартер, взаимозачеты и т.д. Вершины графа при этом описывают участников обменной схемы (цепочки), а дуги – потоки материальных и финансовых ресурсов между ними. Задача заключается в определении цепочки обменов, оптимальной с точки зрения, например, организатора обмена и согласованной с интересами участников цепочки и существующими ограничениями.

из 532
Предыдущая    Следующая
 
Реклама
Авторизуйтесь