Моделирование разрушения сложных систем. Структурные аспекты
|
Рис. 1. Граф-цепь |
Рассмотрим граф-цепь ,
, с равными для всех его вершин
весами
,
.
Очевидно, что всякий граф-цепь утратит связность при удалении хотя бы одной невисячей (внутренней) вершины.
Лемма 1. Всякий граф-цепь ,
, будет разрушен по критерию
, где
, при удалении хотя бы одной невисячей вершины. ◄[1]
Удаление одной невисячей вершины граф-цепи непременно приведет к
распаду его на две компоненты
и
. “Простейшей” компонентой в таком случае может быть
граф-вершина. Всякий граф-цепь
,
,
, имеет
попарно несмежных
внутренних вершин, если
– нечетное, и
, если
– четное. Удаление из
граф-цепи
всех попарно несмежных
внутренних вершин приведет к появлению
компонент в первом
случае и
– во втором, причем
каждая компонента будет представлять собой граф-вершину.
Лемма 2. Всякий граф-цепь ,
,
, будет разрушен по критерию
, где
при нечетном
и
при четном
, если количество попарно несмежных внутренних вершин-эпицентров
равно
. ◄
Примечание 1. Для всякого
граф-цепи ,
,
, структурное разрушение по критерию
в зависимости от
соотношения параметров
и
может произойти различными способами. Например для граф-цепь, изображенный на рис. 1 критерий
разрушения
может быть достигнут двумя способам, поскольку
для этого графа существует два набора попарно несмежных внутренних вершин эпицентров,
причем критерий достигается в момент времени
. ◄
Пусть H=(W,Q) есть n-вершинный
связный граф. Длина кратчайшей цепи, соединяющей пару вершин , называется расстоянием между вершинами w и v и обозначается через
. Заметим, что введенное таким образом расстояние
удовлетворяет известным аксиомам Евклидовой метрики.
Для фиксированной вершины величина
называется эксцентриситетом
вершины
. Максимальный среди
всех эксцентриситетов вершин графа H=(W,Q)
называется диаметром графа H и обозначается через d(H), т.е.
. Если пара вершин
соединяется кратчайшей
цепью длины
, то эта цепь называется диаметральной.
Вершина w называется периферийной,
если
. Радиус графа H обозначается
через r(H) и вычисляется по формуле
. Вершина w называется центральной,
если
. Центром графа H называется
множество центральных вершин.
Рис. 2.
Граф-цепь |
Для граф-цепи ,
, расстояние между двумя его висячими вершинами
и
совпадает с диаметром
и длиной графа цепи
, а сами вершины
и
являются
периферийными.
Всякий граф-цепь ,
, имеет центр, состоящий из двух вершин, если число вершин
цепи
– четное, и состоящий
из одной вершины, если число вершин
– нечетное. В первом
случае
, во втором
. Удаление центральной вершины граф-цепи
приведет к распадению
его на две цепи
и
, с соответствующими диаметрами
и
(см. рис. 2). Очевидно, что при
нечетном
диаметры компонент
и
будут равны
, а при четном
–
.
Теорема 3. Всякий граф-цепь ,
,
будет разрушен по
критерию
при удалении
центральной вершины (т.е. когда эпицентром является центральная вершина). Причем диаметры появившихся в результате
структурного разрушения компонент будут равны
и
. ◄
Следствие 3.1. Всякий граф-цепь ,
,
будет разрушен по
критерию
при удалении
центральной вершины (т.е. когда эпицентром является центральная вершина). Причем диаметры появившихся в результате
структурного разрушения компонент будут равны
и
. ◄
Для эксцентриситета всякой внутренней вершины граф-цепи
справедливо
неравенство
. Также, как и в случае с удалением из граф-цепи центральной
вершины, удаление любой внутренней вершины приведет к распадению граф-цепи
на две компоненты
и
, с соответствующими диаметрами
и
(см. рис. 3). Поэтому из
Леммы 3 очевидным образом вытекает следующая
Лемма 4. Всякий граф-цепь ,
,
будет разрушен по
критерию
при удалении
внутренней вершины
(т.е. когда эпицентром является внутренняя
вершина
). Причем диаметры появившихся в результате структурного
разрушения компонент будут равны
и
. ◄
Следствие 4.1. Всякий граф-цепь ,
,
будет разрушен по
критерию
при удалении
внутренней вершины
(т.е. когда эпицентром является внутренняя
вершина
). Причем диаметры появившихся в результате
структурного разрушения компонент будут равны
и
. ◄
Рис. 3. Граф-цепь
|
Обобщением
теорем 3 и 4 является следующая
Лемма 5. Всякий граф-цепь ,
,
будет разрушен по
критерию
, где
, при удалении
внутренних вершин
(т.е. когда эпицентрами являются
внутренних вершин). ◄
Примечание 2. В
теоремах и леммах 2 – 5 отражены случаи разрушения граф-цепи ,
,
, по критериям
,
, и
. Во всех исследованных случаях было предположено, что все
вершины граф-цепи
имеют равные значения
текущих (начальных) загрузок
и равные значения
предельных загрузок
. Поэтому критерии структурного разрушения во всех этих
случаях достигается в начальный
момент времени
процесса структурного разрушения, т.е. время процесса структурного разрушения
равно
. ◄
Прежде, чем перейти к исследованию структурного
разрушения по критерию , рассмотрим вопрос о разности начальной (текущей)
и предельной загрузки
элементов граф-цепи
.
Предположим
эпицентром на граф-цепи является одна из
его внутренних вершин
. Пусть также
, тогда после удаление эпицентра
текущая загрузка
смежных ему вершин
станет равной
. Поэтому процесс структурного разрушения прекратиться, а его
длительность его будет равна
.
В другом
случае, когда , длительность процесса структурного разрушения
, если система не выйдет из строя при достижении
установленного критерия разрушения.
Иная ситуация
складывается, когда эпицентром является одна из висячих вершин граф-цепи
. В таком случае
, поэтому для смежной эпицентру вершине
будет справедливо
выражению
. А это значит что вершина
выйдет из строя (будет
удалена) в следующий момент времени
. Причем вершина
окажется висячей для
цепи
, что приведет к удалению смежной ей вершине в момент
времени
Этот процесс будет
продолжаться до пор, пока не будут удалены все вершины граф-цепи
, т.е. будет достигнут критерий разрушения
, или ранее пока не будет достигнут другой установленный
критерий разрушения.
Лемма 6. Всякий граф-цепь ,
,
будет разрушен по
критерию
при удалении одной из висячих вершин за
время
. ◄
Теорема 7. Всякий граф-цепь ,
,
будет разрушен по
критерию
при удалении одной из внутренних вершин
за время
, где
– эксцентриситет
вершины
, если
.
Доказательство.
После удаления внутренней вершины граф-цепь
в момент времени
распадется на две компоненты, у каждой
из которых эпицентрами окажутся по одной висячей вершине. Это впоследствии,
согласно Теореме 1.6, при ведет к разрушению обеих компонент по критерию
. Время разрушения в таком случае каждой компоненты совпадает
с числом вершин в них, для большой компоненты это –
, а для меньшей –
. А поскольку процесс структурного разрушения граф-цепи
начался с удаления
внутренней вершины
, то его время
. ◄
Следствие 7.1. Всякий граф-цепь ,
,
будет разрушен по
критерию
при удалении
центральной вершины за время
, где
– радиус граф-цепи
, если
. ◄
У деревьев , как у граф-цепей
, центр может состоять либо из одной, либо из двух вершин.
Если диаметральная цепь дерева
имеет четную длину,
т.е. диаметр
– четный, то центр
дерева состоит из одной вершины, и из двух в противном случае, т.е. когда
диаметр
– нечетный. У всякого
дерева
не менее, чем две
висячие вершины. Все остальные, как в случае с графами-цепями будем называть
внутренними.
Очевидно, что всякое дерево утратит связность при удалении хотя бы одной невисячей (внутренней) вершины.
Теорема 8. Всякое дерево ,
, будет разрушено по критерию
, где
,
–
количество висячих вершин, при удалении
хотя бы одной внутренней вершины за время
. ◄
Очевидно, удаление из дерева хотя бы одной
внутренней вершины приведет к распадению его на компоненты, причем число компонент
будет зависеть от степени удаляемой вершины.
Лемма 9. Всякое дерево ,
, будет разрушено по критерию
при удалении одной внутренней вершины
за время
, причем
. ◄
Теорема 10. Всякое дерево ,
, будет разрушено по критерию
при удалении
попарно несмежных внутренних вершин
за время
, причем
.
Доказательство.
Удаление из дерева всех
внутренних вершин
проведем
последовательно вопреки основным правилам определяющим процесс структурного
разрушения. Это позволит подсчитать количество полученных в результате
структурного разрушения компонент, и никак не повлияет на общую картину их
межэлементных связей.
После удаления первой вершины дерево распадется на
компонент. Поскольку
эпицентры являются попарно несмежными и невисячими вершинами дерева
, то вершина
принадлежащая какой-то
из полученных при удалении вершины
компонент также не
будет являться для свой компоненты висячей вершиной. Поэтому при удалении
вершины
компонента которой она
принадлежит распадется на
компонент. А общее
количество компонент, на которое распадется само дерево
, после удаления вершин
и
станет равно
. И далее, каждое удаление одной из вершин
,
, будет увеличивать число количество компонент на число
. А это значит, что при одновременном удалении всех
эпицентров соответствующих условиям теоремы дерево
распадется на
компонент. И длительность процесса
структурного разрушения составит
. ◄
Уточним, что центральные вершины дерева – это те вершины, для
которых расстояние до любой другой вершины дерева не больше чем радиус дерева
, т.е. расстояние от центральной вершины до самой удаленной
от нее вершины дерева равно радиусу
. Говоря иначе, расстояние от центральной вершины до концов
любой проходящей через центральную вершину цепи будет не больше радиуса
, т.е. после удаление центральной вершины эта цепь распадется
на цепи с диаметром, который меньше чем
. Это позволяет утверждать о справедливости следующей
теоремы.
Лемма 11. Всякое дерево будет разрушено по
критерию
при удалении центральной (центральных
вершин) вершины, т.е. когда эпицентром (эпицентрами) являются центральная
(центральные вершины) вершина,
(
), за время
. ◄
Теорема 12. Всякое дерево будет разрушено по
критерию
при удалении всех
вершин
,
, с эксцентриситетами
, т.е. когда
эпицентрами являются все вершины с эксцентриситетом
, за время
.
Доказательство.
Эксцентриситет любой из удаляемой вершины ,
, удовлетворяет неравенству
. Если
, то доказательство теоремы 12 сводится к доказательству
леммы 11. Если же эксцентриситет
, то, из дерева удаляются все периферийные вершины, что
приводит к уменьшению диаметра. Диаметр, получившегося таким образом дерева
, будет равен
.
В общем случае следует рассмотреть два типа дерева – одноцентровое
и двуцентровое.
Всякое
дерево, центр которого состоит из одной вершины, будем называть одноцентровым (или однокорневым) и
двуцентровым (или двукорневым), если
центр дерева состоит из двух смежных вершин.
У всякого однокорневого
дерева каждая смежная с центральной вершиной вершина имеют эксцентриситет
равный
. Вершины
, расстояние от которых до центрально равно 2, имеют эксцентриситет
равный
и т.д. Наконец,
вершины
, расстояние от которых до центральной равно
, имеют эксцентриситет равный
. Так расстояние между любой периферийной и центральной вершинами
равно
.
Обозначим через центральную вершину
дерева
, а через
– ту компоненту,
которой будет принадлежать вершина
, после удаления из дерева
всех вершин с
эксцентриситетами
,
. Вершины
смежные удаляемым
из дерева
окажутся висячими для
дерева
. Расстояние от этих
вершин
до вершины
останется неизменным
. Все остальные вершины дерева
находятся на таком же
или меньшем расстоянии от вершины
, поскольку в дереве
они имели меньший эксцентриситет,
чем удаленные вершины
. По этой причине вершина
останется центральной
и для дерева
, причем его радиус будет равен
. У всякого одноцентрового дерева радиус ровно в два раза
больше диаметра, что справедливо и для дерева
:
. Это удовлетворяет диаметральному критерию разрушения
одноценрового дерева, когда эпицентрами
являются все
вершин с
эксцентриситетом
(см. следствие 1.12.1).
В случае двукорневого
дерева , после удаления
всех
вершин
, дерево
также будет иметь две
смежных центральных вершины. Поэтому его диаметр будет отличаться от
однокорневого на единицу –
. ◄
Следствие 12.1. Всякое одноцентровое дерево будет разрушено по
критерию
при удалении всех
вершин
,
, с эксцентриситетами
, т.е. когда
эпицентрами являются все вершины с эксцентриситетом
, за время
. ◄
Особое место
в структурном разрушении деревьев, как и в структурном разрушении деревьев,
занимает критерий полного разрушения .
Теорема 13. Всякое дерево будет разрушено по критерию
при удалении вершины
с максимальной степенью
за время
, если
, где
.
Доказательство.
Рассмотрим дерево ,
, с равными для всех его вершин
начальными
и предельными
загрузками.
Любая вершина выйдет из стоя (будет
удалена из дерева
), если в некоторый момент времени
процесса структурного
разрушения дерева
текущая загрузка
превысит предельную
.
Предположим, что вершина смежна с вершиной
, имеющей максимальную
степень
для дерева
. Если в процессе структурного разрушения в некоторый
момент времени
из строя вышла вершина
, то в момент времени
текущая загрузка
вершины
увеличиться
и вершина
выйдет из строя.
Предположим теперь, что вершина смежна с вершиной
, степень которой
. Тогда в случае выхода из строя вершины
в момент времени
процесса структурного
разрушения из строя в следующий момент времени также выйдет и вершина
, поскольку
, а значит и
.
Поскольку эксцентриситет всякой вершины в графе
соответствует длине цепи до самой отдаленной от нее вершине, то время
структурного разрушения по критерию по
критерию при удалении вершины
с максимальной
степенью
равно
. ◄
Всякий связный циклический граф (см. рис. 4). Каждая вершина из
множество вершин
цикла
имеет степень равную
двум (см. рис. 4).
Рис. 4.
Цикл |
Очевидно, что всякий цикл утратит связность при удалении хотя бы двух несмежных вершин.
Лемма 14. Всякий цикл ,
, будет разрушен по критерию
, где
, при удалении хотя бы двух несмежных друг с другом из
вершин. ◄
Удаление двух несмежных вершин цикла
непременно приведет к
распадению его на две компоненты
и
. “Простейшей” компонентой в таком случае может быть
граф-вершина. Всякий цикл
,
,
, имеет
попарно несмежных
вершин, если
– нечетное, и
, если
– четное. Удаление из
цикла
всех попарно несмежных
вершин приведет к появлению
компонент в первом
случае и
– во втором. При
нечетном
все кроме одной
компоненты будет представлять собой граф-вершину, а при четном
все компоненты окажутся
граф-вершинами.
Лемма 14. Всякий цикл ,
,
, будет разрушен по критерию
, где
при нечетном
и
при четном
, если вершины-эпицентры попарно несмежны. ◄
Примечание 3. Для всякого
цикла ,
,
, структурное разрушение по критерию
может произойти
различными способами. Например для
цикла, изображенного на рис. 4 критерий разрушения
может быть достигнут двумя способам,
поскольку для этого графа существует два набора попарно несмежных вершин
эпицентров, причем критерий достигается в начальный
момент времени. ◄
Для всякого цикла ,
, справедливо равенство
, причем
при нечетном
, и
при четном
. Кроме того, каждая вершина цикла
является и центральной
и периферийной.
Теорема 15. Всякий цикл ,
,
, будет разрушен по критерию
при удалении двух
несмежных вершин
, т.е. когда эпицентрами
являются эти несмежные вершины.
Доказательство.
При удалении из цикла ,
,
, двух несмежных
вершин
, цикл распадется на две цепи
и
таким образом, что длина
наименьшей из них (допустим цепи
) равна
. Диаметр этой цепи равен
, цикл будет разрушен по критерию
за время
◄
Для цикла на рис. 4 при эпицентрах и
диаметральный критерий
представляет собой
.
Если в случае взять во внимание длину некратчайшей
цепи из доказательства
теоремы 15, а ее длина равна
, то справедливо
Следствие 15.1. Всякий цикл ,
,
, будет разрушен по критерию
при удалении двух
несмежных вершин
, т.е. когда
эпицентрами являются эти несмежные вершины. ◄
Примечание 4. Если
цикл имеет
эпицентров в начальный
момент процесса структурного разрушения, то целесообразно рассматривать длины
всех
,
,
,
, получившихся при удалении эпицентров. В силу
теоремы 15 и следствия 15.1 возможны различные компонентные критерии
структурного разрушения –
. ◄
Примечание 5. Для Очевидно, что для всякого структурное разрушение не возможно по компонентному критерию,
если число эпицентров меньше двух. ◄
Предположим
эпицентром цикле ,
,
, является одна из его вершин
. Пусть также
, тогда после удаление эпицентра
текущая загрузка
смежных ему вершин
станет равной
. Поэтому процесс структурного разрушения прекратиться, а его
длительность его будет равна
.
В другом
случае, когда , длительность процесса структурного разрушения
, если система не выйдет из строя при достижении
установленного критерия разрушения.
Лемма 16. Всякий цикл ,
,
,будет разрушен по критерию
при удалении одной из вершин
за время
при нечетном
и за время
при четном
, если
.
Доказательство.
После удаления в момент времени процесса структурного
разрушения эпицентра из цикла
к началу момента
времени
получим цепь длины
, эпицентрами которой являются ее концы. Поскольку для каждой
вершины
верно
, к следующему моменту времени
получим цепь длины
. В случае с нечетным
последние две вершины
цикла будут разрушены за
, в случае с четным
последняя вершина цикла
будет разрушена за
. ◄
Рис. 5.
Структурное разрушение 6-ти
вершинного и 5-ти вершинного циклов |
На рис. 5 показан процесс структурного разрушения 5-ти вершинного (справа) и 6-ти вершинного (слева) циклов. Пунктирными окружностями выделены эпицентры в каждом из моментов времени процесса структурного разрушения.
Примечание 6. Если
цикл имеет
эпицентров в начальный
момент процесса структурного разрушения и для его вершин справедливо
, то целесообразно
рассматривать длину максимальной цепи всех
,
, получившихся при удалении эпицентров. Поскольку в силу
теоремы 15, следствия 15.1 и леммы 16 время полного структурного
разрушения цикла
будет равно
при нечетном
и
при нечетном
. ◄
Полный -вершинный граф
сильно связная
структура, поэтому критерий связности при его структурном разрушении может быть
достигнут при
эпицентрах.
Аналогичная ситуация и в случае с компонентном критерием. Он равен
.
Поскольку в полном графе диаметр и радиус равны
, то каждая его вершина одновременно является и центральной и
периферийной. Удалив из полного графа
любую вершину получим
полный граф
с равными диаметром и
радиусом
. Удалив из полного графа
получим полный граф
. Эти рассуждения позволяют заключить, что при структурном
разрушении возможно достижение только диаметрального критерия
.
Лемма 17. Всякий полный граф будет
разрушено по критерию
при удалении вершины
за время
, если
.
Доказательство.
После удаления из полного графа эпицентра
к началу момента
времени
получим полный граф
. По истечению момента времени
каждая вершина графа
будет иметь текущую
загрузку
. Поэтому время полного структурного разрушения полного графа
равна
(см. рис. 6). ◄
Во всех предыдущих параграфах настоящей главы проведено исследование процесса структурного разрушения классов графов, обладающих некоторыми метрическими и топологическими особенностями, упростившими эти исследования.
Вместе с тем, проведенные исследования позволяют сформулировать ряд результатов и для произвольного случая обыкновенного графа.
Рис. 6. Полное структурное разрушение полного 4-х вершинного графа |
Теорема 18. Всякий граф будет разрушен по критерию
при удалении вершины
с максимальной
степенью
за время
, если
, где
.
Доказательство.
Рассмотрим граф , выделим вершину
такую, что
. Вообще говоря, вершин с максимальной степенью на графе
может быть несколько, вершина
одна из них. Далее
выделим на графе
остовное дерево
такое, что все
инцидентные вершине
ребра будут включены в
. Согласно теореме 12 дерево
с максимальной
степенью
будет разрушено за
время
по критерию полного
разрушения при единственном эпицентре
.
Выделим на дереве вершину
. Рассмотрим остовный подграф
, где
,
и инцидентно вершине
(т.е. рассмотрим граф
полученный из дерева
добавлением ребра
, инцидентного вершине
в графе
). Очевидно, ребро
будет входит в единственный
цикл графа
. Проведенное преобразование дерева
никак не повлияет на
процесс структурного разрушения графа
. Степени вершин
,
, в новом графе
окажутся меньше
максимальной степени вершины графов
,
и
:
,
. Поэтому процесс структурного разрушения графа
по критерию полного
разрушения с эпицентром в вершине
с максимальной
степенью
пройдет за время
.
Если к остовному подграфу продолжать добавлять ребра
из
, но не содержащиеся в
, в результате получим граф
. Очевидно, что все получаемы промежуточные остовные графы
при добавлении ребер будут иметь одно и тоже время полного структурного
разрушения
в случае с эпицентром
в вершине с максимальной степенью. А значит и сам граф
будет разрушен по критерию
при удалении вершины
с максимальной
степенью
за время
. ◄
Следствие 18.1. Всякий граф будет разрушен по критерию
при удалении вершины
за время
, если
, где
– максимальная степень
графа
. ◄
Построена математическая модель структурного разрушения сложной системы. Введены четыре критерия выхода системы из строя – критерий полного разрушения, критерий связности, компонентный критерий и диаметральный критерий.
Исследован процесс структурного разрушения для различных классов обыкновенных графов – цепей, циклов, деревьев и простых произвольных графов. Для каждого класса исследованных графов по каждому из предложенных критериев получены оценки времени структурного разрушения. Установлена связь между времени структурного разрушения с количеством эпицентров и их расположением на графах.
Построенная модель в целом расширяет спектр дискретных математических моделей и область приложений теории графов. В соответствии с идеями структурной динамики на основе предложенной модели наравне с понятием клеточного автомата [6] целесообразно использование понятие графового автомата, что также расширяет описательные возможности теории графов.
Авторы выражают искреннюю признательность профессору Малинецкому Г.Г. за внимание к этой и многим другим работам.
1.
Владимиров В.А., Кульба В.В.,
Малинецкий Г.Г, Махутов Н.А. и др. Управление риском. – М.: Наука, 2000.
2.
Архипова Н.И., Кульба В.В.
Управление в чрезвычайных ситуациях. – М.: РГГУ, 1998.
3.
Кочкаров А.А., Малинецкий Г.Г. Обеспечение стойкости сложных систем. Структурные
аспекты: . – М.: ИПМ им. М.В. Келдыша РАН, № 53, 2005.
4.
Емеличев В.А., Мельников О.И., Сарванов В.И.,
Тышкевич Р.И. Лекции по теории
графов. - М.: Наука, 1990.
5.
Форд Л.,
Фалкерсон Д. Потоки в сетях. - М.: Мир, 1966.
6.
Тоффоли Т., Марголус Н. Машины клеточных автоматов.
- М.: Мир, 1991.
[1] Здесь и далее символом “◄” будем обозначать окончание алгоритмов, доказательств лемм, теорем, утверждений, примечаний и т.п..