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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Для графа на рис.9 обратные многозначные отображения вершины х
1
находятся следующим образом:
Г
-1
( х
1
) = { x
5
}
Г
-2
( х
1
) = Г
-
( Г
-1
( х
1
) ) = Г
-
( х
5
) = { х
2
, х
4
}
Г
-3
( х
1
) = Г
-
(Г
-2
( х
1
) ) = Г
-
(х
2
, х
4
) = {х
1
}
Г
-4
(х
1
) = Г
-
(Г
-3
(х
1
) ) = Г
-
(х
1
) = {х
5
} и т.д.
ПРИМЕЧАНИЕ. 1) Когда отображение действует не на одну вершину, а на
множество вершин Х
q
= { x
1
, х
2
, ..., х
q
}, то под Г(Х
q
) понимают объединение.
Г(х
1
)∪Г(х
2
) ∪...∪Г(х
q
).
2) Многозначное отображение для неориентированного графа строится, если
представить каждое ребро двумя противоположно направленными дугами
(рис.10).
. Упражнения 2.1 .
1.Найти прямые многозначные отображения
для всех вершин графа, показанного на рисунке.
Ответ: Г
+1
( x
1
) = {x
1
, x
2
, x
3
, x
4
},
Г
+2
(x
1
) = Г
+
(Г
+1
( x
1
) ) = Г
+
(x
1
, x
2
, x
3
, x
4
) = { x
1
,
x
2
, x
3
, x
4
, x
5
, x
6
},
Г
+3
( x
1
) = Г
+
(Г
+2
(x
1
) ) = Г
+
(x
1
, x
2
, x
3
, x
4
, x
5
, x
6
) =
{ x
1
, x
2
, x
3
, x
4
, x
5
, x
6
}
Г
+4
( x
1
) = Г
+5
(x
1
) = Г
+6
(x
1
) и т. д.
Г
+1
( x
2
) = {x
1
, x
3
},
Г
+2
(x
2
) = Г
+
(Г
+1
( x
1 ,
x
3
) ) = Г
+
( . . . . . . . . . . . . . . . . ) = { . . . . . . . . . . . . . . . . },
Г
+3
( x
2
) = Г
+
(Г
+2
(x
2
) ) = Г
+
(. . . . . . . . . . . . . . . .) = . . . . . . . . . . . . . . . . } Г
+4
( x
2
) = . . . .
. . . . . . . . . . . .
Г
+1
( x
3
) = {x
4
, x
6
},
Г
+2
(x
3
) = Г
+
(. . . . . . . . . . . . . . . .) = { . . . . . . . . . . . . . . . . },
à)
x
4
x
1
x
2
x
3
x
4
x
1
x
2
x
3
á)
Рис. 10. Граф : а) - неориентированный ;
б) - тождествнный ему ориентированный .
Х
1
Х
1
X
4
X
5
X
6
X
2
X
3
        Для графа              на      рис.9        обратные многозначные отображения вершины х1
находятся следующим образом:
                   Г-1 ( х1 ) = { x5 }
                   Г-2 ( х1 ) = Г- ( Г-1 ( х1 ) ) = Г- ( х5 ) = { х2, х4 }
                   Г-3 ( х1) = Г- (Г-2 ( х1 ) ) = Г- (х2, х4) = {х1}
                   Г-4 (х1) = Г- (Г-3 (х1) ) = Г- (х1) = {х5} и т.д.

                            x2                                                                x2


       x1                                                               x1
                                              x3                                                           x3

                       x4                                                                x4
                                                                                                   á)
                         à)
                      Рис. 10. Граф : а) - неориентированный ;
                      б) - тождествнный ему ориентированный .

ПРИМЕЧАНИЕ. 1) Когда отображение действует не на одну вершину, а на
множество вершин Хq = { x1, х2, ..., хq }, то под Г(Хq) понимают объединение.
               Г(х1)∪Г(х2) ∪...∪Г(хq).
    2) Многозначное отображение для неориентированного графа строится, если
представить                 каждое        ребро двумя противоположно                               направленными дугами
(рис.10).
.            Упражнения 2.1                                                                                               .
                                                                                              Х1                              X2
            1.Найти прямые многозначные отображения
для всех вершин графа, показанного на рисунке.
Ответ: Г+1 ( x1) = {x1, x2, x3 , x4},                                               X6
    Г+2 (x1) = Г+ (Г+1 ( x1 ) ) = Г+ (x1, x2, x3 , x4) = { x1,
                                                                                                                              X3
x2, x3 , x4 , x5 , x6},
    Г+3 ( x1) = Г+ (Г+2 (x1) ) = Г+ (x1, x2, x3 , x4 , x5, x6) =                      X5
                                                                                                                              X4
{ x1, x2, x3 , x4 , x5 , x6}
     Г+4 ( x1) = Г+5 (x1) = Г+6 (x1) и т. д.
            Г+1 ( x2) = {x1, x3 },
    Г+2 (x2) = Г+ (Г+1 ( x1 , x3) ) = Г+ ( . . . . . . . . . . . . . . . . ) = { . . . . . . . . . . . . . . . . },
Г+3 ( x2) = Г+ (Г+2 (x2) ) = Г+ (. . . . . . . . . . . . . . . .) = . . . . . . . . . . . . . . . . }             Г+4 ( x2) = . . . .
............
            Г+1 ( x3) = {x4, x6 },
    Г+2 (x3) = Г+ (. . . . . . . . . . . . . . . .) = { . . . . . . . . . . . . . . . . },

Страницы