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

Другой пример графической нотации заимствован из теории графов. Формально граф задается множеством G=(V, Е), где V={v1, v2,..., v_n} – множество вершин графа, а Е={е1, е2,..., е_m} – множество ребер, связывающих вершины графа. Натуральные числа n и m определяют соответственно количество вершин и количество ребер графа. Не все вершины конкретного графа соединены его ребрами: на каждом графе должно быть задано некоторое бинарное отношение связности PG, состоящее из всех пар вида (v_i, v_j), где v_i, v_j Î V. При этом пара (v_i, v_j) принадлежит отношению PG в том и только в том случае, если вершины v_i и v_j соединяются в графе G некоторым ребром e_k Î Е.

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

а) б)

Рисунок 2 – Примеры визуального представления графовых моделей

а) – неориентированный граф; б) – ориентированный граф