21.6. Теорема

Пусть даны деревья

T0 = (ND0, A0),

T1 = (ND1, A1),

..

TN = (NDN, AN)

такие, что T0 является композицией остальных T1 .. TN.

Тогда совпадают замыкания по транзитивности у отношений смежности для вершин: T0 с одной стороны, и суммы отношений (смежности) для T1 .. TN - с другой.

Доказательство

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

• M0 - матрица дуг T0
• 𝕄0 - матриц путей T0, являющаяся замыканием по транзитивности M0
• M1..MN - матрицы дуг T1 .. TN
• M∑ = M1 + .. + MN - сумма матриц
• 𝕄∑ - замыкание по транзитивности M∑

Тем самым, необходимо доказать совпадение 𝕄0 и 𝕄∑.

Поскольку состав вершин, соответствующий набору строк и столбцов в матрице, одинаков согласно определению суммы, то различаться могут только элементы в этой матрице. Рассмотрим ту пару вершин ndi и ndj, для которых в одной матрице есть признак (1) интересующего отношения следования, а в другой - его нет (0), что может случиться в двух вариантах:

1. 𝕄0 содержит, а 𝕄∑ - нет

2. 𝕄∑ содержит, а 𝕄0 - нет

То, что в первом варианте 𝕄0 содержит "признак следования" вершины ndj за ndi означает существование в T0 пути от ndi до ndj. Пусть этот путь в T0 состоит из некоторого набора дуг. Тогда каждая из них обязана принадлежать хотя бы одному дереву T1 .. TN согласно определению композиции деревьев . Значит, и сумма отношений непосредственного следования для этих деревьев, выраженная матрицей M∑, должна содержать признак каждого такого элементарного следования, выражающего существование каждой такой дуги.

Но тогда и 𝕄∑, как транзитивное замыкание M∑, обязано содержать признак следования ndj за ndi, что как раз и означает ошибочность исходного предположение о его отсутствии.

Теперь рассмотрим второй вариант - наличие следования между ndi и ndj в 𝕄∑ и отсутствие его в 𝕄0. Наличие такого признака в 𝕄∑ означает, что в суммарном графе T1 + .. + TN, объединяющем вершины и дуги исходных деревьев и описываемом матрицей M∑, существует путь от ndi к ndj, причём каждая дуга этого пути содержится в одном из T1 .. TN.

Значит, и в M0, являющейся матрицей смежности T0, которое служит прообразом каждого из T1 .. TN, также должны содержаться признаки следования для каждой такой дуги. А следовательно, и 𝕄0 как транзитивное замыкание M0 должно содержать признак существования такого пути от ndi к ndj. █

Назад Вперёд