Математическая модель информационной сети

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

Некоторые сведения из теории графов

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

Граф — это совокупность множества вершин X, множества ребер Y и отображение инцидентности f, которое ставит в соответствие каждому ребру пару вершин.

Смежные вершины— это вершины, соединенные ребром, смежные рёбра— это рёбра, у которых общая вершина. Вершина и ребро инцидентны друг другу, если точка — конец ребра .

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

Петля — это ребро (или дуга), инцидентное только одной вершине.

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

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

Параллельные рёбра — это рёбра, инцидентные одной паре вершин.

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

Цикл — это замкнутая цепь (простой цикл, если цепь простая).

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

Подграф — любая часть графа, которая сама является графом.