Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Топ:
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
2017-10-21 | 315 |
5.00
из
|
Заказать работу |
|
|
Пусть G – построенный информационно-логический граф, а G* - граф, называемый конденсацией графа G, который определяется следующим образом: каждая его вершина соответствует множеству вершин некоторой сильной компоненте графа G, то есть (разным сильным компонентам из графа G отвечают разные вершины в конденсации G*); дуга существует в конденсации G* тогда и только тогда, когда в графе G имеется такая дуга , что вершина принадлежит сильной компоненте , соответствующей вершине в конденсации G*, а вершина принадлежит сильной компоненте , соответствующей вершине в конденсации G*, то есть справедливы следующие соотношения: , а .
Сильными компонентами графа будем считать максимальные подграфы графа G, обладающие заданным свойством. Поскольку в данном случае в качестве такого свойства выступает сильная связность вершин графа G, его сильные компоненты будут представлять собой подмножества (порожденные подграфы) взаимно связных вершин.
Требуется найти его сильные компоненты и построить конденсацию графа G, то есть построить граф G*.
Эта процедура реализуется при использовании матриц достижимости RG и контрдостижимости QG графа G.
Матрица достижимости RG=||rjs|| определяется следующим образом:
1, если вершина ℓs достижима из вершины ℓj (т.е. ℓj→ℓs)
rjs =
0, в противном случае.
Вершина ℓs считается достижимой из вершины ℓj, если существует путь от вершины ℓj к вершине ℓs.
Полагают, что все диагональные элементы матрицы RG равны 1, т.к. каждая вершина достижима из самой себя путем длиной 0. В качестве алгоритма построения матрицы достижимости RG можно предложить следующий:
Вход: Матрица AG смежности графа G, состоящая из строк A1, A2,…, Aj,…, Ak; Aj=(aj1,…, ajs,…, ajk)
|
Выход: Матрица достижимости RG, состоящая из строк R1, R2,..., Rj,…, Rk, где
Rj=(rj1,…, rjs,…, rjk)
Алгоритм запишем в виде, использующем так называемый псевдоалгол:
Начало
1. для j от 1 до k шаг 1 цикл А
2. сформировать множество S индексов s таких, что ajs=1;
3. Rj:= Aj ; k:=0;
4. пока S≠0 цикл В
5. выбрать sєS;
6. Rj:=Rj As;
7. S:=S\{s};
8. K:=K {s};
9. Сформировать множество Ss индексов r таких, что asr=1;
10. S:=S (Ss\K);
11. конец цикла В;
12. возврат Rj;
13. конец цикла А;
Конец
Матрица контрдостижимости QG=║qjs║ определяется следующим образом:
1, если из вершины ℓs графа G достижима вершина ℓj (т.е. ℓj←ℓs)
qjs =
0, в противном случае.
При этом qjs =1, если j=s. Очевидно, что матрица QG есть транспонированная матрица RG.
На следующем этапе алгоритма выполняется поэлементное умножение матриц RG и QG графа G, в результате чего получаем матрицу (RG QG).
При этом строка ℓj матрицы RG QG содержит единицы только в тех столбцах ℓs, для которых выполняется условие: вершины ℓj и ℓs взаимно достижимы. В других местах строки стоят нули. Таким образом, две вершины графа G находятся в одной и той же сильной компоненте тогда, когда соответствующие им строки (или столбцы) в матрице RG QG идентичны.
Следующий шаг алгоритма – преобразование матрицы (RG QG) путем транспонирования ее строк и столбцов в блочно-диагональную матрицу , каждая из диагональных подматриц (блоков) которой соответствует сильной компоненте графа G и содержит только единичные элементы, поскольку вершины, которым отвечают строки, имеющие единицу в столбце ℓs, образуют множество вершин сильной компоненты, содержащей вершину ℓs. Все остальные блоки данной матрицы имеют нули.
Графическое представление полученной диагональной матрицы представляет собой граф искомой структуры, рассматриваемой АСОИУ.
Для инфологического графа G, представленного на рис. 1, его конденсация, то есть граф G*, полученный путем применением рассмотренного алгоритма, представлен на рис. 2.
|
Рис. 1. Пример инфологического графа АСОИУ
Рис. 2. Граф G* как структура АСОИУ
|
|
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!