Презентация к уроку по теме "Графы"

• 1 слайд

  ГРАФИЧЕСКИЕ ИНФОРМАЦИОННЫЕ МОДЕЛИ
  МОДЕЛИРОВАНИЕ И ФОРМАЛИЗАЦИЯ
  

• 2 слайд

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

• 3 слайд

  Граф называется взвешенным, если его вершины или рёбра характеризуются некоторой дополнительной информацией - весами вершин или рёбер.
  Взвешенный граф
  D
  E
  A
  80
  70
  60
  90
  50
  C
  B
  90
  Протяжённость дорог в километрах
  

• 4 слайд

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

• 5 слайд

  Дерево для решения задачи
  0
  1
  2
  2
  2
  2
  2
  1
  1
  1
  1
  2
  1
  1
  2
  Использование графов при решении задач
  Сколько существует трёхзначных чисел, состоящих из цифр 1 и 2?
  XYZ
  На 1 месте (X) могут быть любые 2 цифры – 1 и 2 – 2 варианта
  На 2 месте (Y) могут быть любые 2 цифры – 1 и 2 – 2 варианта
  На 3 месте (Z) могут быть любые 2 цифры - 1 и 2 – 2 варианта
  
  Следовательно: 2*2*2 = 8
  Ответ: 8 вариантов
  

• 6 слайд

  Сколько существует трёхзначных чисел, состоящих из цифр от 0 до 9 при условии, цифры используются 1 раз?
  XYZ
  На 1 месте (X) могут быть любые 10 цифр
  На 2 месте (Y) могут быть любые 9 цифр
  На 3 месте (Z) могут быть любые 8 цифр
  
  Следовательно:10*9*8
  Ответ: 720 вариантов
  

• 7 слайд

  Вопросы и задания
  Грунтовая дорога проходит последовательно через населённые пункты А, B, С и D. При этом длина грунтовой дороги между А и В равна 40 км, между В и С – 25 км,и между С и D – 10 км. Между А и D дороги нет. Между А и С построили новое асфальтовое шоссе длиной 30 км.
  Оцените минимально возможное время движения велосипедиста из пункта А в пункт D, если его скорость по грунтовой дороге - 20 км/ч, по шоссе - 30 км/ч.
  А
  B
  D
  C
  40 гр
  25 гр
  30 ш
  10 гр
  Вопрос: минимально возможное время движения велосипедиста из
  пункта А в пункт D
  Ответ: 1,5 часа