Explore related knowledge and questions →
← Question derivation index · Original question batch
R0050-25921 · q-20261015-advance-20261115-r05-max-flow-min-cut-theorem-0021
Use complete directed vertices=[s, a0, a1, t], ordered edges=[[s, a0], [a0, t], [s, a1], [a1, t]], source=s, sink=t, aligned nonnegative exact capacities=[22, 22, 23, 23]. 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]], source=s, sink=t, aligned nonnegative exact capacities=[22, 22, 23, 23]. 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]], [22, 22, 23, 23], null, s, t]
After
derived = [[a0, a1, s, t], [[a0, t], [a1, t], [s, a0], [s, a1]], [22, 23, 22, 23], 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(22, 23)
After
MFMC cut mask0 OUTWARD capacity = 45
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 = [[2, 3], [], [[[s, a0], 22], [[s, a1], 23]], 45]
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(22, 23)
After
MFMC cut mask1 OUTWARD capacity = 45
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 = [[0, 3], [], [[[a0, t], 22], [[s, a1], 23]], 45]
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(23, 22)
After
MFMC cut mask2 OUTWARD capacity = 45
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 = [[1, 2], [], [[[a1, t], 23], [[s, a0], 22]], 45]
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(22, 23)
After
MFMC cut mask3 OUTWARD capacity = 45
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 = [[0, 1], [], [[[a0, t], 22], [[a1, t], 23]], 45]
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, 45, [[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], 22], [[s, a1], 23]], 45], [[a0, s], [[[a0, t], 22], [[s, a1], 23]], 45], [[a1, s], [[[a1, t], 23], [[s, a0], 22]], 45], [[a0, a1, s], [[[a0, t], 22], [[a1, t], 23]], 45]], 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: 752e7f71cdde4a6bf58c4eeecdfa9a5a49dc2b02669f612a06eea07bc43b6be7candidate record SHA-256: f40b7f3b5fdfc3e6b8f61927ff90d2959eea6f4062952d3e2bca8827c0fe227dsemantic review receipt SHA-256: 74c63a2c12285a3b2073f8d9f102bc2ba5fb7ed890c5b7c3b8afa94f032eda82question-first witness SHA-256: 6d56428610f8e86c45fd00a2ad3b27ad9c052956946f0b91d71a68536f79d95fLean: NOT_RUN · human review: NOT_PERFORMED