- •2. Основные понятия математического моделирования
- •2. Принципы построения математических моделей
- •3.Классификационные признаки и классификация моделей
- •1.Основные этапы математического моделирования
- •2. Понятие о вычислительном эксперименте
- •3.Оценка свойств моделей
- •2.1. Метод нелинейного преобразования, обратного функции распределения
- •2.2. Метод суперпозиции
- •2.3. Некоторые специальные методы моделирования случайных величин
- •2.3.1. Метод Неймана
- •3.2. Метод кусочной аппроксимации
- •2.4. Моделирование векторных случайных величин
- •Раздел 2. Модели и методы исследования структурных свойств сетей связи
- •2. Изоморфность графов
- •1. Подграфы и дополнения
- •2. Деревья, разрезы, циклы
- •1. Матрица циклов и ее связь с матрицей инцидентности.
- •2.Матрица разрезов и ее связь с матрицей циклов
- •Матрицы смежности и перечисления путей
- •2. Связность
- •1. Степенная последовательность вершин графа
- •2. Алгоритм синтеза графов с максимальной связностью
- •3. Алгоритмы синтеза графов с максимальной связностью при заданном числе вершин и ребер.
- •4.Однородные графы. Мера неоднородности.
- •Модели и методы оценки разведзащищенности сетей связи
- •1.Показатели разведзащищенности сетей связи.
- •2.Модель оценки разведзащищенности сети связи.
- •Матрица смежности графа а
- •Матрица смежности графа в
- •Зависимость разведзащищённости от степени неоднородности сетей
- •5. Синтез сетей связи, оптимальных по показателям структурной устойчивости и разведзащищенности.
- •3.1. Моделирование марковских случайных процессов
- •3.2. Разностные и дифференциальные стохастические уравнения
- •2. Понятие эквивалентной функции стохастической сети
- •1.Метод двухмоментной аппроксимации.
- •3.Разложение на простые дроби.
- •3. Общие правила моделирования исследуемых процессов
Зависимость разведзащищённости от степени неоднородности сетей
Количественная мера неоднородности, механизм получения графических последовательностей с различной степенью неоднородности и алгоритмы построения эталонных графов по этим последовательностям рассмотрены ранее.
Множество графических степенных последовательностей Пi вместе с соответствующими характеристиками приведены в таблице2.
Полученные результаты исследования приведены на рис.10. и на первый взгляд, кажутся неожиданными и даже противоестественными, поскольку однородные структуры распознаются с большей вероятностью, чем неоднородные при одинаковой вероятности обнаружения ребра.
i=1i=16
i=7i=8
Рис.9. Графы последовательностей 1,7,8 и 16
Рис.10. Графики зависимости вероятности распознавания от времени и от дисперсии степени вершин
Причина этого заключается в том, что алгоритм распознавания изоморфности прекращает работу, как только одна из реализаций случайного розыгрыша становится изоморфной или изоморфно вкладывается в граф-эталон .
Однако, с уменьшением степени неоднородности графа возрастает число автоморфизмов графа, т.е. число изоморфизмов графа на себя.
Теоретически число вариантов построения графа определяется числом групп с одинаковыми степенями вершин и числом таких вершин, входящих в группу:
, , 1≤L ≤ n
где N- число вариантов построения графа;
n- число вершин графа;
L- число групп вершин с одинаковыми степенями;
ki- число вершин в группе.
При L=N , т.е. когда количество различимых групп равно количеству различимых вершин, (все вершины имеют разные степени) существует всего один вариант построения графа. При L=1, N=n!.
Реальное число вариантов ограничивается особенностями алгоритма построения графа по заданной графической последовательности.
Максимальное число вариантов получается когда di=6. Покажем пример подсчета числа вариантов для последовательности с наибольшим числом вариантов.
vi1 2 3 4 5 6 7 8 9 10 11 12
di6 6 6 6 6 6 6 6 6 6 6 6 П16
Первую вершину можно выбрать 12 способами, далее нужно выбрать 6 вершин из оставшихся 11. Это можно сделать , таким образом первый шаг можно выполнить 12.462=5444 способами.
Второй шаг:
vi8 9 10 11 12 2 3 4 5 6 7 1
di6 6 6 6 6 5 5 5 5 5 5 0
Первую вершину можно выбрать 5 способами, порядок следующих 4х, имеющих степень 6 не играет роли. 6, 7-ю вершину со степенью 5 можно выбрать одним из способов, таким образом второй шаг можно сделать 15х5 =75 способами.
Третий шаг:
vi9 10 11 12 4 5 6 7 2 3 1 8
di5 5 5 5 5 5 5 5 4 4 0 0
Первую вершину можно выбрать 8-ю способами, вторую группу вершин (5) можно выбрать способом, таким образом третий шаг можно выполнить 8х21=168 способами.
Четвертый шаг:
vi6 7 10 11 12 4 5 2 3 1 8 9
di5 5 4 4 4 4 4 4 4 0 0 0
Первую вершину можно выбрать 2-мя способами, вторую группу вершин (со степенью di =4) можно выбрать способами, таким образом четвертый шаг можно выполнить 2х35=70 способами.
Пятый шаг:
vi7 5 2 3 10 11 12 4 1 8 9 6
di4 4 4 4 3 3 3 3 0 0 0 0
Первую вершину можно выбрать 4-мя способами, вторую группу вершин (со степенью di =3) можно выбрать 4 способами, таким образом четвертый шаг можно выполнить 4х4=16 способами.
Шестой шаг:
vi5 2 3 11 12 4 10 1 8 9 6 7
di3 3 3 3 3 3 0 0 0 0 0 0
Первую вершину можно выбрать 6-ю способами, вторую группу вершин (со степенью di =3) можно выбрать способами, таким образом шестой шаг можно выполнить 6х10=60 способами.
Седьмой шаг:
vi12 4 10 2 3 11 1 8 9 6 7 5
di3 3 2 2 2 2 0 0 0 0 0 0
Первую вершину можно выбрать 2-мя способами, вторую группу вершин (со степенью di =2) можно выбрать способами, таким образом седьмой шаг можно выполнить 6х2=12 способами.
Восьмой шаг:
vi4 3 11 10 2 1 8 9 6 7 5 12
di2 2 2 1 1 0 0 0 0 0 0 0
Первую вершину можно выбрать 3-мя способами, восьмой шаг может быть выполнен 3 способами.
Девятый шаг:
vi3 11 10 2 1 8 9 6 7 5 12 4
di1 1 1 1 0 0 0 0 0 0 0 0
Первую вершину можно выбрать 4-мя способами, девятый шаг также может быть выполнен 4-мя способами.
Десятый шаг:
vi10 2 3 4 5 6 7 1 8 9 11 12
di1 1 0 0 0 0 0 0 0 0 0 0
Десятый шаг –соединение 10 и 2 вершины, можно выполнить 2-мя способами, однако, поскольку графы не ориентированы, то порядок соединения не играет роли, поэтому число вариантов 10-го шага –1.
Общее число вариантов равно сумме вариантов на каждом шаге, таким образом для последовательности П16 существует 5953 изоморфных графа.
Число вариантов для других последовательностей показано в таблице 1.
Изоморфность графов проверялось по ходу их построения.
Таким образом, графики на рис.3 необходимо интерпретировать как вероятность распознавания хотя бы одного из изоморфных графов, построенных по графической последовательности, обладающей заданной степенью неоднородности.
Вероятность распознавания конкретной структуры Ркс по полученной вероятности распознавания типовой структуры Ртс, можно получить из следующего соотношения:
РТС=1-(1-РКС)N, откуда , или, или. Графки для пересчета РТС в РКС в зависимости от числа вариантов показаны на рис.11.
Рис. 11. Графики нахождения вероятности распознавания конкретной структуры
При N=1, соответственно lgN=0, РТС = РКС . для того, чтобы получить значение РКС , необходимо иметь с графика рис.3 значение РТС , определить из таблицы №1 значение N и по этим двум параметрам с графики рис.4 снять значение РКС.