Автореферат (1137128), страница 3
Текст из файла (страница 3)
Отметим, что полустепени исхода и захода ОЦФ длины больше 1 могутбыть любыми в диапазоне от 0 до 2. Использование ОЦФ в качестве элементовбазиса позволяет увеличить дискриминирующую способность индексов спектральной сложности при сохранении минимальной вычислительной сложностиалгоритмов построения индексов. Действительно, вместо одного пути длины qq12мы получаем 2 ОЦФ для для нечётного q и ( 22 ) – для чётного. Разница в формулах количества фрагментов объясняется тем, что ОЦФ на нечётном числе дуг являются тождественными, а на чётном – могут иметь нетривиальный автоморфизм.
В таблице 1 приведены диаграммы базовых ОЦФ и ихстандартных значений сложности. Отметим, что сложность элементов базисазадаётся априори и может считаться атрибутом базиса.q 1q 1№1Таблица 1. Минимальные ОЦФ и их стандартная сложностьТекстовое представление ОЦФИзображение ОЦФСложность ОЦФ!120330094011051011600031700132810033901034В качестве примера рассмотрим орграф, изображённый на рис.
1. Используем фрагменты с 1 по 5 из таблицы 1 в качестве как левого, так и правого базисов. Полученная b-модель представлена на рис. 2.1012564378Рис. 1. Исходный орграф (несвязный)На вершинах правой доли (типах фрагментов) показано количество соответствующих помеченных фрагментов, а на вершинах левой доли (помеченныхфрагментах) – каноническое представление ПФ.1(1)2(2)113(3)14(4)115(5)6(6)227(7)28(8)1118222221(1,2)112(2,3)13(3,4)114(4,1)1113338321122222115(5,6)6(5,7)7(6,8)8(7,8)111(1,2,3)112(2,3,4)3(3,4,1)4(4,1,2)5(5,6,8)6(5,7,8)1(6,8,7)1(6,5,7)11161111111111111Рис.
2. b-модель в структурной форме (взвешенный двудольный граф)Рис. 3 иллюстрирует разницу во временной вычислительной сложностипостроения различных моделей структурной сложности орграфов. Используется одно из семейств средних по сложности двусвязных орграфов.11Рис. 3. Сравнение времени, затрачиваемого на построение моделей сложности(треугольники – b-модель BM(tDCF0-3( w) tDCF0-3) в базисе ОЦФ,крестики – b-модель BM(tDP0-3( w) tDP0-3) в базисе путей,квадраты – ISSC(G/DCF0-3), круги – ISSC(G/DP0-3))В третьей главе представлено исследование транзитивных графов и связисимметрии со спектральной сложностью на примере важного и представительного класса графов – связных транзитивных графов степени 4 (ТГС4).
Класс ТГимеет огромное теоретическое и практическое значение. ТГ моделируют структуры гомогенных систем и обладают «оптимальными» характеристиками достижимости и структурной надёжности; являются самыми сложными случаямивходных данных для одних алгоритмов и наиболее простыми для других, частослужат контрпримерами в задачах теории графов, групп, вычислительнойсложности и др. Транзитивными графами являются полноценные вычислительные кластеры, уровни иерархии оптимальной системы управления, модели идеального кристалла, графы перегруппировки при химических реакциях и др.В результате рассмотрения современного уровня исследований на стыкетеории графов и теории групп предложена оригинальная классификация ТГС4,основанная как на характеристиках стабильности симметрии, так и на визуализации диаграмм ТГС4, отражающих симметрию.
Эта работа опирается на опытмногочисленных исследователей проблем, связанных с изоморфизмом/автоморфизмом и транзитивными графами, как наиболее сложными случаями входных данных (L. Babai, M. Luks, B.D. McKay, G.F. Royle, G.Miller, J.Hoprcoft, G. Gati, P. Potočnik, И.А. Фараджев, С.А. Евдокимов, Б.Ю. Вейсфейлер, В.А. Кохов и др.). Исходными данными является полная база ТГС4 до 30вершин включительно и информация о строении ГАГ1.1Кохов В.А., Незнанов А.А. Справочник по теории графов. Характеристики симметрии и сложности связныхтранзитивных графов степени 4 с числом вершин до 30 включительно.
М.: Деп. в ВИНИТИ, №1094-В2004,2004. – 418 с.12Для полноценной классификации ТГ требуется рассмотреть более подробно строение группы автоморфизмов. Фиксатор (стабилизатор) вершины v V– подгруппа Aut(G, v), оставляющая неподвижной вершину v, то естьAut (G, v) {g Aut (G) : g (v) v} . Фиксатор подмножества вершин V0 V –подгруппа Aut(G, V0), оставляющая неподвижной каждую вершину множестваV0, то есть Aut (G,V 0 )Aut (G, v) . Стабилизатор подмножества вершинv V01VV – подгруппа Aut[G, V1], оставляющая множество V1 неподвижным, тоесть Aut[G,V 1 ] {g Aut (G) : v V 1[ g (v) V 1 ]} .Орбита вершины v V относительно фиксатора Aut(G, V 0) – подмножество (Aut(G, V 0), v) вершин графа G, которые могут быть отображены на вершинуvприусловиификсацииподмножестваV 0 V:( Aut (G,V 0 ), v) {v ':[ g Aut (G,V 0 ) : g (v ') v]} .
Орбита вершины v V относительно стабилизатора Aut[G, V 1] – подмножество (Aut[G, V1], v) вершинграфа G, которые могут быть отображены на вершину v при условии стабилизации подмножества V 1 V: ( Aut[G,V 1 ], v) {v ':[ g Aut[G,V 1 ]: g (v ') v]} .В.А. Коховым в 1986 г. введены удобные интегральные характеристикисимметрии. Подмножество вершин VV называется экстремальным подмножеством нетождественной стабильности графа, если справедливо( Aut (G,V ) E p ) & ( v V \ V : Aut (G,V{v}) E p ) . Подмножество вершинVV называется экстремальным подмножеством тождественной стабильностиграфа,еслисправедливо( Aut (G,V ) E p ) & ( v V : Aut (G,V \ {v}) E p ).
Пусть П и П обозначаютсоответственно множество всех подмножеств V и V вершин графа G. Тогдаmax V –min V – число тождественной стабильности графа, аVПVПчисло нетождественной стабильности графа. Числом тождественности t(G)графа G называется минимальное число новых вершин, необходимых для построениятождественногонадграфаOGграфаG,тоестьt (G )min ( VOG VG ) .Aut ( OG ) E pПрорисовка диаграммы графа – получение одного из визуальных образовграфа на плоскости. Мы будем рассматривать симметричные диаграммы ТГС4,то есть диаграммы, хотя бы частично отражающие симметрию вершин графа.Вариантами прорисовки ТГС4 назовём получение диаграмм, существенно отличающихся по расположению вершин и рёбер графа относительно осей симметрии. Наиболее популярными вариантами прорисовок транзитивных графовявляются прорисовки с расположением вершин по нескольким окружностям сцентром в одной и той же точке.
Семейство – последовательность (конечнаяили бесконечная) подобных по некоторым характеристикам графов с возрастающим числом вершин, для которых определена процедура построения следующего представителя последовательности по предыдущему.13Основной результат главы – каталог семейств связных транзитивныхграфов степени 4 (59 бесконечных и 72 конечных).Таблица 2 представляет собой элемент каталога семейств ТГС4 без информации о структурной сложности, а именно – семейство G_21. Для каждогосемейства указываются интегральные характеристики семейства: FV – числовершин в первом графе семейства; UV – число вершин в первом уникальномграфе семейства (когда происходит стабилизация характеристик семейства);FN – число вершин последнего графа в семействе, если оно конечное (в данномпримере отсутствует); SV – шаг числа вершин; |Aut(G)| – число симметрии (порядок группы автоморфизмов);– число тождественной стабильности;–число нетождественной стабильности; n – порядок группы предыдущего представителя семейства.
Видно, что G_21 содержит графы с регулярной группой, укоторых порядок ГАГ равен числу вершин графа. Далее приведены все существенно различные максимально симметричные прорисовки диаграмм этого семейства (в данном случае – 6 вариантов).Таблица 2. Пример информации о семействе ТГС4№ 15. Название: G21FVUVSV|Aut(G1)||Aut(G)|161821018n+2Известные представители: 16-4-2, 18-4-5, 20-4-14, 22-4-6, 24-4-22, 26-4-2, 28-4-17, 30-4-11Диаграммы трёх первых представителей, начиная с уникального:Другие варианты прорисовок диаграмм представителей семейства:3254614Каталог также содержит большой объём дополнительной информации.Так, таблица 3 – пример одной из классификационных таблиц.Таблица 3.
Классификация бесконечных семейств ТГС4по числу нетождественной стабильностиКол-восемейств№1.0192.1113.2194.5.6.7.8.9.410j+1j+2j+4j+8311221Идентификаторы семействG_21, G_22, G_27, G_28, G_29, G_30, G_35, G_36, G_37, G_38, G_74,G_78, G_117, G_214, G_215, G_217, G_220, G_233, G_237G_1, G_2, G_5, G_6, G_7, G_102, G_107, G_108, G_119, G_209, G_231G_11, G_12, G_13, G_14, G_15, G_16, G_17, G_18, G_20, G_33, G_42,G_103, G_125, G_210, G_211, G_219, G_222, G_230, G_239G_26, G_56, G_238,G_10000_4G_10000_1G_1000_2, G_10000_3G_25, G_68G_203Для обеспечения и проверки уникальности представителей семейств средивсех ТГС4 построен лес семейств. Его основное дерево имеет корнем клику на5 вершинах. Каждая развилка в лесе обозначает порождение нового семейства свыделением первого уникального представителя семейства.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
