2015-05-30
1710
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ТЕОРИИ ГРАФОВ
2.1. Понятие о графе. Способы задания графа [4,5].
Задание графа множествами вершин и линий
Граф геометрически представляет собой множество точек, соединенных линиями. Для более полного математического определения графа введем ряд обозначений. Множество точек или вершин х1,х2,…хn графа G обозначим через Х, а множество линий d1,d2,…dm, соединяющих между собой эти вершины – символом А. Тогда граф G можно полностью задать парой (Х,А).
Если соединяющиеся линии из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами и граф с такими линиями называется ориентированным графом. Если соединяющие линии не ориентированы, то они называются ребрами, а граф называется неориентированным. В смешанном графе могут быть дуги (ориентированные линии) и ребра (неориентированные линии). На рис. 2.1 изображен ориентированный граф.
Дуга такого графа задается упорядоченной парой, состоящей из начальной и конечной вершин, ее направление предполагается заданным от первой вершины ко второй. Для подчеркивания ориентации ребра упорядоченная пара обозначается сверху Рис. 2.1 символом вектора, например знаком ®.
|
|
|
Граф на рис. 2.1. можно представить в виде
G1={ x1, x2, x3; (x1,x2), (x2,x3), (x3,x1)}
На рис. 2.2 изображен смешанный граф, и его представление имеет вид
G2={ x1, x2, x3; 2(x1,x2), (x2,x3), (x3,x1)},
где цифра 2 означает две дуги из вершины х1 в вершину х2.
Рис. 2.2
