Математическое моделирование на графах. Часть 1. Берцун В.Н. - 26 стр.

UptoLike

Составители:

Рубрика:

26 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1

На рис. 1.29 приведен пример сильного и одностороннего графа,

где на рис. 1.29, а (С, А, В, С) – простой контур.

АВ

Сильный граф Односторонний граф

Рис. 1.29

Каждый сильный граф всегда является и односторонним.

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

вершин соединена в точности одним ориентированным ребром.

В полном ориентированном графе без петель с n вершинами и m

дугами

m = n(n – 1)/2 .

Орграф может не содержать контуров. Ациклический (бесконтур-

ный) орграф – орграф, не содержащий контуров, но возможно

имеющий циклы. Например, орграф на рис. 1.29, б является ацикли-

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

роли деревьев в множестве неориентированных графов.

При анализе и оптимизации сложных программ часто пользуются

понятием управляющего графа программы (уграфа) [19]. Вершинам

такого орграфа соответствуют операторы алгоритмического языка, а

дуги соответствуют возможным передачам управления. Если каждой

вершине приписать число операций, которым она соответствует, а

дугам приписать условия перехода к новой вершине, то получим на-

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

ная вершина и одна или несколько конечных вершин, вес которых

считается равным нулю [20]. На рис. 1.30 представлены основные

фрагменты уграфов вычислительных алгоритмов.