Сетевые методы и графы в автоматизированном управлении. Лекция 2

1. Лекция 2 – по курсу «Сетевые методы и графы в автоматизированном управлении»

Формулы и рисунки

2. Связность и компоненты графа

v3
v1
v2
v5
v7
v4
v6
v8
v9
Граф G с компонентами G1 , G2 , G3 и G4.

3. Объединение графов

v1
l1
v2
v1
l1
v2
v1
l9
l5
v3
l4
l2
l3
l5
l9
v3
l3
l8
l10
v6
G1
l2
v5
v6
G2
v4
l7
l6
l8
l3
v4
l6
v5
l4
l5
v3
v4
l7
v2
l1
l10
l6
v5
v6
G3

4. Пересечение графов

v1
l1
v2
v1
l1
v2
v1
l9
l5
v3
l4
l2
l3
l5
l9
v3
l3
l8
l10
v6
G1
l2
vv44
l7
l6
v5
v6
G2
l8
ll33
v4
l6
v5
l4
l5l5
vv33
v4
l7
v2
ll11
l10
ll66
vv55
vv66
G
G33

5. Пересечение графов

v1
l1
v2
v1
l1
v2
v1
l9
l5
v3
l4
l2
l3
l5
l9
v3
l3
l8
l10
v6
G1
l2
vv44
l7
l6
v5
v6
G2
l8
ll33
v4
l6
v5
l4
l5l5
vv33
v4
l7
v2
ll11
l10
ll66
vv55
vv66
G
G33

6. Кольцевая сумма

v1
l5
v3
l1
l4
v2
v1
l1
v2
v1
l2
l5
l9
l8
l5
l4
v3
l3
v3
l3
v4
v4
l7
l6
l10
v6
v5
G1
v1 l1
l9 l l4
9
l6
v5
v6
G2
v3
l7
l7
l10
v5
v5
v2
v2
l8
l2 l l8
2
l3
v4 v4
l10
l6
v6
G3G3

7. Удаление вершины

v3
l1
v4
v3
l1
v4
l2
l3
l4
l2
l3
l4
v2
l5
v5
v2
l5
v5
l7
v1
l6
l8
G
v6
v6
G - v1

8. Удаление ребра

v3
l1
v4
v3
v3 l1
l1 v4
v4
l2
l3
l4
l2
l2l3
l3 l
4
l4
v2
l5
v5
v2
v2 l5
l5
v5
v5
v6
v6
l7
v1
l6
l6
l8
G
v6
v1
G -Gv1– (l7, l8)

9. Замыкание или отождествление

v4
l1
l2
l3
v3
l4
l1
(v3, v4)
l2
l3
l5
v1
v2
G
l4
l5
v1
v2
Результат замыкания вершин v3 и v4.

10. Стягивание

v4
l1
l2
l3
v3
l4
l1
(v
,
v
)
4
3
(v , v )
3
4
l2
l3
l2 l3 l4 l4
l5
v1
v2
G
l5
(vv11, v2)
v2
Результат замыкания вершин v3 и v4.
граф G после стягивания l1 и l5.

11.

12. Разделимый граф

v7
v1
v9
v2
v3
v8
v5
v7
v1
v2
v1
v2
v8
v9
v3
v2
v4
v4
Граф G
Блоки графа G
Граф G является разделимым. У него три точки сочленения: v1, v2, v3.
v5

13. Изоморфные графы

v1'
v1
v2
v4'
v3
v2'
v6'
v4
v5
v6
v3'
Изоморфные графы
v5'