Теория графов

Теория графов

Теория графов

Основные понятия и определения

·   Граф - пара множеств V и X - G = (V, X). V - множество вершин, X - множество ребер.

·   Петля - ребро вида (v, v).

·   Кратные рёбра - одинаковые пары в X.

·   Ориентированный граф (орграф D) - граф, для которого пары в Х упорядочены. Ребра в орграфе называются дугами и обозначаются <u, v>.

·   Степенью вершины V графа G называется число d(v) рёбер графа, инцидентных вершине v. Если d(v) = 1, тогда v - висячая вершина, если d(v) = 0, тогда v - изолированная вершина.

·   Полустепенью исхода (захода) вершины v орграфа D называется d⁺(v) - число дуг, исходящих из v (δ ^- (v) - число дуг, заходящих в v).

·   Маршрутом для графа G (путём для орграфа D) называется последовательность v₁x₁v₂x₂v₃…x_kv_k+1.

·   Цепь - незамкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.

·   Простая цепь - цепь, в которой все вершины попарно различны.

·   Цикл (контур) - замкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.

·   Простой цикл (контур) - цикл (контур), в котором все вершины попарно различны.

·   Длина пути - число рёбер (дуг) в маршруте (пути).

·   Путь в графе называется минимальным, если он состоит из минимального количества рёбер.

Орграф D называется нагруженным, если на множестве дуг Х определена весовая функция  - длина дуги хÎХ.

·   Путь называется минимальным в нагруженном графе или орграфе, если он имеет минимальную длину пути.

·   Матрица смежности (графа, орграфа): А = [a_ij], V = {v₁…, v_n},

·   X = {x₁…, x_m}

·

·    Матрица инцидентности: B = [b_ij]

·   (орграфа D)

·    

·   (графа G)

·        

·   Матрица достижимости T = [t_ij]

·  

·   Матрица связности S = [s_ij]

(орграфа D)

(графа G)

·   Дерево - связный граф без циклов

·   Остовное дерево графа (ОД) - любой связный подграф связного графа, содержащий все вершины и являющийся деревом.

Минимальное остовное дерево (МОД) - остовное дерево нагруженного графа с минимальной суммой длин дуг, содержащихся в нём.

Цикломатическое число связного графа G (число циклов в базисе циклов графа) , где n - количество вершин, m - количество ребер в графе.

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

Назовем ребра графа:

1.       Характеристика графа

Ориентированный псевдограф D=(V, X).

V={V0, V1, V2, V3, V4, V5}; X={X0, X1, X2, X3, X4, X5, X6, X7}

X0=<V2, V1>, X1=<V0, V3>, X2=<V0, V3>, X3=<V0, V1>, X4=<V0, V2>, X5=<V4, V0>, X6=<V3, V4>, X7=<V4, V4>

.        Специальные вершины и ребра

X7 - петля, X1, X2 - кратные ребра, V5 - висячая вершина

.        Полустепени вершин

d⁺(V) - число дуг, заходящих в V

δ ^- (V) - число дуг, исходящих из V

δ⁺ (V0)=1    δ⁺ (V1)=2  δ⁺ (V2)=1  δ⁺ (V3)=2  δ⁺ (V4)=2  δ⁺ (V5)=0

δ¯(V0)=4    δ¯(V1)=0    δ¯(V2)=1  δ¯(V3)=1  δ¯(V4)=2  δ¯(V5)=0

.        Матрицы смежности, инцидентности, достижимости, связности