Explore related knowledge and questions →
← Question derivation index · Original question batch
R0050-25913 · q-20261015-advance-20261115-r05-max-flow-min-cut-theorem-0013
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=[14, 14, 15, 15, 19]. A cut contains the source and excludes the sink; its capacity sums only edges leaving the cut, not incoming edges. Give (vertices, source, sink, cut_rows, cut_count, required_cut_count, 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=[14, 14, 15, 15, 19]. A cut contains the source and excludes the sink; its capacity sums only edges leaving the cut, not incoming edges. Give (vertices, source, sink, cut_rows, cut_count, required_cut_count, 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-complete-cut-enumeration]
After
derived = [[vertices, source, sink, cut_rows, cut_count, required_cut_count, 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]], [14, 14, 15, 15, 19], null, s, t]
After
derived = [[a0, a1, s, t], [[a0, s], [a0, t], [a1, t], [s, a0], [s, a1]], [19, 14, 15, 14, 15], 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(14, 15)
After
MFMC cut mask0 OUTWARD capacity = 29
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], 14], [[s, a1], 15]], 29]
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(14, 15)
After
MFMC cut mask1 OUTWARD capacity = 29
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], 14], [[s, a1], 15]], 29]
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(15, 14)
After
MFMC cut mask2 OUTWARD capacity = 29
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], 15], [[s, a0], 14]], 29]
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(14, 15)
After
MFMC cut mask3 OUTWARD capacity = 29
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], 14], [[a1, t], 15]], 29]
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, 29, [[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.([a0, a1, s, t], s, t, [[[s], [[[s, a0], 14], [[s, a1], 15]], 29], [[a0, s], [[[a0, t], 14], [[s, a1], 15]], 29], [[a1, s], [[[a1, t], 15], [[s, a0], 14]], 29], [[a0, a1, s], [[[a0, t], 14], [[a1, t], 15]], 29]], 4, 4, every_subset_containing_s_and_excluding_t_is_enumerated_and_only_forward_edges_are_counted)
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: 112bc19f4fa4fc07fd314ed1e88462bd70a84649cb34571c0eeb45429c35fd4acandidate record SHA-256: a71de6f03a996dd3df33fb0131946309abb1758c523f11d787a87c917cdce219semantic review receipt SHA-256: 74c63a2c12285a3b2073f8d9f102bc2ba5fb7ed890c5b7c3b8afa94f032eda82question-first witness SHA-256: 6d56428610f8e86c45fd00a2ad3b27ad9c052956946f0b91d71a68536f79d95fLean: NOT_RUN · human review: NOT_PERFORMED