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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

2. ДОСТИЖИМОСТЬ И СВЯЗАНОСТЬ В ГРАФАХ
2.1.Многозначные отображения
2.1.1.Прямые отображения
Прямым отображением 1-го порядка вершины x
i
является множество
таких вершин графа, для которых существует дуга (x
i
, x
j
), т.е
Г
1
( x
i
) = {x
j
: ∃ дуга (x
i
, x
j
) ∈ A} для графа G=(X, A), где X={ x
i
}, i=1,2,...,n -
множество вершин, а A={a
i
}, i=1,2,...,m - множество дуг.
Прямое отображение 2-го порядка вершины x
i
- это прямое отображение от
прямого отображения 1-го порядка, т.е.
Г
+2
( x
i
) = Г
+
( Г
+1
( x
i
) ).
Аналогично, можно записать для прямого отображения 3-го и т.д. n-ого порядка.
Г
+3
( х
i
) = Г
+
(Г
+2
( х
i
) ) = Г
+
(Г
+
(Г
+1
( х
i
) ) )
...
Г
+n
( х
i
) = Г
+
(Г
+(n-1)
( x
i
) )
Прямые многозначные отображения для графа
на рис.9 находятся следующим образом:
Г
+1
( x
1
) = {x
2
, x
3
},
Г
+2
(x
1
) = Г
+
(Г
+1
( x
1
) ) = Г
+
(x
2
, x
3
) = {x
3
, x
5
}
Г
+3
( x
1
) = Г
+
(Г
+2
(x
1
) ) = Г
+
(x
3
, x
5
) = {x
3
, x
1
} и т. д.
2.1.2. Обратные отображения
Обратным отображением 1-го порядка для вершины x
i
является
множество элементов x
j
таких, что существует дуга (x
j
, x
i
), принадлежащая
множеству дуг графа, т.е. Г
-1
( х
i
) = { x
j
: ∃ дуга (х
j
, x
i
) ∈ А }
Обратные отображения 2-го, 3-го и т.д. n-го порядка определяется следующим
образом:
Г
-2
( х
i
) = Г
-
( Г
-1
( х
i
) )
Г
-3
( х
i
) = Г
-
( Г
-2
( х
i
) )
...
Г
-n
( х
i
) = Г
-
( Г
- (n-1)
( x
i
) )
x
1
x
2
x
3
x
4
x
5
Рис. 9. 
                     2. ДОСТИЖИМОСТЬ И СВЯЗАНОСТЬ В ГРАФАХ
                                  2.1.Многозначные отображения

                                     2.1.1.Прямые отображения
     Прямым отображением 1-го порядка вершины xi является множество
таких вершин графа, для которых существует дуга (xi, xj), т.е
Г1( xi ) = {xj : ∃ дуга (xi, xj) ∈ A} для графа G=(X, A), где X={ xi }, i=1,2,...,n -
множество вершин, а A={ai}, i=1,2,...,m - множество дуг.
Прямое отображение 2-го порядка вершины xi - это прямое отображение от
прямого отображения 1-го порядка, т.е.
   Г+2 ( xi ) = Г+ ( Г+1 ( xi ) ).
Аналогично, можно записать для прямого отображения 3-го и т.д. n-ого порядка.
                                                    Г+3 ( хi ) = Г+ (Г+2 ( хi) ) = Г+ (Г+ (Г+1 ( хi) ) )
                    x2
                                                    ...
                                                    Г+n ( хi ) = Г+ (Г+(n-1) ( xi ) )
   x1                                x3           Прямые многозначные отображения для графа
                                                  на рис.9 находятся следующим образом:
                                     x4
                   x5                               Г+1 ( x1) = {x2, x3},
                   Рис. 9.

   Г+2 (x1) = Г+ (Г+1 ( x1 ) ) = Г+ (x2, x3) = {x3, x5}
   Г+3 ( x1) = Г+ (Г+2 (x1) ) = Г+ (x3, x5) = {x3, x1}          и т. д.



                                  2.1.2. Обратные отображения


          Обратным отображением 1-го порядка для вершины xi является
множество элементов xj таких, что существует дуга (xj, xi), принадлежащая
множеству дуг графа, т.е. Г-1 ( хi ) = { xj : ∃ дуга (хj, xi) ∈ А }
   Обратные отображения 2-го, 3-го и т.д. n-го порядка определяется следующим
образом:
            Г-2( хi ) = Г- ( Г-1 ( хi ) )
            Г-3( хi ) = Г- ( Г-2 ( хi ) )
            ...
            Г-n ( хi ) = Г- ( Г- (n-1) ( xi ) )

Страницы