Структура матричных характеристик еанных итерграфов - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
«программирование матричных операций» 1 61.76kb.
Лекция 12 Пространственная структура одноцепочечных трнк. Вторичная... 1 98.47kb.
Лекция №7 Определение динамических характеристик промышленных объектов... 1 109.27kb.
Исследование характеристик малогабаритной гировертикали мгв-1 2 617.87kb.
Перечень технических характеристик и параметров излучения радиоэлектронных... 1 15.1kb.
Отчету о втором этапе исследования по теме «Получение интегральных... 1 31.51kb.
Файловая структура операционной системы windows 1 34.42kb.
Структура земельного фонда России 2 432.4kb.
Погрешности и условия применения импульсных методов определения теплофизических... 1 281.85kb.
Направленность личности. Структура направленности личности? 1 79.95kb.
Программа курса. Преподаватель А. А. Кибрик I. Введение в дискурсивный... 1 45.18kb.
Контрольная работа №3 3 Примеры решения задач по цифровой обработке... 1 17.21kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Структура матричных характеристик еанных итерграфов - страница №1/1

УДК 517.977.1+519.179.1
С.Л. БЛЮМИН

S.L. BLYUMIN


СТРУКТУРА МАТРИЧНЫХ ХАРАКТЕРИСТИК ЕАННЫХ ИТЕРГРАФОВ

КАК МОДЕЛЕЙ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ И МУЛЬТИАГЕНТНЫХ СИСТЕМ

STRUCTURE OF MATRIX CHARACTERISTICS OF EAN ITERGRAPHS

AS MODELS OF PARALLEL PROCESSES AND MULTI-AGENT SYSTEMS
В данной статье автор освещает проблему формирования структуры конечных еанов, полных еанных гиперграфов, полных еанных итерграфов, их матриц инцидентности, валентности, смежности и составленных из них лапласианов. Результаты в перспективе могут найти применение при моделировании параллельных процессов, мультиагентных систем, телекоммуникационных систем и компьютерных сетей будущих поколений.

Ключевые слова: еанные итерграфы, матрицы инцидентности, лапласианы.

In given article author shine a problem of formation of structure of finite eans, full ean hypergraphs, full ean itergraphs, their matrices of incidence, valence, adjacency and composed from them Laplacians. Results may find in perspective applications in simulation of parallel processes, multi-agent systems, telecommunication systems and computer networks of next generations.

Keywords: ean itergraphs, incidence matrices, Laplacians.
Работа поддержана РФФИ, проект № 11-07-00580-а
Роль графов и их матричных характеристик в математическом моделировании параллельных вычислений и мультиагентных систем хорошо известна [1-4]. При совместном исследовании параллельных вычислительных систем и алгоритмов, установлении критериев реализуемости, развертки, уравновешенности ключевую роль играет транспонированная матрица инцидентности, известная также как градиент, ориентированного графа, ассоциированного с алгоритмом. При исследовании проблемы согласования состояний – достижения консенсуса – агентов мультиагентной системы ключевую роль играет лапласовская матрица – лапласиан – ориентированного графа, ассоциированного с системой. Эти матрицы взаимосвязаны: лапласиан является произведением матрицы инцидентности на градиент. Они связаны и с другими матричными характеристиками графов: лапласиан является разностью матриц валентности и смежности.

Графы своими ребрами (или, в случае орграфов, дугами) моделируют парные взаимодействия операций алгоритма или агентов мультиагентной системы, представленных вершинами; взаимодействия ребер (дуг), то есть самих пар между собой, в графе не определены. Групповые взаимодействия моделируются гиперребрами (гипердугами) гиперграфов (оргиперграфов) ([5-7], или итерграфов первого порядка [8]; взаимодействия гиперребер (гипердуг), то есть самих групп между собой, в гиперграфе не определены. Парные взаимодействия групп агентов моделируются метаграфами [9]. Групповые взаимодействия групп агентов моделируются гипергиперграфами, или итерграфами второго порядка; гипервершинами гипергиперграфа, как и метавершинами метаграфа, являются не обязательно одноэлементные подмножества носителя, то есть гиперребра гиперграфа с тем же носителем; гипергиперребрами гипергиперграфа являются, по аналогии с гиперграфом и в отличие от метаграфа, не неупорядоченные пары, а неупорядоченные наборы гипервершин, то есть не пары, а наборы подмножеств носителя; гипергипердугами оргипергиперграфа являются некоторым образом ориентированные наборы подмножеств носителя. Метаграфы так же соотносятся с гипергиперграфами, как графы с гиперграфами. Процесс подобного учета взаимодействий может быть продолжен; он соответствует моделированию иерархических структур [10]; дальнейшее развитие графовых структур основано на итерировании булеанов и приводит к итерграфам – итерированным гиперграфам [8]. Каждый из указанных классов графовых моделей описывается соответствующими матричными характеристиками.

Неориентированные графы характеризуются беззнаковыми (signless) матрицами инцидентности и лапласианами, так же связанными между собой; беззнаковый лапласиан является суммой матриц валентности и смежности [11]. Известны примеры применения беззнаковых лапласианов в задачах управления мультиагентными системами (например, перераспределение состояний [12], анти-консенсус [13]). В [14] определена структура беззнаковых лапласианов гиперграфов, а также, при специальном способе кодирования ориентации гипердуг, – структура лапласианов ориентированных гиперграфов. Иерархический процесс учета взаимодействий может быть рассмотрен и в этом контексте.

Ориентированные графы характеризуются стандартными матрицами инцидентности и лапласианами, связь которых указана выше. Гипердугами оргиперграфа являются ориентированные гиперребра – упорядоченные наборы вершин: одна из них определяется как начало, другая – как конец, остальные – как промежуточные вершины гипердуги; этот подход развит в [14, 5-7]. Известен и другой способ ориентации гиперребер, то есть превращения их в гипердуги, при котором гиперребро разбивается на два подмножества, одно из которых определяется как начало, а второе – как конец гипердуги. Так как сами указанные подмножества, в свою очередь, являются, по определению, гиперребрами, то в так определенном оргиперграфе определены взаимодействия некоторых гиперребер, играющих, таким образом, роль вершин орграфа. Это и приводит к следующей графовой структуре – метаграфу. Метадугами орметаграфа являются, по аналогии с орграфом, упорядоченные пары метавершин: одна из них определяется как начало, а вторая – как конец метадуги. Метаребра и метадуги определяют взаимодействия метавершин метаграфа и характер этих взаимодействий. Взаимодействия метаребер и метадуг в метаграфе и орметаграфе не определены. Определенный выше оргиперграф является частным случаем метаграфа.

Гиперребра гиперграфа являются подмножествами множества его вершин; множество гиперребер полного гиперграфа является булеаном множества S его вершин мощности s, который, в соответствии с его теоретико-множественным биномиальным разложением, является объединением непересекающихся множеств гиперребер полных k-равномерных гиперграфов (0ks; случай k=2 соответствует полному графу). Нечеткие гиперребра нечеткого гиперграфа являются нечеткими подмножествами множества его вершин [15]; множество нечетких гиперребер полного нечеткого гиперграфа является фазеаном множества его вершин мощности s, который, в случае конечной шкалы нечеткости мощности f, в соответствии с его теоретико-множественным полиномиальным разложением, является объединением непересекающихся множеств нечетких гиперребер полных ()-равномерных нечетких гиперграфов (; случай соответствует полному нечеткому графу). Известны примеры применения нечетких метаграфов в иерархическом моделировании (например, [16]). Иерархический процесс учета взаимодействий может быть рассмотрен и в этом контексте.

Булеаны и фазеаны являются находящими наибольшее практическое применение примерами еанов [17-19] – множеств отображений некоторого множества S в некоторое множество Е: в случае булеанов E=В={0,1}, в случае фазеанов E=F – некоторое конечное подмножество промежутка [0,1], например, (часто достаточно f=11). Этим определяется актуальность следующей задачи:

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

Далее представлены некоторые результаты.



Еанный гиперграф. Заданы конечные множества S, T, E, |S|=s, |T|=t, |E|=e, и отображение STE – еанный инцидентор – еанное соответствие между множествами S и T, являющееся элементом еана = {STE} этого произведения и определяющее еанный гиперграф EHG(S,T). Каноническая биекция [20] позволяет отождествить множество Т с подмножеством еана ES.

Структура еана. Еан ES, | ES |=, где допускает теоретико-множественное полиномиальное разложение , где – число значений отображений SE, – теоретико-множественные полиномиальные коэффициенты, ||= – числовые полиномиальные коэффициенты. В частном случае E=В={0,1} биномиальное разложение включает множество двухэлементных подмножеств; полный граф =ВHG(s;[2]).

Структура еанной матрицы инцидентности. В соответствии с этим еанная матрица инцидентности (график инцидентора) ЕI(S, ES)=EI(s;[]) полного еанного гиперграфа EHG(S,ES)=EHG(s;[]) имеет блочную структуру EI(s;[])= =[...EI(s;[])...], где EI(s;[]) – матрицы инцидентности полных ()-равномерных еанных гиперграфов; элементы (i;j)E этих матриц формируются из значений отображений SE.

Структура еанного лапласиана. В соответствии с изложенным еанный лапласиан ЕL(S, ES)=EL(s;[]) полного еанного гиперграфа, при надлежащей алгебраической структуре в множестве Е, допускает представление

EL(s;[]) = EI(s;[])EI(s;[])* =

=  EI(s;[]) EI(s;[])* =  EL(s;[]),

где матричная операция *, включающая транспонирование матрицы, может включать и некоторые дополнительные операции над ее элементами, определяемые алгебраической структурой в множестве Е. Для полного гиперграфа ВHG(s;[]) эта структура лапласиана определена в [14], операция * сводится к транспонированию.



Еанный итерграф. Еанный итерграф второго порядка, или еанный гипергиперграф, определяется соотношением . В случае Е=В, в соответствии с биномиальным разложением, определяется метаграф [9] как итерграф дробного порядка, вычисленного в [8], как и дробный порядок графа.

Следует отметить, что предложенное в [9] определение матрицы инцидентности метаграфа согласуется с традиционным, тогда как определение матрицы смежности обладает определенным своеобразием; это отражается на определении лапласиана итерграфа.



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

СПИСОК ЛИТЕРАТУРЫ


  1. Воеводин В.В. Математические модели и методы в параллельных процессах. – М.: Наука, 1986. – 296 с.

  2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002. – 608 с.

  3. Чеботарев П.Ю., Агаев Р.П. Согласование характеристик в многоагентных системах и спектры лапласовских матриц орграфов // АиТ. – 2009. – № 3. – С. 136-151.

  4. Агаев Р.П., Чеботарев П.Ю. Сходимость и устойчивость в задачах согласования характеристик (обзор базовых результатов) // Управление большими системами. Спец. вып. 30.1 «Сетевые модели в управлении». – М.: ИПУ РАН, 2010. – С. 470-505.

  5. Блюмин С.Л. Полные гиперграфы. Спектры лапласианов. Мультиагентные системы // Управление большими системами. – Вып. 30. – М.: ИПУ РАН, 2010. – С.5-23.

  6. Блюмин С.Л. Мультиагентные системы: групповые взаимодействия агентов, взвешенные ориентированные гиперграфы // Системы управления и информационные технологии. – 2011. – № 2(44). – С. 49-53.

  7. Блюмин С.Л. Взвешенные ориентированные гиперграфы в моделировании мультиагентных систем: полный учет расхождений состояний агентов // Сб. тр. 16 Междунар. откр. науч. конф. «Соврем. проблемы информатиз. в экономике и обеспечении безопасности». – Воронеж: НК, 2011. – С. 52-55.

  8. Блюмин С.Л. Итергиперграфы: расширенный класс графовых моделей больших систем // Сб. тр. конф. «Теория активных систем» (ТАС-2011) в рамках Междунар. науч.-прак. мультиконф. «Управление большими системами» (УБС-2011). – М.: ИПУ РАН, 2011. – Т.1. – С. 11-15.

  9. Basu A., Blanning R. Metagraphs and Their Applications. – NY: Springer, 2007. – 172 p.

  10. Губко М.В. Математические модели оптимизации иерархических структур. – М.: ЛЕЛАНД, 2006. – 264 с.

  11. Cvetkovic D., Simic S. Towards a spectral theory of graphs based on the signless Laplacian // Linear Algebra and its Applications. – 2010. – V. 432. – P. 2257-2272.

  12. Блюмин С.Л. Взвешенные неориентированные гиперграфы в моделировании мультиагентных систем: пропорциональное перераспределение состояний агентов // Сб. тр. 16 Междунар. откр. науч. конф. «Соврем. проблемы информатиз. в анализе и синтезе программных и телекоммуникац. систем». – Воронеж: НК, 2011. – С. 309-310.

  13. Zhang L., Jiang H. Impulsive Cluster Anti-Consensus of Discrete Multi-Agent Linear Dynamic Systems // Discrete Dynamics in Nature and Society: An Open Access Journal. – 2011. – 12 p.

  14. Блюмин С.Л. Оргиперграфы: матричные представления // Управление большими системами. Спец. вып. 30.1 «Сетевые модели в управлении». – М.: ИПУ РАН, 2010. – С. 22-39.

  15. Берштейн Л.С., Боженюк А.В. Нечеткие графы и гиперграфы. – М.: Научный мир, 2005. – 256 с.

  16. Dashore P., Jain S. Fuzzy Metagraph and Hierarchical Modeling // International Journal on Computer Science and Engineering. – 2011. – V. 3, No. 1. – P. 435-439.

  17. Блюмин С.Л. Математические проблемы искусственного интеллекта: еанная, оидная и потентная математики // Сб. тр. Междунар. науч. конф. «Соврем. проблемы прикладной матем. и матем. моделирования». – Воронеж: ВГТА, 2005. – С. 34.

  18. Блюмин С.Л. Редукция еанных общих систем // Сб.тр. III Междунар. конф. по проблемам управления. – М.: ИПУ РАН, 2006. – С. 68.

  19. Блюмин С.Л. Математические проблемы искусственного интеллекта: еаны, оиды, потенты // Системы управления и информационные технологии. – 2006. - № 2 (24). – С. 4-8.

  20. Бурбаки Н. Теория множеств. – М.: Мир, 1965. – 455 с.


Блюмин Семён Львович

Липецкий государственный технический университет, г. Липецк

Д.ф.-м.н., профессор кафедры «Прикладная математика»

Тел.: +7(4742) 32-80-51



E-mail: sabl@lipetsk.ru