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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

A
3
= A
4
=
Ответ: a). все пути длиной 3 из вершин А и В : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . .
b). наибольшее число путей длины 3 между вершинами. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
c). орцепь максимальной длины -. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
d). между парой вершин . . . . . . . . . . . . . . . . . . . больше число путей длиной 4 чем между
парой. . . . . . . . . . . . . . . .
3. Построить все возможные пути длиной 2 в графе,
изображенном на рисунке.
Решение.
A=
A
2
=
Ответ:
a).
все пути длиной 2: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
5.3.Вес и длина пути
Иногда дугам графа сопоставляют числа а
i
→ с
i
, называемые весом или длиной,
или стоимостью или ценой. В каждом конкретном случае выбирается то слово,
которое ближе подходит по смыслу задачи.
A
B C D E F G
A 0 1 1 0 1 1 2
B 0 2 2 1 1 2 3
C 0 3 2 1 2 3 2
D 0 0 0 0 0 1 2
E 0 2 1 1 1 2 3
F 0 0 0 0 0 1 3
G 0 0 0 0 0 0 1
A
B C D E F G
A
B
C
D
E
F
G
A
B C D E F
A 0 1 0 1 0 0
B 0 1 1 0 0 0
C 0 0 0 0 0 0
D 1 0 0 0 1 0
E 0 1 0 0 0 1
F 1 0 0 0 0 0
A
B C D E F
A
B
C
D
E
F
A
B
C
D
E
F
                               B       C       D       E        F   G                                 B       C     D       E    F       G
                       A                                                                    A
               A       0       1       1       0       1        1   2                 A
  A3 =         B       0       2       2       1       1        2   3       A4 =      B
               C       0       3       2       1       2        3   2                 C
               D       0       0       0       0       0        1   2                 D
               E       0       2       1       1       1        2   3                 E
               F       0       0       0       0       0        1   3                 F
               G       0       0       0       0       0        0   1                 G

Ответ: a). все пути длиной 3 из вершин А и В : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
..............................................................................
..............................................................................
..........

b). наибольшее число путей длины 3 между вершинами. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
......................................
c). орцепь максимальной длины -. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
..................
d). между парой вершин . . . . . . . . . . . . . . . . . . . больше число путей длиной 4 чем между
парой. . . . . . . . . . . . . . . .

3. Построить все возможные пути длиной 2 в графе,
изображенном на рисунке.                                                                                  F             A

                                                                                              E                                      B
                                   Решение.

                                                                                                          D              C

                           B       C       D       E        F
                   A                                                                      A       B       C   D      E       F

A=         A       0       1       0       1       0        0
                                                                             A
           B       0       1       1       0       0        0               A2=
                                                                             B
           C       0       0       0       0       0        0
                                                                             C
           D       1       0       0       0       1        0
                                                                             D
           E       0       1       0       0       0        1
                                                                             E
           F       1       0       0       0       0        0
                                                      Ответ:                 F                                                      a).
все пути длиной 2: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
..............................................................................
...............................................................
                                                                        .
                                                                        .
                                                           5.3.Вес и длина пути
Иногда дугам графа сопоставляют числа аi → сi, называемые весом или длиной,
или стоимостью или ценой. В каждом конкретном случае выбирается то слово,
которое ближе подходит по смыслу задачи.

Страницы