Графы (продолжение)

Лекция 15. Графы (продолжение) Связность неорграфа Граф G = (V, U) называется связным, если для всех vi и vj  V (vi  vj) всегда существует цепь из vi в vj, т.е. если каждая пара различных вершин может быть соединена по крайней мере одной цепью. Если это условие не выполняется, то граф называется несвязным. Рис 12.1 Например, граф на рис. 12.1 – несвязный. Рассмотрим отношение vi → vj существования пути из vi в vj. Оно 1) симметрично, так как (vi → vj)  (vj → vi), 2) транзитивно, так как (vi → vj) & (vj → vk)  (vi → vk), 3) рефлексивно, так как i (vi → vi). Т.о. это отношение является отношением эквивалентности и разбивает множество вершин на конечное число классов эквивалентности V = V1  V2  … Vn, Vi  Vj = , i  j. При этом граф G разбивается на связные подграфы, которые называются компонентами связности. Например, для графа на рис. 12.1 компонентами связности являются V1 = {v1, v2, v3, v4}, U1 = {u1, u2, u3, u4} и V2 = {v5, v6, v7}, U2 = {u5, u6}. Деревья и леса в неориентированном графе Дерево – связный граф без циклов. Рис. 12.2 Например, граф, изображенный на рис. 12.2, – дерево. Подграф G1 = (V1, E1) графа G = (V, E) называется остовным деревом в графе G, если G1 – дерево и V1 = V. Любой связный граф содержит по крайней мере одно остовное дерево. При добавлении к связному графу нового ребра на тех же вершинах получается цикл. Поэтому при добавлении к дереву нового ребра получается цикл. Пусть в графе G = (V, E) p вершин и q рёбер. Тогда в G не менее p – q связных компонент. Если при этом в G нет циклов, то G состоит ровно из p – q связных компонент. Поэтому дерево – связный граф и q = p – 1 (количество ребер на единицу меньше количества вершин). Дерево, в котором выделена одна вершина, называемая корнем, называется корневым деревом. Лесом из K деревьев называется граф без циклов, состоящий из K компонент. Например, лесом, полученным из графа, изображенного на рис. 12.1 является граф, из которого удалены ребра, замыкающие циклы (рис. 12.3) Рис. 12.3. Пример графа в виде леса из двух деревьев Специальные классы неориентированных графов Обыкновенным называется граф без петель и параллельных ребер. Полным называется обыкновенный граф, в котором любые две вершины являются смежными. Рис. 12.4. Пример обыкновенного полного графа Например, граф, изображенный на рис. 12.4 является обыкновенным полным Граф называется k-связанным, если любая пара различных вершин v и w соединена по крайней мере k различными цепями. Например, граф, изображенный на рис. 12.4 является 4-связным. Двудольным называется граф, в котором вершины могут быть разбиты на 2 непересекающихся подмножества так, что каждое ребро имеет одну инцидентную вершину в одном множестве; другую – в другом. Рис. 12.5. Пример двудольного графа Например, граф, представленный на рис. 12.5 – двудольный. Способы задания орграфов Орграф G = (V, U) с n вершинами и m дугами. V – множество вершин; U  VV – множество дуг. Матрица инцидентности A(n, m) – матрица инцидентности. aij = 1, если vi – начало дуги uj, и uj не петля. aij = -1, если vi – конец дуги uj, и uj не петля. aij = 0 во всех остальных случаях. Рис. 12.6. Пример ориентированного графа Например, для графа, изображенного на рис 12.6 матрица инцидентности выглядит следующим образом u1 u2 u3 u4 u5 u6 v1 1 v2 -1 1 1 -1 v3 -1 1 1 v4 -1 -1 0 или 2 Матрица смежности A(n, n). aij равна числу дуг от вершины vi к vj. Рис. 12.7. Пример орграфа Матрица смежности имеет вид v1 v2 v3 v4 v1 1 1 v2 1 2 v3 1 1 v4 1 Другие способы задания орграфа Списком дуг и вершин. Для рис. 12.7: V = {v1, v2, v3, v4}; U = {(v1, v2), (v2, v1), (v2, v3), (v2, v3), (v3, v3), (v3, v4), (v4, v1), (v1, v3)} Некоторые специальные классы орграфов Симметрическим называется граф G = (U, V), в котором (vi  V, vj  V) (vi, vj)  U => (vj, vi)  U. Например, граф на рис. 12.8. Рис. 12.8. Пример симметрического графа Антисимметрическим называется граф G = (U, V), в котором (vi  V, vj  V) (vi, vj)  U => (vj, vi)  U. Пример антисимметрического графа представлен на рис. 12.9. Рис. 12.9. Пример антисимметрического графа, полного графа Полный граф – граф G = (U, V), в котором (vi  V, vj  V) (vj, vi)  U => (vi, vj)  U. Рис. 12.9 Рефлексивным будем называть граф с петлей в каждой вершине.