Способы задания графов

1.Матрица смежности вершин графа – квадратная матрица н порядка, где н – число вершин. Строки и столбцы матрицы соответствуют вершинам графа. Элементы р_ijравны числу дуг, направленных из и в жи. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0 либо 1. В случае не ориентированного графа ему вместе с ребром (X_i X_j) принадлежит ребро (X_i X_j).

2.Матрица смежности дуг – квадратная матрица м порядка, м – число дуг. Строки и столбцы матрицы соответствуют дугам графа. Элементы q­ij­ равны 1, если дуга у_i непосредственно предшествует дуге y_j и 0 в остальных случаях.

3.Матрица смежности ребер неориентированного графа – матрица м порядка, м – число ребер с элементами q_ij = 1, если ребра y­­_I y_j имеют общую вершину и 0 в остальных.

4.Матрица инцидентности орграфа – прямоугольная матрица, размерности Н х М, строки которой соответствуют вершинам, а столбцы дугам орграфа. Элементы r­_ij равны 1, если дуга y_j исходит из I вершины. Равны 0, если дуга не инцидентна итой вершине.

5 wEZhkZMkI60oXyogG4bLVb0bDywYGSFCKjWA8r+D9rERxtPaDsBe0R+zDdEpozVhAGppLPwua9ge ShV9/EF1rzXKPrfVLg01tQN3Lw1h/0/icv94T/Dvv3nxDQAA//8DAFBLAwQUAAYACAAAACEAmJdc +uAAAAAKAQAADwAAAGRycy9kb3ducmV2LnhtbEyPy07DMBBF90j8gzVI7KjdEDWPxqkQqMsKGliU nRu7SUQ8DrHbpn/PdFV28zi6c6ZYTbZnJzP6zqGE+UwAM1g73WEj4etz/ZQC80GhVr1DI+FiPKzK +7tC5dqdcWtOVWgYhaDPlYQ2hCHn3NetscrP3GCQdgc3WhWoHRuuR3WmcNvzSIgFt6pDutCqwby2 pv6pjlaCr8W8irfvu+gj/v7dvO3W2WXTS/n4ML0sgQUzhRsMV31Sh5Kc9u6I2rNeQpYmRNL8WcTA rkCaLIDtqUiyCHhZ8P8vlH8AAAD//wMAUEsBAi0AFAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAA AAAAAAAAAAAAAAAAAFtDb250ZW50X1R5cGVzXS54bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACU AQAACwAAAAAAAAAAAAAAAAAvAQAAX3JlbHMvLnJlbHNQSwECLQAUAAYACAAAACEAXwb94AkCAAAV BAAADgAAAAAAAAAAAAAAAAAuAgAAZHJzL2Uyb0RvYy54bWxQSwECLQAUAAYACAAAACEAmJdc+uAA AAAKAQAADwAAAAAAAAAAAAAAAABjBAAAZHJzL2Rvd25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAHAF AAAAAA== " strokecolor="black [3200]" strokeweight="2pt"> В случае неориентированного графа будет или 0.

1.

2.

3.

Остовные деревья минимального веса. Алгоритмы Прима и Крускала

Пусть G неориентированный связный граф. Любой связный подграф G* из множества (G* с G) содержащий все вершины графа и не имеющий циклов называется остовом G или остовным деревом.

Постановка задачи:

Имеется связный граф, каждому ребру которого поставлено в соответствие неотрицательное число, называемое весом ребра. Требуется найти остовное дерево минимального веса. Вес дерева равен сумме весов ребер, входящих в него.

Алгоритм Прима

1.Выбирается подграф G₁ из множества G, вершинами которого являются вершины графа, имеющего одно ребро, выбранное из ребер графа G имеющих минимальный вес. На каждом последующем шаге уже построенному графу добавляется одно ребро.

К.Если подграф G_к-1 из множества G уже построен,… получается из G_к-1 добавлением ребра Л обладающего свойствами:

1.Л инцедентно какому-либо ребру G_к-1

2.При добавлении к Л G_{к-1 не обр цикла}

3.Л имеет минимальный вес среди ребер, удовлетворяющих условию 1 и 2.

Алгоритм Крускала

1.Выбирается подграф G₁ из множества G, вершинами которого являются вершины графа, имеющего одно ребро, выбранное из ребер графа G имеющих минимальный вес. На каждом последующем шаге уже построенному графу добавляется одно ребро.

К.Если подграф G_к-1 из множества G уже построен,… получается из G_к-1 добавлением ребра Л обладающего Свойства:

1.При добавлении Л G_к-1 не обр циклов

2. Л имеет мин вес среди ребер, удовлетворяющих условию 1.

Нахождение кратчайших путей между двумя заданными вершинами. Алгоритм Дейкстры

Постановка задачи:

Пусть задан орграф G=(V,E) с заданными положительными длинами ребер. Найти длину кратчайшего пути(и сам путь), соединяющий 2 произвольные фиксированные вершины s(начало) и t(конец).

Алгоритм Дейкстры:

1.В начале алгоритма все вершины не окрашены. Каждой вершине В во время выполнения алгоритма ставиться в соответствие либо L(v) – длина кратчайшего пути включающего только окрашенные, L(v*) – временная метка, которая становиться равной L(v) в момент когда В окрашивается. Полагаем что L(s)=0, L(v*)…. Окрашиваем вершину s. Для каждой неокрашенной вершины и соседней с последней из окрашенных В пересчитываем L(u)=min(L*(u)L(v)+L(v,u)), L(v,u) – длина дуги.

3(?).В момент, когда вершина t становиться окрашенной находим кратчайший путь, соединяющий s t, состоящий из окрашенных дуг.

4 7

3 2

L(s)=0 L(c)=3 L(a)=4 L(d)=6 L(b)=7

L*(a)=4 L*(d)=6 L*(b)=7 L*(t)=8 L*(t)=9

L*(b)=7 L*(d)=6

L*(c)=3

L(t)=8(s-c-d-t)

Алгоритм Флойда (расстояние между 2 точками)

Рассмотрим сеть, в каждой дуге которой (U,V) поставлено в соответствие действительное число L(u,v), называемое длиной дуги. В зависимости от конкретного приложения это число может быть мерой физического расстояния, времени, стоимости или иного параметра.

L₀= здесь пишем расстояния из i в j

S₀= здесь пишем вершины (справочная)

Алгоритм Флойда

1.планируем,что вершины графа G – числа(1,2,…н). Обозначим через L₀ матрицу, элементами которой L_ij=длина или бесконечность(1.1 например). Введем матрицу S₀ матрица н*н, где элементы S_ij=j. Пусть матрицы L_p S_p найдены. Выделим элементы p строки и столбца, назовем их базовой строкой и базовым столбцом соответственно.

2.построим матрицы L_p+1 S_p+1 по следующим правилам:

а)элементы базовой строки и столбца переписываем без изменений.

б) если элемент L_ij>L_ip+1+L_p

3.алгоритм заканчивает свою работу, когда построены матрицы L_n и S_n.

Замечание 1.Если итый элемент базоваого столбца равен бесконечности, то для ээтой строки шаг 2 выполнять не нужно.

Замечание 2.Если житый элемент равен бесконечности, то шаг 2 выполнять не нужно.

Поиск по сайту: