8.2. Графовая модель сети

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

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

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

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

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

Введем некоторые понятия и обозначения.

Граф (см. Рис.8.1) состоит из множества

b₂₃

y₂ ○ ○ y₃

b₁₂ b₂₄ b₃₄

y₁ ○ b₃₅

b₁₅ ○ y₄

y₅ ○

Рис.8.1

Вершин Y={y₁, y₂, …, y_n} и множества ветвей B={b(i, j )…}, соединяющих вершины друг с другом определенным образом. Множества Y и B конечны. Граф обозначается символом Г=(Y, B).

Узел связи информационной сети отождествляется с вершиной графа, линия связи – с ветвью. Ветви b(i, j ) могут быть ориентированы – направлены из вершины y_i в вершину y_j. Для этого используются линии со стрелкой. Говорят: ветвь b(i, j ) инцидентна вершине y_i по выходу, а вершине y_j – по входу, если вершина y_i начальная, а y_j – конечная.

Вместо обозначений b(i, j ) часто используют номера ветвей: b₁, b₂,…, b_L.

Взвешенные графы те, в которых вершинам и ветвям соответствуют некоторые числа, называемые весами. Например, вершинам приписываются веса: P(i), C(i)…, где i - номер узла, ветвям веса: C(i,j) – пропускная способность, P(i,j) – вероятностные характеристики, l(i,j) – длина ветвей и т.д.

Характеристики узлов и линий сети сводятся в матрицы типа:

• связности B=║β_ij║, где β_ij=1, если в сети существует ветвь b(i,j), или β_i=0, если ветви b(i,j) нет.

• длин ветвей L=║l_ij║,

• емкостей ветвей C=║c_ij║,

• надежности P=║p_ij║,

• инцидентности U=║u_ij║ и т.д.

Пусть между вершиной i₁, где возникает информационный поток, и вершиной i_k, где он завершает свое движение обозначается символом μ_j(i₁, i_k). Индекс j на номер пути, поскольку путей следования может быть несколько. Следует учесть, что путь не должен содержать повторяющихся одних и тех же элементов. Каждый путь характеризуется многими параметрами: число промежуточных элементов, длина пути, пропускная способность, надежность и т.д.

Для удобства анализа сети полезно строить дерево путей – графическое представление путей от определенного пункта ко всем другим пунктам.

Перечень путей с характеристиками заводится в таблицы путей.

Общее число ветвей инцидентных вершине называют степенью d(j) вершины.

Путь от узла y_k к узлу y_k через несколько элементов называют циклом, а этот же путь, образованный одной ветвью b(k, k) называют элементарной петлей.

Говорят, что граф связан, если для любой пары вершин y_i и y_j существует хотя бы один путь μ(i, j). Если нет, то граф несвязный.

Сечением (по ветвям) называют множество ветвей, исключение которых порождает граф с двумя компонентами.

Сечением (по вершинам) называют минимальное множество вершин, изъятие которых делит граф на две и более компонент.

Деревом T=(Y, B) графа Г=(Y, B) называют связный подграф T, содержащий все вершины Г и не содержащий ни одного цикла.