Презентация_Графы (2)

1. Теория графов

Задача Кенигсбергских мостов
Как пройти по всем мостам, не проходя ни по
одному из них дважды?

2. Задача о Ханойской башне

Даны три стержня, на одном из них нанизаны
восемь колец разного диаметра, меньшее лежит
на большем.
Как перенести пирамиду из восьми колец за
наименьшее число ходов на другой стержень?
За один раз можно переносить только одно
кольцо и нельзя класть большее кольцо на
меньшее.

3. Поиск путей в графе

Поиск гамильтонова пути (цикла)
Логистика
Задача коммивояжера (курьера)
«Коммивояжёр — как он должен вести себя и что должен делать
для того, чтобы доставлять товар и иметь успех в своих делах —
советы старого курьера», издана в 1832 году

4. Поиск путей в графе

Поиск эйлерова пути (цикла)
Изучение транспортных и
коммуникационных систем
(маршрутизация данных в Интернете)

5. Нахождение кратчайшего пути

Логистика
Маршрутизация
Навигация
Замена оборудования
Расписание ТС
Размещение пунктов на трассе
(телефонных станций и т.п.)

6. Визуализация графов

Схемотехника
Химия

7. Раскраска графов

Проблема четырех красок
Составление расписаний
Распределение памяти
Распределение оборудования
Задача проектирования
коробки скоростей

8.

Связность графов и сетей
проектирование кратчайшей коммуникационной сети
синтез структурно-надежной сети циркуляционной связи
анализ надежности стохастических сетей связи
Изоморфизм графов и сетей
структурный синтез линейных избирательных цепей
Изоморфное вхождение и пересечение графов
локализация неисправности с помощью алгоритмов поиска
покрытие схемы заданным набором типовых подсхем
Автоморфизм графов
конструктивное перечисление структурных изомеров для
производных органических соединений
синтез тестов цифровых устройств

9. Другие примеры использования графов

В информатике и
программировании
В экономике
В химии
В биологии
В физике
Задача о максимальном
потоке
Задача об упаковках и
покрытиях