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

Части графа

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

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

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

Если в рассмотренном прграфе на рис.3.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).

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

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

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

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

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