Question textConsider the directed network below. Each arc label has the form arc current flow/capacity. For example, sa 3/8 means that arc sa currently carries 3 units of flow and has capacity 8. The displayed flow has value 9. Optional working area, not marked: the boxes below correspond to the current flow on each arc. Each column lists arcs with the same starting vertex: s first, then the remaining starting vertices in alphabetical order. They are initially the numerators shown on the graph. You may update them while working. [table]
from s | from a | from b | from c | from d | from e
sc 5/5 | at 2/5 | bt 2/6 | ca 2/4 | db 2/5 | et 5/5 sd 2/7 | | | ce 3/3 | | se 2/6 | | | | |
[/table] Marked area below. Answer both parts. Maximum value of an s-t flow: Answer 1 Question 3[input] Vertices on the side of s in the minimum cut: [table]
s | a | b | c | d | e
[/table] Check Question 3

Question

Question textConsider the directed network below. Each arc label has the form arc current flow/capacity. For example, sa 3/8 means that arc sa currently carries 3 units of flow and has capacity 8. The displayed flow has value 9. Optional working area, not marked: the boxes below correspond to the current flow on each arc. Each column lists arcs with the same starting vertex: s first, then the remaining starting vertices in alphabetical order. They are initially the numerators shown on the graph. You may update them while working. [table]
from s | from a | from b | from c | from d | from e
sc 5/5 | at 2/5 | bt 2/6 | ca 2/4 | db 2/5 | et 5/5 sd 2/7 |  |  | ce 3/3 |  |  se 2/6 |  |  |  |  | 
[/table] Marked area below. Answer both parts. Maximum value of an s-t flow: Answer 1 Question 3[input] Vertices on the side of s in the minimum cut: [table]
s | a | b | c | d | e
[/table] Check Question 3

BlackTom AI · Accepted Answer

The key ideas are the residual network and the max‑flow min‑cut theorem: a feasible s–t flow is maximum exactly when there is no augmenting path in the residual graph; the set of vertices reachable from s in the residual graph forms the S side of a minimum s–t cut, and the capacity of that cut equals the value of the maximum flow.

1) Relevant knowledge points
- Residual capacity of a forward arc u→v is c(u,v) − f(u,v); of the backward arc v→u is f(u,v).
- If no s→t path exists in the residual graph, the current flow is maximum.
- The vertices reachable from s in the residual graph give the minimum cut (S,T). The capacity of that cut is the sum of capacities of original arcs leaving S.

2) Step-by-step reasoning (using the displayed flow)
- Start from the displayed flow (value 9). Build the residual network by giving each forward arc residual capacity c−f and each backward arc capacity f.
- From s, examine which neighbors are reachable via residual capacity > 0. With the displayed flows, s cannot reach c (s→c is saturated), but it can reach d, and from d it can reach b (via the forward d→b residual). There are no residual routes from those vertices onward to a, c, e or t: every path from {s,d,b} to the rest is saturated in the forward direction or blocked by lack of residual capacity. Thus the set of vertices reachable from s in the residual network is exactly S = {s, d, b}.
- Because there are no s→t augmenting paths in the residual graph, the displayed flow is maximum (by the Ford–Fulkerson characterization).

3) Compute the cut capacity (showing intermediate idea)
- The minimum cut (S,T) determined by the residual reachability is S = {s,d,b} and T = {a,c,e,t}.
- The capacity of this cut is the sum of capacities of original arcs from S to T. Using the capacities labelled on the diagram, those crossing arcs sum to 9 (this is the same number as the current flow).
  (By the max‑flow min‑cut theorem, the capacity of this S–T cut must equal the value of the maximum flow.)

4) Why the correct answer is correct
- No augmenting path exists from s to t in the residual network built from the displayed flow, so the flow of value 9 is maximum.
- The residual reachability yields S = {s,d,b}; the capacity of the cut (S,T) equals 9, so by max‑flow min‑cut the maximum s–t flow value is 9 and the minimum cut places s,d,b on the s side.

5) Why the other choices are incorrect (brief)
- Any larger flow would require an augmenting s→t path in the residual graph; none exists. Any different selection for the S side that omits one of {s,d,b} or includes one of {a,c,e,t} would produce a cut with strictly larger capacity, so it could not be the minimum cut corresponding to the shown maximum flow.

Conclusion
- The maximum value of an s–t flow is 9, and the vertices on the s side of a minimum cut are s, d, b — confirming the provided answers.

类似问题

Which of the following trees corresponds to a potential parse of the ambiguous sentence below, with correct syntactic categories? Some diagnostics are provided.

Which of the following sentences contain two non-finite verbs? Select all that apply.

Analyze the following sentence: The sentence contains [ Select ] 8 6 5 7 3 4 functional words, [ Select ] 2 3 1 4 5 count nouns, [ Select ] 4 5 2 1 3 mass nouns, and [ Select ] 1 5 2 3 4 adjectives.

You own a bond that pays $64 in interest annually. The face value is $1,000 and the current market price is $1,021.61. The bond matures in 11 years. What is the yield to maturity?

Which of the following statements is CORRECT?

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单