Разделение графа на составляющие

Рассмотрим понятия, используемые для выделения важнейших частей графа, на примере графа G=(V, ), приведенного выше на рис. 1.2,а.

Суграфом графа G называется граф G' = (V, '), где '  , т.е. суграф получается из исходного графа удалением некоторого числа ребер (дуг). Например, на рис. 2.1,а показан суграф графа (рис. 1.2,а) без кратных ребер и петель.

Подграфом графа G называется граф G' = (V', '), где V'  V, ' =  (V'  V' ) , т.е. подграф получается из исходного графа удалением некоторого числа вершин вместе со всеми ребрами (дугами), инцидентными удаленной вершине. Например, на рис. 2.1,б показан подграф графа (рис. 1.2,а) после удаления вершины v₃ и инцидентных ей ребер ₄ , ₆.

а) v₁ v₂ б) v₁ v₂ в) v₁ v₂

v₄ v₃ v₄ v₄

Рис. 2.1. Разделение графа на составляющие :

а) суграф; б) подграф; в) частичный граф

- 5 -

Частью графа (частичным графом) называется граф G' = (V' , ' ), где V'  V, '  , т.е. часть графа получается из исходного графа применением обеих описанных операций. Например, на рис. 2.1,в показана часть графа (рис. 1.2,а) без кратных ребер и вершины v₃, c инцидентными ей ребрами.

Динамические свойства неориентированного графа

Граф обладает динамическими свойствами, которые позволяют перемещаться по смежным ребрам от одной вершины к другой. Рассмотрим соответствующие этим свойствам понятия.

Маршрутом называется конечная последовательность n ребер графа ( ₁, ₂, ..., _n ) не обязательно различных, но таких, что _i = [v_i-1 , v_i ] для i=1,2,...,n. Длиной маршрута (n) называется число ребер, которые он содержит. Маршрут можно задавать и последовательностью вершин, через которые он проходит.

Говорят, что маршрут замкнутый, если v₀ = v_n , и незамкнутый, если v₀v_n. Например, для графа на рис. 1.2,а последовательность ребер ( ₁, ₂, ₃) образует незамкнутый маршрут длины 3 с последовательностью вершин (v₁,v₂,v₁,v₄), а маршрут ( ₁, ₂, ₃, ₃) через вершины (v₁,v₂,v₁,v₄,v₁) является замкнутым.

Цепью называется незамкнутый маршрут, если все его ребра различны, например, это цепь ( ₁, ₂, ₃ ) через вершины (v₁,v₂,v₁,v₄) на рис. 1.2,а.

Простой цепью называется цепь, в которой все n+1 вершин (v₀,v₁,...,v_n) различны, например, простая цепь ( ₃, ₂, ₄ ) через вершины (v₄,v₁,v₂,v₃) на рис. 1.2,а.

Циклом называется цепь, которая начинается и кончается в одной и той же вершине (v₀=v_n), при этом возможно повторение других вершин.

Простым циклом называется цикл, если v₀=v_n , но все остальные вершины различны, например, простой цикл образуют ребра ( ₁, ₅, ₃ ) с последовательностью вершин (v₁,v₂,v₄,v₁) на рис. 1.2,а.

Связность графа

Граф G=(V, ) называется связным, если для всех вершин v_i , v_j V (v_iv_j) всегда существует цепь из v_i в v_j , т.е., если каждая пара различных вершин может быть соединена, по крайней мере, одной цепью, в противном случае граф называется несвязным. Например, граф на рис. 1.2,а является связным.

Деревом называется связный граф без циклов. Граф является деревом тогда и только тогда, когда каждая пара различных вершин соединяется одной и только одной цепью. Связность дерева означает существование, по крайней мере, одной такой цепи, а из отсутствия циклов следует существование единственной такой цепи. Из любого связного графа, который не является деревом можно удалить некоторые ребра, не нарушая связности (например, любое ребро, входящее в цикл). Удаление любого ребра из дерева делает его несвязным, так как удаляемое ребро составляет единственную цепь, соединяющую его гра-

- 6 -

ничные точки. Следовательно, дерево можно также определить как минимальный связный граф, где минимальность понимается в том смысле, что он не содержит подграфа, который состоит из всех его вершин и является связным.

v ₁ v₂ v₁ v₂ v₁ v₂

v₄ v₃ v₄ v₃ v₄ v₃

Рис. 2.2. Деревья графа

Пример.

Из графа на рис. 1.2,а путем удаления ребер, замыкающих циклы, можно получить различные варианты деревьев, например, такие, как на рис. 2.2.

Задание № 3. ОБРАБОТКА ОРИЕНТИРОВАННОГО ГРАФА

Цель работы: а) освоение понятий специфичных для орграфов; б) овладение методами и приемами выделения частей орграфа с заданными свойствами.

Содержание работы: для исходного орграфа из задания №1 выделить его составные части в соответствии с индивидуальным заданием и представить в отчете по работе.

Методические указания к выполнению задания

Во многих случаях при описании графа линиям, соединяющим вершины графа, необходимо задать ориентацию (направление) и тогда линии называются дугами (стрелками), а граф – ориентированным (орграфом).

Формальные описания орграфа G=(V, U), где V={v₁,...,v_n} – множество вершин, U={u₁,...,u_m} – множество дуг графа, во многом опираются на структурные термины, введенные для неориентированного графа, однако есть специфика, связанная с ориентацией дуг (рис. 3.1).

Дуга и ее граничные вершины инцидентны друг другу. Дуга u₁=(v₁,v₂) cчитается положительно инцидентной ее конечной вершине v₂, говорят, что дуга заходит в вершину v₂. Дуга считается отрицательно инцидентной ее начальной вершине v₁, говорят, что дуга исходит из этой вершины.