Алгоритмы на графах и их приложения. Дорофеева В.И. - 45 стр.

UptoLike

ВУЗ: 

ОГУ | Орел

Составители: 

Рубрика: 

45
но нажать Файл → Открыть, появляется диалог открытия файла, выбрать в
нем нужный и, нажав кнопку Открыть, на экране можно увидеть сохраненный
граф.
3.6 Результаты решения задач
Поскольку изначально графы разрабатывались как способ построения
различных моделей, с их помощью можно решать различные прикладные зада-
чи. В частности, это может быть нахождение кратчайшего расстояния на мест-
ности, решение некоторых сетевых проблем (использование в Internet) и др.
В качестве демонстрации возможностей работы программы, приведем
примеры решения некоторых задач
3.6.1 Задача нахождения кратчайшего расстояния в графе
Задача №1. Эта задача демонстрирует решение для достаточно простого
графа, для которого можно найти минимальное расстояние аналитически, ис-
пользуя алгоритм Дейкстры. Она равна для данного графа, состоящего из 5
вершин и 9 дуг, 48, 85 ед. пути (рисунок 47).
Рисунок 47
Задача №2. Эта задача демонстрирует решение более сложного графа, для
которого можно найти максимальную пропускную способность аналитически
посидев немного с калькулятором. Этот граф имеет 20 вершин. Минимальным 
но нажать Файл → Открыть, появляется диалог открытия файла, выбрать в
нем нужный и, нажав кнопку Открыть, на экране можно увидеть сохраненный
граф.
    3.6 Результаты решения задач
        Поскольку изначально графы разрабатывались как способ построения
различных моделей, с их помощью можно решать различные прикладные зада-
чи. В частности, это может быть нахождение кратчайшего расстояния на мест-
ности, решение некоторых сетевых проблем (использование в Internet) и др.
        В качестве демонстрации возможностей работы программы, приведем
примеры решения некоторых задач
    3.6.1 Задача нахождения кратчайшего расстояния в графе
  Задача №1. Эта задача демонстрирует решение для достаточно простого
графа, для которого можно найти минимальное расстояние аналитически, ис-
пользуя алгоритм Дейкстры. Она равна для данного графа, состоящего из 5
вершин и 9 дуг, 48, 85 ед. пути (рисунок 47).




                                  Рисунок 47
  Задача №2. Эта задача демонстрирует решение более сложного графа, для
которого можно найти максимальную пропускную способность аналитически
посидев немного с калькулятором. Этот граф имеет 20 вершин. Минимальным


                                          45

Страницы