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

Научиться понимать, как графы описываются матрицами, как вычислять длину пути и как считать количество путей в ациклических направленных графах.

Графы окружают нас повсюду: карты дорог, схемы метро, социальные сети, интернет. Умение работать с графами позволяет решать практические задачи: находить кратчайший маршрут, оценивать количество возможных вариантов, анализировать связи. Это фундамент для изучения алгоритмов и программирования.

• Граф — это математическая модель, состоящая из вершин и рёбер, которые соединяют пары вершин.
• В направленном графе каждое ребро имеет направление, поэтому путь можно проходить только в указанном направлении.
• Взвешенный граф — это граф, каждому ребру которого присвоено число (вес), например, расстояние или стоимость.
• Весовая матрица — это таблица, в которой на пересечении строки и столбца записан вес ребра между соответствующими вершинами.
• Длина пути в взвешенном графе — это сумма весов рёбер, составляющих этот путь.
• В невзвешенном графе длина пути равна количеству рёбер в нём.
• Ациклический граф — это направленный граф, в котором нет циклов (нельзя вернуться в исходную вершину, следуя по стрелкам).
• Количество путей между вершинами в ациклическом графе можно вычислить, используя динамическое программирование: количество путей в вершину равно сумме количеств путей во все вершины, из которых есть ребро в данную.

Граф

Способ описания связей между объектами: объекты — это вершины, связи — рёбра.

Вершина (узел)

Точка графа, обозначающая объект (например, город, человек, страница).

Ребро (дуга)

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

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

Квадратная таблица, где число на пересечении i-й строки и j-го столбца равно весу ребра из вершины i в вершину j. Если ребра нет, ставится 0 или бесконечность.

Путь в графе

Последовательность вершин, в которой каждая следующая соединена с предыдущей ребром (в направленном графе — по направлению).

Длина пути

Сумма весов рёбер, составляющих путь (если весов нет — количество рёбер).

Ациклический граф

Направленный граф, в котором невозможно, начав движение из вершины по стрелкам, вернуться в неё же.

• Весовая матрица для графа с n вершинами имеет размер n×n.
• Для невзвешенного графа весовая матрица содержит 1 (если есть ребро) и 0 (если нет).
• В направленном графе матрица может быть несимметричной: вес из A в B не обязан равняться весу из B в A.
• Длина пути в взвешенном графе — это сумма весов всех рёбер пути. Например, если путь A→B (вес 3) и B→C (вес 5), то длина пути A→C равна 8.
• Количество путей в ациклическом графе можно вычислить по формуле: f(v) = сумма f(u) для всех u, из которых есть ребро в v, при этом f(начальной вершины) = 1.
• Если в графе есть цикл, то количество путей может быть бесконечным, поэтому для подсчёта количества путей используют только ациклические графы.

1. Пример 1случай

   Схема дорог между городами

   Пояснение

   • города — вершины, дороги — рёбра, вес — расстояние в километрах
   • Длина пути из Москвы в Санкт-Петербург через Тверь — сумма расстояний Москва–Тверь и Тверь–Санкт-Петербург
2. Пример 2случай

   Организация проекта

   Пояснение

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

   В турнирной таблице

   Пояснение

   • команды — вершины, ребро указывает на победу одной команды над другой
   • Вес может быть разницей забитых и пропущенных мячей

• Графы используются в поисковых системах: алгоритм PageRank, который определяет важность веб-страниц, основан на анализе связей между страницами (гиперссылок).
• Карта метро — это классический пример взвешенного графа, где вес ребра — время или расстояние между станциями.
• В социальных сетях графы помогают находить друзей и рекомендовать контент, анализируя связи между пользователями.

• Представление графов в программировании
• Алгоритмы поиска кратчайшего пути (Дейкстра, Флойд)
• Динамическое программирование