презентация "Моделирование. Введение в теорию графов"
презентация к уроку по информатике и икт (11 класс) на тему

Слайд 1

Слайд 2

Граф G = (V, R) V – множество вершин R - множество ребер, соединяющих пару вершин V 1 V 2 V 3 V 4 R 12 R 23 R 14 R 15 R 45 R 35 R 25 R 34 V 5 Мощность множества – количество вершин (ребер)

Слайд 3

вершины V 1 V 2 V 3 V 4 R 23 R 14 R 15 R 45 R 35 R 25 R 34 V 5 смежные не смежные R 12 - соединяются ребром - не соединяются ребром V 6 – изолированная вершина V 6

Слайд 4

Степень вершины V 1 V 2 V 3 V 4 R 23 R 14 R 15 R 45 R 35 R 25 R 34 V 5 R 12 - количество инцидентных ей ребер V 1 3 V 2 3 V 3 3 V 4 3 V 5 4

Слайд 5

Маршрут графа - последовательность чередующихся вершин и ребер V 1 V 2 V 3 V 4 R 23 R 14 R 15 R 45 R 35 R 25 R 34 V 5 R 12 з амкнутый (цикл) п ростая цепь н ачальная и конечная вершины совпадают в се вершины и ребра различны

Слайд 6

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

Слайд 7

V 1 V 2 V 3 V 4 R 23 R 14 R 34 R 12 R 2 1 R 3 2 Определите входящие и исходящие степени вершин графа: входящая исходящая V 1 V 2 V 3 V 4 R 24

Слайд 8

4 3 5 7 8 5 5 Взвешенный граф (сеть) ребрам или дугам графа поставлены в соответствие числовые величины. V 1 V 2 V 3 V 4 R 23 R 14 R 34 R 12 R 3 2 R 24 R 2 1

Слайд 9

Матрица смежности 1 2 3 4 1 0 35 0 17 2 35 0 32 0 3 0 32 0 18 4 17 0 18 0 - табличная форма представления графа н омера вершин несмежные вершины

Слайд 10

4 3 5 7 8 5 5 V 1 V 2 V 3 V 4 R 23 R 14 R 34 R 12 R 3 2 R 24 с оставить матрицу смежности для ориентированного графа:

Слайд 11

Подграф граф, у которого все вершины и ребра принадлежат исходному графу. V 1 V 2 V 3 V 4 R 23 R 14 R 15 R 45 R 35 R 25 R 34 V 5 R 12 V 1 V 2 V 4 R 14 R 15 R 45 V 5 R 12 V 2 V 3 R 23 R 35 R 25 V 5

Слайд 12

Остовной связной подграф подграф, содержащий все вершины исходного графа и каждая вершина достижима из любой другой. V 3 V 4 R 23 R 14 R 15 R 45 R 35 R 25 R 34 V 5 R 12 V 2 V 1 V 3 V 4 R 23 R 14 R 35 R 34 V 5 V 2 V 1 R 12

Слайд 13

Дерево граф, в котором нет циклов. V 3 V 4 R 23 R 14 R 15 R 45 R 35 R 25 R 34 V 5 R 12 V 2 V 1 V 3 V 4 R 23 R 35 R 34 V 5 V 2 V 1 о стовное связное дерево

Слайд 14

Преобразование графа в остовное связное дерево минимального веса. цикломатическое число γ = m – n + 1 m – количество ребер n – количество вершин V 3 V 4 R 23 R 15 R 45 R 35 R 25 R 34 V 5 R 12 V 2 V 1 γ = 8 – 5 + 1 = 4

Слайд 15

Преобразовать граф в остовные связные деревья: V 3 V 4 R 23 R 15 R 45 R 35 R 25 R 34 V 5 R 12 V 2 V 1

Слайд 16

Алгоритм Крускала Построение остовного связного дерева минимального веса. 1. Удалить из графа все ребра о стовной подграф с изолированными вершинами. V 3 V 4 R 23 R 15 R 45 R 35 R 25 R 34 V 5 R 12 V 2 V 1 V 3 V 5 V 2 V 1 V 4 10 6 10 6 7 8 3 4

Слайд 17

2. Сортировка ребер по возрастанию весов. V 3 V 4 R 23 R 15 R 45 R 35 R 25 R 34 V 5 R 12 V 2 V 1 10 6 10 6 7 8 3 4 R 12 10 R 34 10 R 23 R 1 4 R 1 4 6 6 R 25 7 R 35 8 R 15 3 R 45 4

Слайд 18

R 25 7 R 23 6 R 45 4 3 3. Ребра последовательно включают в остовное дерево по возрастанию их весов: V 3 V 5 V 2 V 1 V 4 R 12 10 R 34 10 R 23 R 1 4 6 6 R 25 7 R 35 8 R 15 3 R 45 4 R 15

Слайд 19

4. Алгоритм заканчивает работу, когда все вершины будут объединены в одно множество. Оставшиеся ребра не включаются в остовное дерево. в ес графа = 3 + 4 + 6 + 7 = 20 R 25 7 R 23 6 R 45 4 3 V 3 V 5 V 2 V 1 V 4 R 15 R 12 10 R 34 10 R 1 4 6 R 35 8 γ = 8 – 5 + 1 = 4