Неориентированные графы

Частичный граф

Для графа G =< A,U > граф H =< A, U ’ > называется частичным графом графа G, если в нем U ’ Í U. Отметим, что частичный граф задан на всех вершинах исходного графа.

Граф P =< A ’, U ’’ > называют подграфом графа G, если A ’ Í A и
U ’’ – подмножество всех дуг из U, заданных на вершинах из А ’.

Граф Q =< A ’, U ^* >, где U ^* Í U ’’, называют частичным подграфом графа G.

Если в графе на рис.2.1 из множества его дуг убрать, например, дуги (3,5) и (2,1), то получим частичный граф исходного графа. Если убрать, например, вершину 5 и все связанные с ней дуги (дуги (5,2), (5,4) и (3,5)), то получим подграф исходного графа. И, наконец, если из полученного подграфа убрать, например, дуги (3,2) и (2,1), получим пример частичного подграфа.

Граф называют неориентированным или неорграфом, если в нем элементы множества U рассматривают как неупорядоченные, т.е. в нем пара (a_i,a_j) неотличима от пары ( a_j,a_i). В этом случае элементы множества U называются ребрами и на рисунке они изображаются в виде отрезков кривых без стрелок.

Аналогом пути в неорграфе является понятие цепь. Цепь может быть простой или составной, элементарной или нет. Замкнутая цепь называется циклом и вводится аналогично понятию контур.

Каждому орграфу однозначно сопоставляется неорграф, если заменить все дуги ребрами, т.е. убрать ориентацию. Если в орграфе есть пары дуг, соединяющие одни и те же вершины в противоположном направлении, то они заменяются одним ребром. Так, неорграф, сопоставленный приведенному в примере графу, будет иметь число ребер на одно меньше числа дуг, потому что паре дуг (1,2) и (2,1) будет сопоставлено одно ребро.

Термин цепь можно ввести и для ориентированного графа, понимая под ней последовательность дуг без учета ориентации. Так, в нашем примере можно говорить о цепи (1,2,5,4).

Граф называется связным, если в нем любая пара вершин связана цепью.

Компонентой связности графа называется такой его связный подграф, для которого не существует другого связного подграфа, включающего данный в качестве своего подграфа.

Таким образом, компонента связности есть максимальный связный подграф в графе. На рис.2.2 приведен граф, в котором три компоненты связности: подграфы на вершинах {1, 2, 3}, {4,5}, {6,7,8}.

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

Ребро графа, удаление которого увеличивает число компонент связности, называется мостом или перешейком. В нашем примере одним из мостов будет ребро (6,7).

Дата добавления: 2014-01-07