3. Задача соединения всех элементов системы без дублирующих связей.

Задача поиска остового дерева.

Под остовым или остовным деревом называются частичный граф, по отношению к некоторому базовому, не имеющий циклов.

При исследовании структур систем задача формирования остового дерева решается при поиске варианта всех элементов системы без дублирующих связей, например при построении локальной сети. Для автоматизации построения остового дерева можно использовать алгоритмы поиска на графе, предназначенные для выявления состава цепей между некоторыми заданными начальными и конечными вершинами N1 и N2. При использовании данных алгоритмов для построения остового дерева поиск необходимо производить до тех пор, пока не будут просмотрены все вершины.

9. Анализа структуры системы на основе взвешенных графов.

1. Взвешенные графы.

Взвешенный граф – это граф дугам, которого поставлены в соответствие некоторые числа (веса дуг).

Способы задания взвешенных графов:

• Графически

Рис 4.9. Графический способ задания взвешенных графов.

• Перечислением

<a,b> 5, <b,c> 13, <b,d> 8, <d,a> 9, <d,c> 8

• С помощью взвешенной матрицы смежности

Отсутствие дуги обычно рассматривается как дуга с весом +∞

	a	b	c	d
a	∞	5	∞	9
b	5	∞	13	8
c	∞	13	∞	8
d	9	8	8	∞

Рис 4.10. Задание взвешенных графов с помощью матрицы смежности.

2. Оптимизационные задачи на взвешенных графах.

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

Общий вид оптимизационной задачи:

Требуется найти значение y, которое зависит от x по некоторой зависимости f, причем y должно обеспечивать экстремальное значение некоторого показателя S.

При этом x должен принадлежать некоторой области допустимых значений D ( x ϵ D ), а y должен принадлежать некоторой области допустимых решений D ( y ϵ R ),.

В общем случае x, y – векторные величины.

Показатель? экстремальное значение, которого необходимо обеспечить в оптимизационной задаче называется критерием оптимальности.

Требования к критерию оптимальности:

• Определенность.

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

В классической оптимизационной задаче необходимо обеспечивать минимум показателя.

• Однозначность.

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

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

,

где S_сл – значение сложного критерия.

S₁, S₂, … S_n – значения частичных критериев.

k₁, k₂, … k_n – веса частичных критериев (весовые коэффициенты) которые соответствуют значимости частичных критериев.