uzluga.ru
добавить свой файл
1


Теория графов

  • Основные определения


Пусть имеется множество вершин V={V1,V2,…,Vn} и пусть на нем задано бинарное отношение Г⊂V×V,

  • Пусть имеется множество вершин V={V1,V2,…,Vn} и пусть на нем задано бинарное отношение Г⊂V×V,

    • Vi Г Vj↔(Vi Vj)∈ Г – эту пару назовем дугой Uk




Если бинарное отношение симметрично, то наряду с дугой (Vi,Vj) есть дуга (Vj,Vi). В этом случае чаще всего переходят к неориентированным графам.



Матрица инцидентности A. По вертикали указываются вершины, по горизонтали - ребра. aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в вершину i входит ребро j. Если ребро - петля, то aij=2.

  • Матрица инцидентности A. По вертикали указываются вершины, по горизонтали - ребра. aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в вершину i входит ребро j. Если ребро - петля, то aij=2.

  • Список ребер. В первом столбце ребра, во втором вершины им инцидентные.

  • Матрица смежности - квадратная симметричная матрица. По горизонтали и вертикали - все вершины. Dij= число ребер, соединяющее вершины i,j.

  • Матрица Кирхгофа: bij=-1, если вершины i и j смежны, bij=0 если вершины i и j не смежны. Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0.





Для ориентированных графов: полустепенью исхода вершины |Г(Vi)| будем называть число дуг, исходящих из вершины Vi; полустепенью захода вершин |Г-1(Vi)| будем называть число дуг, заходящих в вершину. В орграфе две локальных степени вершины v: deg(v)+ и deg(v) - (число ребер с началом и концом в v). Для неориентированных графах говорят только о степени.

  • Для ориентированных графов: полустепенью исхода вершины |Г(Vi)| будем называть число дуг, исходящих из вершины Vi; полустепенью захода вершин |Г-1(Vi)| будем называть число дуг, заходящих в вершину. В орграфе две локальных степени вершины v: deg(v)+ и deg(v) - (число ребер с началом и концом в v). Для неориентированных графах говорят только о степени.

  • Следствие 2 из леммы о рукопожатиях. Число ребер в полном графе n(n-1)/2.



Матрица достижимости R={rij}, {rij}=1, если Vj достижима из Vi, {rij}=0 в противном случае. R=E+A+А2+…+Ak

  • Матрица достижимости R={rij}, {rij}=1, если Vj достижима из Vi, {rij}=0 в противном случае. R=E+A+А2+…+Ak

  • В степенях используется «булевское» умножение матриц (строк на столбец, но 1+1=1, 0+1=1,0+0=0, 1+0=0).

  • K – такое число, при котором дальнейшее сужение степеней не меняет матрицу R.



Составляется список ребер в порядке увеличения весов.

  • Составляется список ребер в порядке увеличения весов.

  • В искомое дерево добавляем, начиная с первого элемента списка по порядку этого списка ветви до те пор, пока не встречаем ветвь, образующую с ранее включенной цикл. Данную ветвь вычеркиваем из списка. Затем продолжаем аналогичные действия до (n-1) ветви.





Пусть имеется направленный ориентированный граф с двумя выделенными вершинами Vs и Vt. Найти минимальный направленный путь из Vs в Vt.

  • Пусть имеется направленный ориентированный граф с двумя выделенными вершинами Vs и Vt. Найти минимальный направленный путь из Vs в Vt.

  • Помечаем вершину Vs, и присваиваем ей вес qs:=0, а всем остальным присваиваем временный вес qi=∞

  • Полагаем i=s – номер последней отмеченной вершины

  • Для каждой неотмеченной вершины Vj выполняется следующий оператор qj:=min(qj, qi+pij), где pij – вес ветви, ведущей из i-той вершины в j-тую, если нет pij, считаем pij=∞



Проверяем, есть ли среди только что отмеченных qj конечное значение. Если таких вершин нет, то мы завершаем алгоритм, пути из s в t не существует. Если же конечное значение qj найдется, то из них выбирается минимальная. Пусть это вершина j0, тогда мы помечаем эту вершину, а так же помечаем ту дугу, по которой мы добирались в вершину Vj0, при получении этого минимального значения.

  • Проверяем, есть ли среди только что отмеченных qj конечное значение. Если таких вершин нет, то мы завершаем алгоритм, пути из s в t не существует. Если же конечное значение qj найдется, то из них выбирается минимальная. Пусть это вершина j0, тогда мы помечаем эту вершину, а так же помечаем ту дугу, по которой мы добирались в вершину Vj0, при получении этого минимального значения.

  • I=jo

  • Проверяем условие i=t. Если это так, алгоритм завершается, L(s-t)=qj0. Сам же минимальный путь считается, начиная с вершины Vt по выделенным дугам в обратном порядке. Если же i≠t, возвращаемся к пункту 3.