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




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


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

Графом называется совокупность двух множеств: множества точек или вершин и множества соединяющих их линий или ребер. Формально граф задается в виде двух множеств: G=(V, Е), где V={v1v2, ..., vn} — множество вершин графа, а Е={е1, е2, ..., еm} — множество ребер графа. Натуральное число n определяет общее количество вершин конкретного графа, а натуральное число m — общее количество ребер графа. Следует заметить, в общем случае не все вершины графа могут соединяться между собой, что ставит в соответствие каждому графу некоторое бинарное отношение PQ, состоящее из всех пар вида <vi, vj>, где vi, vj = V. При этом пара <vi, vj> и, соответственно, пара <vj, vi> принадлежат отношению PG в том и только в том случае, если вершины vi и vj соединяются в графе G некоторым ребром ek=Е. Вершины графа изображаются точками, а ребра — отрезками прямых линий. Рядом с вершинами и ребрами записываются соответствующие номера или идентификаторы, позволяющие их идентифицировать однозначным образом.

Примечание

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

Ориентированный граф также задается в виде двух множеств G=(V, E), где V={v1, v2, ...,vn} — множество вершин графа, а E={е1, е2,...,еm] — множество дуг графа. Натуральное число n определяет общее количество вершин конкретного графа, а натуральное число m — общее количество дуг графа.


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