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

Рангом пути r(µ_st) (иногда этот показатель называют длиной пути, но мы под длиной будем понимать физическую длину, т.е. расстояние между узлами a_s и a_t по данному пути) будем называть число ребер, образующих этот путь. Минимальный ранг 1, максимальный N-1, когда путь проходит через все узлы.
Путь µ^k_st (k-порядковый номер пути) будем записывать перечнем ребер, образующих этот путь, т.е.
µ^k_st= µ_slm…qt=b_slb_lm…b_qt,
или упорядоченным (по их месту в пути) перечнем узлов:
µ^k_st=a_sa_la_m…a_qa_t.
Все пути от a_s к a_t образуют множество m_st , а совокупность (объединение) двух множеств, соответствующих противоположным направлениям, - множество M_st всех путей между a_s и a_t : M_st= m_st U m_ts. Для ненаправленных сетей M_st= m_st = m_ts.
В реальной сети, как правило, для связи между заданными узлами a_s и a_t используются не всевозможные пути, а только пути, выделенные по какому-либо показателю или обладающие некоторыми заданными свойствами. В некоторых случаях приходится рассматривать независимые (по ребрам или узлам) пути, т.е. пути, не включающие одни и те же ребра или не проходящие через одни и те же узлы.
Связной называется сеть, любые узлы которой связаны хотя бы одним путем. Сеть называется h-связной, если любые два узла связаны независимыми путями, число которых – не менее h. Связностью h называется минимальное число независимых путей между всеми парами вершин графа. Так на рис. 1.6 сеть является двухсвязной (h=2). Понятие связности будем относить не ко всей сети, а к заданным узлам a_s и a_t (h_st - связность), а также к множеству путей, обладающих заданным свойством *.
Сечением δ сети (графа) назовем избыточную совокупность ребер (линий), которые надо изъять из сети (графа), чтобы нарушилась ее связность. Сечениями δ_st по отношению к узлам a_s и a_t будем называть такие сечения, при которых узлы a_s и a_t оказываются в разных подсетях (подграфах). При этом в сети (графе) с направленными ребрами будем различать направленные сечения, нарушающие связи от a_s к a_t или наоборот, и ненаправленные – полностью разрушающие связи между a_s и a_t.
В общем случае в сети с N узлами может быть 2^N-1–1 сечений. Однако мы будем рассматривать не все возможные сечения, а лишь те, которые делят сеть на две связные подсети (в частом случае в одной из подсетей может быть один узел), которые иногда называют простыми. На рис. 1.6 б) показаны сечения для путей приведенной структуры сети с рангом не более 2. Каждое сечение может быть записано множеством (перечнем) входящих в него ребер:
σ^ℓ ={b_lm, b_in,…, b_pq}
Рангом сечения r(σ^‫ℓ) будем называть число входящих в него ребер.
Наряду с сечением введем понятие разреза сети – минимальной совокупности узлов или узлов и ребер, которые надо удалить из сети, чтобы сеть стала несвязной. Для сети, изображенной на рис. 1.6, по отношению к связям узла 1 к узлу 3 будет только один разрез, включающий узлы a₂ и а₄ : R₁₃= {a₂a₄} или следующие сечения узлов и ребер: R₁₃=(a₂c, a₂d, a₄a, a₄b).
Для структурного анализа сетей (нахождения путей, сечений и их характеристик) используют структурные матрицы и некоторые операции, основанные на применении математического аппарата булевой алгебры. Каждый путь µ^k_st (сечение δ_st) будем представлять произведением (конъюнкцией) символов ребер, образующих этот путь (сечение), а множество путей m_st (сечений S_st) – дизъюнкцией (логической суммой) этих произведений.
Структурной матрицей B сети G с N узлами будем называть квадратурную матрицу порядка N, в которой каждому узлу a_i соответствует i-я строка и i- столбец:
B=║β_ij║
Здесь i, j = 1, N . Вхождения β_ij определяются по следующему правилу:
- β_ij равно 1 при i=j,
- β_ij равно b_ij (или соответственно буквенные символы: c при ij), в случае, если есть непосредственная связь (ребро, линия, канал) от узла a_i к узлу a_j,
- β_ij равно 0, если такой непосредственной связи нет.
Если все ребра не направлены, то матрица будет симметричной по отношению к главной диагонали, а если есть направленные ребра, то несимметричной.
Возведение структурной матрицы в q-ю степень приводит к тому, что каждое вхождение новой матрицы будет содержать все пути от узла a_i к узлу a_j ранга не более q, т.е. B^q =║m_ij^r≤g║. Имеется некое q_max , такое, что дальнейшее возведение матрицы в степень не меняет ее вхождений, т.е.
B^q_max⁺¹ = B^q_max =M_хар=║m_ij║
Матрица M_хар= B^q_max называется характеристической или матрицей всех путей, содержит все возможные в сети пути между узлами. Поскольку максимальные ранг пути не может быть больше N-1, q_max ≤ N-1.