فهرست مقاله
پیش از انتخابِ محیطِ آزمونِ یکپارچگی، گاهی باید مسئلهٔ کوچک‌تری را حل کنیم: کدام سناریو می‌تواند کدام فیکسچر را بگیرد؟ فیکسچر در این درس، منبعِ آماده‌سازیِ فرضی است، نه ابزارِ واقعیِ متصل. یک انتخابِ محلی ممکن است ظرفیتِ موجود را پنهان کند. با گرافِ سازگاریِ تألیفی، تخصیصِ بیشینه و مرجعِ مستقل، همین مرزِ تصمیم را بررسی می‌کنیم؛ هیچ سرویس یا سخت‌افزاری اجرا نمی‌شود.
۱. هر آزمون به یک فیکسچرِ سازگار نیاز دارد
سمتِ چپ، سناریوهای T0 و T1 و سمتِ راست، منابعِ F0 و F1 هستند. هر سناریو حداکثر یک منبع می‌گیرد و هر منبع در همین نوبت حداکثر به یک سناریو می‌رسد. جدولِ سازگاری را از پیش داده‌ایم: T0 با هر دو منبع و T1 فقط با F0 سازگار است. برنامه، سازگاریِ واقعی را کشف یا تأیید نمی‌کند.
هدف، بیشترین تعدادِ سناریوی تخصیص‌یافته است؛ هزینه، ترجیح، زمان و احتمالِ موفقیت نداریم. نام‌ها و شمارها بی‌واحدند و تعدادِ جفت‌ها، تعدادِ آزمونِ واقعاً موفق نیست. تعریفِ تطبیق و بیشینهٔ تعداد در مستنداتِ پرینستون پشتوانهٔ اصطلاح‌هاست. یال‌های منتخب نباید هیچ سرِ مشترکی داشته باشند.
در دو‌رنگ‌کردن و شاهدِ چرخهٔ فرد، سؤال این بود که آیا می‌توان رأس‌ها را به دو طرف تقسیم کرد. اینجا دو طرف از ابتدا مشخص‌اند؛ مسئله، انتخابِ زیرمجموعه‌ای از یال‌هاست. دوبخشی‌بودنِ ورودی، به‌تنهایی نمی‌گوید هر سناریو منبعِ جداگانه خواهد داشت.
این تصمیمِ مقدماتی برای انتخابِ فیکسچر مفید است، ولی جایِ آزمونِ یکپارچگی را نمی‌گیرد. آماده‌بودنِ سرویس، نسخهٔ پروتکل، پاک‌سازیِ وضعیت و نتیجهٔ واقعیِ درخواست‌ها بیرونِ مدل‌اند. همچنین منبع در طولِ همین تخصیص یک‌بارمصرف فرض شده است؛ استفادهٔ پیاپی در چند نوبت، به مدلِ زمان و بازاستفادهٔ جدا نیاز دارد.
۲. انتخابِ حریصانه چرا ظرفیت را پنهان می‌کند؟
اگر T0 نخست F0 را بگیرد، T1 بدونِ منبع می‌ماند. دیگر نمی‌توان فقط یک یالِ آزاد به جواب افزود؛ هر انتخابِ باقی‌مانده به سرِ اشغال‌شده می‌خورد. این، تطبیقِ بیشین یا maximal است، اما بیشینهٔ تعداد یا maximum نیست: می‌توان T0 را به F1 برد و F0 را به T1 داد. حالا دو سناریو پوشش دارند.
مسیرِ T1، F0، T0، F1 میانِ یالِ انتخاب‌نشده و انتخاب‌شده رفت‌وبرگشت دارد و دو سرش آزادند. با برگرداندنِ عضویتِ یال‌های همین مسیر، یک جفت بیشتر می‌گیریم و تداخلِ منبع ایجاد نمی‌شود. تعریفِ مسیرِ افزایشی و قضیهٔ ۱٫۲ در یادداشتِ Goemans مبنای این تغییر است.
جست‌وجو باید بتواند صاحبِ فعلیِ منبع را هم بررسی کند. در شاهدِ زنجیره‌ای، سه سناریوی اول به منابعِ صفر، یک و دو می‌رسند؛ سناریوی چهارم فقط منبعِ صفر را می‌خواهد. جابه‌جاییِ سه صاحبِ قبلی به منابعِ یک، دو و سه، جایِ چهارمی را باز می‌کند. ممنوع‌کردنِ هر بازنگری، پاسخِ چهار‌جفتی را از دست می‌دهد.
آرایهٔ owner صاحبِ هر منبع را نگه می‌دارد. برای سناریوی تازه، مجموعهٔ منابعِ دیده‌شده از نو ساخته می‌شود؛ در همان تلاش، هر منبع دوباره پیموده نمی‌شود. این مجموعه نباید میانِ تلاش‌های مستقل باقی بماند. تغییرِ مالکیت فقط پس از یافتنِ ادامهٔ موفق انجام می‌شود؛ شاخهٔ ناموفق، انتخابِ قبلی را بی‌دلیل حذف نمی‌کند.
۳. کدِ کاملِ مسیرِ افزایشی با قراردادِ محدود
تابع maximum_assignment دو تاپلِ دقیق با صفر تا شش نام در هر طرف می‌گیرد. نام، رشتهٔ دقیقِ ASCII با حرفِ بزرگِ آغازین و حداکثر هشت نویسه است؛ ادامه می‌تواند حرفِ بزرگ، رقم یا زیرخط باشد. نامِ تکراری و اشتراکِ نام میانِ دو طرف رد می‌شود. جداکردنِ فضای نام، انتخابِ رابطِ همین مثال است، نه ضرورتِ تمامِ نمایش‌های گراف.
یال‌ها نیز تاپلِ دقیق با حداکثر ۳۶ زوجِ تاپلی‌اند؛ هر زوج باید از چپِ اعلام‌شده به راستِ اعلام‌شده برود. زوجِ تکراری، جهتِ معکوس، عضوِ ناشناخته و نوعِ نادرست خطا هستند. برنامه قبل از جست‌وجو کلِ ورودی را کنترل می‌کند. ورودیِ تهی معتبر است و با دادهٔ خراب اشتباه نمی‌شود.
ترتیبِ سناریوها و منابع در تاپل‌های اعلام‌شده، ترتیبِ پیمایش را مشخص می‌کند. ترتیبِ نوشتنِ یال‌ها معیارِ دیگری نمی‌سازد. خروجی جفت‌ها، تعداد، اعضای بی‌جفتِ هر طرف و پرچمِ پوششِ تمامِ چپ را دارد. یک جوابِ مشخص بازتولید می‌شود؛ این سیاست، ادعای یکتایی یا کوچک‌ترین جوابِ واژه‌نامه‌ای نیست.
فایل با Python 3.14.5 و فقط کتابخانهٔ استاندارد اجرا شده است. بازگشتِ محدودِ جست‌وجو در این دامنه جایِ حلِ مسئلهٔ بزرگ یا سنجشِ کارایی نیست. تابع‌های تشخیصی و مرجع روی فیکسچرهای داخلیِ معتبر کار می‌کنند؛ فقط رابطِ اصلی، قراردادِ کاملِ ورودی را اجرا می‌کند. کد شبکه، ساعت یا فرایندِ سرویس نمی‌سازد.
"""Finite synthetic fixture compatibility, not actual integration or hardware."""
from itertools import permutations, product
import json
import platform
import re
def _labels(values):
if type(values) is not tuple:
raise TypeError('declared labels must be an exact tuple')
if len(values) > 6:
raise ValueError('at most six labels per side in this teaching profile')
if any(type(x) is not str or re.fullmatch(r'[A-Z][A-Z0-9_]{0,7}', x) is None
for x in values):
raise ValueError('labels must follow the bounded ASCII profile')
if len(set(values)) != len(values):
raise ValueError('duplicate declared label')
def _validate(left, right, edges):
_labels(left)
_labels(right)
if set(left) & set(right):
raise ValueError('this interface uses disjoint label namespaces')
if type(edges) is not tuple:
raise TypeError('edges must be an exact finite tuple')
if len(edges) > 36:
raise ValueError('at most36 input edges')
seen = set()
for edge in edges:
if type(edge) is not tuple or len(edge) != 2:
raise TypeError('each edge must be an exact pair tuple')
u, v = edge
if type(u) is not str or type(v) is not str:
raise TypeError('edge endpoints must be exact strings')
if u not in left or v not in right:
raise ValueError('edge must go from declared left to declared right')
if edge in seen:
raise ValueError('duplicate compatibility edge')
seen.add(edge)
def maximum_assignment(left, right, edges):
"""Return a maximum unweighted cardinality; supplied compatibility only."""
_validate(left, right, edges)
adjacent = tuple(tuple(j for j, v in enumerate(right) if (u, v) in edges)
for u in left)
owner = [None] * len(right)
def augment(u, seen_right):
for v in adjacent[u]:
if v in seen_right:
continue
seen_right.add(v)
previous = owner[v]
if previous is None or augment(previous, seen_right):
owner[v] = u
return True
return False
for u in range(len(left)):
augment(u, set())
by_left = {u: v for v, u in enumerate(owner) if u is not None}
pairs = tuple((left[u], right[by_left[u]]) for u in range(len(left)) if u in by_left)
return {'pairs': pairs, 'cardinality': len(pairs),
'unmatched_left': tuple(left[u] for u in range(len(left)) if u not in by_left),
'unmatched_right': tuple(right[v] for v, u in enumerate(owner) if u is None),
'covers_all_left': len(pairs) == len(left)}
def greedy_diagnostic(left, right, edges):
# Internal comparison for authored, validated fixtures; never reassigns.
pairs = []
used = set()
for u in left:
for v in right:
if (u, v) in edges and v not in used:
pairs.append((u, v))
used.add(v)
break
return tuple(pairs)
def feasible_pairs(left, right, edges, pairs):
"""Independent pair feasibility check; it does NOT establish optimality."""
if type(pairs) is not tuple:
return False
if any(type(p) is not tuple or len(p) != 2 for p in pairs):
return False
if any(type(u) is not str or type(v) is not str or u not in left or v not in right
or (u, v) not in edges for u, v in pairs):
return False
return len({u for u, v in pairs}) == len({v for u, v in pairs}) == len(pairs)
def exhaustive_cardinality(left, right, edges):
"""Independent partial injections: no search path, owner map or reassignment.
This internal oracle uses only finite authored fixtures. -1 leaves a task
unmatched; all other coordinates select a fixture by its declared index.
"""
optimum = 0
for choices in product(range(-1, len(right)), repeat=len(left)):
selected = [v for v in choices if v != -1]
if len(set(selected)) != len(selected):
continue
if all(v == -1 or (left[u], right[v]) in edges for u, v in enumerate(choices)):
optimum = max(optimum, len(selected))
return optimum
def rejects(left, right, edges):
try:
maximum_assignment(left, right, edges)
except (TypeError, ValueError):
return True
return False
def run_example():
left, right = ('T0', 'T1'), ('F0', 'F1')
edges = (('T0', 'F0'), ('T0', 'F1'), ('T1', 'F0'))
result = maximum_assignment(left, right, edges)
greedy = greedy_diagnostic(left, right, edges)
free_l = set(left) - {u for u, v in greedy}
free_r = set(right) - {v for u, v in greedy}
chain_l, chain_r = tuple('T' + str(i) for i in range(4)), tuple('F' + str(i) for i in range(4))
chain_e = (('T0', 'F0'), ('T0', 'F1'), ('T1', 'F1'), ('T1', 'F2'),
('T2', 'F2'), ('T2', 'F3'), ('T3', 'F0'))
chain = maximum_assignment(chain_l, chain_r, chain_e)
unequal = maximum_assignment(('T0',), ('F0', 'F1'), (('T0', 'F0'),))
shortage_l, shortage_r = ('T0', 'T1', 'T2'), ('F0', 'F1')
shortage_e = tuple(product(shortage_l, shortage_r))
shortage = maximum_assignment(shortage_l, shortage_r, shortage_e)
isolated = maximum_assignment(('T0', 'T1', 'T2'), ('F0', 'F1', 'F2'),
(('T0', 'F0'), ('T2', 'F1')))
empty = maximum_assignment((), (), ())
right_only = maximum_assignment((), ('F0',), ())
left_only = maximum_assignment(('T0',), (), ())
no_edges = maximum_assignment(left, right, ())
oracle_ok, oracle_cases = True, 0
for nl in range(4):
for nr in range(4):
ls = tuple('T' + str(i) for i in range(nl))
rs = tuple('F' + str(i) for i in range(nr))
candidates = tuple(product(ls, rs))
for mask in product((False, True), repeat=len(candidates)):
es = tuple(e for e, selected in zip(candidates, mask) if selected)
actual = maximum_assignment(ls, rs, es)
oracle_ok &= actual['cardinality'] == exhaustive_cardinality(ls, rs, es)
oracle_ok &= feasible_pairs(ls, rs, es, actual['pairs'])
oracle_ok &= set(actual['unmatched_left']) == set(ls) - {u for u, v in actual['pairs']}
oracle_ok &= set(actual['unmatched_right']) == set(rs) - {v for u, v in actual['pairs']}
oracle_cases += 1
triple_l, triple_r = ('T0', 'T1', 'T2'), ('F0', 'F1', 'F2')
triple_e = (('T0', 'F0'), ('T0', 'F1'), ('T1', 'F0'), ('T2', 'F1'), ('T2', 'F2'))
rename_ok, rename_cases = True, 0
for lo in permutations(triple_l):
for ro in permutations(triple_r):
# Rename both namespaces and independently reorder declared vertices.
mapping = {x: 'L' + str(i) for i, x in enumerate(lo)}
mapping.update({x: 'R' + str(i) for i, x in enumerate(ro)})
ls = tuple(mapping[x] for x in reversed(lo))
rs = tuple(mapping[x] for x in reversed(ro))
es = tuple((mapping[u], mapping[v]) for u, v in triple_e)
actual = maximum_assignment(ls, rs, es)
rename_ok &= actual['cardinality'] == exhaustive_cardinality(ls, rs, es) == 3
rename_ok &= feasible_pairs(ls, rs, es, actual['pairs'])
rename_cases += 1
monotone_ok, edge_addition_cases = True, 0
possible = tuple(product(triple_l, triple_r))
for mask in product((False, True), repeat=len(possible)):
chosen = tuple(e for e, selected in zip(possible, mask) if selected)
old_count = maximum_assignment(triple_l, triple_r, chosen)['cardinality']
for e in possible:
if e not in chosen:
new_count = maximum_assignment(triple_l, triple_r, chosen + (e,))['cardinality']
monotone_ok &= old_count <= new_count <= old_count + 1
edge_addition_cases += 1
malformed = [
(list(left), right, edges), (left, list(right), edges), (left, right, list(edges)),
(('T0', 'T0'), right, ()), (('T0',), ('T0',), ()),
(('\u062d\u0633\u06af\u0631',), right, ()), ((True,), right, ()), (('a',), right, ()),
(('T' * 9,), right, ()), (tuple('T' + str(i) for i in range(7)), right, ()),
(left, right, (('T0', 'F9'),)), (left, right, (('F0', 'T0'),)),
(left, right, (('T0', True),)), (left, right, (('T0', float('nan')),)),
(left, right, (('T0',),)), (left, right, (['T0', 'F0'],)),
(left, right, (('T0', 'F0'),) * 2), (left, right, (('T0', 'F0'),) * 37),
]
six_l, six_r = tuple('T' + str(i) for i in range(6)), tuple('F' + str(i) for i in range(6))
six_e = tuple(product(six_l, six_r))
six = maximum_assignment(six_l, six_r, six_e)
snapshot = (left, right, edges)
again = maximum_assignment(left, right, tuple(reversed(edges)))
checks = {
'greedy_trap_reassignment_recovers_two_compatible_fixtures':
result['pairs'] == (('T0', 'F1'), ('T1', 'F0')) and result['cardinality'] == 2,
'feasible_maximal_greedy_is_not_maximum':
feasible_pairs(left, right, edges, greedy) and len(greedy) == 1
and not any(u in free_l and v in free_r for u, v in edges)
and len(greedy) < result['cardinality'],
'long_augmenting_chain_reroutes_three_existing_owners':
chain['pairs'] == (('T0', 'F1'), ('T1', 'F2'), ('T2', 'F3'), ('T3', 'F0'))
and len(greedy_diagnostic(chain_l, chain_r, chain_e)) == 3,
'all_left_covered_does_not_mean_all_vertices_perfect':
unequal['covers_all_left'] is True and unequal['cardinality'] == 1
and unequal['unmatched_right'] == ('F1',),
'fixture_shortage_returns_real_unmatched_tasks_not_input_error':
shortage['cardinality'] == 2 and shortage['unmatched_left'] == ('T2',)
and shortage['covers_all_left'] is False,
'isolated_task_and_unused_fixture_are_both_explicit':
isolated['unmatched_left'] == ('T1',) and isolated['unmatched_right'] == ('F2',),
'empty_partitions_and_absent_edges_are_valid_zero_cardinality':
empty['pairs'] == () and empty['covers_all_left'] is True
and right_only['unmatched_right'] == ('F0',) and right_only['covers_all_left'] is True
and left_only['unmatched_left'] == ('T0',) and left_only['covers_all_left'] is False
and no_edges['cardinality'] == 0,
'edge_input_order_and_repeated_call_preserve_same_contract':
again == result and snapshot == (left, right, edges),
'renaming_and_declared_order_preserve_optimal_cardinality':
bool(rename_ok and rename_cases == 36),
'one_added_edge_never_reduces_or_adds_more_than_one_match':
bool(monotone_ok and edge_addition_cases == 2304),
'all_689_small_graphs_match_exhaustive_partial_injection_oracle':
bool(oracle_ok and oracle_cases == 689),
'independent_feasibility_check_rejects_reused_or_missing_pairs':
all(not feasible_pairs(left, right, edges, p) for p in [
(('T0', 'F0'), ('T1', 'F0')), (('T0', 'F0'), ('T0', 'F1')),
(('T1', 'F1'),), (('T9', 'F0'),), (('T0', True),), [('T0', 'F0')]]),
'shape_names_unknown_edges_duplicates_and_caps_are_rejected':
all(rejects(*args) for args in malformed),
'six_by_six_boundary_matches_independent_oracle_and_fresh_state':
six['cardinality'] == exhaustive_cardinality(six_l, six_r, six_e) == 6
and six['covers_all_left'] is True and feasible_pairs(six_l, six_r, six_e, six['pairs'])
and maximum_assignment(left, right, edges) == result,
}
assert len(checks) == 14 and all(type(v) is bool and v for v in checks.values()), checks
return {'python': platform.python_version(), 'dependencies': 'standard library only',
'unit_contract': 'dimensionless labels and counts; no measured duration or physical compatibility',
'left_tasks': left, 'right_fixtures': right, 'supplied_compatibility': edges,
'greedy_pairs': greedy, 'greedy_cardinality': len(greedy), 'maximum_assignment': result,
'long_chain_assignment': chain, 'unequal_sides_example': unequal,
'shortage_example': shortage, 'all_small_graphs_in_one_group': oracle_cases,
'renaming_cases_in_one_group': rename_cases, 'one_edge_addition_cases_in_one_group': edge_addition_cases,
'meaningful_named_groups': 14, 'checks': checks,
'scope': 'Unweighted maximum cardinality on a supplied finite bipartite compatibility graph; '
'not minimum cost, fairness, stable marriage, unique or lexicographically least matching, '
'fixture discovery, actual service integration, hardware, security or performance validation.'}
if __name__ == '__main__':
print(json.dumps(run_example(), ensure_ascii=True, indent=2, allow_nan=False))
{
"python": "3.14.5",
"dependencies": "standard library only",
"unit_contract": "dimensionless labels and counts; no measured duration or physical compatibility",
"left_tasks": [
"T0",
"T1"
],
"right_fixtures": [
"F0",
"F1"
],
"supplied_compatibility": [
[
"T0",
"F0"
],
[
"T0",
"F1"
],
[
"T1",
"F0"
]
],
"greedy_pairs": [
[
"T0",
"F0"
]
],
"greedy_cardinality": 1,
"maximum_assignment": {
"pairs": [
[
"T0",
"F1"
],
[
"T1",
"F0"
]
],
"cardinality": 2,
"unmatched_left": [],
"unmatched_right": [],
"covers_all_left": true
},
"long_chain_assignment": {
"pairs": [
[
"T0",
"F1"
],
[
"T1",
"F2"
],
[
"T2",
"F3"
],
[
"T3",
"F0"
]
],
"cardinality": 4,
"unmatched_left": [],
"unmatched_right": [],
"covers_all_left": true
},
"unequal_sides_example": {
"pairs": [
[
"T0",
"F0"
]
],
"cardinality": 1,
"unmatched_left": [],
"unmatched_right": [
"F1"
],
"covers_all_left": true
},
"shortage_example": {
"pairs": [
[
"T0",
"F1"
],
[
"T1",
"F0"
]
],
"cardinality": 2,
"unmatched_left": [
"T2"
],
"unmatched_right": [],
"covers_all_left": false
},
"all_small_graphs_in_one_group": 689,
"renaming_cases_in_one_group": 36,
"one_edge_addition_cases_in_one_group": 2304,
"meaningful_named_groups": 14,
"checks": {
"greedy_trap_reassignment_recovers_two_compatible_fixtures": true,
"feasible_maximal_greedy_is_not_maximum": true,
"long_augmenting_chain_reroutes_three_existing_owners": true,
"all_left_covered_does_not_mean_all_vertices_perfect": true,
"fixture_shortage_returns_real_unmatched_tasks_not_input_error": true,
"isolated_task_and_unused_fixture_are_both_explicit": true,
"empty_partitions_and_absent_edges_are_valid_zero_cardinality": true,
"edge_input_order_and_repeated_call_preserve_same_contract": true,
"renaming_and_declared_order_preserve_optimal_cardinality": true,
"one_added_edge_never_reduces_or_adds_more_than_one_match": true,
"all_689_small_graphs_match_exhaustive_partial_injection_oracle": true,
"independent_feasibility_check_rejects_reused_or_missing_pairs": true,
"shape_names_unknown_edges_duplicates_and_caps_are_rejected": true,
"six_by_six_boundary_matches_independent_oracle_and_fresh_state": true
},
"scope": "Unweighted maximum cardinality on a supplied finite bipartite compatibility graph; not minimum cost, fairness, stable marriage, unique or lexicographically least matching, fixture discovery, actual service integration, hardware, security or performance validation."
}۴. مرجعِ مستقلِ همهٔ تخصیص‌ها
مرجع برای هر سناریو یا «بی‌جفت» یا یکی از منابع را انتخاب می‌کند. سپس انتخاب‌هایی با منبعِ تکراری یا یالِ ناموجود کنار می‌روند و بزرگ‌ترین تعدادِ باقی‌مانده گرفته می‌شود. این شمارش، owner، جست‌وجوی مسیر یا جابه‌جاییِ تابعِ اصلی را فراخوانی نمی‌کند. رشدِ ترکیبیِ آن، علتِ محدود نگه‌داشتنِ اندازه است.
تمامِ ۶۸۹ گرافِ ساده با صفر تا سه رأس در هر طرف با این مرجع سنجیده شدند؛ این خانواده یک گروه است. بررسی‌کنندهٔ جدا نیز فقط معتبر بودنِ جفت‌ها را کنترل می‌کند. جوابِ حریصانه از همین کنترل می‌گذرد، با آنکه بهینه نیست؛ بنابراین «هیچ منبعی دوباره استفاده نشد» را به معنای «بیشترین تعداد پیدا شد» نمی‌گیریم.
چهارده گروهِ نام‌دار موفق بودند. تغییرِ نام و ترتیبِ طرف‌ها در ۳۶ حالت، تعدادِ بهینه را نگه داشت؛ افزودنِ یک یال در ۲۳۰۴ مقایسه، تعداد را کاهش نداد و بیش از یک افزایش نساخت. این دو خانواده نیز هرکدام فقط یک گروه‌اند. شاهدِ شش‌درشش، مرزِ مجازِ رابط را با مرجعِ مستقل می‌سنجد.
درسِ انتخابِ مسیرِ کم‌هزینه هدفِ دیگری داشت: جمعِ وزنِ یال‌های یک مسیر. اینجا ممکن است جفت‌های متفاوت، تعدادِ یکسان داشته باشند و هیچ وزنِ هزینه‌ای تعریف نشده باشد. منابع در ۲۷ مهر ۱۴۰۵ خوانده شدند؛ یادداشتِ MIT تاریخِ ۹ فوریهٔ ۲۰۰۹ دارد و صفحهٔ API تاریخِ انتشارِ دقیقی نشان نمی‌دهد. این آموزش، خبرِ تازه نیست.
۵. چهار پرسش دربارهٔ بیشینه و مرزِ مدل
پرسش اول: پوششِ تمامِ چپ، تطبیقِ کامل است؟ پاسخ: همیشه نه. با یک سناریو و دو منبع، یک جفت تمامِ چپ را می‌پوشاند، ولی یک منبع بی‌جفت می‌ماند. تطبیقِ کامل، تمامِ رأس‌های هر دو طرف را می‌پوشاند؛ پس پرچمِ covers_all_left را به آن معنا تفسیر نمی‌کنیم.
پرسش دوم: سه سناریو با دو منبعِ کاملاً سازگار چه می‌شوند؟ پاسخ: بیشینه دو جفت است و یک سناریو می‌ماند. داده نامعتبر نیست. در اجرای ثبت‌شده T2 بی‌جفت است، اما این نتیجه اولویتِ مهندسیِ T0 و T1 را ثابت نمی‌کند؛ عدالت و اولویت در هدف وارد نشده‌اند.
پرسش سوم: چرا افزودنِ یک یال بیش از یک جفت اضافه نمی‌کند؟ پاسخ: جوابِ قبلی هنوز مجاز است، پس تعداد کم نمی‌شود. از جوابِ تازه، اگر یالِ افزوده را برداریم، حداکثر یک جفت حذف می‌شود و جوابی مجاز برای گرافِ قبلی داریم. بنابراین افزایش بیش از یک ممکن نیست.
پرسش چهارم: خروجیِ قطعی یعنی بهترین انتخابِ یکتا؟ پاسخ: خیر. در دو طرفِ دوعضوی با همهٔ یال‌ها، دو جوابِ دوجفتی داریم. رابط یک مورد را طبقِ پیمایش برمی‌گرداند؛ کمینهٔ هزینه، پایداریِ ترجیح‌ها یا یکتایی را اثبات نمی‌کند. چهارده گروه نیز فقط همین مدلِ محدود را پوشش می‌دهند و تصویرهای همراه مفهومی‌اند.
منابع و مطالعهٔ بیشتر
- Michel X.Goemans؛ یادداشت MIT، بخش۱٫۱ و قضیهٔ مسیرِ افزایشی
- Sedgewick و Wayne؛ تعریفِ تطبیقِ بیشینه و کامل در API پرینستون
بررسی منابع: ۲۷ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.
