Полная версия

Главная arrow Математика, химия, физика arrow Комбинаторные алгоритмы: множества, графы, коды

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Порядок выполнения задания

  • 6.5.1. Изучить указанный в варианте задания алгоритм построения минимального остова. Разработать детальное описание алгоритма. Считать, что на вход алгоритма поступает взвешенный граф, содержащий несколько компонент связности. На выходе алгоритм должен выдавать перечень ребер остовного леса с указанием его отдельных компонент. Реализовать алгоритм в виде программной процедуры. Оформление процедуры должно допускать её автономное тестирование. Для тестирования использовать примеры 6.1, 6.2.
  • 6.5.2. Разработать и отладить программу решения прикладной задачи с использованием алгоритма Краскала или Прима согласно номеру варианта задания (табл. 6.1).

Варианты

Номер варианта задания определяет алгоритм построения минимального остова и название прикладной задачи (табл. 6.1).

Таблица 6.1

Номер

варианта

Алгоритм

Задача

1

Краскала

Схема мелиорации рисовых полей

2

Прима

Схема мелиорации рисовых полей

3

Краскала

Проектирование надежной сети передачи информации

4

Прима

Проектирование надежной сети передачи информации

5

Краскала

Дерево максимального взаимопонимания

6

Прима

Дерево максимального взаимопонимания

Схема мелиорации рисовых полей. При выращивании риса небольшие участки земли, огороженные земляными валиками, заливают водой, а позднее, перед снятием урожая, эту воду спускают. Такие участки земли называют чеками. Вид карты рисового поля, состоящего из многих чеков, приведен на рис. 6.4. Ребра графа соответствуют земляным валикам, а вершины - точкам их пересечений. Для заполнения чеков в некоторых земляных валиках открывают проходы и после заполнения их водой закрывают. Каждый земляной валик характеризуется трудоемкостью установления в нем прохода. На рис. 6.4 эти трудоемкости указаны в скобках.

Требуется найти схему установления проходов в земляных валиках, которая позволяла бы открывать или закрывать все чеки рисового поля с минимальной трудоемкостью.

Рис. 6.4

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

Остовное дерево максимальной трудоемкости однозначно определяет места наименее затратного расположения проходов - это ребра, не вошедшие в этот остов.

Проектирование надежной сети передачи информации. На

графе, изображенном на рис. 6.5, каждая вершина представляет некоторое лицо, а ребро {v„ у,} отражает тот факт, что лицо v, может общаться с лицом Vj, и наоборот, т. е. между v, и у, существует канал связи. Передаче сообщения от v, к у, приписывается вероятность рц того, что послание может быть перехвачено посторонним лицом. Эти вероятности в процентах даны на рис. 6.5.

Рис. 6.5

Требуется определить такой способ передачи конфиденциального сообщения между 12 лицами, при котором вероятность утечки информации будет минимальной. Очевидно, что пути передачи сообщения должны образовывать остовное дерево графа. Необходимо найти такое остовное дерево, которое минимизирует величину

где произведение берется по тем ребрам, которые образуют это дерево. Поскольку функция С монотонно возрастающая относительно р^, то требуемое остовное дерево будет совпадать с минимальным остовом, при этом веса ребер определяются следующим образом:

Дерево максимального взаимопонимания. В коллективе, состоящем из 7 человек, была произведена оценка взаимопонимания между членами коллектива по десятибалльной системе (высший балл - 10, низший - 1). Результаты этой оценки представлены в (7 х 7)-матрице W= {Wy} (рис. 6.6).

Рис. 6.6

Матрицу W можно рассматривать в качестве матрицы весов полного неориентированного графа порядка 7. Вершины этого графа - сотрудники коллектива, а веса ребер - уровень взаимопонимания между сотрудниками. В этой ситуации максимальный остов полного графа с матрицей весов W - дерево максимального взаимопонимания, которое в определенной мере характеризует наиболее эффективные контакты между членами коллектива при решении общих вопросов. Требуется найти это дерево.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>