Сети связи

   СОДЕРЖАНИЕ

1. ВВЕДЕНИЕ ………………………………………………………

2. ИСХОДНЫЕ ДАННЫЕ…………………………………………………………

3.ОСНОВНЫЕ ПОНЯТИЯ И  ОПРЕДЕЛЕНИЯ ТЕОРИИ ГРАФОВ…………

4.СПОСОБЫ ОПИСАНИЯ ГРАФОВ…………………………………………

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

5.1.ПОИСК В ШИРИНУ В  ГРАФЕ………………………………………..

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

7.ОПРЕДЕЛЕНИЕ ПРОПУСКНОЙ  СПОСОБНОСТИ (МАКСИМАЛЬНОГО ПОТОКА) СЕТИ СВЯЗИ.............................................................................

   ЗАКЛЮЧЕНИЕ…………………………………………………………………..

   СПИСОК  ЛИТЕРАТУРЫ……………………………………………

                                               

 

 

 

 

 

 

 

 

 

 

 

                                          Введение

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

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

Впервые основы теории графов появились в работе Л.Эйлера, где  он описывал решения головоломок  и математических развлекательных  задач. Широкое же развитие теория графов получила лишь в 50-х годах ХХ века в связи со становлением кибернетики  и развитием вычислительной техники.

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

 

 

 

 

 

 

                                 1 ИСХОДНЫЕ ДАННЫЕ

Вариант 1

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

 

Вариант графа	Метод поиска	S	T	Fнач	С
1	Ш/Д	1	15	3	9

 

 

 

 

 

 

 

 

 

 

 

          3 ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ     ГРАФОВ             

 

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

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

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

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

Определим основные понятия, которыми будем манипулировать в  дальнейшем.Граф G – это совокупность двух конечных множеств: множества V, содержащего n вершин (точек) и множества W, содержащего m неупорядоченных пар вершин.Каждую пару x = {n, m} вершин в W называют ребром графа G и говорят, что x соединяет n и m.Ребра, имеющие одинаковые концевые вершины, называются параллельными.Вершина и ребро называются инцидентными друг к другу, если вершина является для этого ребра концевой точкой. Граф G называется связным, если для любых двух его вершин существует путь, их соединяющий. В противном случае граф G называется  несвязным. Взвешенным называется граф, в котором вершинам и ребрам поставлены в соответствие некоторые числа, называемые весами. Такой граф также называется сетью.

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

 

 

 

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

                         3.2 СПОСОБЫ ОПИСАНИЯ ГРАФОВ

      

          Очевидно, что наиболее понятный и полезный для человека способ представления графа – изображение его на плоскости в виде точек и соединяющих их линий – будет совершенно бесполезным, если мы захотим решить задачи, связанные с графами, с помощью ЭВМ.В теории графов классическим способом представления графа являются матрица инциденций. Это матрицы с n строками и m  столбцами. Для неориентированного графа, столбец, соответствующей ветви (x, y) содержит 1 в строках, соответствующих вершинам x и y, и 0 в остальных строках. Изобразим матрицу инциденций (рисунок 2).

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

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

 

 

 

 

 

 

 

 

 

 

 

 

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

                           

                             Рисунок 2 – Матрица ициденций

Лучшим способом представления  графа является матрица смежности (связности), определяемая как матрица B = [b_i,j] размера n x n, где b_i,j = 1, если существует ребро, ведущее из вершины i в вершину j и b_i,j = 0 в противном случае. На рисунке 3 представлена матрица смежности.

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