Сети связи

Автор: Пользователь скрыл имя, 11 Марта 2013 в 21:04, курсовая работа

Описание работы

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

Содержание

1. ВВЕДЕНИЕ ………………………………………………………
2. ИСХОДНЫЕ ДАННЫЕ…………………………………………………………
3.ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ ГРАФОВ…………
4.СПОСОБЫ ОПИСАНИЯ ГРАФОВ…………………………………………
5.ОПРЕДЕЛЕНИЕ СВЯЗНОСТИ УЗЛОВ КОММУТАЦИИ СЕТИ СВЯЗИ НА ОСНОВЕ ТЕОРИИ ГРАФОВ……………………………………..
5.1.ПОИСК В ШИРИНУ В ГРАФЕ………………………………………..
6.ОПРЕДЕЛЕНИЕ КРАТЧАЙШИХ ПУТЕЙ МЕЖДУ УЗЛАМИ КОММУТАЦИИ СЕТИ СВЯЗИ МЕТОДОМ ДЕЙКСТРЫ……………
7.ОПРЕДЕЛЕНИЕ ПРОПУСКНОЙ СПОСОБНОСТИ (МАКСИМАЛЬНОГО ПОТОКА) СЕТИ СВЯЗИ.............................................................................
ЗАКЛЮЧЕНИЕ…………………………………………………………………..
СПИСОК ЛИТЕРАТУРЫ……………………………………………

Работа содержит 1 файл

курсовая.docx

— 70.17 Кб (Скачать)

   СОДЕРЖАНИЕ

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 = [bi,j] размера n x n, где bi,j = 1, если существует ребро, ведущее из вершины i в вершину j и bi,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

Информация о работе Сети связи