Презентация по информатике "Решение логических задач с помощью графов" (6 класс)

Решение логических задач с помощью графов Графы   являются   существенным   элементом   математических   моделей   в самых   разнообразных   областях   науки   и   практики.   Они   помогают   наглядно представить   взаимоотношения   между   объектами   или   событиями   в   сложных системах. Многие алгоритмические задачи дискретной математики могут быть сформулированы как задачи, так или иначе связанные с графами. Термин граф впервые ввёл 1936г Венгерский математик  Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющие эти точки отрезков прямых или кривых. Решение   многих   математических   задач   упрощается,   если   удается использовать   графы.   Представление   данных   в   виде   графа   придает   им наглядность   и   простоту. Многие   математические   доказательства   также упрощаются,   приобретают   убедительность,   если   пользоваться   графами. Для решения логических задач их также удобно использовать. Графы – это рисунки, которые состоят из точек и линий, соединяющих эти точки. Каждая   пара   точек   в   графе   может   быть соединена   линиями.   Линия указывает на связь между двумя точками. Точки называются вершинами графа, а линиями рёбрами. Ребро может иметь направление, которое указывается стрелочкой. У графа обязательно есть вершины. Граф без рёбер называется пустым. Примеры графов Особым видом графа является дерево. Данная форма модели применяется тогда, когда элементы моделируемого объекта находятся в состоянии какого­ либо подчинения и соподчинения, когда есть отношение иерархичности. Примеры графов вида «Дерево» Примеры решения Задача 1.  задач с помощью графов У Юры два автомобиля, четыре машинки и три мяча. Он хочет выбрать из этих игрушек один автомобиль, одного медвежонка и один мяч. Сколько у него есть вариантов выбора? 1 мячи 2 3 1 1 2 3 1 1 2 3 1 1 2 3 1 1 2 3 1 1 2 3 1 1 2 3 1 1 2 3 1 2 3 4 1 2 3 4 медвежат а 1 автомобили 1 2 Ответ: 24 варианта. Задача 2. Винни­Пух решил навестить своих друзей: Пяточка, Кролика и Ослика. Ему нужно побывать у каждого из них и вернуться домой. Если он к кому­то не зайдет,   то   его   друг   обидится.   Но   Винни­Пух   не   любит   длительных путешествий.   Помогите   ему   выбрать   кратчайший   путь,   если   известно,   как расположены домики друзей и на каком расстоянии они находятся друг от друга: Винни­Пух 30 55 40 Иа Пятачок 60 45 50 Кролик Рисунок 1 Дано:                                  Рассуждения: И – Ослик                           1. Построить граф, используя условия задачи, расставить В – Винни­Пух П – Пятачок  К – Кролик  Найти: Кратчайший путь. В 40 55 П И 45 В И 30 55 П 50 К на нем расстояния. 2. Определить пары симметричных вариантов (например: В – К – П – И – В и В – И – П – К – В) и вычеркнуть на  графе один вариант из каждой пары. 3. Выписать оставшиеся варианты и подсчитать  расстояния: В – К – П – И – В = 60 + 50 + 55 + 30 = 195 В – К – И – П – В = 60 + 45 + 55 + 40 = 200 В – И – К – П – В = 30 + 45 + 50 + 40 = 165 В В 30 И 45 К 50 К 60 45 И 55 В 60 К 50 В 40 50 П П 55 К 45 60 П 40 В И 30 Ответ: самый короткий путь Винни­Пуха: В – И – К – П – В = 165  Задача на закрепление. Пятачок решил навестить своих друзей – Винни­Пуха, Кролика и Ослика. Ему надо   побывать   у   каждого   и   вернуться   домой.   Помогите   Пятачку   выбрать кратчайший путь. Расположение домиков: Рисунок 1.