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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

. Упражнения к п. 2.2 .
1. Найти прямое и обратное транзитивные
замыкания для вершин x
1
и x
3.
Ответ: Т
+
( x
1
) = х
1
∪ Г
+1
( х
1
) ∪ Г
+2
( x
1
) ∪...={ . .
. . . . . . . . . . . . . . . . . . . . }, T
-
( x
1
) = x
1
∪ Г
-1
( x
1
) ∪ Г
-2
( x
1
) ∪... ={ . . . . . . . . . . . . . . . . . . . . . . },
Т
+
( x
3
) = х
3
∪ Г
+1
( х
3
) ∪ Г
+2
( x
3
) ∪...={ . . . . . . . . .
. . . . . . . . . . . . . }, T
-
( x
3
) = x
3
∪ Г
-1
( x
3
) ∪ Г
-2
( x
3
) ∪... ={ . . . . . . . . . . . . . . . . . . . . .
. }.
2. По матрице смежности графа найти прямые и
обратные транзитивные замыкания всех вершин.
Ответ: Т
+
( x
1
) ={ x
1
, x
2,
x
3
, x
5
, x
6
}, Т
+
( x
2
) ={
. . . . . . . . . . . . . . . . . . . . . . . . },
Т
+
( x
3
) ={ . . . . . . . . . . . . . . . . . . . . . . . . },
Т
+
( x
4
) ={ . . . . . . . . . . . . . . . . . . . . . . . . },
Т
+
( x
5
) ={ . . . . . . . . . . . . . . . . . . . . . . . . },
Т
+
( x
6
) ={ . . . . . . . . . . . . . . . . . . . . . . . . },
Матрица смежности
2.3 Достижимость и контрдостижимость
Задач, в которых используется понятие достижимости довольно много. Вот
одна из них. Граф может быть моделью какой-то организации, в которой люди
представлены вершинами, а дуги интерпретируют каналы связи. При
рассмотрении такой модели можно поставить вопрос, может ли информация от
0 1 3 2 Т
-
( x
1
) ={ x
1
, x
2,
x
4
, x
5
}
Т
-
( x
2
) ={ . . . . . . . . . . . . . . . . . . . . . . . . }
Т
-
( x
3
) ={ . . . . . . . . . . . . . . . . . . . . . . . . }
Т
-
( x
4
) ={ . . . . . . . . . . . . . . . . . . . . . . . . }
Т
-
( x
5
) ={ . . . . . . . . . . . . . . . . . . . . . . . . }
Т
-
( x
6
) ={ . . . . . . . . . . . . . . . . . . . . . . . . }
X
1
X
2
X
3
X
4
X
5
X
6
Т
+
( x
1
) Т
+
( x
2
) Т
+
( x
3
) Т
+
( x
4
) Т
+
( x
5
) Т
+
( x
6
)
X
1
0 0 0 0 1 0 0
X
2
1 0 1 0 0 1 2
X
3
0 0 0 0 0 0 3
X
4
0 0 1 0 1 1
X
5
0 1 0 0 0 1 1
X
6
0 0 0 0 0 0
2
x
1
x
2
x
3
x
4
x
5
x
1
x
2
x
3
x
4
x
5
x
6
.         Упражнения к п. 2.2                                                                                    .

                                                                                                      x1
1. Найти прямое и обратное транзитивные
                                                                                                                            x2
замыкания для вершин x1 и x3.                                                     x5
Ответ: Т+ ( x1) = х1 ∪ Г+1 ( х1 ) ∪ Г+2 ( x1 ) ∪...={ . .
. . . . . . . . . . . . . . . . . . . . },            T- ( x1 ) = x1 ∪ Г-1
( x1 ) ∪ Г-2 ( x1) ∪... ={ . . . . . . . . . . . . . . . . . . . . . . },
                                                                                       x4                                 x3
Т+ ( x3) = х3 ∪ Г+1 ( х3 ) ∪ Г+2 ( x3 ) ∪...={ . . . . . . . . .
. . . . . . . . . . . . . },             T- ( x3 ) = x3 ∪ Г-1 ( x3 ) ∪ Г-2 ( x3) ∪... ={ . . . . . . . . . . . . . . . . . . . . .
. }.
2. По матрице смежности графа найти прямые и
обратные транзитивные замыкания всех вершин.                                                           x1
                                                                                                                               x2
Ответ: Т+( x1) ={ x1, x2, x3, x5, x6},                              Т+( x2) ={      x5
. . . . . . . . . . . . . . . . . . . . . . . . },
Т+( x3) ={ . . . . . . . . . . . . . . . . . . . . . . . . },
                                                                                                            x6
    +
Т ( x4) ={ . . . . . . . . . . . . . . . . . . . . . . . . },                            x4                               x3

Т+( x5) ={ . . . . . . . . . . . . . . . . . . . . . . . . },
Т+( x6) ={ . . . . . . . . . . . . . . . . . . . . . . . . },
Матрица смежности


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

    X1 X2 X3 X4 X5 X6     Т+( x1) Т+( x2) Т+( x3) Т+( x4) Т+( x5) Т+( x6)
X1 0 0 0 0 1 0              0
X2 1 0 1 0 0 1              2
X3 0 0 0 0 0 0              3
X4 0 0 1 0 1 1
X5 0 1 0 0 0 1              1
X6 0 0 0 0 0 0              2
представлены вершинами, а дуги    интерпретируют     каналы     связи. При

          0      1          Т-( x1) ={ x1, x2, x4, x5}
                                 3       2
                            Т-( x2) ={ . . . . . . . . . . . . . . . . . . . . . . . . }
                            Т-( x3) ={ . . . . . . . . . . . . . . . . . . . . . . . . }
                            Т-( x4) ={ . . . . . . . . . . . . . . . . . . . . . . . . }
                            Т-( x5) ={ . . . . . . . . . . . . . . . . . . . . . . . . }
                            Т-( x6) ={ . . . . . . . . . . . . . . . . . . . . . . . . }
рассмотрении такой модели можно поставить вопрос, может ли информация от

Страницы