Схема сети. 
Применение математического аппарата для анализа компьютерной сети страховой компании

Площадь компании составляет 270 м2. Здание состоит из 7 кабинетов с центральным коридором.

Компьютеры в предприятии расположены вдоль стены. Между собой они соединяются при помощи витой пары, которая вкладывается в кабель-канал, прикрепленный к стене, также подключаются к коммутатору.

В организации имеется 14 рабочих станций, которые объединены в корпоративную сеть.

Под логической структурой сети понимается ее организация на 3-м и выше уровнях модели OSI, т. е. сетевые протоколы, адресация, взаимодействие рабочих станций с серверами. В качестве основного сетевого протокола в вычислительной сети Предприятия используется протокол IP. Адреса на сетевом уровне для рабочих станций задаются динамически по протоколу DHCP.

Рисунок 1 — Логическая схема сети На данной логической схеме отображена топология расширенная звезда. В схеме показаны необходимые компоненты сети: коммутатор, 14 компьютеров, Web-сервер и сервер.

Использование теории графов для анализа сети

Теория графов в качестве теоретической дисциплины может рассматриваться как раздел дискретной математики, исследующий свойства конечных множеств (бесконечные графы рассматривать мы не будем) с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие технические, экономические, биологические и социальные системы. Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

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

Рисунок 2 — Пример графа Способы задания графов:

• А) Матрица инцидентности A. По вертикали указываются вершины, по горизонтали - ребра. aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в вершину i входит ребро j. Если ребро - петля, то aij=2.
• Б) Список ребер. В первом столбце ребра, во втором вершины им инцидентные.
• В) Матрица смежности - квадратная симметричная матрица. По горизонтали и вертикали - все вершины. Dij= число ребер, соединяющее вершины i, j.
• Г) Матрица Кирхгофа. bij=-1, если вершины i и j смежны, bij=0 если вершины i и j не смежны, bii = deg (i). Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0.

Путями в графах называется последовательность дуг этого графа, такая что каждая начальная точка новой дуги является концом предыдущей. Длиной пути называется число дуг, входящих в путь L (M).

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

Если начало пути графа совпадает с концом, то такой граф называется контуром. Контур единичной длины является петлей в графе.

Основные виды графов:

• А) Симметричный граф — граф, в котором две смежные вершины соединены противоположно ориентированными дугами.
• Б) Ориентированный граф — это граф, на котором указаны стрелки на каждом ребре. Неориентированный граф не имеет стрелок.
• В) Полный граф — это когда любые две вершины соединены хотя бы одним ребром.
• Г) Сильно связным граф является, когда для любых двух вершин существует путь из одной вершины в другую.
• Д) Эйлеровым путем в графе называется путь, содержащий все ребра графа. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа.
• Е) Гамильтонов путь — путь, содержащий каждую вершину графа ровно один раз.

Рисунок 3 — Эйлеров граф Нахождение минимального пути по алгоритму Краскала Алгоритм Краскала - алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Краскалом в 1956 году.

Алгоритм нахождения кратчайшего пути:

• А) Выбираем ребра наименьшей длины
• Б) Из оставшихся ребёр вновь выбираем наименьшей длины
• В) Выбираем ребра наименьшей длины при условии, что оно не образует цикла с рёбрами, выбранными в пунктах 1, 2
• Г) Из оставшихся рёбер выбираем то, которое меньшей длины и не образовывает цикла с рёбрами, выбранными в пунктах 1-3

Для того, чтобы найти минимальный путь в приведенной выше сети, возьмем для рассмотрения небольшую часть этой сети. Для построения графа возьмем компьютеры под номерами: 1, 2, 3, 4, 5, 6 и Ком 2.

Рисунок 4 — Участок сети № 1.

В приведенной ниже таблице размещены числовые значения для каждой дуги графа.

Таблица 1 — Числовые значения дуг.

Вычислим число ребер в полном графе по формуле:

m=n*(n-1)/2, (1).

где m — число ребер, n — число вершин Для данного графа m = 21.

Высчитаем число шагов, за которые мы найдем наименьший путь по следующей формуле:

T=m-y (2).

? находим по еще одно формуле:

y = m-n+k, (3).

где k=1.

В данном графе наименьший путь мы найдем за 6 шагов.

Шаг 1: Выберем любой самый короткий путь, например ПК26 ПК27. Числовое значение этой дуги равно 1.

Шаг 2: Так же произвольно выбираем еще один путь, учитывая длину. Возьмем ПК29 ПК31 = 1.

Шаг 3: Оставшиеся четыре шага мы выбираем кратчайшие пути. При правильном выборе не должны образовываться петли. Берм дугу между ПК25 и ПК26. Она равна 2.

Шаг 4: ПК28 ПК31= 2.

Шаг 5: ПК26 ПК31= 3.

Шаг 6: ПК29 ПК30 = 3.

Считаем общий путь. Для этого необходимо сложить все дуги.

1+1+2+2+3+3= 12.

Наименьший путь в данном графе равен 12.

Построение матрицы смежности Матрица смежности - один из способов представления графа в виде матрицы.

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) - это квадратная матрица Aразмера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.

Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали. Матрица смежности и cписки смежности являются основными структурами данных, которые используются для представления графов в компьютерных программах.

Свойства матриц смежности:

• — если граф симметричен, то его матрица тоже смежности тоже симметрична
• — элементами матрицы A (G) являются целые положительные числа и число ноль
• — Сумма элементов матрицы A (G) по i-й строке (или по i-му столбцу) равна степени соответствующей вершины d (xi)

— В графе, имеющей матрицу смежности, А существует путь длины л, если не равна 0. В графе не существует контуров тогда и только тогда, когда.

=0, начиная с некоторого k.

Рассмотрим новый участок сети для построения матрицы смежности.

В граф будут входить следующие элементы сети: коммутатор 1, коммутатор 4, коммутатор 5, 4 ПК под номерами 11, 12, 13, 14.

Рисунок 5 — Участок сети № 2.

Построим граф.

Рисунок 6 — Граф участка сети № 2.

В данном графе черные дуги обозначают физическое соединение между устройствами, а красные — только логическое.

Для данного графа построим матрицу смежности A = (), где — число дуг, идущих из вершины в вершину .

А=.

Проанализировав матицу, можно сделать некоторые выводы:

• — диагональ матрицы содержит только нули, следовательно, матрица не имеет петель;
• — нет таких вершин, которые соединялись бы между собой более чем одной дугой, потому что матрица содержит только 0 и 1.

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

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

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

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

Изобразим участок сети № 2, из предыдущего пункта, в виде информационного графа.

Рисунок 7 — Информационный граф ПК11 — исходные данные К1 — конечный результат К5, К4, ПК12, ПК13, ПК14 — промежуточные вершины Каждый информационный граф содержит вершины каждая, из которых имеет отношение порядка.

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

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

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

А =

Так как последний столбец 0, то вершина С — исходные данные. Главная диагональ 0 — граф без петель. Третья строка 0, значит вершина К — конечный результат.

Найдем порядки вершин.

Таблица 2 — Порядки вершин.

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

Построение матрицы инцидентности графа Матрица инцидентности - одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро (дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки - вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).

Матрица будет матрицей инцидентности дуг, если у нее нет одинаковых столбцов. В каждом столбце содержится только одна 1 и одна -1. Вся матрица состоит только из 0 и + — 1.

Рисунок 7 — Граф для участка сети № 2.

Нахождение наибольшего потока сети Теория потока в сети является одной из наиболее развитых и изящных исследований в теории графов.

Транспортной сетью (сетью) называется граф без петель с конечным числом вершин, если каждой дуге поставлено в соответствие некоторое число которое является пропускной способностью дуги и выполняются следующие условия:

• — существует только одна вершина X₀ из которой дуги только исходят, эта вершина называется источником;
• — существует только одна вершина Z в которую дуги только приходят, эта вершина называется выходом из сети;

Потоком в транспортной сети называется функция, определенная на множестве U-дуг сети, которое принимает целое неотрицательное значение, такое что выполняются 2 условия:

— значение этой функции для дуги U не превосходит пропускную способность этой дуги U. ;

— для каждой вершины X сети (кроме X₀ и выхода Z) сумма значений функции на дугах входящих в вершину X равна сумме значений функций на дугах исходящих из этой вершины.

Обозначения:

— реальное значение тех данных, которые передаются по дуге;

- множество всех дуг сети заходящих в вершину X;

- множество всех дуг сети исходящих из вершины X.

Пусть X — множество всех вершин в сети.

А — подмножество множества X, причем, а .

Множество дуги сети концы которых содержатся в множестве А. такое множество называют разрезом сети.

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

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

Посчитаем наибольший поток участка сети № 2.

Рисунок 8 — Граф для нахождения наибольшего потока в сети Таблица 3 — Пропускная способность дуг.

Возьмем некоторые множества дуг сети:

Составим разрезы сети этих множеств:

Найдем пропускную способность каждого разреза:

4 + 9 + 5 = 25.

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