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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

одному пути, идущему от x
i
к x
j
. Эти вершины называются существенными или
неотъемлемыми относительно двух концевых вершин x
i
и x
j
. Все остальные
вершины графа называется несущественными или избыточными, поскольку их
удаление не влияет на пути от x
i
к x
j
.
. Упражнения 5.2 .
1. Для графа, представленного на рисунке, a). найти
вершины, входящие в путь и путь между вершинами
X
1
и X
7
матричным способом;
b). орцепь максимальной длины.
Решение.
Заполним матрицу смежности графа.
T
+
(x
7
) = { . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . .},
T
-
(x
7
) = {. . . . . . . . . . . . . . . . . . . . . .
. . },
T
+
(x
1
) ∩ T
-
(x
7
) ={. . . . . . . . . . . . . . .
. . . . . . . . . }.
Ответ:a). путь -
. . . Æ. . . Æ. . . Æ. . . Æ. . .
b). Орцепь максимальной длины -
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . .
2. Для графа , данного на рисунке, найти и записать
a). все пути длиной 3 из вершин А и В;
b). между какими вершинами наибольшее число
путей длины 3;
c). орцепь максимальной длины;
d). между какой парой вершин A и F или C и G
больше число путей длиной 4.
Решение.
A=
A
2
=
Х1
Х2 Х3 Х4 Х5 Х6 Х7T
+
(x
1
)
Х1 0 1 0 0 0 0 0
Х2 0 0 0 1 0 1 0
Х3 0 0 0 0 0 0 1
Х4 0 0 1 0 1 1 0
Х5 0 0 0 0 0 0 0
Х6 0 0 0 0 0 0 0
Х7 0 0 1 0 0 1 0
T
-
(x
7
)
A
B C D E F G
A 0 1 0 0 0 0 1
B 0 1 0 0 1 0 0
C 0 1 1 1 0 0 0
D 0 0 0 0 0 1 0
E 0 0 1 0 0 1 1
F 0 0 0 0 0 1 1
G 0 0 0 0 0 0 1
A
B C D E F G
A
B
C
D
E
F
G
x
5
x
7
x
3
x
4
x
2
x
6
x
1
B
D
A
C
E
F
G
одному пути, идущему от xi к xj. Эти вершины называются существенными или
неотъемлемыми относительно двух концевых вершин xi и xj. Все остальные
вершины графа называется несущественными или избыточными, поскольку их
удаление не влияет на пути от xi к xj.
.        Упражнения 5.2                                                                             .
1. Для графа, представленного на рисунке, a). найти
                                                                                        x2              x3
вершины, входящие в путь и путь между вершинами
X1 и X7 матричным способом;                                                  x1
                                                                                                                  x4
b). орцепь максимальной длины.
                                                                                                                 x5
                    Решение.
Заполним матрицу смежности графа.                                                       x7        x6

                     Х2 Х3 Х4 Х5 Х6 Х7                       T+(x1)
         Х1                                                           T+(x7) = { . . . . . . . . . . . . . . . . . . . . .
Х1       0           1       0       0       0       0   0            . . . . . . . . . .},
Х2       0           0       0       1       0       1   0            T-(x7) = {. . . . . . . . . . . . . . . . . . . . . .
Х3       0           0       0       0       0       0   1            . . },
Х4       0           0       1       0       1       1   0            T+(x1) ∩ T-(x7) ={. . . . . . . . . . . . . . .
Х5       0           0       0       0       0       0   0            . . . . . . . . . }.
Х6       0           0       0       0       0       0   0            Ответ:a). путь -
Х7       0           0       1       0       0       1   0            . . . Æ. . . Æ. . . Æ. . . Æ. . .
                                                                      b). Орцепь максимальной длины -
                                                                      ..............................
T-(x7)
                                                                      ..........

2. Для графа , данного на рисунке, найти и записать                                 B                        C
a). все пути длиной 3 из вершин А и В;
b). между какими вершинами наибольшее число                                                        E               D
                                                                           A
путей длины 3;
c). орцепь максимальной длины;
                                                                                     G                   F
d). между какой парой вершин A и F или C и G
больше число путей длиной 4.
                       Решение.

A=                       B       C       D       E   F   G
                 A                                            A= 2             A        B    C      D        E   F     G

             A   0       1       0       0       0   0   1             A
             B   0       1       0       0       1   0   0             B
             C   0       1       1       1       0   0   0             C
             D   0       0       0       0       0   1   0             D
             E   0       0       1       0       0   1   1             E
             F   0       0       0       0       0   1   1             F
             G   0       0       0       0       0   0   1
                                                                       G

Страницы