ДЛЯ групп 112, 113 на 12.12.25
презентация к уроку

Слайд 1

Слайд 2

Родоначальником теории графов считается выдающийся математик, член Петербургской академии наук Леонард Эйлер . В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Слайд 3

Граф – (от греческого grapho – пишу) - это средство наглядного представления элементов объекта связей между ними . Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год). Термин “граф” впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.

Слайд 4

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

Слайд 5

Основные понятия теории графов Граф G задаётся с помощью пары множеств G=(V, E) , где V - множество вершин, E – множество ребёр , соединяющих пары вершин.

Слайд 6

Основные понятия теории графов 1 ) Маршрут на графе – это последовательность ребер, в которой конец одного ребра служит началом следующего (циклический маршрут – если конец последнего ребра последовательности совпадает с началом 1-го ребра) 2) Цепь – это маршрут, в котором каждое ребро содержится не более одного раза 3) Цикл – это цепь, являющаяся циклическим маршрутом 4) Простая цепь – это цепь, проходящая через каждую свою вершину ровно 1 раз

Слайд 7

Основные понятия теории графов 5) Простой цикл – это цикл, являющийся простой цепью 6) Связанные вершины – это вершины ( например, А и B) , для которых существует цепь, начинающаяся в А и заканчивающаяся в B 7 ) Связный граф – это граф, у которого любые 2 вершины связанны. Если граф несвязен, то в нем можно выделить так называемые связанные компоненты (т.е. множества вершин, соединенных ребрами исходного графа, каждое из которых является связным графом) Один и тот же граф может быть изображен по-разному.

Слайд 8

ВИДЫ ГРАФОВ

Слайд 9

Обычный (неориентированный) граф 2 вершины могут быть соединены только одним ребром. Соединяющие линии называются ребрами. (смежные вершины – это 2 вершины, соединенные ребром)

Слайд 11

Ориентированный граф (орграф) - это граф, у которого на линиях, соединяющих вершины, указано направление (соединяющие линии называются дугами)

Слайд 12

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

Слайд 13

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

Слайд 14

Семантический граф - это граф или орграф, у которого около каждого ребра проставлено не число, а иная информация, характеризующее связь между соответствующими вершинами.

Слайд 15

Подграф – граф, у которого все вершины и ребра принадлежат графу G . Остовной подграф – подграф графа G , который содержит все его вершины.

Слайд 16

Способы представления графов: 1) графический 2) табличный (таблица смежности)

Слайд 17

Пример Дан граф. Выбрать его табличное представление Выбрать его табличное представление:

Слайд 18

Задача 1 Сколько различных путей существует из А в К. 1 СПОСОБ РЕШЕНИЯ: РУЧНОЙ (ВРУЧНУЮ СЧИТАЕМ КОЛИЧЕСТВО ПУТЕЙ ИЗ А В К) ОТВЕТ: 17 2 СПОСОБ РЕШЕНИЯ: ПОСТРОЕНИЕ ДЕРЕВА РЕШЕНИЯ ОТВЕТ: 17

Слайд 19

Задача 2 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? Решение

Слайд 20

Задача 2 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? Решение: А - 1 Б – 1 В – 1+1=2 Д – 1 Г – 1 Е – 1+2=3 Ж – 1+1=2 К – 3+2+1+2=8 Ответ: 8 Назад

Слайд 21

Задача 3 На рисунке — схема дорог, связывающих города A, Б, B, Г, Д, E, Ж, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? Решение

Слайд 22

Задача 3 На рисунке — схема дорог, связывающих города A, Б, B, Г, Д, E, Ж, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? Решение: А - 1 Б – 1 В – 1+1=2 Д – 1 Г – 1 Ж – 1+1+1=3 Е – 1+2=3 К – 3+1+3=7 Ответ: 7 Назад

Слайд 26

Использованные ресурсы: https://foxford.ru/wiki/informatika/teoriya-grafov 2) табличный (таблица смежности) https:// urok.1sept.ru/articles/631065

Слайд 27

Спасибо за внимание