Задачи на графах, 2.1 Описание различных задач на графах - Определение кратчайшего пути в графе

2.1 Описание различных задач на графах

Развитие теории графов в основном обязано большому числу всевозможных приложений. По-видимому, из всех математических объектов графы занимают одно из первых мест в качестве формальных моделей реальных систем.

Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т. п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических цепей и других систем сетевой структуры.

Далее перечислим некоторые типовые задачи теории графов и их приложения:

- Задача о кратчайшей цепи

Замена оборудования

Составление расписания движения транспортных средств

Размещение пунктов скорой помощи

Размещение телефонных станций

- Задача о максимальном потоке

Анализ пропускной способности коммуникационной сети

Организация движения в динамической сети

Оптимальный подбор интенсивностей выполнения работ

Синтез двухполюсной сети с заданной структурной надежностью

Задача о распределении работ

- Задача об упаковках и покрытиях

Оптимизация структуры ПЗУ

Размещение диспетчерских пунктов городской транспортной сети

- Раскраска в графах

Распределение памяти в ЭВМ

Проектирование сетей телевизионного вещания

- Связность графов и сетей

Проектирование кратчайшей коммуникационной сети

Синтез структурно-надежной сети циркуляционной связи

Анализ надежности стохастических сетей связи

- Изоморфизм графов и сетей

Структурный синтез линейных избирательных цепей

Автоматизация контроля при проектировании БИС

- Изоморфное вхождение и пересечение графов

Локализация неисправности с помощью алгоритмов поиска МИПГ

Покрытие схемы заданным набором типовых подсхем

- Автоморфизм графов

Конструктивное перечисление структурных изомеров для

Производных органических соединений

Синтез тестов цифровых устройств

Похожие статьи




Задачи на графах, 2.1 Описание различных задач на графах - Определение кратчайшего пути в графе

Предыдущая | Следующая