Graph::residualGraph
Вычисляет остаточный график
Блокноты MuPAD® будут демонтированы в будущем релизе. Используйте live скрипты MATLAB® вместо этого.
Live скрипты MATLAB поддерживают большую часть функциональности MuPAD, хотя существуют некоторые различия. Для получения дополнительной информации смотрите, Преобразуют Notebook MuPAD в Live скрипты MATLAB.
Синтаксис
Graph::residualGraph(G, f, <Extended>)
Описание
Graph::residualGraph(G, flow) вычисляет невязку графика G относительно потока flow, значение графика, который остается когда поток flow “вычтен” из G.
Graph::residualGraph вычисляет остаточный график относительно данного потока. Поток в Графике является таблицей tbl, где tbl[[i,j]] дает количество модулей, текущих из вершины i к вершине j.
Если дополнительный аргумент Extended дан, затем также, те ребра с нулевой остаточной способностью рассматриваются, в противном случае эти ребра не использованы.
Примеры
Пример 1
В следующем вызове, G2 график, состоящий из остающихся транспортных мощностей после данного потока:
G1 := Graph::createCompleteGraph(3):
G2 := Graph::residualGraph(G1,
table( [1, 2] = 1, [2, 1] = 1/2,
[1, 3] = 0, [3, 1] = 0.5,
[2, 3] = 1, [3, 2] = 0 ) ):
Graph::getEdgeWeights(G2)
Алгоритм обнаруживает отсутствие веса ребра, и ребро стоит и устанавливает весь вес ребра и затраты для значений по умолчанию 1.
Пример 2
Получившийся график зависит от ли опция Extended используется:
V := [1, 2, 3, q, s]:
Edge := [[q, 1], [1, 2], [1, 3], [2, 3], [3, s]]:
up := [5, 4, 4, 2, 5]:
G := Graph(V,Edge,EdgeWeights = up, Directed):
flow := table([q, 1] = 5, [3, s] = 5, [1, 2] = 1,
[1, 3] = 4, [2, 3] = 1):
G1 := Graph::residualGraph(G, flow):
Graph::printGraphInformation(G1);Vertices: [1, 2, 3, q, s] Edges: [[2, 1], [3, 1], [3, 2], [s, 3], [1, q], [1, 2], [2, 3]] Vertex weights: no vertex weights. Edge descriptions: no edge descriptions. Edge weights: [1, 2] = 3, [2, 3] = 1, [2, 1] = 1, [3, 1] = 4, [3, 2] = 1, \ [s, 3] = 5, [1, q] = 5 (other existing edges have no weight) Edge costs: [1, 2] = 1, [2, 3] = 1, [2, 1] = -3, [3, 1] = 0, [3, 2] = -1, \ [s, 3] = 0, [1, q] = 0 (other existing edges have costs zero) Adjacency list (out): 1 = [2, q], 2 = [1, 3], 3 = [1, 2], q = [], s = [3] Adjacency list (in): 1 = [2, 3], 2 = [1, 3], 3 = [2, s], q = [1], s = [] Graph is directed.
Вес ребра содержит остаточный график со всеми потоками. Затраты ребра показывают поток, который был вычтен или добавлен. Например, ребро [1, 2] имело вес 4. После того, как поток 3 был отправлен по нему, остаточное ребро [2, 1] содержит поток-3, и остаточное ребро [1, 2] содержит поток 1. Начиная с отрицательного потока вернувшегося ребра плюс поток ребра в остаточном графике должны суммировать до потока, это показывает, что поток вычисляется правильно. (-(-3) + 1 = 4)
G1 := Graph::residualGraph(G, flow, Extended): Graph::printGraphInformation(G1);
Vertices: [1, 2, 3, q, s] Edges: [[2, 1], [3, 1], [3, 2], [s, 3], [1, q], [1, 2], [1, 3], [2, 3], [3\ , s], [q, 1]] Vertex weights: no vertex weights. Edge descriptions: no edge descriptions. Edge weights: [q, 1] = 5, [1, 2] = 4, [1, 3] = 4, [2, 3] = 2, [3, s] = 5, \ [2, 1] = -4, [3, 1] = -4, [3, 2] = -2, [s, 3] = -5, [1, q] = -5 (other exi\ sting edges have no weight) Edge costs: [1, 2] = 3, [1, 3] = 0, [2, 3] = 1, [3, s] = 0, [q, 1] = 0, [2\ , 1] = 1, [3, 1] = 4, [3, 2] = 1, [s, 3] = 5, [1, q] = 5 (other existing e\ dges have costs zero) Adjacency list (out): 1 = [2, 3, q], 2 = [1, 3], 3 = [1, 2, s], q = [1], s\ = [3] Adjacency list (in): 1 = [2, 3, q], 2 = [1, 3], 3 = [1, 2, s], q = [1], s \ = [3] Graph is directed.
Параметры
|
График |
|
Предопределенный поток |
Опции
|
Включайте ребра с нулевыми мощностями |
Возвращаемые значения
Graph