دو‌رنگ‌کردنِ گراف با پایتون؛ شاهدِ چرخهٔ فرد برای بازبینی الگوریتم

در نگهداریِ یک الگوریتم، پاسخِ «نمی‌شود» زمانی قابلِ بازبینی‌تر است که علتِ کوچک و مشخصی همراهش باشد. این درس برای چند قیدِ ساختگیِ جداسازی، یا دو گروهِ سازگار می‌سازد یا یک چرخهٔ فرد نشان می‌دهد. داده و شناسه‌ها تألیفی‌اند؛ هیچ دستگاه، شبکه یا زمان‌بندیِ واقعی آزمایش نمی‌شود.

۱. هر قیدِ همسایگی، دو سوی متفاوت می‌خواهد

هفت کانالِ فرضی را با عددهای صفر تا شش نام‌گذاری می‌کنیم. هر یال می‌گوید دو کانال باید در دو بانکِ متفاوتِ آزمون قرار بگیرند. عددِ رأس، شناسه است؛ ولتاژ، شمارهٔ پایه یا اولویت نیست. وجودِ این قید نیز فرضِ ورودی است و از اندازه‌گیریِ تداخل به دست نیامده است.

یال‌ها میانِ صفر و یک، یک و دو، دو و سه، سه و صفر، و چهار و پنج‌اند. رأسِ شش هیچ همسایه‌ای ندارد. پس یک چرخهٔ چهاری، یک زوجِ جدا و یک رأسِ تنها داریم. برنامه باید تمامِ این بخش‌ها را ببیند؛ شروعِ جست‌وجو از صفر و رهاکردنِ بقیه، پاسخِ کاملِ گراف نیست.

یادداشتِ آموزشیِ James Aspnes در Yale، دوبخشی‌بودن را با رنگ‌آمیزیِ دوگانه و نبودِ چرخهٔ فرد مرتبط می‌کند. منظور از رنگ، فقط یکی از دو مقدارِ قراردادی است. هر یال باید دو مقدارِ متفاوت را ببیند؛ زیباییِ رسم، فاصلهٔ مکانی و تعدادِ اعضای هر طرف در تعریف دخالتی ندارند.

در بازبینیِ Dijkstra، جهت و مجموعِ هزینه اهمیت داشت. مسئلهٔ حاضر گرافِ بدونِ جهت و بدونِ وزن است. جواب، مسیرِ کم‌هزینه نیست و صفر و یکِ خروجی نیز وزن نیستند. حتی اگر دو درس هر دو از ساختارِ گراف استفاده کنند، قرارداد و مرجعِ درستشان متفاوت است.

۲. جست‌وجوی لایه‌ای و چرخهٔ بستهٔ ناسازگار

برای هر رأسِ هنوز ندیده، جست‌وجوی لایه‌ایِ تازه‌ای شروع می‌کنیم. رنگِ ریشه را صفر می‌گذاریم و به هر همسایهٔ تازه رنگِ مخالف می‌دهیم. صف، ترتیبِ بررسی را نگه می‌دارد و آرایهٔ والد، مسیرِ درختِ جست‌وجو را ثبت می‌کند. یالِ میانِ دو رأسِ هم‌رنگ، شاهدِ تعارض خواهد بود.

در چنین تعارضی، مسیرِ والدهای دو سرِ یال را تا نخستین جدِ مشترک پیدا می‌کنیم. مسیرِ درختیِ میانِ دو سر، طولِ زوج دارد، چون رنگشان یکسان است. افزودنِ خودِ یال، مسیر را با تعدادِ فردِ یال می‌بندد. در خودحلقه، همان رفتن از یک رأس به خودش، شاهدِ یک‌یالیِ مستقیم است.

دلیلِ شکست فقط یک پرچم نیست: دنباله‌ای بسته می‌دهیم که رأسِ نخست در انتها تکرار می‌شود. برای مثلثِ نمونه، شاهد (1,0,2,1) سه یال دارد. در بازبینی باید وجودِ هر یال، فردبودنِ تعداد و نبودِ تکرارِ رأس‌های داخلی کنترل شود؛ چهار عضوِ دنباله به معنای چهار یال نیست.

اگر تعارضی پیدا نشود، تمامِ یال‌های دیده‌شده دو رنگِ متفاوت دارند و هر رأس نیز در یکی از جست‌وجوها دیده شده است. این، گواهِ مستقیمِ تقسیمِ معتبر است. ادعا نمی‌کنیم چرخهٔ برگشتی کوتاه‌ترین یا یکتا است. تغییرِ ترتیبِ یال‌ها می‌تواند شاهدِ دیگری بسازد که به همان اندازه معتبر باشد.

۳. کد کاملِ رنگ‌بندی و ساختنِ شاهد

سازندهٔ Graph.build تعدادِ رأس را int واقعیِ صفر تا ۶۴ می‌خواهد. یال‌ها list یا tuple متناهی با حداکثر ۴۰۹۶ ورودی‌اند؛ هر یال باید tuple دو عضوی از int واقعی باشد. bool، عددِ اعشاری، شناسهٔ خارج از بازه و زوجِ ناقص رد می‌شوند. این کران‌ها سیاستِ آموزشیِ فایل‌اند.

دو جهتِ نوشتنِ یک یال، همان قید را بیان می‌کنند. تکرار و جهتِ معکوس فرو می‌ریزند، ولی ترتیبِ نخستین حضور برای همسایه‌ها حفظ می‌شود. خودحلقه پذیرفته می‌شود تا الگوریتم ناسازگاریِ آن را گزارش کند. ورودیِ تهی با صفر رأس نیز گرافِ معتبر و دوبخشیِ تهی است؛ خطای دریافتِ داده نامیده نمی‌شود.

مستنداتِ deque پایتون، افزودن و برداشتن از دو سر را شرح می‌دهد. اینجا append و popleft یک صفِ معمول می‌سازند. در حلقهٔ جست‌وجو، هر رأس یک بار واردِ صف می‌شود و همسایگی‌ها مرور می‌شوند؛ این توصیفِ ساختاری، اندازه‌گیریِ زمان یا حافظهٔ اجرا نیست.

فایلِ کامل با Python 3.14.5 و فقط کتابخانهٔ استاندارد اجرا شده است. شیءهای گرافِ معتبر باید از سازنده بیایند؛ ساختنِ دستیِ dataclass ناسازگار پشتیبانی نمی‌شود. نتیجه یا tuple رنگِ تمامِ رأس‌هاست یا شاهدِ چرخه. آرایهٔ رنگِ نیمه‌کاره را هنگامِ شکست به عنوانِ تقسیمِ معتبر تحویل نمی‌دهیم.

"""Own finite undirected two-color constraints; no physical scheduling claim."""
from collections import deque
from dataclasses import dataclass
from itertools import combinations_with_replacement, permutations, product
import json
import platform

MAX_VERTICES=64
MAX_INPUT_EDGES=4096


@dataclass(frozen=True)
class Graph:
    n: int
    edges: tuple[tuple[int,int],...]
    neighbors: tuple[tuple[int,...],...]

    @classmethod
    def build(cls,n,edges):
        if type(n)is not int or type(edges)not in (list,tuple):
            raise TypeError('actual int vertex count and finite list/tuple required')
        if not 0<=n<=MAX_VERTICES or len(edges)>MAX_INPUT_EDGES:
            raise ValueError('outside own teaching resource profile')
        adjacent=[[]for _ in range(n)];seen=set();unique=[]
        for edge in edges:
            if type(edge)is not tuple or len(edge)!=2 or any(type(v)is not int for v in edge):
                raise TypeError('edge must be an actual pair tuple of actual ints')
            u,v=edge
            if not (0<=u<n and 0<=v<n):raise ValueError('unknown vertex')
            key=(min(u,v),max(u,v))
            if key in seen:continue
            seen.add(key);unique.append(key);adjacent[u].append(v)
            if u!=v:adjacent[v].append(u)
        return cls(n,tuple(unique),tuple(tuple(row)for row in adjacent))


@dataclass(frozen=True)
class Result:
    colors: tuple[int,...]|None
    odd_cycle: tuple[int,...]


def color_or_witness(graph):
    # Supported inputs are factory-built Graph objects, not manually corrupted
    # dataclass instances. Parent pointers belong to the current BFS forest.
    colors=[-1]*graph.n;parent=[-1]*graph.n
    for root in range(graph.n):
        if colors[root]!=-1:continue
        colors[root]=0;queue=deque([root])
        while queue:
            u=queue.popleft()
            for v in graph.neighbors[u]:
                if colors[v]==-1:
                    colors[v]=1-colors[u];parent[v]=u;queue.append(v)
                elif colors[v]==colors[u]:
                    if u==v:return Result(None,(u,u))
                    ancestors=[];positions={};x=u
                    while x!=-1:
                        positions[x]=len(ancestors);ancestors.append(x);x=parent[x]
                    other=[];x=v
                    while x not in positions:
                        other.append(x);x=parent[x]
                    cycle=ancestors[:positions[x]+1]+list(reversed(other))+[u]
                    return Result(None,tuple(cycle))
    return Result(tuple(colors),())


def valid_certificate(graph,result):
    """Check just the returned certificate, with no traversal/parent logic."""
    if result.colors is not None:
        c=result.colors
        return (type(c)is tuple and len(c)==graph.n and result.odd_cycle==()
                and all(type(v)is int and v in (0,1)for v in c)
                and all(c[u]!=c[v]for u,v in graph.edges))
    cycle=result.odd_cycle
    if type(cycle)is not tuple or len(cycle)<2 or cycle[0]!=cycle[-1]or (len(cycle)-1)%2!=1:return False
    if not all(type(v)is int and 0<=v<graph.n for v in cycle):return False
    if len(set(cycle[:-1]))!=len(cycle)-1:return False
    edges=set(graph.edges)
    return all((min(u,v),max(u,v))in edges for u,v in zip(cycle,cycle[1:]))


def brute_exists(n,edges):
    """Independent exhaustive assignments; no graph builder, BFS or witness."""
    return any(all(bits[u]!=bits[v]for u,v in edges)for bits in product((0,1),repeat=n))


def rejects(*args):
    try:Graph.build(*args)
    except (ValueError,TypeError):return True
    return False


def run_example():
    edges=((0,1),(1,2),(2,3),(3,0),(4,5))
    graph=Graph.build(7,edges);good=color_or_witness(graph)
    changed=Graph.build(7,edges+((0,2),));bad=color_or_witness(changed)
    five=Graph.build(5,((0,1),(1,2),(2,3),(3,4),(4,0)))
    five_result=color_or_witness(five)
    checks={}
    checks['hand_seven_channel_partition']=(good==Result((0,1,0,1,0,1,0),())and valid_certificate(graph,good))
    checks['added_diagonal_returns_closed_odd_witness']=(bad==Result(None,(1,0,2,1))and valid_certificate(changed,bad))
    checks['five_cycle_witness_is_not_assumed_triangle']=(len(five_result.odd_cycle)-1==5 and valid_certificate(five,five_result))
    separate=Graph.build(7,((0,1),(3,4),(4,5),(5,3)))
    checks['disconnected_later_conflict_not_skipped']=(color_or_witness(separate).colors is None and valid_certificate(separate,color_or_witness(separate)))
    self_loop=Graph.build(3,((2,2),))
    checks['self_loop_one_edge_witness']=(color_or_witness(self_loop)==Result(None,(2,2))and valid_certificate(self_loop,color_or_witness(self_loop)))
    checks['empty_and_isolated_vertices']=(color_or_witness(Graph.build(0,()))==Result((),())and color_or_witness(Graph.build(4,()))==Result((0,0,0,0),()))
    duplicate=Graph.build(2,((0,1),(1,0),(0,1)))
    checks['undirected_duplicates_collapsed']=(duplicate.edges==((0,1),)and duplicate.neighbors==((1,),(0,))and valid_certificate(duplicate,color_or_witness(duplicate)))
    checks['input_types_bounds_and_unknown_vertices']=all([
        rejects(True,()),rejects(2.0,()),rejects(-1,()),rejects(65,()),rejects(2,iter(())),
        rejects(2,([0,1],)),rejects(2,((False,1),)),rejects(2,((0,'1'),)),rejects(2,((0,),)),
        rejects(2,((0,2),)),rejects(2,((-1,0),)),rejects(0,((0,0),))])
    flipped=list(good.colors);flipped[4]=1-flipped[4];flipped[5]=1-flipped[5]
    checks['component_colors_are_not_unique']=(valid_certificate(graph,Result(tuple(flipped),()))and tuple(flipped)!=good.colors)
    reorder_ok=all(valid_certificate(Graph.build(4,order),color_or_witness(Graph.build(4,order)))for order in permutations(edges[:4]))
    checks['input_edge_order_may_change_certificate_not_property']=reorder_ok
    oracle_cases=0;oracle_ok=True
    for n in range(5):
        candidates=list(combinations_with_replacement(range(n),2))
        for flags in product((0,1),repeat=len(candidates)):
            chosen=tuple(edge for edge,flag in zip(candidates,flags)if flag)
            candidate=Graph.build(n,chosen);result=color_or_witness(candidate)
            oracle_ok=oracle_ok and ((result.colors is not None)==brute_exists(n,chosen))and valid_certificate(candidate,result)
            oracle_cases+=1
    checks['all_1099_small_graph_assignments_oracle_ONE_group']=bool(oracle_ok and oracle_cases==1099)
    relabel_cases=0;relabel_ok=True
    for mapping in permutations(range(5)):
        remapped=Graph.build(5,tuple((mapping[u],mapping[v])for u,v in five.edges))
        result=color_or_witness(remapped)
        relabel_ok=relabel_ok and result.colors is None and valid_certificate(remapped,result);relabel_cases+=1
    checks['vertex_renaming_preserves_failure_and_witness_validity']=bool(relabel_ok and relabel_cases==120)
    checks['independent_certificate_checker_rejects_bad_outputs']=all([
        not valid_certificate(graph,Result((0,)*7,())),not valid_certificate(graph,Result((0,1),())),
        not valid_certificate(changed,Result(None,(0,1,0))),not valid_certificate(changed,Result(None,(0,1,6,0))),
        not valid_certificate(changed,Result(None,(0,1,2))),not valid_certificate(changed,Result(None,(0,1,0,1,0)))])
    bounded=Graph.build(64,((0,1),)*4096)
    checks['inclusive_resource_profile_boundary']=(bounded.n==64 and len(bounded.edges)==1 and valid_certificate(bounded,color_or_witness(bounded))and rejects(64,((0,1),)*4097))
    assert all(type(value)is bool and value for value in checks.values()),checks
    return dict(python=platform.python_version(),dependencies='standard library only',
        scope='synthetic finite undirected different-bank constraints; no hardware or optimal scheduling',
        vertex_count=7,unique_edge_count=len(graph.edges),colors=good.colors,
        side_zero=[v for v,c in enumerate(good.colors)if c==0],side_one=[v for v,c in enumerate(good.colors)if c==1],
        added_edge=[0,2],odd_cycle=bad.odd_cycle,odd_cycle_edge_count=len(bad.odd_cycle)-1,
        five_cycle_witness=five_result.odd_cycle,oracle_graph_cases_inside_ONE_group=oracle_cases,
        relabel_cases_inside_ONE_group=relabel_cases,shortest_or_unique_witness_claimed=False,checks=checks)

if __name__=='__main__':print(json.dumps(run_example(),ensure_ascii=False,indent=2))

۴. درستیِ گواه را مستقل از ترتیب بسنجیم

نمونهٔ اصلی رنگ‌های صفر، یک، صفر، یک، صفر، یک، صفر می‌دهد. طرفِ صفر شاملِ صفر، دو، چهار و شش و طرفِ یک شاملِ یک، سه و پنج است. افزودنِ یالِ صفر به دو، مثلث می‌سازد و تقسیم را ناممکن می‌کند. یک چرخهٔ پنج‌تاییِ جدا نیز شاهدِ پنج‌یالی می‌دهد.

{
  "python": "3.14.5",
  "dependencies": "standard library only",
  "scope": "synthetic finite undirected different-bank constraints; no hardware or optimal scheduling",
  "vertex_count": 7,
  "unique_edge_count": 5,
  "colors": [
    0,
    1,
    0,
    1,
    0,
    1,
    0
  ],
  "side_zero": [
    0,
    2,
    4,
    6
  ],
  "side_one": [
    1,
    3,
    5
  ],
  "added_edge": [
    0,
    2
  ],
  "odd_cycle": [
    1,
    0,
    2,
    1
  ],
  "odd_cycle_edge_count": 3,
  "five_cycle_witness": [
    2,
    1,
    0,
    4,
    3,
    2
  ],
  "oracle_graph_cases_inside_ONE_group": 1099,
  "relabel_cases_inside_ONE_group": 120,
  "shortest_or_unique_witness_claimed": false,
  "checks": {
    "hand_seven_channel_partition": true,
    "added_diagonal_returns_closed_odd_witness": true,
    "five_cycle_witness_is_not_assumed_triangle": true,
    "disconnected_later_conflict_not_skipped": true,
    "self_loop_one_edge_witness": true,
    "empty_and_isolated_vertices": true,
    "undirected_duplicates_collapsed": true,
    "input_types_bounds_and_unknown_vertices": true,
    "component_colors_are_not_unique": true,
    "input_edge_order_may_change_certificate_not_property": true,
    "all_1099_small_graph_assignments_oracle_ONE_group": true,
    "vertex_renaming_preserves_failure_and_witness_validity": true,
    "independent_certificate_checker_rejects_bad_outputs": true,
    "inclusive_resource_profile_boundary": true
  }
}

بررسی‌کنندهٔ گواه، صف و والدهای الگوریتم را نمی‌خواند؛ فقط رنگ‌ها را با یال‌ها یا چرخه را با مجموعهٔ یال‌ها می‌سنجد. مرجعِ دیگری تمامِ انتساب‌های ممکنِ صفر و یک را برای گراف‌های کوچک امتحان می‌کند. بنابراین پاسخِ انتظار از اجرای دوبارهٔ همان جست‌وجو ساخته نمی‌شود.

تمامِ ۱۰۹۹ گراف با صفر تا چهار رأس، با امکانِ خودحلقه، بررسی شده‌اند. این مجموعه یک گروهِ آزمون است. همچنین ۱۲۰ نام‌گذاریِ متفاوتِ چرخهٔ پنج‌تایی در یک گروهِ دیگر سنجیده شده‌اند. مجموعِ فایل چهارده گروهِ نام‌دارِ موفق دارد؛ شمارِ گراف‌ها یا اجرای دوباره را به آن اضافه نمی‌کنیم.

مستنداتِ رسمیِ NetworkX ابهامِ رنگ‌بندیِ گرافِ جدا را توضیح می‌دهد. NetworkX در این آزمایش اجرا نشده است. می‌توان رنگ‌های یک مؤلفه را برعکس کرد و همچنان جوابِ درست داشت؛ پس مرجع نباید یک tuple خاص را تنها پاسخِ مجازِ تمامِ ورودی‌ها بداند.

تقسیمِ گروهیِ دستگاه‌ها نیز جدایی را کنترل می‌کرد، اما بارِ بخش‌ها و کامل‌ماندنِ گروه مسئلهٔ دیگری بود. اینجا توازنِ اندازه، ظرفیتِ بانک یا ترتیبِ زمانی نداریم. دوبخشی‌بودن به‌تنهایی مجوزِ اجرای یک برنامهٔ واقعیِ آزمون یا تضمینِ حذفِ تداخل نیست.

۵. چهار پرسش دربارهٔ مؤلفه و مرزِ مدل

پرسش اول: چرا رأسِ تنها به طرفِ صفر رفت؟ پاسخ: ریشهٔ هر مؤلفه را قراردادی صفر می‌گذاریم. رأسِ شش یالی ندارد و می‌توانست در طرفِ یک هم باشد. این انتخاب، برتری یا اولویتِ فیزیکیِ بانکِ صفر را ثابت نمی‌کند.

پرسش دوم: چرا یالِ صفر به دو پاسخ را خراب می‌کند؟ پاسخ: صفر، یک و دو یک چرخهٔ سه‌یالی می‌سازند. رنگِ مخالف‌دادن در دو گام، صفر و دو را هم‌رنگ می‌کند، ولی یالِ تازه رنگِ متفاوت می‌خواهد. شاهدِ بسته علتِ ناسازگاری را صریح نشان می‌دهد.

پرسش سوم: باید همان جهتِ شاهد را در آزمون نگه داریم؟ پاسخ: خیر؛ چرخشِ نقطهٔ شروع یا وارونه‌کردنِ مسیر ممکن است همان چرخه را بیان کند. برای این قرارداد، معتبر بودنِ گواه مهم است. شرطِ کوتاه‌ترین شاهد به الگوریتم و آزمونِ اضافه نیاز دارد.

پرسش چهارم: چهارده گروه، درستیِ همهٔ برنامه‌های زمان‌بندی را تضمین می‌کند؟ پاسخ: خیر؛ فقط همین مدلِ محدود آزموده شده است. منابع در ۲۶ مهر ۱۴۰۵ خوانده شدند؛ Yale یک بایگانیِ درس است و مستنداتِ خوانده‌شده نسخه‌های Python 3.14.8 و NetworkX 3.7 را نشان می‌دهند، جدا از نسخهٔ اجرای واقعی.

منابع و مطالعهٔ بیشتر

• Yale؛ معیار دوبخشی، دو رنگ و نبود چرخهٔ فرد
• Python3.14؛ deque، append و popleft
• NetworkX3.7؛ تعریف دوبخشی و ابهام رنگ مؤلفه‌های جدا

بررسی منابع: ۲۶ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.