Explore related knowledge and questions →
← Question derivation index · Original question batch
R0050-26000 · q-20261015-advance-20261115-r05-max-flow-min-cut-theorem-0075
Use complete directed vertices=[s, a0, a1, t], ordered edges=[[s, a0], [a0, t], [s, a1], [a1, t], [a0, s]], source=s, sink=t, aligned nonnegative exact capacities=[26, 26, 27, 27, 31]. A cut contains the source and excludes the sink; its capacity sums only edges leaving the cut, not incoming edges. Give (cut_rows, minimum_capacity, minimum_cuts, certificate).
G001 — Use complete directed vertices=[s, a0, a1, t], ordered edges=[[s, a0], [a0, t], [s, a1], [a1, t], [a0, s]], source=s, sink=t, aligned nonnegative exact capacities=[26, 26, 27, 27, 31]. A cut contains the source and excludes the sink; its capacity sums only edges leaving the cut, not incoming edges. Give (cut_rows, minimum_capacity, minimum_cuts, certificate).Use the original question domain, assumptions and cited MKO definitions. This item has second-context mathematical and bilingual review, with the model, answer and every arithmetic step independently recomputed from the original parameters; the source question remains a candidate.
Before
source roles = [mfmc-minimum-cut-audit]
After
derived = [[cut_rows, minimum_capacity, minimum_cuts, certificate]]
Conditions: none
List the full source field order without JavaScript.LP weak uses13 fields,zero/strong15;premises and roles follow the original operation/mode without padding.
Rule: source_ordered_fields_without_JS · Uses: G001
Before
source roles = [[s, a0, a1, t], [[s, a0], [a0, t], [s, a1], [a1, t], [a0, s]], [26, 26, 27, 27, 31], null, s, t]
After
derived = [[a0, a1, s, t], [[a0, s], [a0, t], [a1, t], [s, a0], [s, a1]], [31, 26, 27, 26, 27], null]
Conditions: none
Use2..12 vertices.Zip directed edges with capacity/flow by original index before sorting;reverse arcs remain distinct.Source and sink differ;reject loops/duplicates but allow zero capacities,no edges and isolated vertices.
Rule: MFMC_complete_directed_network_ZIP_before_source_order · Uses: G001, S001
Before
MFMC cut mask0 OUTWARD capacity := sum(26, 27)
After
MFMC cut mask0 OUTWARD capacity = 53
Conditions: none
Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.
Rule: exact_rational_arithmetic · Uses: G001, S002
Before
source roles = [0, [a0, a1], [s]]
After
derived = [[3, 4], [0], [[[s, a0], 26], [[s, a1], 27]], 53]
Conditions: none
S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.
Rule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S003
Before
MFMC cut mask1 OUTWARD capacity := sum(26, 27)
After
MFMC cut mask1 OUTWARD capacity = 53
Conditions: none
Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.
Rule: exact_rational_arithmetic · Uses: G001, S004
Before
source roles = [1, [a0, a1], [a0, s]]
After
derived = [[1, 4], [], [[[a0, t], 26], [[s, a1], 27]], 53]
Conditions: none
S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.
Rule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S005
Before
MFMC cut mask2 OUTWARD capacity := sum(27, 26)
After
MFMC cut mask2 OUTWARD capacity = 53
Conditions: none
Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.
Rule: exact_rational_arithmetic · Uses: G001, S006
Before
source roles = [2, [a0, a1], [a1, s]]
After
derived = [[2, 3], [0], [[[a1, t], 27], [[s, a0], 26]], 53]
Conditions: none
S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.
Rule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S007
Before
MFMC cut mask3 OUTWARD capacity := sum(26, 27)
After
MFMC cut mask3 OUTWARD capacity = 53
Conditions: none
Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.
Rule: exact_rational_arithmetic · Uses: G001, S008
Before
source roles = [3, [a0, a1], [a0, a1, s]]
After
derived = [[1, 2], [], [[[a0, t], 26], [[a1, t], 27]], 53]
Conditions: none
S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.
Rule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S009
Before
source roles = [[a0, a1, s, t], [a0, a1]]
After
derived = [4, 4, 53, [[s], [a0, s], [a1, s], [a0, a1, s]]]
Conditions: none
Every s–t cut uniquely corresponds to a subset of other vertices,so all2^(n−2) cuts are compared.Select the minimum and all minimizers from this same complete family,retaining mask tie order.
Rule: MFMC_ALL_cut_family_complete_minimum_and_ALL_ties · Uses: G001, S010
S011 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.S010 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.S009 · premise_and_result_audit — Recompute MFMC cut mask3 OUTWARD capacity with exact rational arithmetic, not rounded decimals.S008 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.S007 · premise_and_result_audit — Recompute MFMC cut mask2 OUTWARD capacity with exact rational arithmetic, not rounded decimals.S006 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.S005 · premise_and_result_audit — Recompute MFMC cut mask1 OUTWARD capacity with exact rational arithmetic, not rounded decimals.S004 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.S003 · premise_and_result_audit — Recompute MFMC cut mask0 OUTWARD capacity with exact rational arithmetic, not rounded decimals.S002 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.S001 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.([[[s], [[[s, a0], 26], [[s, a1], 27]], 53], [[a0, s], [[[a0, t], 26], [[s, a1], 27]], 53], [[a1, s], [[[a1, t], 27], [[s, a0], 26]], 53], [[a0, a1, s], [[[a0, t], 26], [[a1, t], 27]], 53]], 53, [[s], [a0, s], [a1, s], [a0, a1, s]], minimum_cut_is_selected_from_the_complete_cut_family)
The full substitutions and premise checks give the original answer; source identity,format and status are unchanged.
Review date: 2026-10-26
Original questions, answers, step expressions, numeric ASTs and historical records are retained. Source candidate labels remain historical and are not overwritten as formal proof.
input commit: 0f7be61e2c22317a4075561dc822c87d881a50dboriginal question SHA-256: 02b434d08b49138da6af6e6ab3a352fe267e29b8dbaa67582177b97b7c906df0candidate record SHA-256: 5629a229373e1f1a5c7a33f877f2f08ab27f0eebd52a8c280df773782106cdf2semantic review receipt SHA-256: 74c63a2c12285a3b2073f8d9f102bc2ba5fb7ed890c5b7c3b8afa94f032eda82question-first witness SHA-256: 6d56428610f8e86c45fd00a2ad3b27ad9c052956946f0b91d71a68536f79d95fLean: NOT_RUN · human review: NOT_PERFORMED