Презентация по вероятности и статистике на тему "Представление об ориентированных графах "

Слайд #1

тест

Слайд #2

Вопрос 1
конечное множество линий и точек
множество точек, некоторые из которых соединены в многоугольники
изображение объектов и связей между ними с помощью точек и линий
2
Графом называется...

Слайд #3

Вопрос 2
ребрами
вершинами
объектами
3
Точки  в графе называются...

Слайд #4

Вопрос 3
вершины
ребра
отрезки
4
Линии  графа - это...

Слайд #5

Вопрос 4
в двух графах вершины связаны ребрами в одном и том же порядке, то один граф можно получить из другого, передвигая вершины.
в двух графах вершины связаны ребрами в любом порядке, то один граф можно получить из другого, передвигая вершины.
5
Графы считают одинаковыми, если...

Слайд #6

Вопрос 5
показатель вершины
степень вершины
валентностью вершины
6
___ в графе - это количество исходящих из нее ребер.

Слайд #7

Вопрос 6
связанным
циклом
цепью
7
Если граф состоит из одной-единственной цепи, то такой граф называют...

Слайд #8

Вопрос 7
2
3
4
8
На рисунке степень вершины Г равна

Слайд #9

Вопрос 8
3
4
2
9
На рисунке степень вершины D равна

Слайд #10

Вопрос 9
цепью
циклом
связанным
10
Замкнутый путь, у которого начало и конец в одной вершине, а рёбра и промежуточные вершины не повторяются, в графе называют...

Слайд #11

Представление об ориентированных графах
Классная работа 17.03.25

Слайд #12

Влияние оратора
Одноклассники Андрей, Борис, Вадим, Григорий, Дмитрий и Евгений устроили турнир
по настольному теннису и решили играть каждый с каждым. Турнир ещё не закончен.
Рёбра графа показывают, кто с кем сыграл к этому моменту

Слайд #13

Влияние оратора
Ничьих в настольном теннисе не бывает, значит, каждая встреча закончилась победой одного игрока.

Слайд #14

Влияние оратора
Нарисуем вместо ребер стрелки.
Каждая стрелка ведет от победителя к проигравшему

Слайд #15

Влияние оратора
Нарисуем вместо ребер стрелки.

Каждая стрелка ведет от победителя к проигравшему.

Ребра получили направления, поэтому эти ребра назовем направленными ребрами.

Слайд #16

Граф называется ориентированным, если указано направление (начало и конец) каждого ребра.

Входящая степень вершины – это число ребер входящих в вершину.

Исходящая степень вершины - это число ребер исходящих из вершины.
16
Определения

Слайд #17

В ориентированном графе сумма исходящих степеней всех вершин равна сумме входящих степеней всех вершин и равна числу ребра.
17
Свойство

Слайд #18

Задачи

Слайд #19

Задача 1
19

Слайд #20

Задача 1. решение
20
1
2
0
4
3

Слайд #21

Задача 1. решение
21
1
2
0
4
3
Никита – 1 место
Олег - 2 место
Лёва – 3 место
Коля – 4 место
Миша – 5 место

Слайд #22

Задача 2
22

Слайд #23

Задача 3
23

Слайд #24

Задача 3
24

Слайд #25

Задача о кёнигсбергских мостах
Город Кёнигсберг (ныне Калининград) был разделен на четыре части рекой Прегель. Эти части были соединены семью мостами. Задача состоит в том, чтобы найти маршрут, который позволил бы пройти по всем семи мостам, проходя по каждому мосту ровно один раз, и вернуться в исходную точку.
25

Слайд #26

Задача о кёнигсбергских мостах
.
26

Слайд #27

Задача о кёнигсбергских мостах
.
27

Слайд #28

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

28

Слайд #29

Задача о кёнигсбергских мостах
.
29
Граф кёнигсбергских мостов имел четыре нечётные вершины , следовательно невозможно пройти по всем мостам , не проходя ни по одному из них дважды .