2015-01-07
3053
ГрафG - это математический объект, состоящий из множества вершинX = { x 1, x 2,..., xn } и множества реберA = { a 1, a 2,..., an }. Таким образом, граф полностью определяется совокупностью множеств X, A: G = (X, A).
Для многих задач несущественно, являются ли ребра отрезками прямых или криволинейными дугами; важно лишь то, какие вершины соединяет каждое ребро.
Если ребрам графа приданы направления от одной вершины к другой, то такой граф называется ориентированным. Ребра ориентированного графа называются дугами. Соответствующие вершины ориентированного графа называют началом и концом. Если направления ребер не указываются, то граф называется неориентированным (или просто графом).
Пример 3.1.
На рис. 3.1 изображен неориентированный граф G = (X, A).
X = { x 1, x 2, x 3, x 4},
A = { a 1 = (x 1, x 2), a 2 = (x 2, x 3), a 3 = (x 1, x 3), a 4 = (x 3, x 4)}.
Рис. 3.1.
Пример 3.2.
На рис. 3.2. изображен ориентированный граф G = (X, A).
X = { x 1, x 2, x 3, x 4},
A = { a 1= (x 1, x 2), a 2= (x 1, x 3), a 3= (x 3, x 4), a 4= (x 3, x 2)}.
Рис. 3.2.
Граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным.
|
|
|
Различные ребра могут соединять одну и ту же пару вершин. Такие ребра называют кратными. Граф, содержащий кратные ребра, называется мультиграфом.
Неориентированное ребро графа эквивалентно двум противоположно направленным дугам, соединяющим те же самые вершины.
Ребро может соединять вершину саму с собой. Такое ребро называется петлей. Граф с кратными ребрами и петлями называется псевдографом.
Множество ребер графа может быть пустым. Множество вершин графа не может быть пустым.
Пример 3.3.
На рис. 3.3. изображен ориентированный граф G = (X, A).
X = { x 1, x 2, x 3, x 4},
A = 
.
Ри c. 3.3.
Как в случае ориентированного, так и в случае неориентированного ребра говорят, что вершины x и yинцидентны ребру a, если эти вершины соединены a.
Две вершины называются смежными, если они инцидентны одному и тому же ребру. Два ребра называются смежными, если они имеют общую вершину.
Степенью вершины графа называется число ребер, инцидентных этой вершине. Вершина, имеющая степень 0, называется изолированной, а степень 1 – висячей.
Для ориентированного графа множество вершин, в которые ведут дуги, исходящие из вершины х, обозначают G (х), то есть G (х) = { y: (x y) 
G }. Множество G (x) называют образом вершины x. Соответственно G- 1(у)– множество вершин, из которых исходят дуги, ведущие в вершину у, G- 1(y)= { x: (x, y) G }. Множество G- 1(у)называют прообразом вершины y.
Пример 3.4.
В графе, изображенном на рис. 3.1, концами ребра a 1являются вершины x 1, x 2; вершина x 2инцидентна ребрам a 1, a 2; степень вершины x 3равна3; вершины x 1и x 3смежные; ребра a 1и a 2смежные; вершина x 4висячая. В ориентированном графе, изображенном на рис. 3.2, началом дуги a 1является вершина x 1, а ее концом - вершина x 2; вершина x 1инцидентна дугам a 1и a 2; G (x 1) = { x 2, x 3}, G (x 2) = Æ, G- 1(x 3) = { x 1}, G- 1(x 1) = Æ.
|
|
|
Подграфом неориентированного графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Аналогично определяется подграф ориентированного графа. Подграф называется собственным, если он отличен от самого графа,
Граф G = (X, A)- полный, если для любой пары вершин xi и xj существует ребро (xi, xj).
Граф G = (X, A)- симметрический, если для любой дуги (xi, xj) существует противоположно ориентированная дуга(xj, xi).
Граф G = (X, A) - планарный, если он может быть изображен на плоскости так, что не будет пересекающихся дуг.
Неориентированный граф G = (X, A)– двудольный, если множество его вершин X можно разбить на два такие подмножества X 1и X 2, что каждое ребро имеет один конец в X 1, а другой в X 2.
