Сети связи

                    

                      Рисунок 3 – Матрица смежности

Основным преимуществом  матрицы смежности является тот  факт, что за один шаг можно узнать, существует ли ребро, связывающее узел x с узлом y. Недостатком же является то, что независимо от числа ребер объем занимаемой памяти равен n² ячеек.

Более экономным в смысле расхода памяти является метод представления  графа с помощью списка пар вершин, соответствующим его ребрам. Для графа на рисунке 1 список пар вершин,  будет иметь следующий вид (рисунок 4)

 

 

1	2	0
1	3	0
1	6	0
2	4	0
2	5	0
3	6	0
3	7	0
4	8	0
5	1	0
5	6	0
5	10	0
5	12	0
6	9	0
6	11	0
7	9	0
8	12	0
8	14	0
9	13	0
9	15	0
10	11	0
10	14	0
11	15	0
12	16	0
13	18	0
14	15	0
14	16	0
14	17	0
15	17	0
15	18	0
16	17	0
17	18	0

                

                    

                        Рисунок 4 – Список пар вершин

Во многих случаях лучшим способом описания графов является структура  данных, называемая списком инцидентности. Она содержит для каждой вершины, помеченной признаком «начало», список вершин инцидентных, к данной вершине. Каждый список вершин заканчивается признаком «конец». Размерность такой структуры m+n для ориентированного графа и n + 2m для неориентированного графа. На рисунке 5 приведен список инцидентности для графа (рисунок 1).

                   нач.1 – 8 – 9 - 7 кон.

                   нач.2 – 7 – 14 – 12 кон.

                   нач.3 – 12 – 10 – 9 кон.

                   нач.4 – 12 – 8 кон.

                   нач.5 – 9 – 13 – 7 – 8 – 14 кон.

                   нач.6 – 8 – 13 – 12 – 8 – 12 кон.

                   нач.7 – 10 – 9 кон.

                   нач.8 – 8 – 11 кон.

                   нач.9 – 8 – 7 – 9 кон.

                   нач.10 – 7 – 10 – 9 кон.

                   нач.11 – 10 – 12 кон.

                   нач.12 – 8 – 11 – 8 кон.

                   нач.13 – 9 – 14 кон.

                   нач.14 – 10 – 14 – 13 – 9 – 11 кон.

                   нач.15 – 7 – 10 – 14 – 9 – 9 кон.

                   нач.16 – 8 – 9 – 12 кон.

                   нач.17 – 8 – 9 – 12 – 13 кон.

                   нач.18 – 14 – 8 – 9 кон.

              Рисунок 5 – Список инцидентности

Описание графа в виде списка инцидентности благодаря  признакам «нач.» и «кон.» может  выполняться не в виде таблицы, а  в виде строки, что позволяет значительно  экономить занимаемую описанием  графа память. 

 

    5 ОПРЕДЕЛЕНИЕ СВЯЗНОСТИ УЗЛОВ КОММУТАЦИИ СЕТИ СВЯЗИ НА ОСНОВЕ ТЕОРИИ ГРАФОВ

 

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

  - метод позволяет  легко вставить себя в алгоритм  решаемой задачи;

            - каждое ретро графа анализируется   не более одного раза (или число  раз, ограниченное).

                           5.1 Поиск в ширину в графе

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

Поиск проведем для вершины графа, заданного на рисунке 1, V_o = 1.

1                              использована                           1

2 3 5 6                     использована                       12356

4 7 9 10 11 12         использована                   1 2 3 4 5 6 7 9 10 11 12

8 13 14 15 16        использована     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

17 18          использована          1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Новых вершин нет – конец.

Данный алгоритм анализирует  каждую вершину в точности один раз. Сложность данного алгоритма  К(m + n).

 

 

6 ОПРЕДЕЛЕНИЕ КРАТЧАЙШИХ ПУТЕЙ МЕЖДУ УЗЛАМИ КОММУТАЦИИ СЕТИ    СВЯЗИ

№	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	Опред. вершина
1	0	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞
2	-	7	9	∞	9	8	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	2(7)
3	-	-	9	19	21	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	3(9)
4	-	-	-	19	21	21	19	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	4(19)
5	-	-	-	-	21	21	19	27	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	7(19)
6	-	-	-	-	21	21	-	27	28	∞	∞	∞	∞	∞	∞	∞	∞	∞	5(21)
7	-	-	-	-	-	34	-	27	28	28	∞	29	∞	∞	∞	∞	∞	∞	8(27)
8	-	-	-	-	-	34	-	-	28	28	∞	38	∞	38	∞	∞	∞	∞	9(28)
9	-	-	-	-	-	36	-	-	-	28	∞	38	37	38	35	∞	∞	∞	10(28)
10	-	-	-	-	-	36	-	-	-	-	37	38	37	38	35	∞	∞	∞	15(35)
11	-	-	-	-	-	36	-	-	-	-	45	38	37	49	-	∞	44	44	6(36)
12	-	-	-	-	-	-	-	-	-	-	48	38	37	49	-	∞	44	44	13(37)
13	-	-	-	-	-	-	-	-	-	-	48	38	-	49	-	∞	44	51	12(38)
14	-	-	-	-	-	-	-	-	-	-	48	-	-	49	-	46	44	51	17(44)
15	-	-	-	-	-	-	-	-	-	-	48	-	-	57	-	56	-	52	11(48)
16	-	-	-	-	-	-	-	-	-	-	-	-	-	57	-	56	-	52	18(52)
17	-	-	-	-	-	-	-	-	-	-	-	-	-	57	-	56	-	-	16(56)
18	-	-	-	-	-	-	-	-	-	-	-	-	-	65	-	-	-	-	14(65)
О.в.	0	7	9	19	21	36	19	27	28	28	48	38	37	65	35	56	44	52

 

 

                         Таблица 6 – Веса определенных вершин

 

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

Для рассматриваемого варианта кратчайший путь 1-2-3-5-6-11-14.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

             7 ОПРЕДЕЛЕНИЕ ПРОПУСКНОЙ СПОСОБНОСТИ СЕТИ СВЯЗИ

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

(3.1)

где:

- div f(i)- дивергенция потока в i- том узле;

- - суммарный поток, выходящий из узла i в узел j;

- - суммарный поток, входящий в узел i  от узла j;

1) то f(S,T) называют исходящим потоком, 

       - f(S,T) -входящим потоком.

2) Причем f(S,T) =│- f(S,T)│ т.е. сколько информации выходит из узла-источника - столько ее и приходит в узел - получателя.

3) Дивергенция в любом  другом узле сети связи (кроме  S и T) равно 0.

Поток, удовлетворяющий таким  условиям, называется допустимым потоком. Рассмотрим сеть связи, представленной графом на рисунке 3. Проводим распределение начального потока. C=9, S=1, T=15, Fнач.=3.

 

 

 

 

                            Рисунок 7 – Граф сети

div f (1)=3-0=3

div f (15)=0-3=-3

div f (2)=2-2=0

div f (3)=1-1=0

div f (4)=2-2=0

div f (5)=3-3=0

div f (6)=3-3=0

div f (7)=1-1=0

div f (8)=2-2=0

div f (9)=1-1=0

div f (10)=2-2=0

div f (11)=2-2=0

div f (12)=2-2=0

div f (13)=0-0=0

div f (14)=2-2=0

div f (16)=2-2=0

div f (17)=1-1=0

div f (18)=1-1=0

т.е. начальное распределение  потока является допустимым.

2.Определим пути наращивания потока по формуле

,

 

 

 

 

С полученными данными  вводим корректировку в распределение  потока на графе сети связи.В дальнейшем путей наращивания потока по ветвям сети связи нет. Максимальный поток  f_max(1;15) =27 при этом, исходящий поток из узла-источника f_max (1)= 27  и входящий поток в узел получателя f_max (15)= -27.