Итак, если произвольные точки пространства соединены между собой отрезками или дугами (необязательно все), то такое соединение (схема) называется графом. Граф — это набор точек, некоторые из которых соединены линиями. Эти точки называются вершинами. Соединяющие их линии называются ребрами графа. Граф - это геометрическая фигура, состоящая из точек (вершины графа) и линий, их соединяющих (ребра графа). При этом с помощью вершин изображают элементы некоторого множества (предметов, людей и т.д.), а с помощью рёбер - определённые связи между элементами. Для удобства иллюстрации условия задачи, вершины графа могут быть заменены кругами или прямоугольниками. Задача. Вася, Коля, Петя, Аня и Наташа - лучшие лыжники в пятом классе. Для участия в соревнованиях нужно выбрать из них одного мальчика и одну девочку. Сколькими способами это можно сделать? Решение: Эту задачу можно решить с помощью следующей схемы. Ответ: 6 способов. Дерево – это граф, схема, отражающая структуру задачи, упорядочения многошагового процесса принятия решений. Дерево – это особый тип графа, который является связным и ациклическим, что означает, что в графе нет циклов. Основное различие между графом и деревом состоит в том, что дерево - это иерархическая структура, которая имеет только один путь между вершинами, тогда как граф - это сетевая структура данных, которая может иметь много путей между вершинами. Внешне такая схема напоминает дерево, отсюда и название – дерево возможных вариантов. Дерево состоит из корня и ветвей, соответственно, ветви дерева отображают различные события, которые могут иметь место, а корень дерева – состояние, в котором возникает необходимость выбора. Задача. «Сколько двузначных чисел можно записать, используя цифры 5, 4 и 7?» Задача. «Сколько двузначных чисел можно записать, используя цифры 5, 4 и 7?» Решение.
Do'stlaringiz bilan baham: |
