Теория графов презентация

Задача прокладки коммуникаций
2
3
4
1
5

Граф G:
G=(V,R),
где V – множество вершин
R – множество рёбер, соединяющих пары вершин
V2
V3
V1
V4
V5
R12
R23
R34
R14
R25
R35
R45
R15

Граф G:
Смежные вершины –
те, которые соединены рёбрами
V2
V3
V1
V4
V5
R12
R23
R34
R14
R25
R35
R45
R15

Граф G:
Мощность множеств V и R- количество вершин и количество ребер соответственно
V2
V3
V1
V4
V5
R12
R23
R34
R14
R25
R35
R45
R15
5 вершин и 8 рёбер

Граф G:
ребро и любая из его двух вершин называются инцидентными
V2
V3
V1
V4
V5
R12
R23
R34
R14
R25
R35
R45
R15

Граф G:
Степень вершины – количество инцидентных ей рёбер
V2
V3
V1
V4
V5
R12
R23
R34
R14
R25
R35
R45
R15
Степень V3 – 3
Степень V5 – 4

Граф G:
Маршрут графа – это последовательность чередующихся вершин и рёбер
Замкнутый (циклическим) – называется тот маршрут, у которого начальная и конечная вершины совпадают
V2
V3
V1
V4
V5
R12
R23
R34
R14
R25
R35
R45
R15

Граф G:
Маршрут называется простой цепью, если все его вершины и рёбра - различны
V2
V3
V1
V4
V5
R12
R23
R34
R14
R25
R35
R45
R15

Граф G:
Граф является связным если каждая его вершина достижима из другой вершины
V2
V3
V1
V4
V5
R12
R23
R34
R14
R25
R35
R45
R15