Решение логических задач с помощью графов

• 1 слайд

  Решение логических задач
  с помощью графов
  Подготовил:
  Учитель информатики МБОУ «ЦО №34»
  Титова Галина Юрьевна
  

• 2 слайд

  Денеш Кениг
  Венгерский математик
  в 1936 году впервые ввел
  термин «граф»
  Но первая работа по теории графов принадлежала перу великого Леонардо Эйлера и была написана еще в 1736 году
  

• 3 слайд

  Основные понятия:
  Графы – это рисунки, которые состоят из точек и линий, соединяющих эти точки.
  Каждая пара точек в графе может быть соединена линиями. Линия указывает на связь между двумя точками.
  Точки называются вершинами графа, а линиями рёбрами.
  Ребро может иметь направление, которое указывается стрелочкой.
  У графа обязательно есть вершины.
  Граф без рёбер называется пустым.
  

• 4 слайд

  Примеры графов:
  

• 5 слайд

  Граф вида «Дерево»
  Данная форма модели применяется тогда, когда элементы моделируемого объекта находятся в состоянии какого-либо подчинения и соподчинения, когда есть отношение иерархичности.
  Примеры графов вида «Дерево»
  

• 6 слайд

  Примеры решения задач:
  Задача 1.
  
  У Юры два автомобиля, четыре медвежонка и три мяча. Он хочет выбрать из
  этих игрушек один автомобиль, одного медвежонка и один мяч.
  Сколько у него есть вариантов выбора?
  Ответ: 24 варианта.
  

• 7 слайд

  Примеры решения задач:
  Задача 2.
  Винни-Пух решил навестить своих друзей: Пяточка, Кролика и Ослика. Ему нужно побывать у каждого из них и вернуться домой. Если он к кому-то не зайдет, то его друг обидится. Но Винни-Пух не любит длительных путешествий. Помогите ему выбрать кратчайший путь, если известно, как расположены домики друзей и на каком расстоянии они находятся друг от друга:
  

• 8 слайд

  Примеры решения задач:
  Построить граф, используя условия задачи, расставить на нем расстояния.
  Определить пары симметричных вариантов (например: В – К – П – И – В и В – И – П – К – В) и вычеркнуть на графе один вариант из каждой пары.
  Выписать оставшиеся варианты и подсчитать расстояния:
  В – К – П – И – В = 60 + 50 + 55 + 30
  В – К – И – П – В = 60 + 45 + 55 + 40
  В – И – К – П – В = 30 + 45 + 50 + 40
  Дано:
  И – Ослик
  В – Винни-Пух
  П – Пяточек
  К – Кролик
  
  Найти:
  Кратчайший путь
  Рассуждения:
  

• 9 слайд

  Рассуждения:
  1. Выстраиваем вспомогательные линии
  2. Строим граф, используя условия задачи
  К
  П
  И
  В
  П
  И
  К
  И
  К
  П
  И
  П
  И
  К
  П
  К
  В
  В
  В
  В
  В
  В
  3. Расставляем расстояния, используя данные рисунка
  60
  40
  30
  50
  45
  50
  55
  55
  45
  55
  55
  45
  45
  50
  50
  30
  40
  30
  60
  60
  40
  4. Определяем пары симметричных вариантов
  5. Выписываем оставшиеся варианты и подсчитываем результаты
  В – К – П – И – В = 60 + 50 + 55 + 30 =
  В – К – И – П – В = 60 + 45 + 55 + 40 =
  В – И – К – П – В = 30 + 45 + 50 + 40 =
  195
  200
  165
  

• 10 слайд

  Задача на закрепление:
  Пятачок решил навестить своих друзей – Винни-Пуха, Кролика и Ослика. Ему надо побывать у каждого и вернуться домой. Помогите Пятачку выбрать кратчайший путь. Расположение домиков:
  Ответ: 165
  

• 11 слайд

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

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