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

• 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
  Граф кёнигсбергских мостов имел четыре нечётные вершины , следовательно невозможно пройти по всем мостам , не проходя ни по одному из них дважды .