Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Анализ связей в графе заключается, прежде всего, в нахождении и оценке путей между его вершинами. Помимо непосредственного отыскания пути в некоторой системе коммуникаций к этой задаче относится, например, задача выбора оптимальной стратегии и др. Действительно, достаточно вершинам графа поставить в соответствие некоторые цели, а длинам путей - стоимости достижения этих целей, чтобы получить задачу выбора стратегии достижения цели с наименьшими издержками.
Поиски путей по чертежу при сложной структуре графа (на практике приходится анализировать графы с числом вершин более 100) затруднены и сопряжены с возможностью ошибок. Рассмотрим один из алгебраических методов, удобный для использования на ЭВМ. Этот метод позволяет, исходя из матрицы непосредственных связей , построить полную матрицу путей , где - число путей из вершины i к вершине j ( = 0), либо ограничиться отысканием одного из ее элементов.
Числа или их буквенные выражения определяются при помощи определителей особого рода - квазиминоров (беззнаковых определителей). Имеет место формула
.
Выражение называют квазиминором элемента матрицы . Знак является символом квазиминора, а указывает на матрицу с вычеркнутыми l -й строкой и k -м столбцом, которая вписывается в символ квазиминора подобно матрице, вписываемой в символ обычного минора.
Вычисление квазиминора сводится к разложению его на квазиминоры меньшего порядка по формуле
Здесь
Процедура вычисления во многом сходна с процедурой вычисления обычных определителей, но для овладения этим методом требуется некоторый навык.
Пример.
Пусть матрица непосредственных связей имеет вид
Необходимо найти все пути, ведущие из вершины 1 в 5, и подсчитать их число.
Для рассматриваемого примера получаем
Первоначально в матрице вычеркивается столбец 1, соответствующий номеру вершины, от которой начинается путь, и строка 5, соответствующая номеру вершины, в которой путь заканчивается. Это соответствует удалению из графа всех ребер, ведущих в вершину 1 и выходящих из вершины 5. Положение и нумерацию остальных строк и столбцов удобнее оставить без изменения. Далее необходимо произвести разложение полученного квазиминора по ненулевым элементам 1-й строки
Разложение для первого слагаемого ведется по второй строке, второго - по третьей, третьего - по четвертой, т.е. номер строки, по которой ведется разложение, равен номеру столбца, в котором находился последний член разложения.
Если теперь положить для ненулевых элементов = 1 и произвести операции по правилам обычной арифметики, то получим - .
Если же в полученном выражении произвести действия по правилам булевой алгебры, то получим значение полной матрицы связей , которая характеризует связность графа. Значения элементов полной матрицы связей определяются так:
= 1, если вершина i связана с вершиной j хотя бы одним путем,
=0 в противном случае.
Обычно считают, что .
Связность - важнейшая характеристика структурной схемы системы. Структура тем лучше, чем полнее заполненность полной матрицы связей. Наличие большого числа нулей говорит о серьезных изъянах в структуре системы.
Другая важная характеристика структуры - распределение значимости элементов системы. Количественная характеристика значимости - ранг элемента - впервые явно была сформулирована при анализе структуры отношений доминирования (превосходства, преобладания) в группах индивидуумов (людей, животных).
Используя полную матрицу путей , значения рангов элементов определяются по формуле
.
Следует иметь в виду, что значимость элемента определяется не самим значением , а сравнением рангов всех элементов, т.е. ранг - это относительный показатель значимости.
Какие же практические рекомендации можно выработать, проведя ранжирование элементов системы?
Чем больше ранг данного элемента, тем большим числом путей он связан с другими элементами и тем для большего числа элементов нарушатся нормальные условия работы при его отказе. Следовательно, при формировании программы обеспечения надежности рассматриваемой системы необходимо уделить особое внимание элементам с большим рангом.
Для систем со структурой типа сетей наличие элементов с рангами, значительно большими, чем у остальных, обычно свидетельствует о функциональной перегрузке этих элементов. Желательно перераспределить связи, предусмотреть обходные пути, чтобы уравнять значимость элементов данной системы.
Существуют и другие методики определения рангов. Выбор подходящей методики определяется спецификой задачи.
Следует отметить, что имеются структуры, ранжирование элементов которых может потерять практический смысл. Это, прежде всего, иерархические структуры. Значимость элемента в них определяется уровнем иерархии.
Сетевое планирование
Дата публикования: 2015-10-09; Прочитано: 636 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!