Элементы теории графов, связность и сильная связность графов, дифференцирование графов, сети;

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

Графом будем называть совокупность двух множеств V(точек) и E(линий), между элементами которых определено отношение инцидентности.

Неориентированный (ориентированный) граф G – это пара множеств G=<V,E>, где V – конечное множество, элементы которого называют вершинами или узлами. E – множество неупорядоченных (упорядоченных) пар на V, т.е. подмножество множества двухэлементных подмножеств V (V´V), элементы которого называют ребрами (дугами). Лемма о рукопожатиях. Сумма степеней всех вершин графа равна удвоенному числу ребер.

Основные понятия теории графов:

• Две вершины графа смежны, если они соединены ребром.;
• Два ребра смежны, если они имеют общую вершину.;
• Вершина V и ребро L называются инцидентными, если V является одним из концов ребра L.;
• Если множество V - конечно, то граф называется конечным.
• Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми ребрами (дугами), соединяющими вершины из этого множества. Если из графа удалить часть ребер (дуг), то получим частичный граф.
• Путем называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги. Простой путь – путь, в котором ни одна дуга не встречается дважды. Элементарный путь – путь, в котором ни одна вершина не встречается дважды. Контур – путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).
• Цепью называется множество ребер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого. Другое определение: цепь – последовательность смежных вершин. Замкнутая цепь называется циклом. По аналогии с простым и элементарным путем, можно определить соответственно простые и элементарные цепь и цикл. Любой элементарный цикл является простым, обратное утверждение в общем случае неверно.

Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами. Связностью графа называется минимальное число ребер, после удаления которых граф становится несвязным. Для ориентированных графов, если любые две вершины графа можно соединить путем, то граф называется сильно связным. Известно, что: связность графа не может быть больше, чем [ 2m / n ], где [ x ] – целая часть числа x; существуют графы с n вершинами и m ребрами, имеющие связность [ 2m / n ]; в сильно связном графе через любые две вершины проходит контур.

Граф (неориентированный и ориентированный) может быть представлен в виде следующей матрицы, называемой матрицей инциденции размера n´m, где n – число вершин, а m – число ребер (или дуг): a_ij={^{1, если j-ое ребро инцидентно i-й вершине,}_{0, иначе.} (неориентированный граф); a_ij={^{1, если j-я дуга выходит из I-й вершины,}_{-1, если j-я дуга заходит в i-ю вершину,}^{0, иначе} (ориентированный граф). Матрица смежности вершин – это квадратная матрица B n-го порядка, элементы которой определяются для неориентированного графа следующим образом: b_ij={^{1, если i-я и j-я вершины соединены ребром,}_{0, иначе}. Для орграфа – аналогично. Для неорграфа матрица смежности вершин симметрична.

Замкнутая цепь называется циклом.

Дифференцирование графов

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

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

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