Автореферат (1137128), страница 2
Текст из файла (страница 2)
Основные результаты, полученные в процессе выполнениядиссертационной работы, опубликованы в 3 статьях (из них – 2 из списка ВАКРФ), в трудах и тезисах докладов конференций, учебно-методических пособиях.Структура и объём работы. Диссертация состоит из введения, четырёхглав, заключения, списка литературы (76 наименований) и 3 приложений. Онасодержит 127 страницу в основной части и 309 страниц приложений.6Содержание работыВо введении обоснована актуальность темы диссертационной работы, поставлены цели и задачи исследований, сформулированы научная новизна ипрактическая значимость, приведено краткое содержание работы по главам.В первой главе рассматриваются основные понятия, связанные с исследованием структурной сложности и симметрии графовых моделей систем (ГМС),формулируются основные решаемые задачи и раскрывается их прикладное значение.
Вначале даётся обзор развития понятий о системах в целом и об ихструктурах в частности, вводится понятие структурной сложности.Структурная сложность – одно из важнейших понятий в структурном анализе систем, неразрывно связанное с другими базовыми понятиями: сходством,симметрией и т.п. Именно развитие математических моделей структурнойсложности позволило формализовать новые подходы к анализу структурногосходства, предложить новые подходы к решению многих прикладных задач иповысить эффективность их решения.Далее уточняются объекты исследований: ГМС в виде обыкновенных графов и орграфов, а также их подклассы – транзитивные, планарные и пр. Далеепод графом будем понимать ГМС произвольного класса. Граф G1 изоморфновкладывается в граф G2, если G2 изоморфен G1 или в G2 есть часть, изоморфнаяG1.
Части графа определяются в соответствии с алгебраической системой КлодаБержа. Абстрактный тип или абстрактный граф (t) – произвольный граф, определённый с точностью до автоморфизма. Группу его вершинных автоморфизмов (также с точностью до изоморфизма) обозначим через Aut(t). Граф t назовём фрагментом графа G, если t изоморфно вкладывается в G в некоторомзаранее определённом смысле, то есть, если необходимо, будем различатьфрагменты-подграфы, фрагменты-частичные графы и т.п.
Теперь можно провести формализацию результата изоморфного вложения фрагмента в граф. Помеченным графом называется граф, каждой вершине которого сопоставленуникальный вес (пометка), то есть каждая вершина которого имеет уникальный атрибут. Наличие пометок будем обозначать верхним индексом «(l)». Понятие пометок вершин графа отличается от понятия нумерации (идентификации)вершин с целью хранения структурной информации.Помеченным фрагментом (ПФ) f (l)t типа t графа G назовём помеченныйграф t (l), пометками которого являются вершины графа G, образующие (вместес некоторыми инцидентными им рёбрами) часть графа G, изоморфную t.
ЧерезF(l)t(G) { f (l)t1, f (l)t2, …, f (l)tm} обозначим множество всех помеченных фрагментов типа t графа G.Для различения абстрактного типа и типов реальных фрагментов графа будем называть тип фрагмента с заданной нумерацией вершин идентификационным типом. Специального обозначения вводить не будем, так как из контекстаобычно ясно, введена нумерация вершин или нет. Не ограничивая общности,можно считать, что вершины нумеруются числами из натурального ряда: (1, 2,…, p), где p – число вершин графа. Это позволит записывать ПФ в виде векторапометок, в порядке, задаваемым нумерацией вершин идентификационного ти-7па.
Если на множестве вершин абстрактного типа фрагмента t и графа G задананумерация, то помеченный фрагмент графа f (l)t может быть представлен различными изоморфными вложениями – отображениями номеров вершин t в номера вершин G. Число изоморфных вложений, представляющих один и тот жепомеченный фрагмент графа, равно порядку группы автоморфизмов абстрактного типа ( | Aut(t) | ). Таким образом, число всех изоморфных вложений фрагмента типа t в граф G равно | F(l)t(G) | | Aut(t) |.
Помеченный фрагмент удобнопредставлять одним из изоморфных вложений, которое назовём каноническим.Каноническим будем считать то из изоморфных вложений, образующихфрагмент f (l)t графа G, у которого список номеров вершин графа G, в порядкенумерации вершин типа фрагмента t, лексикографически минимален. Такимобразом, устанавливается взаимно однозначное соответствие между частямиграфа и каноническими представлениями ПФ.Вводится понятие инварианта графа и классифицируются пространствахарактеризации структурной сложности, определяются индексы структурнойсложности в виде чисел, векторов, матриц и структурных моделей. Далее излагаются различные подходы (К.
Шеннона, А.Н. Колмогорова, С. Бертца, П. Виллета, Д. Бончева, М. Рандича, В.А. Кохова и др.) к пониманию и формализацииструктурной сложности графов и показывается, что исследование сложностинеотделимо от исследований симметрии. Спектральная структурная сложность графа определяется разнообразием и количеством его фрагментов. В еёоснове лежат понятия базиса и структурного спектра.
Базис фрагментов (B) –упорядоченный набор абстрактных типов (возможно, с весами). Структурныйспектр SS(G/B) графа G в базисе произвольных абстрактных типов B = (t1, t2,…, tk) определяется следующим образом:SS(G B) = <w1, w2, ..., wk>,где wi – число канонических изоморфных вложений (в некотором смысле)абстрактного типа ti в граф G.Заметим, что SS не содержит информации о сложности фрагментов.
Обобщения же вектор-индекса SS с использованием весовых коэффициентов, рекурсивных схем их вычисления, свёрток и других методов позволяют строитьмножества индексов и вектор-индексов спектральной сложности графа.Вектор-индекс структурной спектральной сложности V_ISSC(G/ B) графа G в базисе произвольных абстрактных типов B = (t1, t2, …, tk) определяетсяследующим образом:V_ISSC(G B) = <w1*ISC(t1), w2*ISC(t2), ..., wk*ISC(tk)>,где wi – число канонических изоморфных вложений (в некотором смысле)абстрактного типа ti в граф G, ISC(ti) – некоторая мера сложности типа ti.Затем можно предложить процедуры свёртки вектор-индексов для получения индексов спектральной сложности (ISSC(G B)) и рекурсивного вычисленияиндексов больших графов на основе априорно заданных значений сложностибазовых графов (например, вершины и ребра).
Недостаток этого подхода состоит в невозможности учёта влияния взаимного расположения фрагментов насложность графа.8Шенноновский подход к формализации структурной сложности основан научёте симметрии вершин и более крупных ПФ графа. Через Aut(G) обозначимгруппу автоморфизмов графа G (ГАГ), а через |Aut(G)| – порядок группы. Если|Aut(G)| = 0, то все элементы графа уникальны с точки зрения расположения внём, а если |Aut(G)| > 0, то граф обладает нетривиальной симметрией, и егоэлементы могут быть автоморфны. Орбита вершины v V – подмножество(Aut(G), v) вершин графа G, которые могут быть отображены на вершинуv: ( Aut (G), v) {v ':[ g Aut (G) : g (v ') v]} . Граф называется транзитивным,если все его вершины принадлежат одной орбите, и тождественным, есличисло орбит равно числу вершин.
Симметрия более крупных ПФ определяетсяаналогично, с использованием индуцированных представлений Aut(G) на множестве ПФ конкретного типа (t-группы – Autt(G)). Чем больше порядок группы,тем крупнее могут быть классы эквивалентности элементов (орбит) графа поотношению «быть автоморфными». Можно определить информационное содержание (количество информации), приходящееся на один фрагмент изk| F (l )t i |Ci log 2 Ci , где CiF(l)t(G), по формуле IIC tв предположении, что(l )t|F|i 1(l)tмножество F разбивается на k классов эквивалентности F(l)ti, i (1, k). На основе понятия информационного содержания ПФ можно построить большоечисло обобщений, включая индексы и вектор-индексы информационной сложности графа в различных базисах.В работе также рассматривается предложенная В.А. Коховым1 стратифицированная система структурных моделей структурной сложности (GMS), объединяющая несколько подходов.
Наиболее общими являются g-модели, представляющие собой двудольные графы, вершины которых взвешены помеченными фрагментами или их классами (вплоть до орбит t-групп), а рёбра – различными характеристиками взаимного расположения помеченных фрагментов/классов/орбит. b-модели и их подмодели являются наиболее важными спрактической точки зрения, так как в них вершины одной из долей взвешеныабстрактными типами, что делает вершины доли уникальными и позволяетприменить полиномиальные алгоритмы поиска максимального общего фрагмента двух b-моделей для эффективной реализации обобщённого подструктурного подхода к анализу сходства графов.Также в главе даётся обзор других популярных подходов к формализацииструктурной сложности, и приводятся примеры практического применения соответствующих моделей.
Дополнительно даётся обзор методов визуализацииГМС, что будет востребовано в главе 3.Далее в работе подробно исследуются следующие задачи:исследование отличий анализа спектральной сложности орграфов иобыкновенных графов с построением алгоритмов и получением новыхнаучных результатов для класса орграфов;1Кохов В.А.
Концептуальные и математические модели сложности графов. - Москва: Издательство МЭИ, 2002.- 160 c.9исследование значимости учёта симметрии и анализ сложности транзитивных графов степени 4 при их классификации и созданием системы синтеза их семейств.Во второй главе исследуется структурная сложность орграфов различныхклассов на основе как ранее разработанных программных средств построенияиндексов сложности, так и на основе оригинальной системы построения вектор-индексов спектральной сложности и b-моделей в базисах путей, контуров иориентированных цепных фрагментов (ОЦФ). Базисы путей и контуров ограниченной длины (DP0-n и DC0-n) для орграфов уже рассматривались ранее и реализуются для полноты программных разработок и сравнения результатов.Цепным фрагментом орграфа или ориентированным цепным фрагментом(ОЦФ) назовём связный орграф, состоящий либо из одной вершины (ОЦФ длины 0, наименьший элемент базиса), либо из большего числа вершин, причемдве из них имеют степень 1, а остальные – 2 (длина ОЦФ равна числу дуг внём).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
