Содержание к диссертации
Введение
Глава I. Математическая модель структурного разрушения сложной системы 28
1.1. Математическая модель структурного разрушения сложной системы 28
1.2. Характеристики и особенности структурного разрушения сложной системы 31
1.3. Структурное разрушение граф-цепей 33
1.3.1. Структурное разрушение граф-цепей по критерию связности 33
1.3.2. Структурное разрушение граф-цепей по компонентному критерию 34
1.3.3. Структурное разрушение граф-цепей по диаметральному критерию 35
1.3.4. Структурное разрушение граф-цепей по критерию полного разрушения 38
1.4. Структурное разрушение деревьев 39
1.4.1. Структурное разрушение деревьев по критерию связности 39
1.4.2. Структурное разрушение деревьев по компонентному критерию 40
1.4.3. Структурное разрушение деревьев по диаметральному критерию 41
1.4.4. Структурное разрушение деревьев по критерию полного разрушения 43
1.5. Структурное разрушение циклических графов 45
1.5.1. Структурное разрушение циклов по критерию связности 45
1.5.2. Структурное разрушение циклов по компонентному критерию 45
1.5.3. Структурное разрушение циклов по диаметральному критерию 46
1.5.4. Структурное разрушение циклов по критерию полного разрушения 47
1.6. Структурное разрушение полных графов 49
1.7. Структурное разрушение графов по критерию полного разрушения 50
1.8. Выводы 52
Глава II. Структурное разрушение предфрактальных графов (поро/вдение одной затравкой) 53
2.1. Фрактальные и предфрактальные графы 53
2.2. Структурное разрушение предфрактального графа, порожденного полной затравкой, с сохранением смежности старых ребер 58
2.2.1. Разрушение предфрактального графа с эпицентрами в вершинах L -го ранга 59
2.2.2. Разрушение предфрактального графа с эпицентрами в вершинах (L -1) -го ранга 64
2.2.3. Разрушение предфрактального графа с эпицентрами в вершинах /-го ранга, где / = /,-1,...,2 773
2.2.4. Разрушение предфрактального графа с эпицентрами в вершинах первого ранга 81
2.2.5. Разрушение предфрактального графа с эпицентрами в вершинах разных рангов 87
2.3. Выводы 90
Глава III. Структурное разрушение предфрактальных графов (порождение множеством затравок) 91
3.1. Разрушение предфрактального графа с эпицентрами в вершинах L -го ранга 91
3.2. Разрушение предфрактального графа с эпицентрами в вершинах (L -1) -го ранга 95
3.3. Разрушение предфрактального графа с эпицентрами в вершинах /-го ранга 100
3.4. Разрушение предфрактального графа с эпицентрами в вершинах первого ранга 106
3.5. Разрушение предфрактального графа с эпицентрами в вершинах разных рангов 109
3.6. Выводы 111
Литература 113
- Характеристики и особенности структурного разрушения сложной системы
- Структурное разрушение циклических графов
- Структурное разрушение предфрактального графа, порожденного полной затравкой, с сохранением смежности старых ребер
- Разрушение предфрактального графа с эпицентрами в вершинах /-го ранга
Введение к работе
Сетевые системы и структурное моделирование
Эффективность функционирования большинства отраслей экономики государства зависит от пространственной распределенности и разветвленно-сти ее коммуникационных сетей (электроэнергетических, информационных, водо- и теплоснабжающих и т.п.). Чем шире зона покрытия коммуникационных сетей, тем выше конкурентоспособность соответствующей отрасли экономики как на внутреннем рынке государства, так и за его пределами.
Сети с большой зоной покрытия требуют больших затрат на обеспечение штатного функционирования с одной стороны, а другой такие коммуникационные сети имеют сложную многоэлементную структуру с нетривиальным набором связей, что существенно повышает риск возникновения чрезвычайных и внештатных ситуаций. Кроме того, сбои в функционировании коммуникационных сетей имеют значительные последствия, выходящие за пределы коммуникационных сетей.
Аварий в электроэнергетических системах крупных городов России (Москва, 2005 г.), Европы (Лондон, 2003 и 2006 гг.; Париж, 2006 г.), США и Канады (Детройт, Нью-Йорк, Кливленд, Оттава, Торонто, 2003 г.), показали, что развитие чрезвычайных ситуаций в коммуникационных системах с сетевой структурой проходит по "принципу домино" (в случае электроэнергетических систем - это веерные отключения). Один вышедший из строя объект (элемент системы) сильно повышает вероятность аварии на остальных, что приводит к возникновению лавины аварий. О последствиях таких аварий красноречиво свидетельствует следующий факт.
14 августа 2003 года в ряде крупнейших городов восточного побережья США и Канады - Детройте, Ныо-Иорке, Кливленде, Оттаве, Торонто и др. -произошло 9-секундное отключение электроснабжения, приведшее к веерным отключениям электроэнергии на площади более 24 тыс. кв. км и получившее название "Блэкаут-2003". Причина-перегрузка на энергетическом
каскаде Ниагара-Мохок (граница США и Канады). Авария затронула более 50 млн. человек в восьми штатах США и провинции Онтарио Канады, привела к остановке более 100 электростанций, в том числе 22 атомных реакторов. Ликвидация последствий аварии заняла более 30 часов. Сумма нанесенного США финансового ущерба составляет не менее 6 млрд. долларов.
Нередки чрезвычайные ситуации в России в сетях тепло-, водо- и газопроводного транспорта. Во многих случаях причиной аварий является изношенность самих сетей и узлового оборудования. Предотвращение, прогнозирование и профилактика чрезвычайных ситуаций с далеко идущими последствиями в сетевых системах со сложной структурой требует новых исследовательских подходов в моделировании [1 - 8] с учетом всех структурных особенностей моделируемой системы.
Структурная динамика и структурное управление
Современные исследования сложных систем, таких как информационные, электроэнергетические, WWW (Internet), коммуникационные, показывают, что структуры этих систем по истечении времени претерпевают определенные изменения, вызываемые различными внешними обстоятельствами, внутренней потребностью самой системы (см. [9-13]). Структуру системы произвольной природы (социальной, социально-экономической, технической, химико-биологической и т.п.) можно представить в виде графа. Граф (см. [14-40]) - это абстрактный объект, как правило, вершины графа соответствуют элементам системы, а ребра - связям между элементами этой системы. Изменения, происходящие в структуре сложной системы, могут быть описаны простейшими теоретико-графовыми операциями: стягивание ребра, удаление (добавление) ребра, удаление (добавление) вершины. Изменения структуры системы могут быть разовыми, а могут быть постоянными. Для второго случая разумно ввести понятие структурной динамики - изменение структуры системы с течением времени. Несомненно, для описания структурной динамики лучше всего подходит аппарат теории графов.
Одним из наиболее распространенных сценариев структурной динамики является рост структуры. Рост структуры - это регулярное появление новых элементов и связей в структуре системы. Рост структуры может происходить по строго сформулированным правилам, не исключая наличие в них фактора случайности.
Вместе с тем, в системах с быстроизменяющимися структурами целесообразно ввести контроль появляющихся связей между "старыми" и "новыми" элементами системы. При этом важно не допускать появления в системе особо уязвимых для внешних воздействий (угроз) и внутренних ошибок связей между элементами системы. Решение этих задач требует особых подходов структурного управления.
Одним из формальных представлений систем с динамически изменяющейся структурой являются масштабно-инвариантные или самоподобные графы (self-similar graphs) большой размерности, называемые фрактальными (предфрактльные).
Фрактальный граф - сложный абстрактный объект, совмещающий в себе свойства, характеристики и достоинства фракталов и "обычных" графов.
Понятие фрактал, введенное Бенуа Мандельбротом [41], объединило объекты, обладающие особым свойством, - свойством самоподобия (self-similarity) или масштабной инвариантности. Работы, связанные с исследованием фрактальных объектов (фрактальных множеств), долгое время считались занимательными, но не имеющими значительных приложений. Мнения в мировой научной среде изменились с изданием книги [41]. В настоящее время о перспективности и значимости исследований, связанных с фрактальными множествами, можно судить по регулярно проводимым конференциям, периодическим изданиям (см., например, журнал "Chaos, Solitons & Fractals"), целиком посвященным соответствующей тематике, и множеству книг (учебников и монографий) [41 -47]. Это позволяет говорить о сформировавшемся круге прикладных физических модельных задач на основе фрак-
тальных множеств [48-60]. Среди них выделяются задачи и модели, где фрактальные множества представлены как самоподобные (фрактальные или масштабно-инвариантные) графы большой размерности, т.е. с большим количеством вершин. К ним относятся, например, задачи о броуновском движении (случайном блуждании), диффузии и просачиваемости. Кроме того, самоподобные графы нередко выступают в качестве моделей структур сложных многоэлементных систем, таких как коммуникационные сети. Первое упоминание о фрактальных графах можно найти в работе [48].
Активное изучение фрактальных графов и областей их приложения ведется в научной школе профессора Кочкарова A.M. Исследования ведутся по трем направлениям: распознавание фрактальных графов [61, 62], свойства и характеристики фрактальных графов [63 - 78], задачи многокритериальной оптимизации в системах с масштабно-инвариантной структурой [79-106]. Надо отметить, что масштабная инвариантность структур моделируемых систем является следствием структурной динамики в этих системах.
Надежность, живучесть, стойкость
С точки зрения концепции безопасности [107], всякую сложную техническую систему следует изучать с трех основных позиций: надежности системы, живучести системы и ее безопасности. Каждая из этих позиций по-разному описывает связь и взаимодействие системы с окружающей ее средой. Исследование перечисленных свойств системы позволяет уменьшить риск возникновения чрезвычайных ситуаций (ЧС), возникающих в результате бедствий, аварий и катастроф.
С позиции классических моделей теории надежности система изучается изолированно от окружающей среды: ни система не подвергается воздействиям внешней среды, ни сама окружающая среда не испытывает на себе воздействий со стороны системы.
Надежность [108-114] - свойство системы сохранять в течение определенного промежутка времени значение параметров, характеризующих
функционирование системы. Надежность - это комплексное свойство системы, зависящее от ее безотказности, ремонтопригодности, долговечности и т.д.
Теория надежности использует аппарат теории вероятностей и математической статистики. Как правило, для оценки возможности возникновения опасного для окружающей среды состояния системы используется дерево событий (отказов). Дерево событий {отказов) - это диаграммное представление всех событий (отказов), последовательное и(или) совместное появление которых в системе приводит к некоторому главному событию (возможно, потенциально опасному происшествию). Зная вероятности появления тех или иных событий (отказов), можно подсчитать возможность возникновения главного события (опасного происшествия). В зависимости от задачи и традиций той или иной области, главным событием называют либо отказ системы (выход из строя), либо адекватную реакцию на воздействие.
В сложных многоэлементных системах к потенциально опасному происшествию могут привести последовательные и(или) совместные отказы различных элементов системы. Поэтому для повышения надежности элементов (вероятности безотказной работы) системы и, как следствие, надежности самой системы, используются различные методы резервирования [108 - 114].
Для коммуникационной сети (как и для других сложных систем, представляемых в виде графов) численный расчет ее надежности может оказаться задачей, требующей значительных временных ресурсов. По сути, построение дерева отказов для коммуникационной сети сводится к простому перебору всех возможных вариантов недостижения информационного сигнала от одной вершины до другой.
Живучесть - свойство системы, характеризующее ее способность функционировать под влиянием внешних воздействий (нагрузок), возбуждаемых в окружающей систему среде.
Изучение живучести систем возможно с помощью вероятностных моделей, в рамках современной математической теории надежности [108 - 114], и детерминистических, в рамках механики катастроф [107].
Вероятностную модель, описывающую живучесть системы, называют "нагрузка- прочность" ("нагрузка- несущая способность", "нагрузка- сопротивляемость", прочностная модель) [107]. Под действием внешней нагрузки прочность системы постепенно уменьшается до тех пор, пока система не выйдет из строя. Внешние нагрузки описываются случайной величиной (функцией) и, как правило, не приводят к скачкообразному изменению прочности системы.
Детерминистическая модель живучести системы лежит в основе механики катастроф [107]. Объектами исследований механики катастроф являются системы, испытывающие постоянные внешние воздействия (нагрузки). Простыми примерами таких систем являются инженерные конструкции. В рамках механики катастроф исследуются процессы накопления повреждений, достижения предельного (критического) состояния, реакции элементов конструкций на внешние воздействия и т.д.
Особое место в механике катастроф занимает изучение процесса закри-тического поведения элементов конструкций (систем), которое и приводит к тем или иным нежелательным событиям (авариям, катастрофам и т.д.). Элементы конструкций (систем) в своей закритической области выходят из строя, оказывают влияние на другие элементы системы, порождая тем самым внутренние для самой конструкции (системы) негативные воздействия. Внешние и внутренние воздействия приводят к последовательности отказов элементов системы, инициирующих переход системы в аварийное состояние (ЧС).
Понятие живучести широко используется и при исследовании систем со сложной структурой, таких как коммуникационные сети систем управления и систем энергетики [115]. Нарушение функционирования этих систем возможно при нарушении связности их структур. Система не может выпол-
нять свои функции, когда не существует взаимодействия между всеми или, по крайней мере, жизненно важными элементами. '''Мерой живучести" в этом случае служит минимальное число элементов системы {вершинная связность) или связей {реберная связность), выход из строя которых под влиянием внешних воздействий приводит к нарушению связности структуры системы. Внешние воздействия делят на воздействия природного [107] и техногенного [107] характера. Ко вторым относятся и воздействия, вызываемые умышленными действиями человека. Во многих случаях, при создании сложных технических систем, приходится принимать во внимание и возможность террористических актов. В зависимости от интенсивности и мощности оказываемых на систему воздействий рассматриваются нормативные (проектные) и экстремальные (сверхнормативные) нагрузки. В первом случае изучается живучесть системы в штатных (нормальных) условиях функционирования, когда переход в аварийное состояние возможен при длительном накоплении системой повреждений и достижения предельного (критического) состояния. (Подобное поведение систем описывается и методами самоорганизованной критичности [116, 117].) Во втором случае изучается живучесть системы, когда возможен относительно быстрый переход в аварийное состояние - форс-мажорные обстоятельства.
Механика катастроф занимается не столько изучением воздействий различного рода, сколько созданием аппарата перехода от воздействий к расчетным действующим нагрузкам.
Живучесть и надежность систем являются теми характеристиками, которые позволяют оценить риск возникновения чрезвычайных ситуаций при
Инициирование
ЧС (1этап)
предельное состояние
Выход ЧС за пределы системы (Шэтап)
Рис. 1. Схема развития чрезвычайных ситуаций
эксплуатации сложных технических систем. Используя эти критерии, возможно обеспечение безопасности систем при чрезвычайных ситуациях или наделение системы необходимыми качественными характеристиками, не допускающими возникновения чрезвычайных ситуаций. В схеме на рис. 1 надежность и живучесть описывают переход от первого этапа ко второму. Живучесть системы предполагает тщательное описание поведения систем (в отличие от надежности) при имеющихся внешних воздействиях на систему как в докритической области (до ЧС), так и в закритической (при развитии ЧС), когда система функционирует, достигнув предельного состояния. Третий этап предполагает изучение возможных последствий ЧС на окружающую систему среду и лежит в области обеспечения безопасности систем [107].
Безопасность системы можно обеспечить различными способами: не допустить развитие ЧС в системе, не допустить выхода ЧС за пределы системы, и свести к возможному минимуму влияние аварий на окружающую систему среду.
В рамках концепции моделей, предлагаемых в работах [118 - 132], исследованы сложные технические системы, подвергнутые внешним воздействиям. Это соответствует попаданию системы в зону "форс-мажорных обстоятельств", т.е. под влияние ненормативных, непредусмотренных при проектировании системы, экстремальных нагрузок, имеющих также внезапный характер. В основе моделей лежит формально представленная структура системы, что позволяет детально воспроизвести все возможные варианты распространения внешних воздействий по элементам системы. Модели, при заданных нагрузках на некоторое множество элементов системы, вызываемых различными внешними воздействиями, определяют темп и сроки достижения системой предельного состояния.
Стойкостью [118-132] системы называют ее способность противостоять внешним воздействиям и функционировать в штатном режиме на этапе инициирования ЧС, т.е. в докритической области функционирования системы. Другими словами, стойкость - это живучесть системы в докритиче-
ской области функционирования под влиянием внешних ненормативных воздействий (нагрузок). Поэтому основной характеристикой стойкости системы будет служить время достижения системой предельного состояния. Увеличение этого промежутка времени будет способствовать уменьшению риска развития ЧС в системе и обеспечению ее безопасности.
В настоящей работе предлагается модель структурного разрушения сложной системы, описывающая поведение и изменение состояния многоэлементной системы со сложной структурой на II этапе развития ЧС согласно схеме, представленной на рис 1.
Краткое содержание и структура диссертационной работы
Диссертационная работа посвящена моделированию структурного разрушения сложных систем. Рассмотрены различные сценарии структурного разрушения и достижения критериев выхода системы из строя.
Публикации. По результатам выполненной работы имеется 14 публикаций.
Структура диссертации. Диссертация состоит из введения и трех глав, изложенных на 126 страницах, содержит 23 рисунка и библиографию из 141 наименования.
Во введении обоснована актуальность темы диссертационной работы. Проведен анализ существующих моделей по направлениям, близким к теме диссертации. Определена область приложений исследования, проведенного в диссертации.
Дается краткое изложение содержания диссертации. В первой главе предложена математическая модель структурного разрушения сложной системы и исследован процесс структурного разрушения на обыкновенных графах.
Обозначим через G = (V, Е) - граф, соответствующий структуре исследуемой системы, V - множество вершин, Е - множество ребер графа G.
Каждой вершине veV припишем веса w(v) и w(v), отражающие текущую загрузку и предельную загрузку элемента системы. В случае, когда текущая загрузка w(v) элемента системы достигает предельного значения w(v), то элементы системы выходят из строя, а проходящие через него потоки перераспределяются по "соседним" элементам системы. Выход из строя элемента системы в теоретико-графовой терминологии соответствует удалению из графа системы вершины с инцидентными ей ребрами. А перераспределение
весов в тривиальном случае соответствует равному разделению веса w(v)
удаленной вершины по вершинам, смежным с удаляемой.
Структурное разрушение, вообще говоря, процесс динамический. Не нарушая общности, будем считать, что wt(v) - текущая загрузка вершины
veV в момент времени / = 0,1,2,3,...,7^,..,. Если через Vt ={vj}qV, j = 1,2,3,..., Vt , обозначить множество вершин, вышедших из строя в момент времени t, т.е. те, у которых wt(Vj)>w(Vj), а через (vj) = {v/} - окружение вериШНЫ Vj (ИЛИ МНОЖеСТВО ВерШИН СМеЖНЫХ С верШИНОЙ Vy),
(vj) =degvj, ij =1,2,3,..., (vj), то процесс структурного разрушения формально будет выглядеть следующим образом.
В момент времени t = 0 необходимо произвести проверку по всем вершинам veV и сформировать множество Vx из вершин, для которых справедливо w0(v)> w(v). Во все последующие моменты времени / = 1,2,3,...,Г,... следует воспользоваться правилом
^1(^.) = ^^) + ^.-^.), ij = l,2,3,...,|
Если w/+1 (v/) > w(v/), то вершина v/ удаляется из графа G и
P/+1+V;
15 Коэффициент Є: - параметр распределения загрузки. Параметр распределения загрузки может зависеть от различных факторов, в простейшем случае он равномерно распределяет предельную загрузку удаляемой верши-
1
ны по соседним, т.е. для каждой вершины Vy вычисляется как є.- = .
degvj
Структурное разрушение при параметре распределения загрузки є . =
degvj
будем назвать равномерным.
Процесс структурного разрушения следует продолжать до тех пор, пока система не перейдет в критическое состояние 3, т.е., когда перестанет выполнять возложенные на нее функции.
Критическое состояние 3 определяется, исходя из особенностей моделируемой системы. Например, система может считаться пребывающей в критическом состоянии, если из ее структуры удален хотя бы один элемент (вершина), или система может считаться функционирующей, если ее структура после удаления элементов все еще остается связной. В настоящей работе будут рассмотрены различные критерии отказа системы (перехода в состояние отказа системы) или, иначе, критерии разрушения.
Основной задачей моделирования структурного разрушения системы является выяснение, условий, при которых система может перейти в критическое состояние. Начальные причины повреждения системы могут быть как внутренние, так и внешние. Переход системы в критическое состояние означает, что в ней начался процесс структурного разрушения, но это не значит, что она окончательно прекратила функционировать. Систему можно считать вышедшей из строя только в том случае, когда изменения, произошедшие в ее структуре, будут удовлетворять критериям отказа. Поэтому одной из основных характеристик в модели структурного разрушения будет служить время Тсг структурного разрушения, отражающее длительность самого процесса структурного разрушения.
Нельзя утверждать, что система, перейдя в критическое состояние, когда из ее структуры удаляются элементы (начало процесса структурного разрушение), непременно впоследствии выйдет из строя (перейдет и в состояние отказа системы). Время Тсг структурного разрушения системы соответствует
продолжительности процесса структурного разрушения от момента первого удаления (выхода из строя) элемента системы до момента остановки процесса разрушения или отказа самой системы.
Для исследования процесса структурного разрушения систем с "простой" структурой целесообразно использовать следующие критерии отказа.
1) критерий полного разрушения ст0(к). Система считается вышедшей
из строя, если в системе выйдут из строя все элементы (будут удалены все вершины графа - структуры системы). Критерий полного разрушения <т${к)
зависит от одного параметра: к - числа удаленных вершин в начальный момент времени структурного разрушения;
2) критерий связности ах (k). Система считается вышедшей из строя,
если нарушена связность ее структуры при удалении вершин. Критерий связ
ности crj (к) зависит от одного параметра: к - числа удаленных вершин в на
чальный момент времени структурного разрушения;
3) компонентный критерий cr2(k,m). Система считается вышедшей из
строя, если число компонент в структуре системы при ее разрушении окажется не меньше заданного числа т. Компонентный критерий а2(к,т) выхода системы из строя зависит от двух параметров: от к - числа удаленных вершин в начальный момент времени структурного разрушения, и т - максимально допустимого числа компонент структуры при ее разрушении;
4) диаметральный критерий
строя, если диаметр хотя бы одной из компонент структуры системы в про
цессе разрушения окажется меньше заданного числа D. Диаметральный кри
терий a3(k,D) выхода системы из строя зависит от двух параметров: от А: -
числа удаленных вершин в начальный момент времени структурного разру-
шения, и D - минимально допустимого диаметра компонент структуры при ее разрушении.
По мере необходимости в дальнейшем будут вводиться и другие критерии отказа систем.
Множество 0(G) элементов, вышедших из строя (удаленные из структуры) в момент времени t = 1, будем называть эпицентрами структурного разрушения. В критериях о~0(к), <Ух{к), a2(k,m),a3(k,D), число к соответствует количеству эпицентров структурного разрушения системы.
Для систем со структурами, представляемыми в виде обыкновенных графов, проведено исследование структурного разрушения с равными значениями начальных загрузок w0(v) и равными значениями предельных загрузок w(y) для всех вершин графов.
В формулировках следующих лемм и теорем констатируется связь между различными классами структур (цепей, деревьев, циклов, регулярных графов), временем структурного разрушения системы и множеством эпицентров структурного разрушения. Связи установлены по каждому из предложенных критериев структурного разрушения.
Лемма 1.1. Всякий граф-цепь С = (VC,EC), \VC\ = п, будет разрушен по критерию о"і(Аг), где \<к<п-\, при удалении хотя бы одной невисячей вершины.
Лемма 1.2. Всякий граф-цепь С = (VC,EC), \Vc\ = n, п>3, будет разрушен по критерию о~2(к,т), где 2<т<(п + 1)/2 при нечетном п и 2<т<п/2 при четном п, если количество попарно несмежных внутренних вершин-эпицентров равно к = т-\.
Теорема 1.3. Всякий граф-цепь С = (VC,EC), \Vc\-n, п>3 будет разрушен по критерию сг3(1,г(С)) при удалении центральной вершины (т.е., когда эпицентром является центральная вершина). Причем, диа-
метры появившихся в результате структурного разрушения компонент будут равны г{С) -1 и d{C) - г(С) -1.
ТЕОРЕМА 1.7. Всякий граф-цепь С = (VC,EC), \Vc\ = n> п>3 будет разрушен по критерию <т0(1) при удалении одной из внутренних вершин veVc за время Tcr =(v) + l, где s(v) -эксцентриситет вершины veVc, если w(v) - w0 (у) < w(y) 12.
ТЕОРЕМА 1.8. Всякое дерево T = (VT,ET), \VT\ = n, будет разрушено по критерию cr^k), где \<к<пТ, пт - количество висячих вершин, при удалении хотя бы одной внутренней вершины за время Тсг=\.
Теорема 1.10. Всякое дерево T = (VT,ET), \VT\ = n, будет разрушено
по критерию о~2(к,т) при удалении к попарно несмежных внутренних
к вершин Vj є VT за время Тсг=\, причем m = X(^eg(v/)-1) + 1-
/=i
Теорема 1.11. Всякое дерево T-(VT,ET) будет разрушено по критерию о~3(к,2(є(у)-г(Т)-1) + 1) при удалении всех к вершин v^Vj, і = \,к, с эксцентриситетами s(v), т.е., когда эпицентрами являются все вершины с эксцентриситетом s(v),3a время Tcr = 1.
Теорема 1.12. Всякое дерево T = (VT,ET) будет разрушено по критерию сг0(1) при удалении вершины veVT с максимальной степенью А(Т) за время Tcr = s{v), если w(v)- w0(v) < w(v)l Д(Г), где Д(Г) = deg(v).
Теорема 1.14. Всякий цикл P = (VP,EP), tyP\ = n, п>А, будет разрушен по критерию <т3 (2, р(у', v") - 2) при удалении двух несмежных вершин V,v" є VP, т.е., когда эпицентрами являются эти несмежные вершины.
19 Лемма і .15. Всякий цикл P = (VP,EP), \VP\ = n, п> 4, будет разрушен по критерию <т0(1) при удалении одной из вершин veVP за время Тсг = (и+ 1)/2 при нечетном п и за время Тсг=п/2 + 1 при четном п, если w(y) - w0 (v) < w(y) 12.
ЛЕММА 1.16. Всякий полный граф Кп =(VK,EK) будет разрушен по критерию <т0(1) при удалении вершины veVK за время Тсг=2, если w(v) - Wq (v) < w(v)l(n -1).
ТЕОРЕМА 1.17. Всякий граф G = (V,E) будет разрушен по критерию (J0(l) при удалении вершины veV с максимальной степенью A(G) за время Tcr = e(v), если w(v)-w0(v) < w(v)/A(G), где A(G) = deg(v).
Во второй и в третьей главах исследовано структурное разрушение систем со структурой, представляемой в виде масштабно-инвариантных графов большой размерности - предфрактальных графов.
В основе определения фрактальных графов лежит операция замены вершины затравкой. Термином затравка (ЗВЗ) условимся называть какой-либо связный граф H = (W,Q). Суть операции (ЗВЗ) заключается в следующем. В данном графе G = (V,E) у намеченной для замещения вершины її є v выделяется множество V = {vj} с V, j = 1,2,..., V смежных ей вершин. Далее из графа G удаляется вершина v и все инцидентные ей ребра. Затем каждая вершина Vj є V, j = 1,2,..., V соединяется ребром с одной из вершин затравки Н. Вершины соединяются произвольно (случайным образом) или по определенному правилу при необходимости.
Предфрактальный граф будем обозначать через GL ={VL,EL), где VL
- множество вершин графа, a EL -~ множество его ребер. Определим его ре-
куррентно, поэтапно заменяя каждый раз в построенном на предыдущем этапе / = 1,2,...,/,-1 графе G[ =(Г/,/) каждую его вершину затравкой Я. На
20 этапе / = 1 предфрактальному графу соответствует затравка Gx = Н. Об описанном процессе говорят, что предфрактальный граф GL порожден затравкой Н. Процесс порождения предфрактального графа GL, по существу, есть процесс построения последовательности предфрактальных графов G\, G2,..., Gj,..., GL, называемой траекторией. Фрактальный граф G = (V, Е), порожденный затравкой Н, определяется бесконечной траекторией.
Для предфрактального графа GL ребра, появившиеся на 1-ом,
/є{1,2,...,1), этапе порождения, будем называть ребрами ранга 1. Новыми ребрами предфрактального графа GL назовем ребра ранга L, а все остальные ребра назовем старыми.
При удалении из предфрактального графа GL всех ребер рангов
/ = 1,2,..., L- г получим множество [В^]}, г є {1,2,..., L -1}, блоков г -го ранга, где i = \,2,...,nL~r - порядковый номер блока. Термином подграф-
затравка z)l будем называть блок B\'s, s = l,n 1 первого ранга предфрактального графа Gj, l = \,L из траектории. Мощность множества
Z(GL) = {z^P}, l = \,L, s = 1, n ~x всех подграф-затравок из траектории графа
GL равна \Z(GL)\ = -.
п-\
Предфрактальный граф GL={VL,EL) условимся называть (n,q,L)-графом, если он порожден п -вершинной q -реберной связной затравкой H = {W,Q).
Будем говорить, что предфрактальный граф GL ={VL,EL) -вершинно взвешен, если каждой его вершине vw є VL приписано действительное число
н>(у(/))є(#ма,#/_16),где / = 1,1 -ранг вершины, я>0,и в < —.
Рассмотрим вершинно взвешенный предфрактальный граф GL ={VL,EL), порожденный полной затравкой Н = (W,Q), ^V\-n, \Q\ = q с
сохранением смежности старых ребер. Не нарушая правила взвешивания предфрактального графа, определим веса вершин следующим образом. Каждой вершине приписывается два числа, отражающие соответственно ее текущий и предельный вес. Предельный вес вершины v^ є VL определяется как w{v^) = 6lAb, а ее текущий вес - w(v^) = 0IAa, где l = l,L, а>0 и
9<а-. Ь
Рангом вершины предфрактального графа GL будем называть наименьший ранг / среди всех инцидентных ей ребер. Вершину / -го ранга обозначим как v^, где /є{1,2,...,Ц. Вершину /-го ранга v^ ,являющуюся эпицентром, назовем эпицентром 1-го ранга, где / = 1,2,...,/,.
Ранговый критерий
если разрушенными оказались все вершины /-го ранга, l = \,L. Ранговый критерий <т4 (к, I) выхода системы из строя зависит от двух параметров, где
к - число удаленных вершин в начальный момент времени структурного разрушения.
Потерей веса будем называть ситуацию, когда, в результате удаления вершины, ее предельный вес не может быть полностью перераспределен среди вершин окружения.
Во второй главе рассмотрен случай структурного разрушения систем со структурой, представимой в виде предфрактального, порожденного одной затравкой. Процесс структурного разрушения исследован при различных порождениях предфрактального графа различными классами затравок, при различных вариантах смежности старых ребер предфрактального графа.
На число вершин затравки и веса рассматриваемого предфрактального графа наложим следующие ограничения:
в-Ь
то есть разрушение любого количества вершин L-ro ранга предфрак-тального графа не влечет за собой разрушение вершин (L - 1)-го ранга;
в-Ъ
п< , (2.7)
(в-\)Ъ + а V ;
то есть разрушение любого количества вершин (1-І)-го ранга пред-фрактального графа не влечет за собой разрушение вершин (L - 2) -го ранга;
а<Ь(1~), (2.9)
текущие веса вершин L-ro ранга не превышают предельные, и процесс разрушения предфрактального графа останавливается.
Следующие теоремы устанавливают связь между временем структурного разрушения системы, представляемой в виде предфрактального графа, порожденного одной затравкой, и множеством эпицентров структурного разрушения. Связи установлены по основным из предложенных критериев структурного разрушения.
Теорема 2.3. Всякий предфрактальный граф GL, порожденный полной затравкой с сохранением смежности старых ребер и с эпицентрами L -го ранга, может быть разрушен по критерию a3(k,D) при выполнении условия (2.5) только для D = 2L-2 и D = 2L-3, где соответственно k = nLA -{n-\)-\uk = nLA .(w-l)-2.
Теорема 2.4. Всякий предфрактальный граф GL, порожденный полной затравкой с сохранением смежности старых ребер и с эпицентрами (L-T)-го ранга будет разрушен по критерию o~i(k) при выполнении условий (2.7) и (2.9), где\<к<п1~2-(п-\).
Теорема 2.6. Всякий предфрактальный граф GL, порожденный полной затравкой с сохранением смежности старых ребер и с эпш{ентрами (L-1)-го ранга, при выполнении условий (2.7) и (2.9) будет разрушен по критерию а2(к,т) для всех m
ТЕОРЕМА 2.7. Всякий предфрактальный граф GL, порожденный полной затравкой с сохранением смежности старых ребер, будет разрушен по критерию o~2(k,D) при удалении хотя бы одной вершины (L-ї) -го ранга для всех 1 < D < 2L -1, при выполнении условий (2.7) и (2.9).
ТЕОРЕМА 2.14. Всякий предфрактальный граф GL, порожденный полной затравкой с сохранением смеэюности старых ребер и с эпицентрами 1-го ранга, будет разрушен по критерию o~4(r,t), где г - число всех вершин 1-го
ранга, при выполнении неравенства в ~ Ъ 1{{п-\)-2)>в ~ Ь- в ~ а для всех t = l,l + l,...,L.
ТЕОРЕМА 2.15. Всякий предфрактальный граф GL, порожденный полной затравкой с сохранением смежности старых ребер и с эпицентрами 1-го
Ї— 1 / —0 1—О
ранга, при выполнении неравенства в Ъ-{п-\)>в Ь-9 а будет разрушен по критерию o~4(r,t), где г - число всех вершин 1-го ранга, пошагово для всех ? = /,/-1,...,1.
Третья глава посвящена исследованию процесса структурного разрушения систем со структурой, представимой в виде предфрактального графа, порожденного множеством затравок.
Обобщением описанного процесса порождения предфрактального графа GL является такой случай, когда вместо единственной затравки Н используется множество затравок И = {Н(}={Н1,Н2,...,Н(,...,НТ}, Т>2. Суть этого обобщения состоит в том, что при переходе от графа GM к графу G/ каждая вершина замещается некоторой затравкой Ht є Н, которая выбирается случайно или согласно определенному правилу, отражающему специфику моделируемого процесса или структуры. Для мощностей множеств вершин затравок Ht є Н будем использовать следующие обозначения -
nmax = max Пі,птіп= mm Пі.
ієТ іеТ
Следующие теоремы устанавливают связь между временем структурного разрушения системы, представляемой в виде предфрактального графа,
порожденного множеством затравок, и множеством различных эпицентров структурного разрушения.
ТЕОРЕМА 3.3. Всякий предфрактальный граф GL, порожденный мно
жеством полных затравок с сохранением смежности старых ребер и с эпи
центрами L-го ранга, может быть разрушен по критерию <х3 (&,/)) при вы
полнении условия птах < +1, только для D = 2L-2 и D = 2L-3, где со-
в-Ъ
ответственно k = \VL | - Yl-\ \ ~ 1 и к = \^l \ ~ |^i-i | ~ 2
ТЕОРЕМА 3.4. Всякий предфрактальный граф GL, порожденный мно-
жеством полных затравок с сохранением смежности старых ребер и с эпицентрами (Ь-\)-го ранга, будет разрушен по критерию о~х(к) при
в-Ь
выполнении условий птах < и Ь/(2пт[п-2)<вЬ-2ва, где
{в -\)Ь + а
ТЕОРЕМА 3.6. Всякий предфрактальный граф GL, порожденный множеством полных затравок с сохранением смежности старых ребер и с
эпицентрами (L-1)-го ранга, при выполнении условии итах < и
(0-Y)b + a
Ь/(2пт-т-2)<вЬ-2ва будет разрушен по критерию а2(к,т) для всех
m
На число вершин затравки и веса рассматриваемого предфрактального графа наложим следующие ограничения:
в1-]Ь-(птах-\) <в1-2ь_в1-2а^ (3<3)
(/2min -1).(1-/) + 1
в'~1Ь/((птіп -\)-{L-U\))
bl{{nm^-\)-(L-\))>eb-6a. (3.8)
Теорема ЗЛО. Всякий предфрактальный граф GL> порожденный мноэ/сеством полных затравок с сохранением смежности старых ребер и с
эпицентрами I-го ранга, при выполнении условий (3.3) и (3.6) будет разрушен по критерию сг2(к,т) для всех m<(L-l)k + l, где \
luk^V^-f^, / = 1-1,1-2,...,1.
ТЕОРЕМА 3.11. Всякий предфрактальный граф GL, порожденный множеством полных затравок с сохранением смежности старых ребер будет разрушен по критерию о~2 (k,D) при удалении хотя бы одной вершины I-
го ранга для любого D>2, где \ < k ^V^-fr^] / = /,-1,/,-2,...,1 при выполнении условий (3.3) и (3.6).
Теорема 3.13. Всякий предфрактальный граф GL, порожденный
множеством полных затравок с сохранением смежности старых ребер и с эпицентрами 1-го ранга, будет разрушен по критерию cr4(r,t), где г - число всех вершин 1-го ранга, при выполнении неравенства в1~2Ь/((пшх -1) 2) > в1АЪ - 6L~xa пошагово для всех t = l,l +1,...,/,.
ТЕОРЕМА 3.14. Всякий предфрактальный граф GL, порожденный множеством полных затравок с сохранением смежности старых ребер и с эпицентрами 1-го ранга, при выполнении неравенства
вЬ (пт-т -1) ^ , . . / ч n
— >Ь-а будет разрушен по критерию
(«max -1)-(^-2) + 1
число всех вершин 1-го ранга, пошагово для всех t = /,/-1,...,1.
Теорема 3.18. Всякий предфрактальный граф GL, порожденный множеством полных затравок с сохранением смежности старых ребер и с эпицентрами первого ранга, будет разрушен по критерию а4 (г,2) при выполнении условия (3.8) на втором шаге, где г - число всех вершин первого ранга.
Апробация работы. Основные результаты работы были доложены на 14-ой международной конференции "Проблемы управления безопасностью сложных систем" (Москва, 2006), на 6-ой международной конференции "Когнитивный анализ и управление развитием ситуаций" (Москва, 2006), на
2-ой Всероссийской научно-практической конференции "Перспективные системы и задачи управления" (Домбай, 2007), на 5-ой Московской международной конференции по исследованию операций (Москва, 2007), на Международной междисциплинарной научной конференции "Третьи Курдюмов-ские чтения. Идеи синергетики в естественных науках" (Тверь, 2007), на Международной научной конференции "Проблемы регионального и муниципального управления" (Москва, 2007), на 10-ом научно-практическом семинаре "Новые информационные технологии" (Москва, 2007), а также на научных семинарах профессорско-преподавательского состава Карачаево-Черкесской Государственной технологической академии и Карачаево-Черкесского филиала Южного Федерального Университета (Черкесск, 2004-2007).
Основные положения, выносимые на защиту:
1) построена математическая модель структурного разрушения сложной
системы. Введены четыре критерия выхода системы из строя - крите
рий полного разрушения, критерий связности, компонентный критерий
и диаметральный критерий;
исследован процесс структурного разрушения для различных классов обыкновенных графов - цепей, циклов, деревьев и простых произвольных графов. Для каждого класса исследованных графов по каждому из предложенных критериев получены оценки времени структурного разрушения. Установлена связь между временем структурного разрушения с количеством эпицентров и их расположением на графах;
исследован процесс структурного разрушения предфрактального графа. Обоснована представимость структур сложных многоэлементных систем в виде предфрактальных графов. Для исследования структурного разрушения предфрактальных графов введен пятый - ранговый критерий выхода системы из строя. Доказаны утверждения, описывающие связи между временем структурного разрушения системы, представ-
ляемой в виде предфрактального графа, и множеством эпицентров структурного разрушения. Связи установлены по всем пяти введенным критериям структурного разрушения для предфрактальных графов, порожденных одной или множеством затравок при различных условиях сохранения смежности старых ребер.
Характеристики и особенности структурного разрушения сложной системы
Основной задачей моделирования структурного разрушения системы является выяснение условий, при которых система может перейти в критическое состояние. Начальные причины повреждения системы могут быть как внутренние, так и внешние. Переход системы в критическое состояние означает, что в ней начался процесс структурного разрушения, но это не значит, что она окончательно прекратила функционировать. Систему можно считать вышедшей из строя только в том случае, когда изменения, произошедшие в ее структуре, будут удовлетворять критериям отказа. Поэтому одной из основных характеристик в модели структурного разрушения будет служить время Тсг структурного разрушения, отражающее длительность самого процесса структурного разрушения.
Нельзя утверждать, что система, перейдя в критическое состояние, когда из ее структуры удаляются элементы (начало процесса структурного разрушения), непременно впоследствии выйдет из строя (перейдет в состояние отказа системы). Время Тсг структурного разрушения системы соответствует продолжительности этого процесса от момента первого удаления (выхода из строя) элемента системы до момента остановки процесса разрушения или отказа самой системы.
Поскольку построенная модель структурного разрушения системы непосредственно связана с типом ее структуры, важно исследовать системы с различными типами структур, найти связь между типом структуры системы и временем ее структурного разрушения.
Нельзя подменять два представления о сложности систем. Сложность системы может заключаться и в сложности ее динамического поведения (самоорганизация, динамический хаос, бифуркации, случайное поведение и т.п.), и в сложности структуры, т.е. связей между элементами системы. Часто системы совмещают в себе эти оба представления о сложности, хотя не всегда исследователям удается жестко определить понятия сложности системы в поведении и в структуре. Не тривиален этот вопрос и для исследуемого в настоящей работе процесса структурного разрушения системы.
Простыми структурами в контексте настоящей работы следует считать регулярные, периодические, симметричные, автоморфные графы и деревья. Именно с исследования таких структур начнется исследование процесса структурного разрушения систем, но нельзя при этом считать, что сам процесс окажется так же "простым".
Для исследования процесса структурного разрушения систем с "простой" структурой целесообразно использовать следующие критерии отказа: 1) критерий полного разрушения т0 (k). Система считается вышедшей из строя, если в системе выйдут из строя все элементы (будут удалены все вершины графа - структуры системы). Критерий полного разрушения (Т0(к) зависит от одного параметра: к - числа удаленных вершин в начальный момент времени структурного разрушения; 2) критерий связности Т\ (k). Система считается вышедшей из строя, если нарушена связность ее структуры при удалении вершин. Критерий связности (J\{k) зависит от одного параметра: к - числа удаленных вершин в начальный момент времени структурного разрушения; 3) компонентный критерий cr2(k,m). Система считается вышедшей из строя, если число компонент в структуре системы при ее разрушении окажется не меньше заданного числа т. Компонентный критерий а2(к,т) выхода системы из строя зависит от двух параметров: от к -числа удаленных вершин в начальный момент времени структурного разрушения, и т - максимально допустимого числа компонент структуры при ее разрушении; 4) диаметральный критерий т3 (&, ). Система считается вышедшей из строя, если диаметр хотя бы одной из компонент структуры системы в процессе разрушения окажется меньше заданного числа D. Диаметральный критерий т3 (k, D) выхода системы из строя зависит от двух параметров: от к - числа удаленных вершин в начальный момент времени структурного разрушения, и D - минимально допустимого диаметра компонент структуры при ее разрушении. По мере необходимости в дальнейшем будут вводиться и другие критерии отказа систем.
Множество 0(G) элементов, вышедших из строя (удаленные из структуры) в момент времени t = 1, будем называть эпицентрами структурного разрушения. В критериях 70(&), Т\(к), 72(&,ш),сгз (&, ), число к соответствует количеству эпицентров структурного разрушения системы.
Далее в настоящей главе проведено исследование структурного разрушения "простых" графов (цепей, деревьев, циклов, регулярных графов) с равными значениями начальных загрузок wQ(v) и равными значениями предельных загрузок w(v) для всех их вершин.
Структурное разрушение циклических графов
Удаление двух несмежных вершин цикла P = (VP,EP) \VP\ 4 непременно приведет к распадению его на две компоненты Р = {Vp,EP ) и Р" = (УР ,Ер ). "Простейшей" компонентой в таком случае может быть граф-вершина. Всякий цикл P = (Vp,EP), \VP\ = n, п 4, имеет (и-1)/2 попарно несмежных вершин, если п - нечетное, и л/2, если п - четное. Удаление из цикла P = (VP,Ep) всех попарно несмежных вершин приведет к появлению (п -1)/2 компонент в первом случае и п/2 - во втором. При нечетном п все, кроме одной компоненты, будут представлять собой граф-вершину, а при четном п все компоненты окажутся граф-вершинами. ЛЕММА 1.13.6. Всякий цикл P = (VP,EP), \VP\ = n, п 4, будет разрушен по критерию a2(k,k), где 2 k (n-l)/2 при нечетном п и 2 k nl2 при четном п, если вершины-эпицентры попарно несмежны. А ПРИМЕЧАНИЕ 1.3. Для всякого цикла P-(VP,EP), Р/ = л, п 4, структурное разрушение по критерию o 2(k,k) может произойти различными способами. Например, для цикла, изображенного нарис 1.4, критерий разрушения сг2 (3,3) может быть достигнут двумя способами, поскольку для этого графа существует два набора попарно несмежных вершин эпицентров, причем критерий достигается в начальный t = \ момент времени. -4
Для всякого цикла P = (VP,EP), \VP\ = n, справедливо равенство d(P) = r(P), причем d(P) = r{P) = (n-\)l2 при нечетном п, и d(P) = r(P) = n/2 при четном п. Кроме того, каждая вершина цикла P = (VP,EP) является и центральной, и периферийной. ТЕОРЕМА 1.14. Всякий цикл P = (VP,EP), \VP\ = n, п 4, будет разрушен по критерию 73(2,/?(v ,v")-2) при удалении двух несмежных вершин v , v" є VP, т.е., когда эпицентрами являются эти несмежные вершины. ДОКАЗАТЕЛЬСТВО. При удалении из цикла P = (VP,EP), \VP\ = n, п 4, двух несмежных вершин v , v" є VP, цикл распадется на две цепи С и С таким образом, что длина наименьшей из них (допустим цепи С") равна p(v ,v")-2. Диаметр этой цепи равен d(C ) = p(v ,v")-2, цикл будет разрушен по критерию 73(2,/)(v ,v") -2) за время Тсг -1 А Для цикла на рис. 1.4 при эпицентрах v, и v2 диаметральный критерий представляет собой сг3 (2,1). Если в случае взять во внимание длину некратчайшей цепи С" из доказательства теоремы 1.14, а ее длина равна n-p(v ,v")-2, то справедливо СЛЕДСТВИЕ 1.14.1. Всякий цикл P = (VP,EP), \VP\ = n, п 4, будет разрушен по критерию J3(2,«-yC (v ,v")-2) при удалении двух несмежных вершин v ,v"eVP, т.е., когда эпицентрами являются эти несмежные вершины. 4 ПРИМЕЧАНИЕ 1.4.Если цикл P = (VP,EP) имеет 2 к п эпицентров в начальный момент процесса структурного разрушения, то целесообразно рассматривать длины всех 7,-=( -, -), [Р} = И/, i = \,N, N п, получившихся при удалении эпицентров. В силу теоремы 1.14 и следствия 1.14.1 возможны различные компонентные критерии структурного разрушения -сг2(к,Пі).
После удаления в момент времени t = \ процесса структурного разрушения эпицентра из цикла Р = (VP,EP), к началу момента времени t = 2 получим цепь длины п - 2, эпицентрами которой являются ее концы. Поскольку для каждой вершины veVP верно w(y)-w0(v) w(v)l2 к следующему моменту времени t = 3 получим цепь длины п - 4. В случае с нечетным п последние две вершины цикла будут разрушены за Tcr =(п +1)/2, в случае с четным п последняя вершина цикла будет разрушена за Тсг = л/2 + 1. А
Если к остовному подграфу De =(V,ED \Je) продолжать добавлять ребра из Е, но не содержащиеся в ED\Je, в результате получим граф G = (V,E). Очевидно, что все получаемые промежуточные остовные графы при добавлении ребер будут иметь одно и то же время полного структурного разрушения Tcr = s(v) в случае с эпицентром в вершине с максимальной степенью. А значит, и сам граф G будет разрушен по критерию а0(1) при удалении вершины v є V с максимальной степенью A(G) за время Tcr = s{v). Л СЛЕДСТВИЕ 1.17.1. Всякий граф G = (V,E) будет разрушен по критерию сг0(1) при удалении вершины veV за время Tcr=s{v), если w(v)-w0(v) w(v)/ A(G), где A(G) - максимальная степень графа G. Л
Построена математическая модель структурного разрушения сложной системы. Введены четыре критерия выхода системы из строя - критерий полного разрушения, критерий связности, компонентный критерий и диаметральный критерий.
Исследован процесс структурного разрушения для различных классов обыкновенных графов - цепей, циклов, деревьев и простых произвольных графов. Для каждого класса исследованных графов по каждому из предложенных критериев получены оценки времени структурного разрушения. Установлена связь между временем структурного разрушения с количеством эпицентров и их расположенем на графах.
Структурное разрушение предфрактального графа, порожденного полной затравкой, с сохранением смежности старых ребер
Рассмотрим вершинно взвешенный предфрактальный граф GL ={VL,EL), порожденный полной затравкой Н = {W,Q), w = «, б = 7 с сохранением смежности старых ребер. Не нарушая правила взвешивания предфрактального графа, определим веса вершин следующим образом. Каждой вершине приписывается два числа, отражающие соответственно ее текущий и предельный вес. Предельный вес вершины v є VL определяется как w{v ) = 0lAb, а ее текущий вес - w(v ) = 0 la, где l = \,L, а 0 и в а . Ь.
Рангом, вершины предфрактального графа GL будем называть наименьший ранг / среди всех инцидентных ей ребер. Вершину /-го ранга обозначим как v , где /е{1,2,...,/,}. Вершину /-го ранга v \ являющуюся эпицентром, назовем эпицентром 1-го ранга, где / = 1,2,...,/,.
Ранговый критерий cr4(k,l). Система считается вышедшей из строя, если разрушенными оказались все вершины /-го ранга, / = 1,/,. Ранговый критерий cr4(k,l) выхода системы из строя зависит от двух параметров, где к - число удаленных вершин в начальный момент времени структурного разрушения.
Потерей веса будем называть ситуацию, когда в результате удаления вершины ее предельный вес не может быть полностью перераспределен среди вершин окружения. 2.2.1. Разрушение предфрактального графа с эпицентрами в вершинах L-ro ранга
Рассмотрим случай, когда эпицентром является вершина L-ro ранга vj( подграф-затравки z, , то есть на момент времени / = 1 текущий вес вершины превышает предельное значение: w(vj ) w(vj ), а сам процесс структурного разрушения является равномерным. Так как порождающая затравка Н = (W,Q) предфрактального графа GL - полный граф, а смежность старых ребер сохраняется, окружением вершины v, является множество (v, ) = {v2 \v\ ,...,V _J}U{VJ _)}, включающее я-2 вершины L-ro ранга и одну вершину (L-l)-ro. Тогда, удаляя вершину v, \ распределяем ее предельный вес w(v, ) среди вершин окружения (vj ). Текущие веса смежных вершин 1-го ранга изменяются следующим образом: w{v\L ) = w(v\L ) + w(y )l{n-\), / = 2,3,..,я-1, и вершина (1-І)-го ранга w(v\LA)) = w(v1(L_1)) + wiv ) 1{п -1).
Если на подграф-затравке z\L\ s = \,..,nLA присутствует более одного эпицентра L-ro ранга, в силу того, что затравка - полный граф, эпицентры являются смежными вершинами. Тогда удаляются все разрушенные вершины подграф-затравки, а вес распределяется (равномерно) среди окружения каждой из них, за исключением самих удаляемых вершин.
Для всякого предфрактального графа GL, порожденного полной затравкой с сохранением смежности старых ребер, удаление любого количества вершин L-го ранга не нарушает его связности, при условии выполнения неравенства 2.5.
Поскольку вершины L -го ранга не являются точками сочленения, удаление любой из них при выполнении неравенства 2.5 не может вызвать распадение предфрактального графа GL на отдельные компоненты связности. Таким образом, уменьшается число вершин графа, но не нарушается связность его структуры. 4
Всякий предфрактальный граф GL, порожденный полной затравкой с сохранением смежности старых ребер и с эпицентрами L-го ранга, при условии выполнения неравенства 2.5 не может быть разрушен по критерию т0 (к), где \ к п -{п-\). А
В следствии 2.1.1 выполнение условия неравенства 2.5 не позволяет развиваться процессу разрушения в случае эпицентров L -го ранга. В результате удаления всех вершин L-ro ранга предфрактального графа GL, полученный подграф будет соответствовать предфрактальному графу GLA.
Всякий предфрактальный граф GL, порожденный полной затравкой с сохранением смежности старых ребер и с эпицентрами L-го ранга, при условии выполнения неравенства 2.5 не может быть разрушен по критерию ах (к), где \ к п 1 (п -1). Поскольку удаление какой-либо вершины LO ранга не нарушает связности предфрактального графа, тогда соответственно не изменяется число компонент связности.
Выполнение неравенства 2.5, не позволяет развиваться процессу разрушения "в центр". Результаты развития процесса разрушения предфрак-тального графа в случае выполнения противоположного неравенства 2.4 будут рассмотрены отдельно.
Разрушение предфрактального графа с эпицентрами в вершинах /-го ранга
Так как смежность старых ребер сохраняется, удаление любой вершины / -го ранга приводит к появлению компоненты с диамет 104 ром, равным единице, что означает разрушение предфрактального графа GL по критерию 73 (k,D) для любого D 2.
Для всякого предфрактального графа GL, порожденного множеством полных затравок, с сохранением смежности старых ребер, в условиях выполнения неравенств 3.3 и 3. б при разрушении любого количества вершин 1-го ранга потери веса не произойдет, где / = 1,/,-1,..,1.
.Для всякого предфрактального графа GL, порожденного множеством полных затравок с сохранением смежности старых ребер, удаление одной вершины I-го ранга, 1 = L \,L-2,..,1, при условии выполнения неравенста 3.5 на следующем шаге приводит к разрушению всех смежных ей вершин большего ранга.
Условие неравенства 3.5 говорит о том, что разрушение вершины / -го ранга приведет к превышению текущего веса над предельным для каждой из вершин (/ + 1)-го ранга. А поскольку условие неравенства является наиболее весомым среди всех условий 3.4, то выполнение неравенства 3.5 означает выполнение всех условий 3.4 для вершин (/ + 2),(/ + 3),..,Z рангов. Тогда удаление вершины 7-го ранга приводит к разрушению вершин (L-1 + l) разных рангов. А
Всякий предфракталъный граф GL, порожденный множеством полных затравок с сохранением смежности старых ребер и с эпицентрами 1-го ранга, будет разрушен по критерию o 4(r,t), где г - число всех вершин 1-го ранга, в случае выполнения неравенства 0L 2b/((nm&x -\)-2) 9LAb- 9LAa пошагово для всех t = 1,1 + 1,..,1.
. Для всякого предфрактального графа GL, порожденного множеством полных затравок с сохранением смежности старых ребер, при условии выполнения неравенства 3.9 разрушение любого количества вершин первого ранга не приведет к потере веса.. А случай, когда выполняются условия неравенства 3.1 для эпицентров L-ro ранга неравенств 3.3 и 3.6 для эпицентров 1-го ранга l = L-\,L-2,...,2, 3.9 для эпицентров первого ранга.
.Для всякого предфракталыюго графа GL, порожденного множеством полных затравок с сохранением смеэ/сности старых ребер, удаление вершин к ,кг \...,к разных рангов приводит к появлению 1 ( + 2 к +... + {L-1) &( +1 компоненты связности в условиях выполнения неравенств 3.1, 3.3, 3.6 и 3.9, где число эпицентров 1-го ранга на одной подграф-затравке z - не превышает (п - 2) для всех І є [\,L].
Всякий предфрактальный граф GL, порожденный множеством полных затравок с сохранением смежности старых ребер и с эпицентрами разных рангов в условиях выполнения неравенств 3.1, 3.3, 3.6 и 3.9 будет разрушен по критерию а2(к,т) для всех m \-k(L-l) +2-k(L 2) +... + (L-\)-k(l) +\, k = k(L)+k(L-l)+... + kil), гдечис ло эпицентров I -го ранга на одной подграф-затравке z не превышает (п - 2) для всех І є [1, L]. А
Всякий предфрактальный граф GL, порожденный множеством полных затравок, с сохранением смежности старых ребер, и с эпицентрами разных рангов, будет разрушен по критерию о \ (к) в условиях выполнения неравенств 3.1, 3.3, 3.6 и 3.9.
В соответствии с теоремой 3.19 удаление вершин разных рангов приводит к появлению нескольких компонент связности, что означает нарушение связности предфрактального графа GL, то есть разрушение по критерию сг & где к = к +k L 1 +... + к 1 . А
