ПОИСК Статьи Чертежи Таблицы Декомпозиция системы. Сильносвязанные области из "Компьютерная поддержка принятия решений " В примере А уже отмечалось, что при анализе системы расхода горючего эксперты первоначально назвали 500 факторов, влияющих на ее функционирование. Анализировать такой граф крайне сложно, если не невозможно. Для преодоления этой трудности можно произвести декомпозицию графа, разбив его на некоторое число областей, а затем произвести анализ как каждой области, так и обобщенного графа. В обобщенном графе каждая выделенная область является вершиной графа. Одним из возможных методов декомпозиции графа является разбиение его на тесно связанные области. [c.133] Надо сразу отметить, что во многих случаях лучше идти не сверху вниз , то есть не создавать сначала очень сложный граф, а потом производить его декомпозицию, а сразу выделить некоторые области и из них строить обощенный граф. Так в примере С вершина 2 смена администрации территории легко может быть развернута в достаточно содержательный граф, требующий самостоятельного изучения. [c.133] Введем определение тесно связанной области [2.35]. [c.133] В настоящее время разработано довольно много алгоритмов выделения тесно связанных областей [2.35-2.41], они достаточно сложны. Для пояснения идей выделения тесно связанных областей ниже приводится один из самых простых. [c.133] Пример. Граф на рис. 2.19 образует следующий список сильно связанных областей 5, 5-6, 2-7-3-4, 3-4. [c.134] Узлы 2-7 и 2-3-4 также образуют сильно связные области, но если в список сильно связных областей включить как область 2-7, так и область 2-3-4, то нарушается условие 3, так как 2-7г 2-3-4 2-3-4. [c.134] Тесно связанные области можно определять неформальным путем. [c.134] Пример. Граф рис. 2.19 может быть разбит на следующие области так, как это показано в табл. 2.16 и на рис. 2.20. [c.134] Заметим, что один и тот же узел может входить в несколько тесно связанных областей, но при этом обязательно меньшая область является подмножеством большей. [c.135] На рис. 2.21 показаны подсистемы второго уровня, входящие в граф рис. 2.20. [c.135] Вершины 3 и 4 образуют область третьего уровня. [c.135] Каждая тесно связанная область может рассматриваться как некоторая подсистема, живущая своей жизнью , но связанная со всей системой. Граф системы рис. 2.19 может быть представлен графом рис. 2.20, значительно более простым и более легким для анализа. Подграфы рис. 2.21 могут анализироваться отдельно. [c.135] Теперь рассмотрим алгоритм [2.41] нахождения сильно связных областей, обладающих свойствами 1-3 настоящего параграфа. Алгоритм рассмотрим на примере графа, показанного на рис. 2.19. [c.135] Матрица связи для графа рис. 2.19 показана в табл. 2.18. [c.136] Вводятся булевы векторы Кк, определяющие узлы графа на некотором замкнутом пути к. Элемент вектора Ккз=1, если через yзeлj проходит замкнутый путь к. [c.136] Если вершины и находятся на одном замкнутом пути длиной 1 И С 11 = 1, то И Jij = 1. [c.136] Для нахождения матрицы С по матрице О обозначим через С строку 1 матрицы О. Предварительно будем считать, что все элементы матрицы С равны нулю (С ц=0,1о=1,2.п). Тогда если вершина] следует немедленно за вершиной то С = С] V С + . [c.136] Поясним эту формулу на примере графа рис. 2.19. За вершиной 2 немедленно следуют вершины 3 и 7. [c.136] Это окончательное значение Сг . Ясно, что если бы за третьей вершиной графа непосредственно следовала только одна вершина, то для вычисления Сг нужно было бы сделать только один шаг, если бы за ней следовало п вершин - п шагов. [c.137] Полученный результат говорит, что путь длины 2 связывает вершину 2 с вершинами 4, 5, и 8, а также с самой вершиной 2, что легко проверить непосредственно. [c.137] Вернуться к основной статье