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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

. .
2.2. Транзитивные замыкания
2.2.1. Прямое транзитивное замыкание.
Прямым транзитивным замыканием некоторой вершины х
i
- T
+
( х
i
)
является объединение самой вершины х
i
с прямыми отображениями 1-го
порядка, второго порядка и т.д., т.е.
T
+
( х
i
) = х
i
∪ Г
+1
( х
i
) ∪ Г
+2
( x
i
) ∪...
Многозначное отображение находятся до тех пор, пока в них добавляются
новые вершины.
Так для графа на рис.9.
Г
+1
( х
1
) = { х
2
, х
3
}
Г
+2
( х
1
) = { х
3 ,
х
5
}
Г
+3
( х
1
) = { х
3
, х
1
}
Г
+4
( х
1
) = { х
2
, х
3
}
Отображение четвертого порядка содержит те же элементы, что и отображение
1-го порядка, следовательно других элементов в последующих отображениях
не появится. Транзитивное замыкание для вершины х
1
получается следующим
образом :
T
+
( х
1
) = х
1
∪ { х
2
, х
3
} ∪ { х
3
, х
5
} ∪ { х
3
, х
1
} = { х
1
, х
2
, х
3
, х
5
}
Проанализировав множество вершин, входящих в T
+
( х
i
), можно сделать
вывод: прямое транзитивное замыкание содержит вершины, в которые есть пути
из вершины х
i
. Таким образом, можно дать второе определение T
+
( х
i
).
Прямое транзитивное замыкание некоторой вершины х
i
T
+
( х
i
) - это
множество вершин, достижимых из вершины х
i
, т.е. T ( х
i
) = { х
j
| ∃ путь из х
i
в х
j
}.
2.2.2. Обратное транзитивное замыкание
Обратным транзитивным замыканием некоторой вершины x
i
-T
-
( x
i
)
является объединение этой вершины с обратными отображениями 1-го,2-го и т.д.
n-го порядка , т. е. T
-
( x
i
) = x
i
∪ Г
-1
( x
i
) ∪ Г
-2
( x
i
) ∪...
Иначе, обратное транзитивное замыкание для некоторой вершины x
i
- T
-
( x
i
) - это
множество вершин, из которых достижима вершина x
i
, т.е. T
-
( x
i
) = { x
i
| E путь из x
i
в x
j
}
Рассмотрим построение обратного транзитивного замыкания для графа на рис.9 
.                                                                                         .


                                     2.2. Транзитивные замыкания

                               2.2.1. Прямое транзитивное замыкание.
           Прямым транзитивным замыканием некоторой вершины хi - T+ ( хi )
является объединение самой вершины хi                          с    прямыми         отображениями 1-го
порядка, второго порядка и т.д., т.е.
      T+ ( хi ) = хi ∪ Г+1 ( хi ) ∪ Г+2 ( xi ) ∪...
    Многозначное отображение                находятся до тех пор,            пока в них добавляются
новые вершины.
    Так для графа на рис.9.
    Г+1 ( х1 ) = { х2, х3 }
    Г+2 ( х1 ) = { х3 , х5 }
    Г+3 ( х1 ) = { х3, х1 }
    Г+4 ( х1 ) = { х2, х3 }
    Отображение четвертого порядка содержит те же элементы, что и отображение
1-го порядка, следовательно других элементов в последующих отображениях
не появится. Транзитивное замыкание для вершины х1 получается следующим
образом :
       T+ ( х1 ) = х1 ∪ { х2, х3 } ∪ { х3, х5 } ∪ { х3, х1 } = { х1, х2, х3, х5 }
          Проанализировав множество вершин, входящих в T+ ( хi ), можно сделать
вывод: прямое транзитивное замыкание содержит вершины, в которые есть пути
из вершины хi. Таким образом, можно дать второе определение T+ ( хi ).
          Прямое транзитивное замыкание некоторой вершины хi T+ ( хi ) - это
множество вершин, достижимых из вершины хi, т.е. T ( хi ) = { хj | ∃ путь из хi в хj }.

                               2.2.2. Обратное транзитивное замыкание
            Обратным транзитивным замыканием некоторой вершины xi -T- ( xi )
является объединение этой вершины с обратными отображениями 1-го,2-го и т.д.
n-го порядка , т. е. T- ( xi ) = xi ∪ Г-1 ( xi ) ∪ Г-2 ( xi ) ∪...
Иначе, обратное транзитивное замыкание для некоторой вершины xi - T- ( xi ) - это
множество вершин, из которых достижима вершина xi, т.е. T -( xi ) = { xi | E путь из xi
в xj }
Рассмотрим построение обратного транзитивного замыкания для графа на рис.9

Страницы