Презентация по информатике "Комплексное решение задач-графов используя дерево" (9-10 класс)

• 1 слайд

  Комплексное решение при помощи корневого дерева
  «Корень» = начальная вершина пути
  Количество «ветвей» вершины = количество инцидентных этой вершине ребер*
  Висячая вершина («лист»)= конечная вершина пути
  ___________
  * Любой путь от корня до листа не должен содержать циклов (т.е. вершины в этом пути встречаются лишь раз)
  * Исключение – начальная и конечная вершины совпадают
  Правила и свойства:
  

• 2 слайд

  F
  B
  E
  G
  H
  D
  C
  A
  Найти количество различных вариантов путей AG.
  Найти минимальную стоимость пути AG,
  проходящего через максимальное количество узлов.
  Найти количество возможных вариантов путей AG, проходящие
  через 3 узла (не включая начальный и конечный узел).
  3
  2
  5
  1
  3
  8
  2
  6
  1
  1
  4
  2
  AG - ?
  

• 3 слайд

  0 ур.
  5 ур.
  4 ур.
  3 ур.
  2 ур.
  1 ур.
  А
  С
  D
  B
  H
  H
  H
  E
  F
  E
  G
  E
  G
  F
  G
  E
  G
  F
  G
  F
  G
  G
  F
  G
  1
  1
  3
  4
  2
  6
  5
  2
  2
  8
  2
  8
  2
  8
  1
  3
  1
  1
  3
  3
  3
  3
  1
  9
  11
  13
  15
  12
  8
  10
  12
  

• 4 слайд

  Домашнее задание
  Найти количество путей AF.
  Найти минимальную
  стоимость пути AF.
  Есть ли путь AF, соединяющий
  все вершины, посещая каждую
  лишь раз?
  Какова минимальная
  стоимость пути AF через
  с 2-мя дополнительным
  узлами посещения?
  А
  С
  1
  E
  F
  B
  D
  1
  2
  2
  3
  3
  2
  5
  12
  10
  3
  4
  

• 5 слайд

  D
  A
  1
  1
  4
  B
  C
  F
  G
  E
  H
  K
  1
  2
  2
  2
  3
  3
  5
  6
  8
  8
  Найти количество различных вариантов путей AK.
  Найти минимальную стоимость пути AK, проходящего через максимальное количество узлов.
  Найти количество возможных вариантов путей AG, проходящие через 2 узла (не включая начальный и конечный узел).
  AK - ?
  

Краткое описание документа:

Составление деревьев на основе графа дает решения широкого спектра различных задач в курсах с 7 по 11 классыВ презентации разобран пример построения дерева.Тема берет свое начало в курсе 8 класса ("правило суммы и произведения" при работе с множествами)