Основы теории графов

Размещено на http://www.allbest.ru/

Основы теории графов

Определение. Ориентированным графом называется структура G = (V, E), где V - конечное множество вершин, E - множество ребер, которое задается как бинарное отношение на V: E Н--V ґ--V.

Ориентированный граф называется орграфом. Граф может содержать ребра - циклы, которые соединяют вершину саму с собой. Про ребро (u, v) говорят, что оно выходит из вершины u и входит в вершину v.

Ориентированный граф

V = {1, 2, 3, 4, 5, 6}, E = {{1, 3}, {3, 2}, {2, 2}, {2, 4}, {5, 6}}

В неориентированном графе множество ребер E состоит из неупорядоченных пар вершин. Про ребро (u, v) неориентированного графа говорят, что оно инцидентно вершинам u и v. Если в графе G есть ребро (u, v), то говорят, что вершина u смежная с вершиной v. Для неориентированного графа отношение смежности является симметричным.

Определение. Степенью вершины в неориентированном графе называется количество инцидентных ей ребер. Для ориентированных графов различают входную и выходную вершины; сумма входных и выходных степеней называется степенью вершины.

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

Определение. Матрицей смежности графа G (V, E), |V| = n, называется такая булева матрица А размера n ґ--n, что A [i, j] = 1 тогда и только тогда, когда между вершинами i и j существует ребро. В случае взвешенного графа матрица смежности представляется двумерной числовой матрицей, в которой A [i, j] равно весу ребра, если между вершинами i и j оно существует, и A [i, j] = 0 иначе.

Матрица смежности для графа, изображенного выше, имеет вид:

Проверка присутствия ребра (v_i, v_j) при помощи матрицы смежности занимает время O(1). Нахождение всех вершин, смежных с v_i, требует O(n) времени (для этого достаточно просмотреть i - ую строку матрицы смежности).

Утверждение. Матрица смежности неориентированного графа симметрична.

Неориентированный граф и его матрица смежности

Определение. Неориентированный граф называется простым, если он не имеет петель и произвольная пара вершин соединена не более чем одним ребром.

Определение. Простой граф называется полным, если каждая пара вершин соединена ребром. Такой граф содержит ребер.

Определение. Путь длины k из вершины u в вершину v определяется как последовательность вершин (v₀, v₁, …, v_k), в которой v₀ = u, v_k = v и (v_i-1, v_i) О--E для всех i = 1, …, k. Путь длины k состоит из k ребер. Вершину v₀ называют началом пути, а v_k - его концом.

Если для заданных вершин u и v существует путь из u в v, то говорят, что вершина v достижима из вершины u.

Определение. Путь называется простым, если все вершины в нем разные.

Определение. Циклом в ориентированном графе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро. Ребро - цикл (петля) называется циклом длины 1. Цикл называется простим, если в нем отсутствуют одинаковые вершины (кроме первой и последней), то есть все вершины v₀, v₁, …, v_k разные.

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

Определение. В неориентированном графе путь (v₀, v₁, …, v_k) называется (простым) циклом, если k і--3, v₀ = v_k, и все вершины v₀, v₁, …, v_k разные.

Определение. Граф, в котором отсутствуют циклы, называется ацикличным.

Определение. Неориентированный граф называется связным, если для произвольной пары вершин существует путь из одной вершины в другую. Для неориентированного графа отношение «быть достижимым из» является отношением эквивалентности на множестве вершин. Классы эквивалентности называются связными компонентами графа.

граф неориентированный матрица смежность

Размещено на Allbest.ru