9 класс. Граф. Весовая матрица графа. Длина пути между вершинами графа. Вычисление количества путей в направленном ациклическом графе

Граф - это информационная модель, представляющая собой совокупность вершин (узлов) и ребер (линий), соединяющих эти вершины

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

• Карта метро
• Карта дорог
• Генеалогическое древо
• Блок-схема алгоритма
• Планирование строительства
• Структура молекул
• Структура компьютерной сети

Разновидности графов

Весовая матрица графа

Весовая матрица графа — это квадратная таблица, где каждая строка и столбец соответствуют вершинам графа, а элементы матрицы показывают вес ребер между этими вершинами

Граф:

Весовая матрица: