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

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

Важными понятиями теории графов являются понятия маршрута и пути, которые ассоциируются с последовательным перемещением от вершины к вершине по соединяющим их ребрам или дугам. Для неориентированного графа маршрут определяется как конечная или бесконечная упорядоченная последовательность ребер S=<, esl, es2, ..., esk>>, таких, что каждые два соседних ребра имеют общую вершину. Нас будут интересовать только конечные маршруты S=, т. е. такие маршруты, которые состоят из конечного числа ребер. При этом ребро esl принято считать началом маршрута S, а ребро esk – концом маршрута S. Для ориентированного графа соответствующая последовательность дуг S= называется ориентированным маршрутом, если две соседние дуги имеют общую вершину, которая является концом предыдущей и началом последующей дуги.

Примерами маршрутов для неориентированного графа (рис. 2.4, а) являются последовательности ребер: S1=, S2=, S3=. Если в маршруте не повторяются ни ребра, ни вершины, как в случае S1 и S3, то такой неориентированный маршрут называется простой цепью.

Примерами ориентированных маршрутов для графа (рис. 2.4, б) являются такие последовательности дуг: S1=, S2=, S3=. Если в ориентированном маршруте не повторяются ни ребра, ни вершины, как в случае S1 и S2, то такой ориентированный маршрут называется путем. Последнее понятие также иногда применяется для обозначения простой цепи в неориентированных графах и для определения специального класса графов, так называемых деревьев. В общем случае деревья служат для графического представления иерархических структур или иерархий, занимающих важное место в ООАП.

Деревом в теории графов называется такой граф D=, между любыми двумя вершинами которого существует единственная простая цепь, т. е. неориентированный маршрут, у которого вершины и ребра не повторяются. Применительно к ориентированным графам соответствующее определение является более сложным, поскольку основывается на выделении некоторой специальной вершины v0, которая получила специальное название корневой вершины или просто – корня. В этом случае ориентированный граф D= называется ориентированным деревом или сокращенно – деревом, если между корнем дерева v0 и любой другой вершиной существует единственный путь, берущий начало в v0. Ниже представлены два примера деревьев: неориентированного дерева (рис. 2.5, а) и ориентированного дерева (рис. 2.5, б).