Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 25 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

одного лица х
i
быть передана другому лицу х
j
, то есть существует ли путь,
идущий от вершины х
i
к вершине х
j
. Если такой путь существует, то говорят, что
вершина х
j
достижима из вершины х
i
. Можно интересоваться достижимостью
вершины х
j
из вершины х
i
только на таких путях, длины которых не превосходят
заданной величины или длина которых меньше наибольшего числа вершин в
графе и т.п. задачи.
Достижимость в графе описывается матрицей достижимостей R=[r
ij
],
i.j=1,2, ... n, где n-число вершин графа, а каждый элемент определяется
следующим образом:
r
ij
=1, если вершина х
j
достижима из х
i
,
r
ij
=0, в противном случае.
Множество вершин R(x
i
) графа G, достижимых из заданной вершины x
i
,
состоит из таких элементов x
j
, для которых (i,j)-ый элемент в матрице
достижимостей равен 1.Очевидно ,что все диагональные элементы в матрице R
равны 1, поскольку каждая вершина достижима из себя самой путeм длины 0.
Поскольку прямое отображение 1-го порядка Г
+1
( x
i
) является
множеством таких вершин x
j
, которые достижимы из x
i
с использованием путей
длины 1,то множество Г
+
(Г
+1
( x
i
) ) = Г
+2
( x
i
) состоит из вершин, достижимых из x
i
с использованием путей длины 2. Аналогично Г
+p
( x
i
) является множеством
вершин, которые достижимы из x
i
с помощью путей длины p.
Так как любая вершина графа, которая достижима из x
i
, должна быть
достижима с использованием пути (или путей) длины 0, или 1, или 2,..., или
p, то множество вершин, достижимых для вершины x
i
, можно представить в виде:
R ( x
i
) = { x
i
} ∪ Г
+1
( x
i
) ∪ Г
+2
(x
i
) ∪ ... ∪ Г
+p
(x
i
).
Как видим, множество достижимых вершин R ( x
i
) представляет собой
прямое транзитивное замыкание вершины x
i
, т.е. R ( x
i
) = T
+
( x
i
). Следовательно,
для построения матрицы достижимости находим достижимые множества R ( x
i
)
для всех вершин x
i
∈X. Полагая, r
ij
=1, если x
j
∈ R ( x
i
) и r
ij
=0 в противном случае.
Для графа, приведенного на рис.12,а. множества достижимостей
находятся следующим образом:
R ( x
1
) = { x
1
} ∪{ x
2
, x
5
} ∪ { x
2
, x
4
, x
5
} ∪ { x
2
, x
4
, x
5
} = { x
1
, x
2
, x
4
, x
5
},
R ( x
2
) = { x
2
} ∪ { x
2
, x
4
} ∪ { x
2
, x
4
, x
5
} ∪ { x
2
, x
4
, x
5
} = { x
2
, x
4
, x
5
},
R ( x
3
) = { x
3
} ∪ { x
4
} ∪ { x
5
} ∪ { x
5
} = { x
3
, x
4
, x
5
},
R ( x
4
) = { x
4
} ∪ { x
5
} ∪ { x
5
} = { x
4
, x
5
},
R ( x
5
) = { x
5
} ∪ { x
5
} = { x
5
}, 
одного лица хi быть передана другому лицу хj, то                       есть   существует ли путь,
идущий от вершины хi к вершине хj. Если такой путь существует, то говорят, что
вершина хj достижима из вершины хi. Можно интересоваться достижимостью
вершины хj из вершины хi только на таких путях, длины которых не превосходят
заданной величины или длина которых меньше наибольшего числа вершин в
графе и т.п. задачи.
      Достижимость в          графе          описывается матрицей достижимостей R=[rij],
i.j=1,2, ... n, где n-число вершин графа, а каждый элемент                             определяется
следующим образом:
      rij=1, если вершина хj достижима из хi,
      rij=0, в противном случае.
      Множество вершин R(xi) графа G, достижимых из заданной вершины xi,
состоит из таких элементов xj, для которых (i,j)-ый элемент в матрице
достижимостей равен 1.Очевидно ,что все диагональные элементы в матрице R
равны 1, поскольку каждая вершина достижима из себя самой путeм длины 0.
Поскольку        прямое          отображение              1-го         порядка Г+1 ( xi ) является
множеством таких вершин xj, которые достижимы из xi с использованием путей
длины 1,то множество Г+ (Г+1 ( xi ) ) = Г+2 ( xi ) состоит из вершин, достижимых из xi
с использованием путей длины 2. Аналогично Г+p ( xi ) является множеством
вершин, которые достижимы из xi с помощью путей длины p.
      Так как любая вершина графа, которая достижима из xi, должна быть
достижима с использованием пути (или путей) длины 0, или 1, или 2,..., или
p, то множество вершин, достижимых для вершины xi, можно представить в виде:
      R ( xi ) = { xi } ∪ Г+1 ( xi ) ∪ Г+2(xi) ∪ ... ∪ Г+p(xi).
      Как видим, множество             достижимых вершин R ( xi ) представляет собой
прямое транзитивное замыкание вершины xi, т.е. R ( xi ) = T+ ( xi ). Следовательно,
для построения матрицы достижимости находим достижимые множества R ( xi )
для всех вершин xi∈X. Полагая, rij=1, если xj ∈ R ( xi ) и rij=0 в противном случае.
      Для    графа,      приведенного          на   рис.12,а.     множества          достижимостей
находятся следующим образом:
      R ( x1 ) = { x1 } ∪{ x2, x5 } ∪ { x2, x4, x5 } ∪ { x2, x4, x5 } = { x1, x2, x4, x5 },
      R ( x2 ) = { x2 } ∪ { x2, x4 } ∪ { x2, x4, x5 } ∪ { x2, x4, x5 } = { x2, x4, x5 },
      R ( x3 ) = { x3 } ∪ { x4 } ∪ { x5 } ∪ { x5 } = { x3, x4, x5 },
      R ( x4 ) = { x4 } ∪ { x5 } ∪ { x5 } = { x4, x5 },
      R ( x5 ) = { x5 } ∪ { x5 } = { x5 },

Страницы