Элементы графов

План

Общее понятие.

Способы задания.

Элементы графов.

Операции с частями графов.(Самостоятельное изучение).

Общее понятие и определение

Граф G как математический объект-это совокупность двух множеств: непустого множества вершин V и множества ребер E, элементы которого представляют собой неупорядоченные (для ориентированного графа - упорядоченные) пары элементов из множества V.

G(V, E) = á V; Eñ, n(V)> 0, E Ì V х V,

где для неориентированного графа E = E^-1 (бинарное отношение E симметрично).

Минимальный граф состоит из одной вершины.

Каждому неориентированному графу можно поставить в соответствие ориентированный граф, в котором каждое ребро заменено двумя противоположными ориентированными ребрами, инцидентными тем же вершинам.

Пусть v₁ и v₂ – вершины, e₁ = (v₁, v₂) – соединяющее их ребро.

Тогда вершина v₁ и ребро e₁ инциденты, вершина v₂ и ребро e₁ также инциденты. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

Обычно граф изображают на плоскости в виде диаграммы: вершины – точками, ребра – линиями, соединяющими инцидентные вершины.

Способы задания графов

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

1 Отношение инцидентности задано матрицей смежности:

- столбцы и строки матрицы – вершины графа;

- для смежных вершин элемент матрицы равен 1, для остальных – 0:

- для неориентированного графа эта матрица всегда симметрична;

- число рёбер равно числу единиц выше или ниже главной диагонали матрицы (включая элементы диагонали).

2 Отношение инцидентности задано матрицей инцидентности:

- столбцы матрицы соответствуют вершинам графа, а строки – рёбрам;

- если ребро е_i инцидентно вершине V_i, то Элемент матрицы e_ij =1, в противном случае - e_ij =0.

Таким образом, в каждой строке одна или две единицы, остальные нули

(для петли две единицы).

Для ориентированного графа при заполнении матрицы:

e_ij = -1, если V_j – начало ребра;

e_ij =1, если V_j – конец ребра;

e_ij= a (где a - любое число, кроме -1, 1, 0), если ребро – петля в вершине V_j;

в остальных случаях e_ij=0.

3 Граф задан списком ребер.

Примечание. Здесь е_i – ребро, V_i, V_j – пара вершин, соединяемых этим ребром.

Элементы графов

Граф без кратных ребер называют полным, если каждая пара вершин соединена ребром.

Граф H называют частью графа G, если множество вершин графа H принадлежит множеству вершин графа G и множество рёбер графа H принадлежит множеству рёбер графа G, т.е.:

V(H) Ì V(G); E(H) Ì E(G).

Часть графа H называется суграфом, если она содержит все вершины графа G.

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

Подграф G(U) графа G на множестве вершин U (U Ì V) – это часть графа, которой принадлежат все ребра с обоими концами из U.

Звёздный граф для вершины v (v Î G) состоит из всех ребер с началом и концов в вершине v. Множество вершин звёздного графа состоит из вершины v и других смежных с ней вершин.