Дискретная математика: Учебное пособие. Часть 3 - Основы теории графов, страница 2

Последовательность смежных вершин, соединяющего вершины x_i и x_j , называют переходом и обозначают n_ij=(x_i,..x_j). Например, для неориентированного графа, приведенного на рис. 10, между вершинами x₀ и x₅ существует шесть переходов, т.е. n₀₅={(x₀, x₄, x₅); (x₀, x₁, x₄, x₅); (x₀, x₁, x₅); (x₀, x₄, x₁, x₅); (x₀, x₄, x₁, x₃, x₅);

(x₀, x₁, x₃, x₅)}.

Маршрут неориентированного графа, связывающий вершины x_i и x_j различными ребрами, называют цепью, а ориентированного - путём.

Маршрут называют простым, если при его обходе каждая промежуточная вершина встречается не более одного раза.

Маршрут называют открытым, если его концевые вершины различны, и замкнутым, если его концевые вершины совпадают. Замкнутый маршрут, который содержит только одно ребро или дугу, называют петлёй. На рис. 10 петля указана для вершины x₄. Замкнутый маршрут называют циклом, замкнутый простой маршрут простым циклом.

Маршрут называют эйлеровым, если он замкнут и проходит через каждое ребро графа только по одному разу. Таким является маршрут m₀₀=(r₀₄, r₄₁, r₁₅, r₅₃, r₃₁, r₁₀)}, показанный на рис. 11. 

Маршрут называют гамильтоновым, если он замкнут и проходит через каждую вершину графа только по одному разу. Таким является маршрут m₀₀=(r₀₄, r₄₅, r₅₃, r₃₁, r₁₀)}, показанный на рис.11.

Длина маршрута равна числу смежных рёбер, соединяющих вершины x_i и x_j , т.е. l_i;j=Sr_k,l, где k¹l и i£k,l£j.

Длину минимального маршрута, соединяющего вершины x_i и x_j называют расстоянием. Например, расстояние между вершинами x₀ и x₅ графа, приведённого на рис. 10б), равно 2.

Если ребро или дуга обладают дополнительной характеристикой – протяжённостью - l_k,l, то длина маршрута равна сумме длин рёбер или дуг, его составляющих, т.е. l_i;j=S_k,l, где k¹l и i£k,l£j.

Если ребро или дуга обладают дополнительной характеристикой - пропускной способностью - с_k,l, то пропускная способность маршрута равна минимальной пропускной способности рёбер или дуг, его составляющих.

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

Граф называют полным, если любые две его вершины смежны между собой  (см. рис. 12а) и пустым, если любые две его вершины не смежны (см. рис.12б).

Граф называют дополнительным для графа G=<X; r>, если он опирается на множество вершин X и дополнения отношения r, т. е. ùG=<X;`r>.

Для формирования дополнительного графа G¢=ùG=<X; `r > необходимо найти дополнение отношения r по матрице смежности графа G:

                                        1, если r_i,j=0;

                          r _i,j =                                                                                                                                         0, если r_i,j=1.

          Граф называют деревом, если он связный, но без циклов, петель и кратных рёбер или дуг. Ориентированные деревья интенсивно используют для представления в компьютере данных и организации доступа к ним по ключу, для рганизации структуры программы и структуры операторов управления, каталогов и файлов в операционных системах. В графе типа дерево (см. рис. 14а) всегда выделяют корневую вершину, узлы и крону. Число рёбер или дуг графа равно (n-1), где n - число вершин графа.

Если множество вершин графа G=<X; r> разбить на два подмножества X’ и X\X’ при условии, что X’È(X\X’)=X и X’Ç(X\X’)=Æ, то множество рёбер или дуг, одни из концевых вершин которых принадлежат множеству X’, а другие - множеству (X\X’), называют разрезом. Поиск разрезов сводится к определению отношения принадлежности x_iÎX’ и x_jÎ(X\X’) с последующим выделению множества рёбер, соединяющих эти подмножества.

На рис. 14б) дан разрез {r₀₄, r₁₄, r₁₅, r₃₅}, cоединяющий два подмножества X’={x₀, x₁, x₃} и (X\X’)={x₄, x₅}.

Удаление множества рёбер или дуг разреза преобразует связный граф в несвязный.