Узбекское агентство связи и информатизации

1.4.2. Понятие о структуре сети, путях и сечениях

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

Для изучения структурных свойств сети их удобнее всего представить в виде графа без петель (рис. 1.6 а) G = {A, B}, где A = {a₁,…, a_N} – совокупность пунктов (узлов) сети (вершин графа) и B = {b_ij} – множество ребер, соединяющих узлы a_i и a_j , соответствующих всем линиям или каналам связи между этими узлами. Поскольку каналы могут быть одностороннего (по направлению передачи информации или установления соединения) и двустороннего действия, то и соответствующие им ребра будут направленными (ориентированными) или ненаправленными (неориентированными).

Рис. 1.6. Пример сети, изображенной в виде графа: а) мостиковая сеть с направленным ребром, б) сечения для путей с рангом r ≤ 2

Граф может быть записан матрицей смежности (связности) порядка N, по главной диагонали которой поставлены знаки неопределенности, которые в конкретных случаях могут заменяться 0 или 1, а вхождения α_ij принимают значения 1, если есть ребро, связывающее узел a_i с узлом a_j и 0, если ребра нет. Если в сети нет направленных ребер, то матрица будет симметричной по отношению к главной диагонали. Для сети на рис.1.4.3 матрица смежности имеет вид

R =		-	1	0	1
		1	-	1	1
		0	1	-	1
		1	0	1	-

Пункты (узлы), соединенные ребром, будем называть смежными. Число ребер, инцидентных данному пункту (входящих или исходящих из него), называется рангом r(a_i) этого узла. Узел ранга 1 является тупиковым – оконечным, и через него не могут проходить никакие пути. Для упрощения записи отдельные ребра могут обозначаться буквами a, b, c, …(рис.1.6 а)

Путь (самонепересекающийся) µ_st из узла a_s в узел a_t это упорядоченная последовательность ребер, начинающаяся в a_s , заканчивающаяся в a_t и не проходящая дважды через один и тот же узел, причем конец каждого предыдущего ребра совпадает в промежуточном (для данного пути) узле с началом последующего ребра. Путь, намеченный (выбранный) для доставки тех или иных сообщений между заданной парой пунктов (узлов), будем называть маршрутом, а процесс установления таких маршрутов (путей) – маршрутизацией.