Graph::convertSSQПреобразует График в один источник один График приемника
Блокноты MuPAD® будут демонтированы в будущем релизе. Используйте live скрипты MATLAB® вместо этого.
Live скрипты MATLAB поддерживают большую часть функциональности MuPAD, хотя существуют некоторые различия. Для получения дополнительной информации смотрите, Преобразуют Notebook MuPAD в Live скрипты MATLAB.
Graph::convertSSQ(G, q, s)
Graph::convertSSQ(G, q, s) преобразует график G в направленный один источник один график приемника. Заданные вершины q и s добавляются к графику. Это - ошибка, если они уже предопределены. В противном случае они соединяются с другими вершинами графика следующим образом:
Новое ребро [q,i] добавляется для каждой вершины i с положительным весом. Новое ребро [i,s] добавляется для каждой вершины i с отрицательным весом. Мощности этих ребер находятся в каждом случае вес узла i. Вес ребра является нулем.
testexample, чтобы показать преобразование.
V := [1, 2, 3, 4]:
Vw := [4, 0, 0, -4]:
Ed := [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4]]:
Ec := [2, 2, 1, 3, 1]:
Ew := [4, 2, 2, 3, 5]:
G1 := Graph(V, Ed, VertexWeights = Vw,
EdgeWeights = Ew,EdgeCosts = Ec):
G2 := Graph::convertSSQ(G1, [q], [s]):
Graph::printGraphInformation(G2)Vertices: [1, 2, 3, 4, q, s] Edges: [[1, 2], [1, 3], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4\ , 2], [4, 3], [4, s], [q, 1]] Vertex weights: 1 = 0, 2 = 0, 3 = 0, 4 = 0, q = 4, s = -4 (other existing \ vertices have no weight) Edge descriptions: no edge descriptions. Edge weights: [1, 2] = 4, [1, 3] = 2, [2, 3] = 2, [2, 4] = 3, [3, 4] = 5, \ [2, 1] = 4, [3, 1] = 2, [3, 2] = 2, [4, 2] = 3, [4, 3] = 5, [q, 1] = 4, [4\ , s] = 4 (other existing edges have no weight) Edge costs: [1, 2] = 2, [1, 3] = 2, [2, 3] = 1, [2, 4] = 3, [3, 4] = 1, [2\ , 1] = 2, [3, 1] = 2, [3, 2] = 1, [4, 2] = 3, [4, 3] = 1, [q, 1] = 0, [4, \ s] = 0 (other existing edges have costs zero) Adjacency list (out): 1 = [2, 3], 2 = [1, 3, 4], 3 = [1, 2, 4], 4 = [2, 3,\ s], q = [1], s = [] Adjacency list (in): 1 = [2, 3, q], 2 = [1, 3, 4], 3 = [1, 2, 4], 4 = [2, \ 3], q = [], s = [4] Graph is directed.
Бывший неориентированный граф был преобразован в направленного!
|
Вершины, не предопределенные в Графике |
|
График |
Направленный увеличенный График
Оба, Белман и Дейкстра ожидают График без отрицательных кругов. Только Дейкстра может возвратить ошибочные результаты, когда отрицательные ребра (или веса или затраты) заданы.
Алгоритм Белмана, порожденный из: Ahuja, Magnanti, Orlin: Dom:: Потоки Графика, Prentice Hall, 1 993 Раздела 5.4