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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

. Упражнения 5.1 .
1. a). Построить все возможные пути
длиной 2 в графе, изображенном на рисунке
для вершин A и E.
b).Построить орцепи максимальной длины из
всех вершин графа.
c).Построить простые орцепи максимальной
длины из всех вершин графа.
Ответ: a).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
b).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
c).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2. Для графа на рисунке даны маршруты из
вершины A в вершину F:
a). (A, B), (B, C), (C, G), (G, F) ;
b). (A, K), (K, H), (H, F);
c). (A, C), (C, E), (E, D), (D, C), (C, H), (H, F);
d). (A, K), (K, H), (H, C), (C, K), (K, H), (H,F);
Найти среди них цепи и простые цепи.
Ответ: цепи . . . . . . . . . . . . . . . . . . .и простые цепи. . . . . . . . . . . . . . . . . . . . .
.
5.2 Матричный метод нахождения путей в графах
Матрица смежности полностью определяет структуру графа. Возведем
матрицу смежности в квадрат по правилам математики. Каждый элемент матрицы
А
2
определяется по формуле
Слагаемое в формуле равно 1 тогда и только тогда, когда оба числа a
ij
и a
jk
равны 1, в противном случае оно равно 0. Поскольку из равенства a
ij
= a
jk
=1
следует существование пути длины 2 из вершины x
i
в вершину x
k
, проходящего
через вершину x
j
, то (i-й, k-й) элемент матрицы А
2
равен числу путей длины 2,
идущих из x
i
в x
k
.
(2) n
a
ik
= ∑a
ij
a
jk
j=1
A
B
C
D
E
F
A
B
C
K
H
D
E
F
G
.         Упражнения 5.1                                                                                                         .
   1. a). Построить все возможные пути
                                                                                                                   F                 A
длиной 2 в графе, изображенном на рисунке
для вершин A и E.                                                                                       E                                         B
b).Построить орцепи максимальной длины из
всех вершин графа.                                                                                                 D                  C
c).Построить простые орцепи максимальной
длины из всех вершин графа.
Ответ: a).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
..............................................................................
..............................................
b).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
..............................................................................
.............................................
c).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.....................................................................


2. Для графа на рисунке даны маршруты из
вершины A в вершину F:                                                                                             B                     D
                                                                                                                               C
a). (A, B), (B, C), (C, G), (G, F) ;                                                             A                                                  E
b). (A, K), (K, H), (H, F);                                                                                                          G
c). (A, C), (C, E), (E, D), (D, C), (C, H), (H, F);                   K
d). (A, K), (K, H), (H, C), (C, K), (K, H), (H,F);                                                     H                                            F
Найти среди них цепи и простые цепи.
Ответ: цепи . . . . . . . . . . . . . . . . . . .и простые цепи. . . . . . . . . . . . . . . . . . . . .
.
                           5.2 Матричный метод нахождения путей в графах
           Матрица смежности полностью определяет структуру графа. Возведем
матрицу смежности в квадрат по правилам математики. Каждый элемент матрицы
А2 определяется по формуле

                                                  (2)     n
                                                aik = ∑aij ajk
                                                          j=1



           Слагаемое в формуле равно 1 тогда и только тогда, когда оба числа aij и ajk
равны 1, в противном случае оно равно 0. Поскольку из равенства aij= ajk=1
следует существование пути длины 2 из вершины xi в вершину xk, проходящего
через вершину xj, то (i-й, k-й) элемент матрицы А2 равен числу путей длины 2,
идущих из xi в xk.

Страницы