Содержание

Введение. 3

1. Математическая модель структурного разрушения сложной системы.. 4

2. Характеристики и особенности структурного разрушения сложной системы.. 6

3. Структурное разрушение граф-цепей. 8

3.1. Структурное разрушение граф-цепей по критерию связности.. 8

3.2. Структурное разрушение граф-цепей по компонентному критерию... 9

3.3. Структурное разрушение граф-цепей по диаметральному критерию... 9

3.4. Структурное разрушение граф-цепей по критерию
полного разрушения. 12

4. Структурное разрушение деревьев. 13

4.1. Структурное разрушение деревьев по критерию связности.. 13

4.2. Структурное разрушение деревьев по компонентному критерию... 13

4.3. Структурное разрушение деревьев по диаметральному критерию... 14

4.4. Структурное разрушение деревьев по критерию полного разрушения. 16

5. Структурное разрушение циклических графов. 16

5.1. Структурное разрушение циклов по критерию связности.. 16

5.2. Структурное разрушение циклов по компонентному критерию... 17

5.3. Структурное разрушение циклов по диаметральному критерию... 17

5.4. Структурное разрушение циклов по критерию полного разрушения. 18

6. Структурное разрушение полных графов. 20

7. Структурное разрушение графов по критерию полного разрушения. 20

8. Выводы.. 22

Литература. 22

Введение

Эффективность функционирования большинства отраслей экономики государства зависит от пространственной распределенности и разветвленности ее коммуникационных сетей (электроэнергетических, информационных, водо- и теплоснабжающих и т.п.). Чем шире зона покрытия коммуникационных сетей, тем выше конкурентоспособность соответствующей отрасли экономики как на внутреннем рынке государства так и за его пределами.

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

Ряд аварий в электроэнергетических системах в крупных городах России (Москва, 2005 г.), Европы (Лондон, 2003 и 2006 гг.; Париж, 2006 г.) США и Канады (Детройте, Нью-Йорке, Кливленде, Оттаве, Торонто, 2003  г.), показал, что развитие чрезвычайных ситуаций в коммуникационных системах с сетевой структурой проходит по “принципу домино” (в случае электроэнергетических систем – это веерные отключения). Один вышедший из строя объект (элемент системы) сильно повышает вероятность аварии на остальных, что приводит к возникновению лавины аварий. О последствия таких аварий красноречиво свидетельствует следующий факт.

14 августа 2003 года в ряде крупнейших городов восточного побережья США и Канады – Детройте, Нью-Йорке, Кливленде, Оттаве, Торонто и др. – произошло 9-секундное отключение электроснабжения, приведшее к веерным отключениям электроэнергии на площади более 24 тыс. кв. км и получившее название “Блэкаут-2003”. Причина – перегрузка на энергетическом каскаде Ниагара-Мохок (граница США и Канады). Авария затронула более 50 млн. человек в восьми штатах США и провинции Онтарио Канады, привела к остановке более 100 электростанций, в том числе 22 автомных реакторов. Ликвидация последствий аварии заняла более 30 часов. Сумма нанесенного США финансового ущерба составляет не менее 6 млрд. долларов.

Нередки чрезвычайные ситуации в России в сетях тепло-, водо- и газопроводного транспорта. Во многих случаях причиной аварий является изношенность самих сетей и узлового оборудования. Предотвращение, прогнозирование и профилактика чрезвычайных ситуаций [1, 2] с далеко идущими последствия в сетевых системах со сложной структурой требует новых исследовательских подходов в моделировании с учетом всех структурных особенностей моделируемой системы.

Описанная в настоящей работе математическая модель структурного разрушения сложной системы является дополнением к модели распространения внешних воздействий по структуре системы [3]. Эти модели в схеме развития чрезвычайных ситуаций (инициирование ЧС→развитие ЧС→выход ЧС за пределы системы) описывают первый и второй этапы.

1. Математическая модель структурного разрушения сложной системы

Изменения, происходящие в структуре сложной системы, могут быть описаны простейшими теоретико-графовыми операциями [4]: стягиванием ребра, удалением (добавлением) ребра, удалением (добавлением) вершины. Изменения структуры системы могут быть разовыми, а могут быть постоянными (периодическими, регулярными). Для второго случая, разумно, ввести понятие структурной динамики – изменение структуры системы с течением времени. Несомненно, для описания структурной динамики лучше всего подходит аппарат теории графов [4].

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

Существует ряд моделей и задач, для описания которых используются потоки в сетях и на графах [5]. Потоками в сетях моделируют автотранспортное движение, перевозку товаров по железным дорогам, перекачку жидкости и газа по сети трубопроводов от источника до пункта потребления и т.д. Но все эти модели и задачи не учитывают возможность внезапного прекращения функционирования узловых элементов сетей (развязки автомобильных и железных дорог, станций высокого давления, трансформаторов и т.п.), а это часто приводит к внештатным ситуациям, неописываемым этими моделями. Нередко отказ одного узлового элемента системы приводит к череде отказов в системе (каскадному отключению), вследствие чего из строя выходит вся система.

Обозначим через  – граф, соответствующий структуре исследуемой системы,  – множество вершин, соответствующее элементам системы, а  – множество ребер, соответствующее связям между элементами систмы. Каждой вершине  припишем веса  и , отражающие текущую загрузку и предельную загрузку элемента системы. В случае, когда текущая загрузка  элемента системы достигает предельного значения , элемент систем выходит из строя. А проходящие через него потоки перераспределяются по “соседним” элементам системы. Выход из строя элемента системы в теоретико-графовой терминологии соответствует удалению из графа системы вершины с инцидентными ей ребрами. А перераспределение весов в тривиальном случае соответствует равному разделению веса  удаленной вершины по вершинам, смежным с удаляемой.

При выходе из строя одного или нескольких элементов системы возможны несколько сценариев дальнейшего развития событий. Один из них возможен, если система функционирует в предельном состоянии, т.е. загрузка элементов близка к предельному значению. Тогда возможен “быстрый” переход системы в критическое состояние, когда система не может выполнять возложенные на нее функции.

Структурное разрушение, вообще говоря, процесс динамический. Не нарушая общности, будем считать, что  – текущая загрузка вершины  в момент времени . Если через , , обозначить множество вершин вышедших из строя в момент времени , т.е. те, у которых , а через  – окружение вершины  (или множество вершин, смежных с вершиной ), , , то процесс структурного разрушения формально описывается следующим образом.

В момент времени  необходимо произвести проверку по всем вершинам , и сформировать множество  из вершин, для которых справедливо . Во все последующие моменты времени  следует воспользоваться правилом

, , .        (1)

Если , то вершина  удаляется из графа  и .

Коэффициент  – параметр распределения загрузки. Параметр распределения загрузки может зависеть от различных факторов, в простейшем случае он равномерно распределяет предельную загрузку удаляемой вершины по соседним, т.е. на для каждой вершины  вычисляется как . Структурное разрушение при параметре распределения загрузки  будем назвать равномерным.

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

Критическое состояние  определяется исходя из особенностей моделируемой системы. Например, система может считаться пребывающей в критическом состоянии, если из ее структуры удален, хотя бы один элемент (вершина), или система может считаться функционирующей, если ее структура после удаления элементов все еще остается связной. В настоящей работе будут рассмотрены различные критерии отказа системы (перехода в состояние отказа системы) или, иначе, критерии разрушения.

2. Характеристики и особенности структурного разрушения сложной системы

Основная задача моделирования структурного разрушения системы – выяснить, при каких условиях система может перейти в критическое состояние. (Начальные причины повреждения системы могут быт как внутренними, так и внешними.) Переход системы в критическое состояние означает, что в системе начался процесс структурного разрушения, но это не значит что система окончательно прекратила функционировать. Систему можно считать вышедшей из строя только в том случае, когда изменения, произошедшие в структуре системы будут удовлетворять критериям отказа. Поэтому одной из основных характеристик в модели структурного разрушения будет служить время  структурного разрушения, отражающее длительность самого процесса структурного разрушения.

Нельзя утверждать, что система перейдя, в критическое состоянии, когда из ее структуры удаляются элементы (начало процесса структурного разрушение), непременно впоследствии выйдет из строя (перейдет и в состояние отказа системы). Время  структурного разрушения системы соответствует продолжительности процесса структурного разрушения от момента первого удаления (выхода из строя) элемента системы до момента остановки процесса разрушения или отказа самой системы.

Поскольку построенная модель структурного разрушения системы непосредственно связана с типом структуры самой системы, важно исследовать системы с различными типами структур, найти связь между типом структуры системы и временем структурного разрушения системы.

Нельзя подменять два представления о сложности систем. Сложность системы может заключаться и в сложности ее динамического поведения (самоорганизация, динамический хаос, бифуркации, случайное поведение и т.п.) и в сложности структуры, т.е. связей между элементами системы. Часто системы совмещают в себе эти оба представления о сложности, хотя не всегда исследователям удается жестко определить понятия сложности системы в поведении и в структуре. Нетривиален этот вопрос и для исследуемого в настоящей работе процесса структурного разрушения системы.

Простыми структурами в контексте настоящей работы следует считать регулярные, периодические, симметричные, автоморфные графы и деревья. Именно с исследования таких структур начнется исследование процесса структурного разрушения систем, но нельзя при этом считать, что сам процесс окажется так же “простым”.

Для исследования процесса структурного разрушения систем с “простой” структурой целесообразно использовать следующие критерии отказа.

1. Критерий полного разрушения . Система считается вышедшей из строя, если в системе выйдут из строя все элементы (будут удалены все вершины графа – структуры системы). Критерий полного разрушения  зависит от одного параметра:  – числа удаленных вершин в начальный момент времени структурного разрушения.

2. Критерий связности . Система считается вышедшей из строя, если нарушена связность ее структуры при удалении вершин. Критерий связности  зависит от одного параметра:  – числа удаленных вершин в начальный момент времени структурного разрушения.

3. Компонентный критерий . Система считается вышедшей из строя, если число компонент в структуре системы при ее разрушении окажется не меньше заданного числа . Компонентный критерий  выхода системы из строя зависит от двух параметров: от  – числа удаленных вершин в начальный момент времени структурного разрушения, и  – максимально допустимого числа компонент структуры при ее разрушении.

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

По мере необходимости в дальнейшем будет вводиться и другие критерии отказа систем.

Множество  элементов вышедших из строя (удаленные из структуры) в момент времени  будем называть эпицентрами структурного разрушения. В критериях , , ,, число  соответствует количеству эпицентров структурного разрушения системы.

Далее в настоящей главе проведено исследование структурного разрушения “простых” графов (цепей, деревьев, циклов, регулярных графов) с равными значениями начальных загрузок  и равными значениями предельных загрузок  для всех их вершин.

3. Структурное разрушение граф-цепей

3.1. Структурное разрушение граф-цепей по критерию связности

Всякий связный ациклический граф  называется деревом. Частным случаем дерева  является граф-цепь  (см. рис. 1). Множество вершин  граф-цепи  состоит из двух висячих вершин – концов цепи со степенями равными единице (на рис. 1 вершины v₁ и v₂ – висячие), и внутренних вершин со степенями равными двум.

Рассмотрим граф-цепь , , с равными для всех его вершин весами , .

Очевидно, что всякий граф-цепь утратит связность при удалении хотя бы одной невисячей (внутренней) вершины.

Лемма 1. Всякий граф-цепь , , будет разрушен по критерию , где , при удалении хотя бы одной невисячей вершины. ◄[1]

3.2. Структурное разрушение граф-цепей по компонентному критерию

Удаление одной невисячей вершины граф-цепи  непременно приведет к распаду его на две компоненты  и . “Простейшей” компонентой в таком случае может быть граф-вершина. Всякий граф-цепь , , , имеет  попарно несмежных внутренних вершин, если  – нечетное, и , если  – четное. Удаление из граф-цепи  всех попарно несмежных внутренних вершин приведет к появлению  компонент в первом случае и  – во втором, причем каждая компонента будет представлять собой граф-вершину.

Лемма 2. Всякий граф-цепь , , , будет разрушен по критерию , где  при нечетном  и  при четном , если количество попарно несмежных внутренних вершин-эпицентров равно . ◄

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

3.3. Структурное разрушение граф-цепей по диаметральному критерию

Пусть H=(W,Q) есть n-вершинный связный граф. Длина кратчайшей цепи, соединяющей пару вершин , называется расстоянием между вершинами w и v и обозначается через . Заметим, что введенное таким образом расстояние удовлетворяет известным аксиомам Евклидовой метрики.

Для фиксированной вершины  величина  называется эксцентриситетом вершины . Максимальный среди всех эксцентриситетов вершин графа H=(W,Q) называется диаметром графа H и обозначается через d(H), т.е. . Если пара вершин  соединяется кратчайшей цепью длины , то эта цепь называется диаметральной. Вершина w называется периферийной, если . Радиус графа H обозначается через r(H) и вычисляется по формуле . Вершина w называется центральной, если . Центром графа H называется множество центральных вершин.

Для граф-цепи , , расстояние между двумя его висячими вершинами  и  совпадает с диаметром и длиной графа цепи , а сами вершины  и  являются периферийными.

Всякий граф-цепь , , имеет центр, состоящий из двух вершин, если число вершин цепи  – четное, и состоящий из одной вершины, если число вершин  – нечетное. В первом случае , во втором . Удаление центральной вершины граф-цепи  приведет к распадению его на две цепи  и , с соответствующими диаметрами  и  (см. рис. 2). Очевидно, что при нечетном  диаметры компонент  и  будут равны , а при четном  – .

Теорема 3. Всякий граф-цепь , ,  будет разрушен по критерию  при удалении центральной вершины (т.е. когда эпицентром является центральная вершина). Причем диаметры появившихся в результате структурного разрушения компонент будут равны  и . ◄

Следствие 3.1. Всякий граф-цепь , ,  будет разрушен по критерию  при удалении центральной вершины (т.е. когда эпицентром является центральная вершина). Причем диаметры появившихся в результате структурного разрушения компонент будут равны  и . ◄

Для эксцентриситета всякой внутренней вершины  граф-цепи  справедливо неравенство . Также, как и в случае с удалением из граф-цепи центральной вершины, удаление любой внутренней вершины приведет к распадению граф-цепи  на две компоненты  и , с соответствующими диаметрами  и  (см. рис. 3). Поэтому из Леммы 3 очевидным образом вытекает следующая

Лемма 4. Всякий граф-цепь , ,  будет разрушен по критерию  при удалении внутренней вершины  (т.е. когда эпицентром является внутренняя вершина ). Причем диаметры появившихся в результате структурного разрушения компонент будут равны  и . ◄

Следствие 4.1. Всякий граф-цепь , ,  будет разрушен по критерию  при удалении внутренней вершины  (т.е. когда эпицентром является внутренняя вершина ). Причем диаметры появившихся в результате структурного разрушения компонент будут равны  и . ◄

Обобщением теорем 3 и 4 является следующая

Лемма 5. Всякий граф-цепь , ,  будет разрушен по критерию , где , при удалении  внутренних вершин (т.е. когда эпицентрами являются  внутренних вершин). ◄

Примечание 2. В теоремах и леммах  2 – 5 отражены случаи разрушения граф-цепи , , , по критериям , , и . Во всех исследованных случаях было предположено, что все вершины граф-цепи  имеют равные значения текущих (начальных) загрузок  и равные значения предельных загрузок . Поэтому критерии структурного разрушения во всех этих случаях достигается в начальный  момент времени процесса структурного разрушения, т.е. время процесса структурного разрушения равно . ◄

3.4. Структурное разрушение граф-цепей по критерию полного разрушения

Прежде, чем перейти к исследованию структурного разрушения по критерию , рассмотрим вопрос о разности начальной (текущей)  и предельной загрузки  элементов граф-цепи .

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

В другом случае, когда , длительность процесса структурного разрушения , если система не выйдет из строя при достижении установленного критерия разрушения.

Иная ситуация складывается, когда эпицентром является одна из висячих вершин  граф-цепи . В таком случае , поэтому для смежной эпицентру вершине  будет справедливо выражению . А это значит что вершина  выйдет из строя (будет удалена) в следующий момент времени . Причем вершина  окажется висячей для цепи , что приведет к удалению смежной ей вершине в момент времени  Этот процесс будет продолжаться до пор, пока не будут удалены все вершины граф-цепи , т.е. будет достигнут критерий разрушения , или ранее пока не будет достигнут другой установленный критерий разрушения.

Лемма 6. Всякий граф-цепь , ,  будет разрушен по критерию  при удалении одной из висячих вершин за время . ◄

Теорема 7. Всякий граф-цепь , ,  будет разрушен по критерию  при удалении одной из внутренних вершин  за время , где  – эксцентриситет вершины , если .

Доказательство. После удаления внутренней вершины  граф-цепь  в момент времени  распадется на две компоненты, у каждой из которых эпицентрами окажутся по одной висячей вершине. Это впоследствии, согласно Теореме 1.6, при ведет к разрушению обеих компонент по критерию . Время разрушения в таком случае каждой компоненты совпадает с числом вершин в них, для большой компоненты это – , а для меньшей – . А поскольку процесс структурного разрушения граф-цепи  начался с удаления внутренней вершины , то его время . ◄

Следствие 7.1. Всякий граф-цепь , ,  будет разрушен по критерию  при удалении центральной вершины за время , где  – радиус граф-цепи , если . ◄

4. Структурное разрушение деревьев

4.1. Структурное разрушение деревьев по критерию связности

У деревьев , как у граф-цепей , центр может состоять либо из одной, либо из двух вершин. Если диаметральная цепь дерева  имеет четную длину, т.е. диаметр  – четный, то центр дерева состоит из одной вершины, и из двух в противном случае, т.е. когда диаметр  – нечетный. У всякого дерева  не менее, чем две висячие вершины. Все остальные, как в случае с графами-цепями будем называть внутренними.

Очевидно, что всякое дерево утратит связность при удалении хотя бы одной невисячей (внутренней) вершины.

Теорема 8. Всякое дерево , , будет разрушено по критерию, где ,  – количество висячих вершин, при удалении хотя бы одной внутренней вершины за время . ◄

4.2. Структурное разрушение деревьев по компонентному критерию

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

Лемма 9. Всякое дерево , , будет разрушено по критерию  при удалении одной внутренней вершины  за время , причем . ◄

Теорема 10. Всякое дерево , , будет разрушено по критерию  при удалении  попарно несмежных внутренних вершин  за время , причем .

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

После удаления первой вершины  дерево распадется на  компонент. Поскольку эпицентры являются попарно несмежными и невисячими вершинами дерева , то вершина  принадлежащая какой-то из полученных при удалении вершины  компонент также не будет являться для свой компоненты висячей вершиной. Поэтому при удалении вершины  компонента которой она принадлежит распадется на  компонент. А общее количество компонент, на которое распадется само дерево , после удаления вершин  и  станет равно . И далее, каждое удаление одной из вершин , , будет увеличивать число количество компонент на число . А это значит, что при одновременном удалении всех эпицентров соответствующих условиям теоремы дерево  распадется на  компонент. И длительность процесса структурного разрушения составит . ◄

4.3. Структурное разрушение деревьев по диаметральному критерию

Уточним, что центральные вершины дерева  – это те вершины, для которых расстояние до любой другой вершины дерева не больше чем радиус дерева , т.е. расстояние от центральной вершины до самой удаленной от нее вершины дерева равно радиусу . Говоря иначе, расстояние от центральной вершины до концов любой проходящей через центральную вершину цепи будет не больше радиуса , т.е. после удаление центральной вершины эта цепь распадется на цепи с диаметром, который меньше чем . Это позволяет утверждать о справедливости следующей теоремы.

Лемма 11. Всякое дерево  будет разрушено по критерию  при удалении центральной (центральных вершин) вершины, т.е. когда эпицентром (эпицентрами) являются центральная (центральные вершины) вершина,  (), за время . ◄

Теорема 12. Всякое дерево  будет разрушено по критерию  при удалении всех  вершин , , с эксцентриситетами , т.е. когда эпицентрами являются все вершины с эксцентриситетом , за время .

Доказательство. Эксцентриситет любой из удаляемой вершины , , удовлетворяет неравенству . Если , то доказательство теоремы 12 сводится к доказательству леммы 11. Если же эксцентриситет , то, из дерева удаляются все периферийные вершины, что приводит к уменьшению диаметра. Диаметр, получившегося таким образом дерева , будет равен .

В общем случае следует рассмотреть два типа дерева – одноцентровое и двуцентровое.

Всякое дерево, центр которого состоит из одной вершины, будем называть одноцентровым (или однокорневым) и двуцентровым (или двукорневым), если центр дерева состоит из двух смежных вершин.

У всякого однокорневого дерева каждая смежная с центральной вершиной вершина имеют эксцентриситет равный . Вершины , расстояние от которых до центрально равно 2, имеют эксцентриситет равный  и т.д. Наконец, вершины , расстояние от которых до центральной равно , имеют эксцентриситет равный . Так расстояние между любой периферийной и центральной вершинами равно .

Обозначим через  центральную вершину дерева , а через  – ту компоненту, которой будет принадлежать вершина , после удаления из дерева  всех вершин с эксцентриситетами , . Вершины  смежные удаляемым  из дерева  окажутся висячими для дерева . Расстояние от этих вершин  до вершины  останется неизменным . Все остальные вершины дерева  находятся на таком же или меньшем расстоянии от вершины , поскольку в дереве  они имели меньший эксцентриситет, чем удаленные вершины . По этой причине вершина  останется центральной и для дерева , причем его радиус будет равен . У всякого одноцентрового дерева радиус ровно в два раза больше диаметра, что справедливо и для дерева : . Это удовлетворяет диаметральному критерию разрушения  одноценрового дерева, когда эпицентрами являются все  вершин с эксцентриситетом  (см. следствие 1.12.1).

В случае двукорневого дерева , после удаления всех  вершин , дерево  также будет иметь две смежных центральных вершины. Поэтому его диаметр будет отличаться от однокорневого на единицу – . ◄

Следствие 12.1. Всякое одноцентровое дерево  будет разрушено по критерию  при удалении всех  вершин , , с эксцентриситетами , т.е. когда эпицентрами являются все вершины с эксцентриситетом , за время . ◄

4.4. Структурное разрушение деревьев по критерию полного разрушения

Особое место в структурном разрушении деревьев, как и в структурном разрушении деревьев, занимает критерий полного разрушения .

Теорема 13. Всякое дерево  будет разрушено по критерию  при удалении вершины  с максимальной степенью  за время , если , где .

Доказательство. Рассмотрим дерево , , с равными для всех его вершин  начальными  и предельными  загрузками.

Любая вершина  выйдет из стоя (будет удалена из дерева ), если в некоторый момент времени  процесса структурного разрушения дерева  текущая загрузка  превысит предельную .

Предположим, что вершина  смежна с вершиной , имеющей максимальную степень  для дерева . Если в процессе структурного разрушения в некоторый момент времени  из строя вышла вершина , то в момент времени  текущая загрузка вершины  увеличиться  и вершина  выйдет из строя.

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

Поскольку эксцентриситет всякой вершины в графе соответствует длине цепи до самой отдаленной от нее вершине, то время структурного разрушения по критерию по критерию  при удалении вершины  с максимальной степенью  равно . ◄

5. Структурное разрушение циклических графов

5.1. Структурное разрушение циклов по критерию связности

Всякий связный циклический граф  (см. рис. 4). Каждая вершина из множество вершин  цикла  имеет степень равную двум (см. рис. 4).

Очевидно, что всякий цикл утратит связность при удалении хотя бы двух несмежных вершин.

Лемма 14. Всякий цикл , , будет разрушен по критерию , где , при удалении хотя бы двух несмежных друг с другом из  вершин. ◄

5.2. Структурное разрушение циклов по компонентному критерию

Удаление двух несмежных вершин цикла   непременно приведет к распадению его на две компоненты  и . “Простейшей” компонентой в таком случае может быть граф-вершина. Всякий цикл , , , имеет  попарно несмежных вершин, если  – нечетное, и , если  – четное. Удаление из цикла  всех попарно несмежных вершин приведет к появлению  компонент в первом случае и  – во втором. При нечетном  все кроме одной компоненты будет представлять собой граф-вершину, а при четном  все компоненты окажутся граф-вершинами.

Лемма 14. Всякий цикл , , , будет разрушен по критерию , где  при нечетном  и  при четном , если вершины-эпицентры попарно несмежны. ◄

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

5.3. Структурное разрушение циклов по диаметральному критерию

Для всякого цикла , , справедливо равенство , причем  при нечетном , и  при четном . Кроме того, каждая вершина цикла  является и центральной и периферийной.

Теорема 15. Всякий цикл , , , будет разрушен по критерию  при удалении двух несмежных вершин , т.е. когда эпицентрами являются эти несмежные вершины.

Доказательство. При удалении из цикла , , , двух несмежных вершин , цикл распадется на две цепи  и  таким образом, что длина наименьшей из них (допустим цепи ) равна . Диаметр этой цепи равен , цикл будет разрушен по критерию  за время  ◄

Для цикла на рис. 4 при эпицентрах  и  диаметральный критерий представляет собой .

Если в случае взять во внимание длину некратчайшей цепи  из доказательства теоремы 15, а ее длина равна , то справедливо

Следствие 15.1. Всякий цикл , , , будет разрушен по критерию  при удалении двух несмежных вершин , т.е. когда эпицентрами являются эти несмежные вершины. ◄

Примечание 4. Если цикл  имеет  эпицентров в начальный момент процесса структурного разрушения, то целесообразно рассматривать длины всех , , , , получившихся при удалении эпицентров. В силу теоремы 15 и следствия 15.1 возможны различные компонентные критерии структурного разрушения – . ◄

Примечание 5. Для Очевидно, что для всякого структурное разрушение не возможно по компонентному критерию, если число эпицентров меньше двух. ◄

5.4. Структурное разрушение циклов по критерию полного разрушения

Предположим эпицентром цикле , , , является одна из его вершин . Пусть также , тогда после удаление эпицентра  текущая загрузка смежных ему вершин  станет равной  . Поэтому процесс структурного разрушения прекратиться, а его длительность его будет равна .

В другом случае, когда , длительность процесса структурного разрушения , если система не выйдет из строя при достижении установленного критерия разрушения.

Лемма 16. Всякий цикл , , ,будет разрушен по критерию  при удалении одной из вершин  за время  при нечетном  и за время  при четном , если .

Доказательство. После удаления в момент времени  процесса структурного разрушения эпицентра из цикла  к началу момента времени  получим цепь длины , эпицентрами которой являются ее концы. Поскольку для каждой вершины  верно , к следующему моменту времени  получим цепь длины . В случае с нечетным  последние две вершины цикла будут разрушены за , в случае с четным  последняя вершина цикла будет разрушена за . ◄

На рис. 5 показан процесс структурного разрушения 5-ти вершинного (справа) и 6-ти вершинного (слева) циклов. Пунктирными окружностями выделены эпицентры в каждом из моментов времени процесса структурного разрушения.

Примечание 6. Если цикл  имеет  эпицентров в начальный момент процесса структурного разрушения и для его вершин справедливо , то целесообразно рассматривать длину максимальной цепи всех , , получившихся при удалении эпицентров. Поскольку в силу теоремы 15, следствия 15.1 и леммы 16 время полного структурного разрушения цикла  будет равно  при нечетном  и  при нечетном . ◄

6. Структурное разрушение полных графов

Полный -вершинный граф  сильно связная структура, поэтому критерий связности при его структурном разрушении может быть достигнут при  эпицентрах. Аналогичная ситуация и в случае с компонентном критерием. Он равен .

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

Лемма 17. Всякий полный граф  будет разрушено по критерию  при удалении вершины  за время , если .

Доказательство. После удаления из полного графа  эпицентра  к началу момента времени  получим полный граф . По истечению момента времени  каждая вершина графа  будет иметь текущую загрузку . Поэтому время полного структурного разрушения полного графа  равна  (см. рис. 6). ◄

7. Структурное разрушение графов по критерию полного разрушения

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

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

Теорема 18. Всякий граф  будет разрушен по критерию  при удалении вершины  с максимальной степенью  за время , если , где .

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

Выделим на дереве  вершину . Рассмотрим остовный подграф , где ,  и инцидентно вершине  (т.е. рассмотрим граф полученный из дерева  добавлением ребра , инцидентного вершине  в графе ). Очевидно, ребро  будет входит в единственный цикл графа . Проведенное преобразование дерева  никак не повлияет на процесс структурного разрушения графа . Степени вершин , , в новом графе  окажутся меньше максимальной степени вершины графов ,  и : , . Поэтому процесс структурного разрушения графа  по критерию полного разрушения с эпицентром в вершине  с максимальной степенью  пройдет за время .

Если к остовному подграфу  продолжать добавлять ребра из , но не содержащиеся в , в результате получим граф . Очевидно, что все получаемы промежуточные остовные графы при добавлении ребер будут иметь одно и тоже время полного структурного разрушения  в случае с эпицентром в вершине с максимальной степенью. А значит и сам граф  будет разрушен по критерию  при удалении вершины  с максимальной степенью  за время . ◄

Следствие 18.1. Всякий граф  будет разрушен по критерию  при удалении вершины  за время , если , где  – максимальная степень графа . ◄

8. Выводы

Построена математическая модель структурного разрушения сложной системы. Введены четыре критерия выхода системы из строя – критерий полного разрушения, критерий связности, компонентный критерий и диаметральный критерий.

Исследован процесс структурного разрушения для различных классов обыкновенных графов – цепей, циклов, деревьев и простых произвольных графов. Для каждого класса исследованных графов по каждому из предложенных критериев получены оценки времени структурного разрушения. Установлена связь между времени структурного разрушения с количеством эпицентров и их расположением на графах.

Построенная модель в целом расширяет спектр дискретных математических моделей и область приложений теории графов. В соответствии с идеями структурной динамики на основе предложенной модели наравне с понятием клеточного автомата [6] целесообразно использование понятие графового автомата, что также расширяет описательные возможности теории графов.

Авторы выражают искреннюю признательность профессору Малинецкому Г.Г. за внимание к этой и многим другим работам.

Литература

1.           Владимиров В.А., Кульба В.В., Малинецкий Г.Г, Махутов Н.А. и др. Управление риском. – М.: Наука, 2000.

2.           Архипова Н.И., Кульба В.В. Управление в чрезвычайных ситуациях. – М.: РГГУ, 1998.

3.           Кочкаров А.А., Малинецкий Г.Г. Обеспечение стойкости сложных систем. Структурные аспекты: . – М.: ИПМ им. М.В. Келдыша РАН, № 53, 2005.

4.           Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, 1990.

5.           Форд Л., Фалкерсон Д. Потоки в сетях. - М.: Мир, 1966.

6.           Тоффоли Т., Марголус Н. Машины клеточных автоматов. - М.: Мир, 1991.