Граф со взвешенными дугами

Граф G = (N, A) называется взвешенным, если на множестве дуг A определена некоторая функция l: A → R, которую называют весовой функцией.

Тем самым в взвешенном графе G каждой дуги x A поставлено в соответствие некоторое действительное число l(x). Значение l(x) называются длиной дуги x.

Для любого пути P_i взвешенного графа G обозначающим через l(P_i) сумму длин входящих в P_i дуг, при этом каждая дуга учитывается столько раз, сколько она входит в путь. Величину l(P_i) называют длиной пути P_i в взвешенном графе G.

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

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

Определение. Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G.

Дуги 8,9 - называются параллельными (кратными). Дуги 5,6 - называются противоположными. Вершина k - называется изолированной.

Определение. Полным графом называется граф с n вершинами без петель, кратных и противоположных дуг (ориентация безразлична), у которого любые две вершины соединены дугой.

Определение. Полным двудольным графом называется граф с n+m вершинами без петель, кратных и противоположных дуг (ориентация безразлична), у которого множество вершин разбито на два непересекающихся подмножества с n и m вершинами так, что любые две вершины различных подмножеств соединены дугой и никакие две вершины одного подмножества не соединены дугой.

3.

Матрица смежности: строки и столбцы соответствуют варшинам. Элемент матрицы

Пример. Составить матрицу смежности для графа G:

Заполняем строчку s: если есть дуга из s в другую вершину графа G, то ставим 1, если нет - 0. Из s есть дуги в x:(sx) и в y:(sy). По аналогии заполняем другие строки.

Матрица инцедентности: строки соответствуют вершинам, а столбцы дугам, при этом в столбце, соответствующем дуге (x,y) 1 ставится в строке x, -1 в строке y, остальные элементы равны 0.

Рисунок 3.1.13.

4.

Определение. Цепью длины n на графе (N,A) называется последовательность дуг такая, что у любой дуги одна вершина общая с дугой f(i-1), а другая - общая с дугой f(i+1).

Вершина дуги f(1), не являющаяся общей с дугой f(2), называется началом цепи, вершина дуги f(n), не являющаяся общей с дугой f(n-1), называется концом цепи.

Если начало цепи совпадает с ее концом, то цепь называется циклом.

Определение. Путем длины n на графе (N,A) называется последовательность дуг такая, что у любой дуги f:(i)(i=1..n) начала дуги совпадает с концом дуги f(i-1), а конец дуги совпадает с началом дуги f(i+1).

Начало дуги f(1) называется началом пути, конец дуги f(n) называется концом пути.

Если начало пути совпадает с концом пути, то путь называют контуром.

Из 2 в 7 путь длины 6:(2,1),(1,3),(3,4),(4,5),(5,6),(6,7).(Двигается по направлению стрелок). Контур длины 3:(2,1),(1,3),(3,2).

Из 2 в 8 цепь длины 4:(2,3),(3,4),(4,5),(5,8). Цикл длины 4:(2,1),(1,4),(4,3),(3,2).

Определение. Граф называется связным, если для любых двух его вершин x и y существует цепь, соединяющая x и y.

Определение. Говорят, что вершина у графа G достижима из вершины x, если существует путь из x в y.

вершина 2 достижима из 1:(1,2)

вершина 4 достижима из 1:(1,2),(2,4)

вершина 3 не достижима из 1.

Определение. Граф называется сильно связным, если для любых двух его вершин x и y, существует путь соединяющий x и y.

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

Получили 4 компоненты сильной связности графа G1 (вершина является компонентой сильной связности).

Рисунок 3.1.22.

Получим 2 компоненты сильной связности графа G2.

Определение. Пусть дан граф G=(N,A)(N=[V1,...,Vn]). Матрицей достижимости графа G называется квадратная матрица порядка n, у которой , если вершина Vj достижима из Vi, и - в противоположном случае.

Определение. Матрицей сильной связности графа G=(N,A) называется матрица порядка n, у которой , если вершина Vj достижима из Vi, и - в противоположном случае.