Ключевая информация §3.5

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

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

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

Граф однозначно задан, если задано множество его вершин, множество ребер (дуг) и указано, какие вершины какими ребрами соединены.

Формализация при построении графа включает в себя следующие этапы:

• выявление всех элементов объекта;
• определение элементов (названий, номеров, весов и т.п.);
• установление наличия и вида связи  (односторонняя или двухсторонняя) между элементами;
• определение характеристик связей – весов ребер и дуг;
• выбор формы изображения вершин и ребер, введение условных обозначений в случае необходимости;
• представление выделенных элементов и связей в графическом виде.

Для компьютерного моделирования более удобным является символическое и/или табличное задание графа.

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

---