Самоучитель по UML




Теория графов - часть 2


При этом каждая дуга еk=Е ориентированного графа G имеет свое начало— некоторую единственную вершину vi=V и конец — некоторую единственную вершину vj=V, В отличие от ребра, дуга всегда имеет обозначение со стрелочкой, которая направлена к конечной вершине дуги. Множество дуг ставит в соответствие каждому ориентированному графу некоторое бинарное отношение PG, состоящее из всех пар вида <vi, vj>, где vi, vj=V. При этом пара <vi, vj> принадлежит отношению PG в том и только в том случае, если вершины vi и vj соединяются в графе G некоторой дугой еk=Е с началом в вершине viи концом в вершине vj.

Ниже представлены два примера конкретных графов (рис. 2.4). При этом первый из них (рис. 2.4, а) является неориентированным графом, а второй (рис. 2.4, б) — ориентированным графом. Как нетрудно заметить, для неориентированного графа ребро е1 соединяет вершины v1 и v2, ребро е2 — вершины v1 и v3, а ребро e3 — вершины v2 и v3 и т. д. Последнее ребро, e8, соединяет вершины v4 и v5, тем самым задается описание графа в целом. Других ребер данный граф не содержит, как не содержит других вершин, не изображенных на рисунке. Так, хотя ребра е6 и e7 визуально пересекаются, но точка их пересечения не является вершиной графа.

Для ориентированного графа (рис. 2.4, б) ситуация несколько иная. А именно, вершины v1 и v2 соединены дугой е1, для которой вершина v2 является началом дуги, а вершина v1 — концом этой дуги. Далее дуга е2 соединяет вершины v1 и v4, при этом началом дуги e2

является вершина v1, а концом — вершина v4.

Рис. 2.4. Примеры неориентированного (а) и ориентированного (б) графов

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


Содержание  Назад  Вперед