Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Введение в теорию графов
Содержание
- 1. Введение в теорию графов
- 2. ГрафG = (V, R)V – множество вершин
- 3. вершиныV1V2V3V4R23R14R15R45R35R25R34V5смежныене смежныеR12- соединяются ребром- не соединяются ребромV6 – изолированная вершинаV6
- 4. Степень вершиныV1V2V3V4R23R14R15R45R35R25R34V5R12- количество инцидентных ей ребер
- 5. Маршрут графа- последовательность чередующихся вершин и реберV1V2V3V4R23R14R15R45R35R25R34V5R12замкнутый
- 6. Ориентированный графкаждое ребро (дуга) имеет одно направление.
- 7. V1V2V3V4R23R14R34R12R21R32Определите входящие и исходящие степени вершин графа:R24
- 8. 4357855Взвешенный граф (сеть)ребрам или дугам графа поставлены в соответствие числовые величины.V1V2V3V4R23R14R34R12R32R24R21
- 9. Матрица смежности- табличная форма представления графаномера вершиннесмежные вершины
- 10. 4357855V1V2V3V4R23R14R34R12R32R24составить матрицу смежности для ориентированного графа:
- 11. Подграфграф, у которого все вершины и ребра принадлежат исходному графу.V1V2V3V4R23R14R15R45R35R25R34V5R12V1V2V4R14R15R45V5R12V2V3R23R35R25V5
- 12. Остовной связной подграфподграф, содержащий все вершины исходного графа и каждая вершина достижима из любой другой.V3V4R23R14R15R45R35R25R34V5R12V2V1V3V4R23R14R35R34V5V2V1R12
- 13. Деревограф, в котором нет циклов.V3V4R23R14R15R45R35R25R34V5R12V2V1V3V4R23R35R34V5V2V1остовное связное дерево
- 14. Преобразование графа в остовное связное дерево минимального
- 15. Преобразовать граф в остовные связные деревья:V3V4R23R15R45R35R25R34V5R12V2V1
- 16. Алгоритм КрускалаПостроение остовного связного дерева минимального веса.1.
- 17. 2. Сортировка ребер по возрастанию весов.V3V4R23R15R45R35R25R34V5R12V2V11061067834R1210R3410R23R14R1466R257R358R153R454
- 18. R257R236R45433. Ребра последовательно включают в остовное дерево по возрастанию их весов:V3V5V2V1V4R1210R3410R23R1466R257R358R153R454R15
- 19. 4. Алгоритм заканчивает работу, когда все вершины
- 20. Скачать презентанцию
ГрафG = (V, R)V – множество вершин R - множество ребер, соединяющих пару вершин V1V2V3V4R12R23R14R15R45R35R25R34V5Мощность множества – количество вершин (ребер)
Слайды и текст этой презентации
Слайд 3вершины
V1
V2
V3
V4
R23
R14
R15
R45
R35
R25
R34
V5
смежные
не смежные
R12
- соединяются ребром
- не соединяются ребром
V6 – изолированная вершина
V6
Слайд 5Маршрут графа
- последовательность чередующихся вершин и ребер
V1
V2
V3
V4
R23
R14
R15
R45
R35
R25
R34
V5
R12
замкнутый
(цикл)
простая цепь
начальная и конечная
вершины совпадают
все вершины и ребра различны
Слайд 6Ориентированный граф
каждое ребро (дуга) имеет одно направление. Дуга – упорядоченная
пара вершин.
входящая степень
вершины
исходящая степень
вершины
- число входящих в вершину
дуг- число исходящих из вершины дуг
Слайд 84
3
5
7
8
5
5
Взвешенный граф (сеть)
ребрам или дугам графа поставлены в соответствие числовые
величины.
V1
V2
V3
V4
R23
R14
R34
R12
R32
R24
R21
Слайд 11Подграф
граф, у которого все вершины и ребра принадлежат исходному графу.
V1
V2
V3
V4
R23
R14
R15
R45
R35
R25
R34
V5
R12
V1
V2
V4
R14
R15
R45
V5
R12
V2
V3
R23
R35
R25
V5
Слайд 12Остовной связной подграф
подграф, содержащий все вершины исходного графа и каждая
вершина достижима из любой другой.
V3
V4
R23
R14
R15
R45
R35
R25
R34
V5
R12
V2
V1
V3
V4
R23
R14
R35
R34
V5
V2
V1
R12
Слайд 13Дерево
граф, в котором нет циклов.
V3
V4
R23
R14
R15
R45
R35
R25
R34
V5
R12
V2
V1
V3
V4
R23
R35
R34
V5
V2
V1
остовное связное дерево
Слайд 14Преобразование графа в остовное связное дерево минимального веса.
цикломатическое число
γ =
m – n + 1
m – количество ребер
n – количество
вершинV3
V4
R23
R15
R45
R35
R25
R34
V5
R12
V2
V1
γ = 8 – 5 + 1= 4
Слайд 16Алгоритм Крускала
Построение остовного связного дерева минимального веса.
1. Удалить из графа
все ребра
остовной подграф с
изолированными вершинами.
V3
V4
R23
R15
R45
R35
R25
R34
V5
R12
V2
V1
V3
V5
V2
V1
V4
10
6
10
6
7
8
3
4
Слайд 172. Сортировка ребер по возрастанию весов.
V3
V4
R23
R15
R45
R35
R25
R34
V5
R12
V2
V1
10
6
10
6
7
8
3
4
R12
10
R34
10
R23
R14
R14
6
6
R25
7
R35
8
R15
3
R45
4
Слайд 18R25
7
R23
6
R45
4
3
3. Ребра последовательно включают в остовное дерево по возрастанию их
весов:
V3
V5
V2
V1
V4
R12
10
R34
10
R23
R14
6
6
R25
7
R35
8
R15
3
R45
4
R15
Слайд 194. Алгоритм заканчивает работу, когда все вершины будут объединены в
одно множество. Оставшиеся ребра не включаются в остовное дерево.
вес графа
= 3 + 4 + 6 + 7 = 20R25
7
R23
6
R45
4
3
V3
V5
V2
V1
V4
R15
R12
10
R34
10
R14
6
R35
8
γ = 8 – 5 + 1= 4
