Лекция 2. Сеть. Кратчайшие пути. Алгоритм Дейкстры

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

Эти определения иллюстрируются рис. 1.

Рис. 1. Граф G

В графе G имеется три пути между вершинами и : (), (), (). Ребра и образуют остовное дерево, то же верно для ребер и . Еще одно остовное дерево можно составить из ребер и . Вершина имеет степень 3 в графе G и степень 2 в последнем остовном дереве. Если ребро ориентировано от к , то по-прежнему есть три пути из в , но ни одного пути из в .

В большинстве приложений с ребрами или вершинами ассоциируются некоторые числа. В этом случае граф называется сетью. Все определения теории графов применимы и к сетям. В теории сетей мы обычно используем термины «узлы» и «дуги» вместо «вершины» и «ребра».