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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

В качестве иллюстративного примера рассмотрим граф, вершины которого
представляют сотрудников некоторого учреждения, а дуги -линии связи между
сотрудниками. Тогда граф, представляющий только наиболее важные связи или
каналы связи данного учреждения, является остовным подграфом; граф,
который подробно описывает линии связи
только какой-то части учреждения (например, отдела ) является порожденным
подграфом, а
граф, который представляет только важные линии связи в пределах
отдела, является просто подграфом.
. Упражнения к п. 3.2 .
x
2
x
4
x
3
x
1
x
5
x
2
x
1
x
4
x
5
x
2
x
4
x
3
x
1
x
5
x
1
x
2
x
3
x
5
x
2
x
4
x
3
x
1
x
5
x
2
x
3
x
1
x
2
x
4
x
1
x
5
а) б)
в)
г)
Рис. 19. Виды подграфов:
а)Исходный граф б)подграфы в) остовные
подграфы г) порожденные подграфы
                                                                                                            x2
                               x2                                       x2
                                                                                                                 x3
           x1                                            x1                            x1
                                         x3
                                                                                                 x5
                x5                  x4                        x5                  x4
                          а)                                                           б)

                                     x2                                                 x2

                     x1                                            x1

                                                   x3                                                  x3

                          x5                  x4                        x5                       x4
                                                              в)
                                                                                            x2
                                         x2
                                                                    x1
                     x1

                                                    x3
                                                                             x5                       x4
                                                              г)
                           Рис. 19. Виды подграфов:
                           а)Исходный граф б)подграфы в) остовные
                           подграфы г) порожденные подграфы




В качестве иллюстративного примера рассмотрим граф, вершины которого
представляют сотрудников некоторого учреждения, а дуги -линии связи между
сотрудниками. Тогда граф, представляющий только наиболее важные связи или
каналы связи данного учреждения, является остовным подграфом; граф,
который подробно описывает линии связи
только какой-то части учреждения (например, отдела ) является порожденным
подграфом, а граф, который представляет только важные линии связи в пределах
отдела, является просто подграфом.




.    Упражнения к п. 3.2                                                                                          .

Страницы