🗊Презентация Графы и их применение

Графы и их применение

Некоторые основные понятия теории графов Граф – рисунок, состоящий из множества точек и множества отрезков, оба конца которых принадлежат заданному множеству точек. Степень вершины называется число ребер графа, которым принадлежит эта вершина. Путь графе от А1 до Аn в графе называется такая последовательность ребер, ведущая от А1 до Аn, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза. Цикл в графе называется путь, в котором совпадают его начальная и конечная вершины. Граф называется несвязным, если существуют хотя бы две вершины несвязные путем Граф называется деревом, если для каждой пары вершин существует единственный соединяющий их путь

Зачем нужны деревья? Для организации данных Классификация объектов Описания структуры Для решения задач, в которых надо найти Все существующие решения Самое короткое решение или длинное решение Разработать стратегию игры И так далее.

Отыскание пути

Решение задачи

МАТРИЦЫ ГРАФОВ

Спасибо за внимание