Euler আর Hamilton path — Königsberg থেকে NP-কঠিনতা

১ · Königsberg-এর সাত সেতু — একটি ধাঁধা থেকে graph theory

ধরুন বাজারঘরের একজন ডেলিভারি রাইডার সকালে গুদাম থেকে বের হন। তাঁর কাজ প্রতিটি গলিতে লিফলেট দেওয়া: এমন রুট কি আছে, যাতে প্রতিটি গলি ঠিক একবার ঘোরা হয় আর শেষে তিনি গুদামে ফেরেন? আরেকজন রাইডারের কাজ প্রতিটি মোড়ে একবার একটি পার্সেল দেওয়া। প্রথম প্রশ্নটি edge নিয়ে, দ্বিতীয়টি vertex নিয়ে। শুনতে প্রায় একই, কিন্তু প্রথমটির উত্তর এক লাইনে দেওয়া যায়, আর দ্বিতীয়টির জন্য আজও কোনো দ্রুত পদ্ধতি জানা নেই।

Euler-এর মূল অন্তর্দৃষ্টি ছিল বিমূর্ত করা: গুরুত্বপূর্ণ শুধু কোন ভূখণ্ড কোনটির সঙ্গে কয়টি সেতু দিয়ে যুক্ত। প্রতিটি ভূখণ্ডকে একটি vertex আর প্রতিটি সেতুকে একটি edge ধরলে পাওয়া যায় একটি multigraph, কারণ একই দুই ভূখণ্ডের মধ্যে দুটি সেতু আছে।

এই পর্ব পর্ব ৫৭ “গ্রাফ — সংজ্ঞা, degree আর handshake theorem” আর পর্ব ৫৯ “Connectivity — path, component, cut vertex আর Menger-এর ধারণা”-এর ভাষা ব্যবহার করে। দরকারি সংজ্ঞাগুলো এক জায়গায়:

Königsberg-এ ফিরি। যাত্রার মাঝখানের প্রতিটি ভূখণ্ডে যতবার ঢোকা হয়, ততবারই বের হওয়া হয়, তাই সেখানে সেতুর সংখ্যা জোড় হতে হবে; বিজোড় degree-র ভূখণ্ড কেবল শুরু বা শেষ হতে পারে। কিন্তু চারটিরই degree বিজোড় (5, 3, 3, 3), আর শুরু-শেষ মিলে মাত্র দুটি জায়গা। তাই হাঁটা অসম্ভব। এই যুক্তিটিই পরের উপপাদ্যের অর্ধেক।

২ · Euler-এর উপপাদ্য — কখন প্রতিটি edge ঠিক একবার

“Connected” কথাটি এখানে একটু সাবধানে বলতে হয়: কোনো edge-ই নেই এমন বিচ্ছিন্ন vertex (isolated vertex) থাকলেও Euler circuit-এর কোনো ক্ষতি নেই, কারণ circuit-কে তাদের ছুঁতে হয় না। তাই নিচে “connected” মানে: অন্তত একটি edge-যুক্ত সব vertex একই component-এ।

প্রমাণের আগে একটি lemma লাগবে, যা Hierholzer-এর পদ্ধতিরও মূল।

1. হাঁটা একটি trail, কারণ কোনো edge দুবার নেওয়া হয় না; edge সসীম, তাই হাঁটা কোথাও থামে। — সসীমতা
2. ধরুন হাঁটা এখন w ≠ s-এ। w-তে প্রতিবার ঢোকা আর বের হওয়া মিলে ২টি করে edge খরচ হয়েছে, আর এইমাত্র ঢোকার জন্য আরও ১টি; মোট বিজোড় সংখ্যক। — গোনা
3. deg(w) জোড়, তাই w-তে অন্তত একটি edge এখনো অব্যবহৃত, আর হাঁটা চলতে পারে। অর্থাৎ w ≠ s-এ হাঁটা কখনো আটকায় না। — জোড় − বিজোড় ≥ 1
4. তাই হাঁটা থামে কেবল s-এ, আর তৈরি হয় s থেকে s-এ একটি circuit. ∎ — ধাপ ১ আর ৩

লক্ষ করুন lemma কী বলে না: আটকানোর সময় সব edge ব্যবহার হয়ে গেছে, এমন কোনো দাবি নেই। শুধু s-এর edge-গুলো শেষ। এই পার্থক্যটি অনুশীলন ৪-এর ভুল প্রমাণের মূলে।

উপপাদ্য ২.১-এর প্রমাণ, “কেবল যদি” দিক (circuit থাকলে সব degree জোড়)।

1. Euler circuit-টি v₀, e₁, v₁, …, e_m, v_m = v₀ লিখুন। প্রতিটি edge এখানে ঠিক একবার আছে। — সংজ্ঞা
2. circuit-টি একটি vertex-এর মধ্য দিয়ে প্রতিবার যাওয়ায় দুটি edge খরচ করে: একটি দিয়ে ঢোকে, একটি দিয়ে বের হয় (একটি loop একবারেই ২ গোনে)। শুরুর v₀-এ প্রথমবার বের হওয়া আর শেষবার ঢোকা মিলেও একটি জোড়া। — জোড়ায় গোনা
3. প্রতিটি edge ঠিক একবার আছে বলে প্রতিটি vertex-এর degree = এই জোড়াগুলোর মোট edge, অর্থাৎ জোড়। ∎ — ধাপ ১, ২

“যদি” দিক (সব degree জোড় হলে circuit আছে), m-এর ওপর strong induction (পর্ব ১১)।

1. দাবি: শর্ত মানে এমন প্রতিটি multigraph-এ, যার edge সংখ্যা m ≥ 1, Euler circuit আছে। ধরুন m-এর চেয়ে কম edge-এর সব ক্ষেত্রে দাবিটি সত্য। — induction hypothesis
2. lemma ২.২ থেকে একটি circuit C পাওয়া যায়। C যদি সব edge ব্যবহার করে, তবে C-ই Euler circuit, কাজ শেষ। — lemma ২.২
3. না হলে C-এর edge-গুলো মুছে বাকি graph H নিন। C প্রতিটি vertex-এ জোড় সংখ্যক edge খরচ করে (“কেবল যদি” দিকের ধাপ ২), তাই H-এর প্রতিটি degree এখনো জোড়। — জোড় − জোড় = জোড়
4. H-এর যেকোনো edge-যুক্ত component K নিন। K-এর edge m-এর চেয়ে কম আর সব degree জোড়, তাই hypothesis অনুযায়ী K-এর একটি Euler circuit C_K আছে। — induction hypothesis
5. G connected বলে K-এর কোনো vertex x অবশ্যই C-এর ওপর আছে: না হলে K-এর edge আর C-এর edge-এর মধ্যে G-তে কোনো পথ থাকত না। — connectedness
6. C ধরে হাঁটতে হাঁটতে x-এ পৌঁছে প্রথমে পুরো C_K ঘুরে x-এ ফিরুন, তারপর C-এর বাকি অংশ চালিয়ে যান। প্রতিটি component-এর জন্য এভাবে “জোড়া” (splice) দিলে প্রতিটি edge ঠিক একবার ব্যবহার হয়। ∎ — splicing

1. “কেবল যদি”: u থেকে v-তে একটি Euler trail-এ মাঝের প্রতিটি vertex-এ ঢোকা-বের হওয়া জোড়ায় আসে, তাই তাদের degree জোড়। u = v হলে এটি একটি circuit, বিজোড় vertex ০টি; u ≠ v হলে শুধু u আর v-এ একটি করে বাড়তি edge, তাই ঠিক এরা দুটি বিজোড়। — উপপাদ্য ২.১-এর একই গোনা
2. “যদি”, ০টি বিজোড় হলে উপপাদ্য ২.১ নিজেই একটি circuit দেয়। — উপপাদ্য ২.১
3. ঠিক ২টি বিজোড় u, v হলে একটি নতুন edge u–v যোগ করুন (parallel হলেও চলবে)। এখন সব degree জোড়, তাই একটি Euler circuit আছে, যা নতুন edge-টি একবার ব্যবহার করে। — উপপাদ্য ২.১
4. circuit-টিকে নতুন edge-এর জায়গায় কেটে দিলে বাকি অংশ u থেকে v-তে একটি trail, যা G-এর প্রতিটি edge ঠিক একবার নেয়। ∎ — circuit থেকে একটি edge বাদ

বিজোড় vertex ১টি বা ৩টি হওয়া অসম্ভব, handshake lemma অনুযায়ী। আর কোনো connected graph-এ বিজোড় vertex 2k-টি (k ≥ 1) হলে তার edge-গুলো ঠিক k-টি trail-এ ভাগ করা যায়, কমে নয়: k-টি কাল্পনিক edge দিয়ে বিজোড়দের জোড়ায় জুড়ে circuit বানিয়ে কাল্পনিক edge-গুলো কেটে দিলেই হয়। “কলম না তুলে ছবি আঁকা” ধাঁধার এটিই উত্তর।

৩ · Hierholzer আর Fleury — circuit বানানোর দুই পদ্ধতি

উপরের প্রমাণটি নিজেই একটি algorithm: একটি circuit বানানো, বাকি edge-এ আরেকটি circuit বানানো, তারপর দুটি জুড়ে দেওয়া। একে বলে Hierholzer-এর algorithm. নিচের stepper বাজারঘরের পাঁচটি হাব A, B, C, D, E-এর একটি multigraph-এ কাজটি দেখায়; B আর D-এর মধ্যে দুটি আলাদা রাস্তা আছে।

Hierholzer কেন সঠিক। দুটি invariant: (১) হাতের ক্রমটি সবসময় একটি বৈধ circuit, কারণ বন্ধ ঘুরপথ ঢোকালে ক্রম বন্ধই থাকে; (২) বাকি edge-এর graph-এ সব degree জোড়, তাই lemma ২.২ অনুযায়ী নতুন হাঁটা শুরুতেই ফেরে। edge বাকি থাকলে connectedness অনুযায়ী circuit-এর ওপর এমন vertex আছে যার edge বাকি; প্রতিবার edge কমে, তাই কাজ শেষ হয়, আর তখন সব edge ব্যবহৃত।

প্রোগ্রামে splice আলাদা করে লাগে না: stack-এ বর্তমান হাঁটা রাখুন; অব্যবহৃত edge থাকলে এগোন, না থাকলে vertex-টিকে stack থেকে তুলে ফলাফলে যোগ করুন। প্রতিটি edge একবার দেখা হয়: O(n + m). DSA কোর্সের পর্ব ৩৯ “গ্রাফ — উপস্থাপন আর পরিভাষা”-এ এর প্রোগ্রামিং দিক আছে।

Fleury-র পদ্ধতি (১৮৮৩ সালের বলে উল্লেখ করা হয়) একটিই হাঁটা চালায়, কিন্তু নিয়ম মেনে: বর্তমান vertex থেকে একটি bridge (যে edge মুছলে বাকি অব্যবহৃত graph দুই ভাগ হয়) নেবেন না, যদি অন্য কোনো উপায় থাকে। তাহলে কোনো edge “ওপারে” আটকে থাকে না। পদ্ধতিটি সঠিক (প্রমাণ এখানে বাদ; বেশির ভাগ discrete math পাঠ্যবইয়ে আছে), কিন্তু প্রতি ধাপে bridge পরীক্ষায় সরল রূপে প্রায় O(m²) কাজ লাগে। তাই হাতে Fleury, প্রোগ্রামে Hierholzer.

নিচের ব্লক degree পরীক্ষা করে, stack-ভিত্তিক Hierholzer চালায়, আর ফলাফলটি সত্যিই প্রতিটি edge ঠিক একবার নেয় কি না যাচাই করে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে; পরের ব্লকগুলো দ্রুত চলে।

from collections import Counter, defaultdict
def odd_vertices(edges):              # loops count 2, parallel edges each 1
    deg = Counter(v for e in edges for v in e)
    return deg, sorted(v for v in deg if deg[v] % 2)
def hierholzer(edges, start):
    adj = defaultdict(list)           # vertex -> [(neighbour, edge id)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i)); adj[v].append((u, i))
    used = [False] * len(edges)
    stack, circuit = [start], []
    while stack:
        v = stack[-1]
        while adj[v] and used[adj[v][-1][1]]:
            adj[v].pop()              # skip edges walked from the other end
        if adj[v]:
            w, i = adj[v].pop(); used[i] = True
            stack.append(w)           # extend the current trail
        else:
            circuit.append(stack.pop())   # stuck: v is finished
    return circuit[::-1]
def uses_each_edge_once(seq, edges):
    return Counter(frozenset(p) for p in zip(seq, seq[1:])) == \
           Counter(frozenset(e) for e in edges)
konig = [("A","B"), ("A","B"), ("A","C"), ("A","C"), ("A","D"), ("B","D"), ("C","D")]
deg, odd = odd_vertices(konig)
print("Konigsberg:", dict(deg), "odd:", odd)
hubs = [("A","B"), ("B","C"), ("C","A"), ("C","D"), ("D","E"), ("E","C"), ("B","D"), ("D","B")]
deg, odd = odd_vertices(hubs)
c = hierholzer(hubs, "A")
print("hubs odd:", odd, "circuit:", "-".join(c), uses_each_edge_once(c, hubs))
konig8 = konig + [("B","C")]          # an 8th bridge between the banks
deg, odd = odd_vertices(konig8)
t = hierholzer(konig8, odd[0])
print("8 bridges odd:", odd, "trail:", "-".join(t), uses_each_edge_once(t, konig8))

Konigsberg: {'A': 5, 'B': 3, 'C': 3, 'D': 3} odd: ['A', 'B', 'C', 'D']
hubs odd: [] circuit: A-C-E-D-B-D-C-B-A True
8 bridges odd: ['A', 'D'] trail: A-D-C-B-A-C-A-B-D True

৪ · দিকযুক্ত graph আর de Bruijn sequence

শহরের সব রাস্তা দুই দিকে চলে না। একমুখী রাস্তার জন্য directed graph লাগে, যেখানে প্রতিটি edge u থেকে v-তে একটি তীর। একটি vertex-এ ঢোকা তীরের সংখ্যা তার in-degree deg⁻(v), আর বেরোনো তীরের সংখ্যা out-degree deg⁺(v). Euler-এর যুক্তি এখানে আরও সরল: প্রতিবার ঢুকলে একবার বেরোতে হয়।

প্রমাণ উপপাদ্য ২.১-এর হুবহু অনুবাদ। “কেবল যদি”: circuit প্রতিবার একটি vertex-এ ঢুকে বের হয়, তাই ঢোকা = বেরোনো। “যদি”: lemma ২.২-এর directed রূপ সত্য, কারণ w ≠ s-এ এইমাত্র ঢুকলে ব্যবহৃত বেরোনো তীর ব্যবহৃত ঢোকা তীরের চেয়ে একটি কম, আর deg⁺(w) = deg⁻(w) বলে একটি বেরোনো তীর বাকি থাকে। তারপর একই induction আর splice. শর্ত পূরণ হলে তীর-যুক্ত সব vertex আসলে strongly connected, কারণ Euler circuit সবাইকে একটি বন্ধ পথে বাঁধে। ∎

de Bruijn sequence: একটি তালার সব কোড একটানা

বাজারঘরের গুদামের একটি পুরোনো তালায় ৩-বিটের কোড, আর তালাটি শুধু শেষ তিনটি চাপা বিট দেখে। প্রতিটি কোড আলাদা চাপলে 8 × 3 = 24 চাপ লাগে, কিন্তু কোডগুলো একে অন্যের ওপর চাপানো যায়: 0001011100 চাপলে পরপর তিনটি করে বিট 000, 001, 010, 101, 011, 111, 110, 100, অর্থাৎ ৮টি কোডই আসে, মাত্র ১০ চাপে। চক্রাকারে লিখলে এমন একটি string-কে বলে de Bruijn sequence B(2, n): দৈর্ঘ্য 2ⁿ-এর একটি চক্রাকার bit string, যাতে প্রতিটি n-বিট শব্দ ঠিক একবার আসে। পর্ব ৫১-এর necklace আলোচনায় এদের দেখা পেয়েছিলেন।

1. প্রতিটি vertex x-এর পরে 0 বা 1 বসিয়ে দুটি বেরোনো তীর, আর সামনে 0 বা 1 বসিয়ে দুটি ঢোকা তীর: deg⁺ = deg⁻ = 2. — গোনা
2. যেকোনো x থেকে যেকোনো y-তে যাওয়া যায়: y-এর n − 1টি বিট একে একে পেছনে জুড়ে দিলে n − 1 ধাপে x “সরে গিয়ে” y হয়ে যায়। তাই graph connected. — shift
3. উপপাদ্য ৪.১ অনুযায়ী একটি directed Euler circuit আছে, যা প্রতিটি তীর, অর্থাৎ প্রতিটি n-বিট শব্দ, ঠিক একবার নেয়। — উপপাদ্য ৪.১
4. circuit-এর প্রতিটি তীর থেকে তার নতুন (শেষ) বিটটি পরপর লিখলে 2ⁿ দৈর্ঘ্যের একটি চক্রাকার string পাওয়া যায়, যার প্রতিটি n-বিট জানালা ঠিক একটি তীর। ∎ — নির্মাণ

from itertools import product
def de_bruijn(n):                     # Euler circuit in the de Bruijn digraph
    out = {"".join(p): ["1", "0"] for p in product("01", repeat=n - 1)}
    start = "0" * (n - 1)
    stack, circuit = [start], []
    while stack:                      # Hierholzer, directed version
        v = stack[-1]
        if out[v]:
            b = out[v].pop()          # unused edge v -> v[1:] + b
            stack.append(v[1:] + b)
        else:
            circuit.append(stack.pop())
    circuit.reverse()
    return "".join(v[-1] for v in circuit[1:])   # new bit of each edge
def is_de_bruijn(s, n):
    t = s + s[:n - 1]                 # read the string as a circle
    return len(s) == 2 ** n and len({t[i:i + n] for i in range(len(s))}) == len(s)
for n in (3, 4):
    s = de_bruijn(n)
    print(f"n={n}: {s}  every {n}-bit word once: {is_de_bruijn(s, n)}")
for n in (3, 4):                      # brute force over all 2^(2^n) strings
    L = 2 ** n
    hits = sum(is_de_bruijn("".join(p), n) for p in product("01", repeat=L))
    print(f"n={n}: {hits:3} strings, {hits // L:2} circles,"
          f" formula 2^(2^(n-1)-n) = {2 ** (2 ** (n - 1) - n)}")

n=3: 01011100  every 3-bit word once: True
n=4: 0100110101111000  every 4-bit word once: True
n=3:  16 strings,  2 circles, formula 2^(2^(n-1)-n) = 2
n=4: 256 strings, 16 circles, formula 2^(2^(n-1)-n) = 16

৫ · বাজারঘরের রাইডার — route inspection (Chinese postman)

বাস্তবের রাস্তার জাল প্রায় কখনো সব-জোড় degree-র নয়, তবু রাইডারকে প্রতিটি রাস্তায় অন্তত একবার গিয়ে গুদামে ফিরতে হয়; কিছু রাস্তা দুবার যেতেই হবে। মোট সময় সবচেয়ে কম কীভাবে? একে বলে route inspection বা Chinese postman সমস্যা; চীনা গণিতবিদ Kwan Mei-Ko (Guan Meigu) ১৯৬০-এর দশকের শুরুতে ডাকপিয়নের রুট নিয়ে এটি তোলেন বলে নামটি এসেছে।

1. যেকোনো এমন রুট একটি closed walk. প্রতিটি edge যতবার নেওয়া হয়েছে ততটি কপি বসালে একটি multigraph G′ হয়, যার Euler circuit-ই রুটটি; তাই G′-এর সব degree জোড়। — উপপাদ্য ২.১
2. বাড়তি কপিগুলো দিয়ে একটি graph D বানান, যাতে G′ = G + D. G′-এর সব degree জোড়, তাই D-তে একটি vertex-এর degree বিজোড় ঠিক তখন, যখন G-তে তার degree বিজোড়: D-এর বিজোড় vertex-এর সেট ঠিক O. — parity
3. উপপাদ্য ২.৩-এর পরের মন্তব্যটি D-এর প্রতিটি component-এ প্রয়োগ করলে D-এর ভেতরে k-টি edge-বিচ্ছিন্ন trail পাওয়া যায়, যারা O-এর বিন্দুগুলোকে জোড়ায় জোড়ে; প্রতিটি trail-এর দৈর্ঘ্য অন্তত তার দুই প্রান্তের d. তাই বাড়তি ≥ কোনো একটি জোড়ভাগের ∑d ≥ minimum. — নিম্নসীমা
4. উল্টো দিকে, সবচেয়ে ভালো জোড়ভাগের প্রতিটি জোড়ার সবচেয়ে ছোট পথ দ্বিতীয়বার যোগ করলে সব degree জোড় হয়, আর Euler circuit ঠিক ওই দৈর্ঘ্যের রুট দেয়। ∎ — নির্মাণ

উদাহরণ: ঢাকার ছয়টি এলাকা মিরপুর (M), ফার্মগেট (F), ধানমন্ডি (D), গুলশান (G), মতিঝিল (T) আর উত্তরা (U)-এর মধ্যে ৯টি রাস্তা, মিনিটে সময় দেওয়া (সংখ্যাগুলো কাল্পনিক, শুধু উদাহরণের জন্য)। নিচের ব্লক বিজোড় vertex খোঁজে, পর্ব ৫৪-এর Warshall-এর মতো একটি লুপে (Floyd–Warshall) সব জোড়ার সবচেয়ে ছোট দূরত্ব বের করে, আর সব জোড়ভাগ পরীক্ষা করে।

from collections import Counter
roads = {("M","F"): 10, ("M","D"): 12, ("F","D"): 7, ("F","G"): 9, ("F","T"): 11,
         ("G","T"): 8, ("D","T"): 14, ("G","U"): 15, ("M","U"): 20}   # minutes
V = sorted({v for e in roads for v in e})
d = {(a, b): 0 if a == b else float("inf") for a in V for b in V}
for (a, b), w in roads.items():
    d[a, b] = d[b, a] = w
for k in V:                           # Floyd-Warshall: all shortest distances
    for a in V:
        for b in V:
            d[a, b] = min(d[a, b], d[a, k] + d[k, b])
deg = Counter(v for e in roads for v in e)
odd = [v for v in V if deg[v] % 2]
print("degrees:", dict(sorted(deg.items())), " odd:", odd)
def pairings(xs):                     # every way to split xs into pairs
    if not xs:
        yield []
        return
    for i in range(1, len(xs)):
        for rest in pairings(xs[1:i] + xs[i + 1:]):
            yield [(xs[0], xs[i])] + rest
best = None
for p in pairings(odd):
    extra = sum(d[pair] for pair in p)
    print("pair", p, "extra", extra)
    if best is None or extra < best[0]:
        best = (extra, p)
total = sum(roads.values())
print("all roads once:", total, "min extra:", best[0], "tour:", total + best[0])

degrees: {'D': 3, 'F': 4, 'G': 3, 'M': 3, 'T': 3, 'U': 2}  odd: ['D', 'G', 'M', 'T']
pair [('D', 'G'), ('M', 'T')] extra 37
pair [('D', 'M'), ('G', 'T')] extra 20
pair [('D', 'T'), ('G', 'M')] extra 33
all roads once: 106 min extra: 20 tour: 126

৬ · Hamilton path আর cycle — কেন কোনো সহজ শর্ত নেই

এবার দ্বিতীয় রাইডার: প্রতিটি মোড়ে ঠিক একবার, রাস্তা যতবার লাগুক তাতে আপত্তি নেই, শুধু কোনো মোড়ে দ্বিতীয়বার নয়। নামটি এসেছে William Rowan Hamilton-এর ১৮৫৭ সালের দিকের “Icosian game” থেকে: একটি dodecahedron-এর ২০টি কোণ ঠিক একবার ছুঁয়ে ফিরে আসা। Thomas Kirkman প্রায় একই সময়ে এমন cycle নিয়ে লিখেছিলেন বলেও উল্লেখ পাওয়া যায়।

Euler-এর শর্তটি স্থানীয়: প্রতিটি vertex আলাদা করে পরীক্ষা করা যায়। Hamilton-এর জন্য এমন শর্ত জানা নেই। আমরা জানি কিছু আবশ্যিক শর্ত (ভাঙলে cycle নেই) আর কিছু যথেষ্ট শর্ত (থাকলে cycle আছে); মাঝখানের বিরাট অঞ্চলে খুঁজতেই হয়।

1. (ক) cycle সব vertex-কে একটি বন্ধ পথে বাঁধে, তাই যেকোনো দুটি যুক্ত; আর cycle-এ প্রতিটি vertex-এর দুটি প্রতিবেশী। — সংজ্ঞা
2. (খ) একটি cycle থেকে k-টি vertex মুছলে cycle-টি সর্বোচ্চ k-টি টুকরো path-এ ভাঙে (বৃত্তকে k জায়গায় কাটলে সর্বোচ্চ k টুকরো)। প্রতিটি টুকরো connected, আর graph-এর বাকি edge শুধু টুকরোগুলোকে আরও জুড়তে পারে। তাই component ≤ k. k = 1-এ: একটি vertex মুছলে graph connected থাকে। — টুকরো গোনা
3. (গ) bipartite graph-এর প্রতিটি edge X আর Y-এর মধ্যে, তাই cycle ধরে হাঁটলে X, Y, X, Y, … পালাক্রমে আসে, আর শুরুতে ফিরতে হলে দৈর্ঘ্য জোড়, X আর Y থেকে সমান সংখ্যক vertex. Hamilton cycle সব vertex নেয়, তাই |X| = |Y|. ∎ — পালাক্রম

(গ)-এর একই যুক্তিতে Hamilton path-এর জন্য ||X| − |Y|| ≤ 1 লাগে, কারণ path-এ X আর Y পালাক্রমে আসে কিন্তু শুরু-শেষ মিলতে হয় না। নিচের stepper এই যুক্তিটি বাজারঘরের ৩ × ৩ গুদাম-গ্রিডে চালায়।

Petersen graph. ১০টি vertex, ১৫টি edge: বাইরের একটি পাঁচভুজ, ভেতরের একটি পাঁচকোণা তারা, আর বাইরের প্রতিটি কোণ থেকে ভেতরের একটি কোণে একটি করে “স্পোক”। প্রতিটি vertex-এর degree 3, কোনো cut vertex নেই, bipartite-ও নয়, তবু এতে কোনো Hamilton cycle নেই; অথচ যেকোনো একটি vertex মুছলে বাকিটায় Hamilton cycle আছে। এটি একটি সুপরিচিত ফল, যার হাতে-লেখা প্রমাণ কয়েকটি ক্ষেত্রে ভাগ করে করা হয়; এখানে আমরা নিচের ব্লকে সব সম্ভাবনা খুঁজে যাচাই করব। Julius Petersen ১৮৯৮ সালে এটি একটি পাল্টা-উদাহরণ হিসেবে ব্যবহার করেন বলে জানা যায়। Petersen graph গ্রাফ তত্ত্বের অনেক অনুমানের পাল্টা-উদাহরণ; পর্ব ৫৮ “গ্রাফের representation আর isomorphism”-এও এটি আসবে।

Gray code আর hypercube. Hypercube Q_n-এর vertex সব n-বিট string, আর এক বিটে আলাদা দুটি string-এর মধ্যে edge. পর্ব ৩৬-এর চক্রাকার Gray code ঠিক Q_n-এর একটি Hamilton cycle (n ≥ 2): 000, 001, 011, 010, 110, 111, 101, 100, আবার 000. Reflected নির্মাণটিই induction-এ প্রমাণ যে প্রতিটি Q_n (n ≥ 2) Hamiltonian. অন্যদিকে Q_n-এর প্রতিটি degree n, তাই Q_n-এ Euler circuit আছে ঠিক তখন, যখন n জোড়।

দাবার ঘোড়া। Knight's tour মানে ঘোড়ার চাল দিয়ে বোর্ডের প্রতিটি ঘরে ঠিক একবার যাওয়া: ঘর = vertex, ঘোড়ার চাল = edge ধরলে এটি একটি Hamilton path (শুরুতে ফিরলে cycle); 8 × 8 বোর্ডে বন্ধ tour আছে। ঘোড়া প্রতিবার রং বদলায় বলে graph-টি bipartite, তাই উপপাদ্য ৬.১(গ) অনুযায়ী বিজোড় সংখ্যক ঘরের বোর্ডে (যেমন 5 × 5) বন্ধ tour অসম্ভব।

৭ · Dirac আর Ore-এর উপপাদ্য — যথেষ্ট শর্ত

শুধু “মোট edge বেশি” যথেষ্ট নয়: K_n−1-এর সঙ্গে একটি ঝুলন্ত vertex জুড়লে প্রায় সব edge আছে, তবু degree 1-এর vertex-এর জন্য cycle নেই। প্রতিটি vertex-এর নিজের degree বড় হওয়া চাই।

Dirac সরাসরি Ore থেকে আসে: δ ≥ n/2 হলে যেকোনো দুটি vertex-এর degree-র যোগফল ≥ n/2 + n/2 = n. তাই শুধু Ore প্রমাণ করলেই হয়। প্রমাণের হৃদয় একটি “ক্রসিং edge” যুক্তি, যা আগে নিচের stepper-এ একটি ৮-vertex উদাহরণে দেখুন।

Ore-এর উপপাদ্য ৭.১-এর প্রমাণ। বিরোধ দিয়ে (proof by contradiction).

1. ধরুন এমন একটি G আছে যা শর্ত মানে, কিন্তু Hamiltonian নয়। G-তে নতুন edge একটি একটি করে যোগ করুন, যতক্ষণ graph Hamiltonian না হয়। শেষে পাওয়া যায় একটি H ⊇ G, যা Hamiltonian নয়, কিন্তু যেকোনো একটি নতুন edge যোগ করলেই Hamiltonian হয়। — K_n Hamiltonian বলে প্রক্রিয়াটি K_n-এর আগে থামে
2. edge যোগ করলে degree কমে না, আর অসংলগ্ন জোড়া কমে; তাই H-ও Ore-এর শর্ত মানে। H ≠ K_n, তাই H-এ অসংলগ্ন u, v আছে। — degree একঘেয়েভাবে বাড়ে
3. H + uv Hamiltonian, আর তার যেকোনো Hamilton cycle অবশ্যই uv ব্যবহার করে (না হলে H নিজেই Hamiltonian হতো)। cycle থেকে uv বাদ দিলে H-এ একটি Hamilton path u = v₁, v₂, …, v_n = v. — H-এর গঠন
4. S = {i : 1 ≤ i ≤ n − 1, u ~ v_i+1} আর T = {i : 1 ≤ i ≤ n − 1, v ~ v_i} নিন। u-এর প্রতিটি প্রতিবেশী v₂, …, v_n−1-এর মধ্যে (v_n = v নয়), তাই |S| = deg(u); একইভাবে |T| = deg(v). — সংজ্ঞা
5. |S| + |T| = deg(u) + deg(v) ≥ n, কিন্তু S ∪ T ⊆ {1, …, n − 1}, যেখানে মাত্র n − 1টি সংখ্যা। তাই কোনো i ∈ S ∩ T আছে। — pigeonhole
6. এই i-তে u ~ v_i+1 আর v ~ v_i. তাহলে v₁, v_i+1, v_i+2, …, v_n, v_i, v_i−1, …, v₂, v₁ একটি Hamilton cycle, যা H-এর edge দিয়েই তৈরি। কিন্তু H Hamiltonian নয়: বিরোধ। তাই G Hamiltonian. ∎ — stepper-এর ধাপ ৬

শর্তগুলো প্রায় নিখুঁত। Dirac-এর n/2-কে কমানো যায় না: K_k,k+1-এ n = 2k + 1, δ = k = (n − 1)/2, কিন্তু দুই দিক অসমান বলে উপপাদ্য ৬.১(গ) অনুযায়ী Hamilton cycle নেই। আবার শর্তগুলো শুধু যথেষ্ট, আবশ্যিক নয়: C₆ নিজেই একটি Hamilton cycle, অথচ এর প্রতিটি degree 2 < 3 = n/2. নিচের ব্লক একটি backtracking অনুসন্ধানে (backtracking, DSA কোর্সের পর্ব ৫৬) এসব দাবি পরীক্ষা করে।

import random
from itertools import combinations
def ham_cycle(adj):                   # backtracking from vertex 0
    n, path, seen = len(adj), [0], {0}
    def extend():
        if len(path) == n:
            return path[0] in adj[path[-1]]
        for w in sorted(adj[path[-1]] - seen):
            path.append(w); seen.add(w)
            if extend(): return True
            path.pop(); seen.discard(w)
        return False
    return path + [0] if extend() else None
def ore(adj):                         # deg u + deg v >= n for non-adjacent u, v
    return all(len(adj[u]) + len(adj[v]) >= len(adj)
               for u, v in combinations(adj, 2) if v not in adj[u])
petersen = {i: set() for i in range(10)}
for i in range(5):                    # outer 5-cycle, spokes, inner star
    for u, v in ((i, (i + 1) % 5), (i, i + 5), (i + 5, (i + 2) % 5 + 5)):
        petersen[u].add(v); petersen[v].add(u)
grid = {i: {j for j in range(9) if abs(i // 3 - j // 3) + abs(i % 3 - j % 3) == 1}
        for i in range(9)}            # 3x3 grid, vertex 3*row + col
cube = {i: {i ^ 1, i ^ 2, i ^ 4} for i in range(8)}
for name, g in (("Petersen", petersen), ("3x3 grid", grid), ("Q3", cube)):
    print(f"{name}: Ore {ore(g)}, Hamilton cycle {ham_cycle(g)}")
random.seed(60); n_ore = n_ham = ham_not_ore = 0
for _ in range(2000):
    n, p = random.randint(5, 8), random.choice((0.4, 0.6, 0.8))
    g = {i: set() for i in range(n)}
    for u, v in combinations(range(n), 2):
        if random.random() < p: g[u].add(v); g[v].add(u)
    h, o = ham_cycle(g) is not None, ore(g)
    assert h or not o                 # Ore's theorem: Ore => Hamiltonian
    n_ore += o; n_ham += h; ham_not_ore += h and not o
print("Ore:", n_ore, " Hamiltonian:", n_ham, " Hamiltonian, not Ore:", ham_not_ore)

Petersen: Ore False, Hamilton cycle None
3x3 grid: Ore False, Hamilton cycle None
Q3: Ore False, Hamilton cycle [0, 1, 3, 2, 6, 7, 5, 4, 0]
Ore: 667  Hamiltonian: 1165  Hamiltonian, not Ore: 498

৮ · NP-completeness — Euler সহজ, Hamilton কঠিন

“Euler circuit আছে?” — degree আর connectedness দেখুন, O(n + m) সময়ে উত্তর। “Hamilton cycle আছে?” — সব graph-এ polynomial সময়ে উত্তর দেয় এমন কোনো algorithm জানা নেই। এটি শুধু আমাদের অজ্ঞতা কি না, সেটিই P বনাম NP প্রশ্ন।

যাচাই আর খোঁজার এই পার্থক্যই মূল কথা। কেউ একটি ক্রম দিলে আপনি n ধাপে দেখে নিতে পারেন প্রতিটি vertex একবার এসেছে কি না, আর পরপর দুটি সংলগ্ন কি না। কিন্তু নিজে খুঁজতে গেলে সম্ভাব্য ক্রম K_n-এ (n − 1)!/2টি (পর্ব ৩৩-এর circular permutation): n = 20-এ প্রায় ৬ × ১০¹⁶. Backtracking শাখা কাটে, কিন্তু খারাপ ক্ষেত্রে তাও exponential; সবচেয়ে ভালো জানা সঠিক algorithm-ও exponential, যেমন dynamic programming-এ O(n² 2ⁿ) (Bellman, Held–Karp, ১৯৬২-এর দিকে)। NP-completeness-এর পূর্ণ তত্ত্ব DSA কোর্সের পর্ব ৬৪ “P বনাম NP — NP-complete আর reduction”-এ আছে, আর এমন সমস্যা বাস্তবে কীভাবে সামলানো হয় তা পর্ব ৬৫-এ।

Euler সহজ কেন? Lemma ২.২ নিশ্চয়তা দেয় যে ভুল পথে গেলেও কিছু হারায় না, পরে splice করে ঠিক করা যায়। Hamilton-এ একটি ভুল সিদ্ধান্ত পরে শোধরানো যায় না, কারণ ছোঁয়া vertex-এ আর ফেরা নিষেধ।

Traveling salesperson-এর পূর্বাভাস। Hamilton cycle-এর ওজনযুক্ত রূপ: প্রতিটি শহর জোড়ার দূরত্ব দেওয়া, সবচেয়ে ছোট Hamilton cycle (tour) কোনটি? এটিই traveling salesperson problem (TSP), আর এটি অন্তত HAMILTON CYCLE-এর সমান কঠিন (NP-hard): একটি graph G থেকে K_n বানান যেখানে G-এর edge-এর দৈর্ঘ্য 1 আর বাকিগুলোর 2; G Hamiltonian ⇔ দৈর্ঘ্য n-এর একটি tour আছে। পর্ব ৬১ “Shortest path-এর গণিত — Dijkstra-র প্রমাণ আর traveling salesperson”-এ TSP-এর brute force আর heuristic আসবে। Route inspection (§৫) সব edge ঢাকে আর polynomial; TSP সব vertex ঢাকে আর NP-hard: Euler বনাম Hamilton-এর একই বিভাজন।

৯ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

অঙ্ক ১: কোন পরিচিত graph-এ Euler circuit বা trail

• K_n (n ≥ 3): প্রতিটি degree n − 1. Euler circuit ⇔ n বিজোড়। K₄-এ চারটি vertex-ই বিজোড় (degree 3), তাই trail-ও নেই।
• K_m,n: একদিকের degree n, অন্যদিকের m. Euler circuit ⇔ m আর n দুটিই জোড়। K_2,3-এ ২-দিকের দুটি vertex-এর degree 3, বাকি তিনটির 2: ঠিক দুটি বিজোড়, তাই Euler trail আছে, circuit নেই।
• Q_n: প্রতিটি degree n, connected: Euler circuit ⇔ n জোড়। Q₄-এ আছে, Q₃-এ নেই (৮টি বিজোড় vertex, তাই অন্তত ৪টি trail লাগে)।

অঙ্ক ২: Hamilton cycle গোনা

K₆-এ কয়টি আলাদা Hamilton cycle? আর K_3,3-এ? (cycle-কে edge-এর সেট হিসেবে ধরুন, তাই শুরু আর দিক গুরুত্বহীন।)

1. K_n: vertex 1 থেকে শুরু ধরে বাকি n − 1টির যেকোনো ক্রম একটি cycle, (n − 1)!টি; প্রতিটি cycle দুই দিকে পড়া যায়, তাই (n − 1)!/2. n = 6-এ 120/2 = 60.
2. K_n,n: X-এর একটি নির্দিষ্ট vertex থেকে শুরু; X-এর বাকি n − 1টি (n − 1)! ক্রমে, Y-এর n-টি n! ক্রমে পালাক্রমে বসে; দিকের জন্য ২ দিয়ে ভাগ: n!(n − 1)!/2. n = 3-এ 6 · 2/2 = 6; n = 4-এ 72 (তিনটিই scratch-এ সব ক্রম গুনে মেলানো)।

অঙ্ক ৩: গ্রিডে Hamilton cycle

m × n গ্রিড graph (m, n ≥ 2)-এ Hamilton cycle কখন আছে? উত্তর: ঠিক তখন, যখন mn জোড়। mn বিজোড় হলে রঙের দুই দলের আকার (mn + 1)/2 আর (mn − 1)/2, অসমান: উপপাদ্য ৬.১(গ)। mn জোড় হলে (ধরুন m জোড়) প্রথম কলাম বাদ রেখে সারিগুলো সাপের মতো ঘুরে প্রথম কলাম ধরে শুরুতে ফেরা যায়। scratch-এর backtracking 3 × 4-এ একটি cycle পেয়েছে, 3 × 3, 3 × 5, 5 × 5-এ কোনোটি নয়।

প্রমাণের ভুল ধরুন: “degree ≥ 2 হলেই Hamiltonian”

একজন লিখলেন: “দাবি: n ≥ 3 vertex-এর প্রতিটি connected simple graph, যার প্রতিটি degree ≥ 2, Hamiltonian. প্রমাণ n-এর ওপর induction. n = 3: একমাত্র এমন graph হলো ত্রিভুজ, যা নিজেই Hamilton cycle. ধাপ: n vertex-এর এমন একটি graph-এর Hamilton cycle v₁, …, v_n নিন, আর একটি নতুন vertex w যোগ করুন যা cycle-এর পাশাপাশি দুটি vertex v_i, v_i+1-এর সঙ্গে যুক্ত। তাহলে v_i, w, v_i+1 ঢুকিয়ে n + 1 vertex-এর cycle পাওয়া যায়। ∎”

ভুল কোথায়: ধাপটি একটি নির্দিষ্ট ধরনের (n + 1)-vertex graph বানায়, কিন্তু দাবিটি সব (n + 1)-vertex graph নিয়ে, আর সবাইকে এভাবে বানানো যায় না। সঠিক ধাপ শুরু হয় যেকোনো (n + 1)-vertex graph থেকে, তারপর একটি vertex সরিয়ে hypothesis প্রয়োগ (“build-up” ভুল)। পাল্টা-উদাহরণ: দুটি ত্রিভুজ একটি vertex-এ জোড়া (“bow-tie”, ৫টি vertex নিয়ে)। connected, প্রতিটি degree ≥ 2, কিন্তু মাঝের vertex একটি cut vertex, তাই উপপাদ্য ৬.১(খ) অনুযায়ী Hamilton cycle নেই (scratch-এর backtracking-ও কিছু পায়নি)। ভুল প্রমাণ এমন graph কখনো “বানায়” না, তাই এটিকে ছুঁয়েও দেখেনি।

১০ · AI-এর যুগে — Euler আর Hamilton-এর দাবি যাচাই

Graph-এর প্রশ্নে AI সহকারী প্রায়ই Euler আর Hamilton গুলিয়ে ফেলে। নিয়মিত ভুল আর ধরার উপায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রশ্নটি edge-ঢাকা (Euler) না vertex-ঢাকা (Hamilton), নিজে নিশ্চিত হয়েছি
• degree-র যোগফল 2m কি না, আর বিজোড় vertex জোড় সংখ্যক কি না মিলিয়েছি
• দেওয়া circuit বা cycle-এর প্রতিটি পরপর জোড়া graph-এ সত্যিই edge কি না দেখেছি
• উপপাদ্যের প্রতিটি শর্ত (connected, simple, n ≥ 3) উত্তরে উল্লেখ আছে
• “নেই” দাবির পেছনে একটি প্রমাণ (parity, cut vertex, bipartite অসমতা) আছে, বা ছোট graph-এ brute force চালিয়েছি
• উদ্ধৃত নাম, সাল আর উৎস বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

যেকোনো দাবি করা circuit বা cycle এক লাইনের কোডে যাচাই হয়, আর ছোট graph-এ “নেই” দাবিও backtracking দিয়ে মেলানো যায়; ভুল প্রমাণ সাধারণত bow-tie, Petersen বা দুটি আলাদা ত্রিভুজেই ধরা পড়ে।