Теория графов

Граф – это средство для наглядного представления состава и структуры системы.

Основные понятия
Граф состоит из вершин, связанных между собой дугами или ребрами. Вершины могут быть обозначены кругами, овалами, точками, прямоугольниками.
Связи между вершинами изображаются линиями.
Направленную линию называют дугой, не направленную ребром.

Граф, в котором все линии направленные, называется ориентированным графом(орграфом)

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

Взвешенный граф – это граф с вершинами или линиями которого связана дополнительная информация. Ее называют весом.

Таблица 11.3. Примеры взвешенных графов
Примеры взвешенных графов