Spanning tree — DFS/BFS, minimum spanning tree আর Kirchhoff-এর গণনা

১ · Spanning tree কী, আর কখন থাকে

এই পর্বে graph মানে সসীম undirected graph G = (V, E), |V| = n, |E| = m; দরকার হলে multigraph-ও চলবে। Tree মানে connected আর cycle-হীন graph. পর্ব ৬৫ “Tree — ধর্ম, rooted tree আর m-ary tree-এর হিসাব” tree-এর সমতুল্য সংজ্ঞাগুলো প্রমাণ করে; এখানে আমরা সেখান থেকে তিনটি তথ্য ব্যবহার করব: n vertex-এর tree-তে ঠিক n − 1টি edge; tree-তে দুই vertex-এর মধ্যে পথ ঠিক একটি; আর n vertex-এর connected graph-এ n − 1টি edge থাকলে সেটি tree.

(⇒) T connected আর G-এর প্রতিটি vertex T-তে আছে, তাই যেকোনো দুই vertex-এর মধ্যে T-এর ভেতরেই পথ আছে, আর সেটি G-এরও পথ। (⇐) ধরুন G connected.

1. G-এর সব vertex রেখে কিছু edge বাছলে যত connected subgraph পাওয়া যায়, তাদের সেট খালি নয় (G নিজেই একটি)। পর্ব ১১-এর well-ordering অনুযায়ী এদের মধ্যে সবচেয়ে কম edge-এর একটি H আছে। — well-ordering
2. ধরুন H-এ একটি cycle C আছে আর e = uv তার একটি edge. H − e থেকেও u থেকে v-তে যাওয়া যায়: C-এর বাকি অংশ ঘুরে। তাই H-এর যে walk e ব্যবহার করত, সেটি ঘুরপথে চলে, আর H − e connected থাকে। — cycle-এর ঘুরপথ
3. H − e-তে H-এর চেয়ে কম edge, অথচ সেটি connected আর সব vertex ধারণ করে: H-এর বাছাইয়ের বিরোধ। তাই H-এ কোনো cycle নেই। — বিরোধ
4. H connected, cycle-হীন, আর সব vertex ধারণ করে: H একটি spanning tree. ∎

প্রমাণটি একটি পদ্ধতিও দেয়: cycle পেলে তার একটি edge মুছুন, আর cycle না থাকা পর্যন্ত চালিয়ে যান। Spanning tree-তে n − 1টি edge, তাই মোট ঠিক m − n + 1টি edge মুছতে হয়, যেকোনো ক্রমে। এই সংখ্যার নাম circuit rank বা cyclomatic number. পর্ব ৫৯-এ দেখেছেন connected graph-এ m ≥ n − 1; spanning tree সেই সীমার নিখুঁত উদাহরণ।

নিচের ছবিতে বাজারঘরের সাত হাব আর ১১টি সম্ভাব্য কেবল-পথ, প্রতিটির পাশে কিলোমিটারে কেবলের দৈর্ঘ্য (সংখ্যাগুলো কাল্পনিক, আসল দূরত্ব নয়)। এমন graph-কে weighted graph বলে, আর সংখ্যাগুলো edge weight. এখানে m − n + 1 = 11 − 7 + 1 = 5, তাই যেকোনো spanning tree পাঁচটি পথ বাদ দেয়। scratch-এ সব উপসেট গুনে দেখা গেছে, এই graph-এ মোট ১৪১টি spanning tree, যাদের ওজন 31 থেকে 53. সবুজ মোটা রেখাগুলো সবচেয়ে হালকা tree, যা §৩–৪-এ আমরা খুঁজে বের করব।

একটি ছোট কিন্তু বারবার লাগা তথ্য এখনই প্রমাণ করে রাখি। এটিই পরের সব প্রমাণের যন্ত্র।

1. (ক) T + e-এর যেকোনো cycle-এ e থাকতেই হবে (T নিজে cycle-হীন)। e বাদ দিলে cycle-এর বাকি অংশ T-এ u থেকে v-এর একটি পথ, আর সেই পথ একটিই, P. তাই cycle-ও একটিই। — tree-তে পথ অনন্য
2. (খ) T′-এ edge-সংখ্যা (n − 1) + 1 − 1 = n − 1. — গণনা
3. T′ connected: T-এর যে পথ f ব্যবহার করত, তাতে f-এর জায়গায় cycle P + e-এর বাকি অংশ বসান; সেই অংশে f নেই, e আছে, তাই সেটি T′-এর ভেতরে। — ঘুরপথ
4. n vertex, n − 1টি edge আর connected: পর্ব ৬৫-এর সমতুল্যতা অনুযায়ী T′ একটি tree. ∎

২ · DFS tree আর BFS tree — খোঁজার পথই একটি tree

Spanning tree খোঁজার সবচেয়ে স্বাভাবিক উপায় হলো graph ঘুরে দেখা। BFS (breadth-first search) একটি root s থেকে স্তরে স্তরে এগোয়: আগে s-এর সব প্রতিবেশী, তারপর তাদের নতুন প্রতিবেশী। DFS (depth-first search) যতদূর পারে গভীরে যায়, আটকে গেলে পেছনে ফেরে। দুই ক্ষেত্রেই প্রতিটি নতুন vertex v যে edge দিয়ে প্রথম আবিষ্কৃত হয়, সেটি v থেকে তার “parent”-এর দিকে একটি edge. এই edge-গুলোকে tree edge বলে, আর এরা মিলে BFS tree বা DFS tree. Root ছাড়া প্রতিটি পৌঁছানো vertex ঠিক একটি parent পায়, আর parent সবসময় আগে আবিষ্কৃত, তাই এই edge-গুলোতে cycle হয় না: G connected হলে n − 1টি edge-এর একটি spanning tree পাওয়া যায়। Algorithm-এর কোড DSA কোর্সের পর্ব ৪০ আর পর্ব ৪১-এ; এখানে আমরা দুই tree-এর গঠনের প্রমাণ দেখব।

1. (ক) পর্ব ৫৯-এর উপপাদ্য ৮.১ ঠিক এই কথা প্রমাণ করেছে: BFS যে স্তরে v-কে প্রথম পায়, সেটিই দূরত্ব d(s, v). Tree-তে s থেকে v-এর পথে স্তর প্রতি ধাপে ১ করে বাড়ে, তাই পথের দৈর্ঘ্য L(v) = d(s, v). — পর্ব ৫৯
2. (খ) uv একটি edge হলে s থেকে u-এর সবচেয়ে ছোট পথের শেষে uv জুড়লে v-তে একটি walk পাওয়া যায়, তাই d(s, v) ≤ d(s, u) + 1. একইভাবে d(s, u) ≤ d(s, v) + 1. — দূরত্বের triangle inequality
3. দুটি মিলিয়ে আর (ক) ব্যবহার করে |L(u) − L(v)| ≤ 1. ∎

বাজারঘরের graph-এ D থেকে BFS: K, T, N, G, S স্তর 1-এ, আর M স্তর 2-এ (scratch-এ মেলানো)। (খ) থেকে একটি পুরোনো প্রশ্নের সুন্দর উত্তর আসে। কোনো edge একই স্তরের দুই vertex u, v জুড়লে, tree-তে তাদের সবচেয়ে কাছের সাধারণ পূর্বপুরুষ w থেকে u আর v-এর দূরত্ব সমান, ধরুন k; তাহলে w থেকে u, তারপর uv, তারপর v থেকে w মিলে দৈর্ঘ্য 2k + 1-এর একটি বিজোড় cycle. আর এমন edge না থাকলে স্তরের জোড়-বিজোড় দিয়ে দুই রঙে রাঙানো যায়, কারণ প্রতিটি edge পাশাপাশি স্তর জোড়ে। তাই BFS একবার চালিয়েই জানা যায় graph bipartite কি না।

1. DFS-এর visit(u) চলাকালে যে vertex প্রথমবার আবিষ্কৃত হয়, সে u-এর বংশধর: তাকে আবিষ্কার করে এমন একটি visit, যা visit(u)-এর ভেতর থেকে ডাকা, আর তার parent-শৃঙ্খল ডাকার শৃঙ্খল ধরে u-তে পৌঁছায়। — recursion-এর গঠন
2. যেকোনো edge uv নিন; ধরুন u আগে আবিষ্কৃত। visit(u) শুরু হওয়ার সময় v তখনো অদেখা। — ধরে নেওয়া (WLOG)
3. visit(u) শেষ হওয়ার আগে u-এর প্রতিবেশী-তালিকায় v-এর পালা আসে। তখন v অদেখা থাকলে সেখানেই আবিষ্কৃত হয় (u তার parent); আর আগেই দেখা হয়ে থাকলে তা visit(u) চলাকালেই হয়েছে। দুই ক্ষেত্রেই ধাপ ১ অনুযায়ী v হলো u-এর বংশধর। ∎ — ধাপ ১

এই ধর্মই bridge খোঁজার ভিত্তি: tree edge (p, c) bridge ঠিক তখন, যখন c-এর subtree থেকে কোনো back edge p বা তার ওপরে পৌঁছায় না। নিচের ব্লক এলোমেলো graph-এ দুই উপপাদ্যই পরীক্ষা করে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from collections import deque
import random
def dfs_tree(adj, root):
    parent = {root: None}
    def visit(u):
        for v in adj[u]:
            if v not in parent:
                parent[v] = u; visit(v)
    visit(root); return parent
def bfs_tree(adj, root):
    parent, level, q = {root: None}, {root: 0}, deque([root])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in parent:
                parent[v], level[v] = u, level[u] + 1; q.append(v)
    return parent, level
def ancestors(P, v):
    return {v} | ancestors(P, P[v]) if v is not None else set()
random.seed(59); graphs = nontree = 0
for trial in range(300):
    n = random.randint(2, 9)
    E = [(u, v) for u in range(n) for v in range(u + 1, n) if random.random() < 0.4]
    adj = {u: [] for u in range(n)}
    for u, v in E: adj[u].append(v); adj[v].append(u)
    P = dfs_tree(adj, 0)
    if len(P) < n: continue                        # keep connected graphs only
    B, lev = bfs_tree(adj, 0); graphs += 1
    for u, v in E:
        if P[u] != v and P[v] != u:                # DFS non-tree edge
            nontree += 1
            assert u in ancestors(P, v) or v in ancestors(P, u)
        assert abs(lev[u] - lev[v]) <= 1           # BFS: same or next level
print(graphs, "connected graphs,", nontree, "DFS non-tree edges: all ancestor-descendant;",
      "every edge joins BFS levels that differ by at most 1")

166 connected graphs, 443 DFS non-tree edges: all ancestor-descendant; every edge joins BFS levels that differ by at most 1

৩ · Minimum spanning tree — cut property আর cycle property

১৪১টি spanning tree-এর মধ্যে বাজারঘর চায় সবচেয়ে কম মোট কেবলের tree-টি। Spanning tree T-এর ওজন w(T) = T-এর edge-গুলোর ওজনের যোগফল। যে spanning tree-এর ওজন সবচেয়ে কম, সেটি minimum spanning tree (MST). Connected graph-এ spanning tree সসীম সংখ্যক, তাই MST সবসময় আছে; প্রশ্ন হলো দ্রুত খুঁজে পাওয়া আর প্রমাণ করা যে খুঁজে পাওয়াটিই সর্বনিম্ন। সব tree গোনা চলে না: K_n-এ nⁿ⁻²টি tree (§৬)।

দুটি পরিভাষা লাগবে। Cut হলো vertex-গুলোর দুই অশূন্য ভাগে বিভাজন (S, V − S). যে edge-এর এক প্রান্ত S-এ আর অন্যটি V − S-এ, সেটি cut-টি পার হয়: crossing edge. পার হওয়া edge-গুলোর মধ্যে যার ওজন সবচেয়ে কম (সমান থাকলে তাদের যেকোনোটি), সেটি cut-এর light edge. বাজারঘরের graph-এ S = {S} নিলে পার হওয়া edge S–K 7, D–S 9, S–M 10, G–S 11, তাই light edge S–K.

1. T একটি MST যাতে A ⊆ T. e ∈ T হলে কাজ শেষ। ধরুন e = uv ∉ T, যেখানে u ∈ S, v ∈ V − S. — অনুমান
2. T-এ u থেকে v-এর পথ P নিন। P শুরু হয় S-এ, শেষ হয় V − S-এ, তাই P-এর অন্তত একটি edge f cut-টি পার হয়। A কোনো edge দিয়ে cut পার হয় না, তাই f ∉ A. — পথকে কোথাও না কোথাও পার হতে হয়
3. Lemma ১.৩(খ) অনুযায়ী T′ = T + e − f একটি spanning tree, আর A ∪ {e} ⊆ T′. — edge-বদল
4. e light edge আর f-ও পার হয়, তাই w(e) ≤ w(f), ফলে w(T′) = w(T) + w(e) − w(f) ≤ w(T). T সর্বনিম্ন, তাই T′-ও MST. — সমান ওজনও এখানে চলে, তাই tie কোনো সমস্যা নয়
5. e একাই সবচেয়ে হালকা হলে w(e) < w(f), তাই e ∉ T ধরলে w(T′) < w(T), যা অসম্ভব। অতএব e প্রতিটি MST-তে। ∎ — বিরোধ

ধাপ ৪-এর “≤” চিহ্নটি গুরুত্বপূর্ণ। অনেক বইয়ে প্রমাণ শুধু আলাদা ওজনের জন্য দেওয়া থাকে; সমান ওজন থাকলে “প্রতিটি MST-তে আছে” কথাটি ভুল হতে পারে (ত্রিভুজের তিন edge-এর ওজন 1 হলে কোনো edge-ই সব MST-তে নেই), কিন্তু “কোনো একটি MST-তে আছে” সবসময় সত্য। Algorithm-এর জন্য দুর্বল রূপটিই যথেষ্ট। প্রমাণের কৌশলটির নাম exchange argument: সর্বোত্তম উত্তর থেকে একটি অংশ বদলে আমাদের পছন্দ ঢোকানো, ক্ষতি ছাড়াই।

1. বিপরীতে ধরুন e = uv একটি MST T-তে আছে। T − e দুটি component-এ ভাঙে; u-এরটির vertex-সেট S, তাই v ∈ V − S. — tree থেকে একটি edge সরালে দুই টুকরো
2. C − e হলো u থেকে v-এর একটি পথ, তাই তার কোনো একটি edge f cut (S, V − S) পার হয়, আর f ≠ e. — উপপাদ্য ৩.১-এর ধাপ ২-এর মতো
3. T − e + f connected (দুই টুকরো f জোড়ে) আর তাতে n − 1টি edge, তাই spanning tree; আর w(f) < w(e), তাই এর ওজন w(T)-এর চেয়ে কম। বিরোধ। ∎ — edge-বদল

দুই ধর্ম একে অন্যের প্রতিচ্ছবি: cut property বলে কোন edge নিশ্চিন্তে নেওয়া যায়, cycle property বলে কোন edge নিশ্চিন্তে বাদ দেওয়া যায়। প্রথমটি থেকে আসে Kruskal আর Prim, দ্বিতীয়টি থেকে “reverse-delete” পদ্ধতি: সবচেয়ে ভারী থেকে শুরু করে প্রতিটি edge মুছুন, যদি মোছার পরও graph connected থাকে।

1. বিপরীতে ধরুন T₁ ≠ T₂ দুটি MST. দুটিতে edge-সংখ্যা সমান, তাই symmetric difference T₁ ⊕ T₂ অশূন্য। তার সবচেয়ে হালকা edge e নিন (ওজন আলাদা, তাই অনন্য); ধরুন e ∈ T₁ − T₂. — WLOG
2. T₂ + e-তে e-এর fundamental cycle C আছে (Lemma ১.৩)। C-এর সব edge T₁-এ থাকতে পারে না, কারণ T₁ cycle-হীন; তাই C-তে একটি f ∈ T₂ − T₁ আছে, আর f ≠ e. — tree-তে cycle নেই
3. f-ও symmetric difference-এ, আর e সেখানে সবচেয়ে হালকা, ওজন আলাদা: w(e) < w(f). — e-এর বাছাই
4. T₂ + e − f একটি spanning tree (Lemma ১.৩(খ)), যার ওজন w(T₂)-এর চেয়ে কম। T₂ MST হওয়ার বিরোধ। ∎

বাজারঘরের graph-এ সব ওজন আলাদা, তাই MST একটিই; scratch-এ ১৪১টি tree গুনে মেলানো: ওজন 31-এর tree একটিই, তার পরের ওজন 33 (এমন tree তিনটি).

৪ · Kruskal আর Prim — দুই পথ, একই উত্তর

Kruskal-এর algorithm (Joseph Kruskal, ১৯৫৬): সব edge ওজনের ছোট থেকে বড় ক্রমে সাজান। খালি forest A থেকে শুরু করে প্রতিটি edge দেখুন: যদি তা A-এর দুটি আলাদা component জোড়ে, নিন; একই component-এর দুই vertex জুড়লে (অর্থাৎ cycle বানালে) বাদ দিন। “একই component কি না” প্রশ্নের দ্রুত উত্তর দেয় union-find, যার দলগুলো আসলে পর্ব ৫৫-এর equivalence class: “A-তে পথ আছে” সম্পর্কের class.

1১১টি edge, ওজনে সাজানো2D–K 23D–T 34K–N 45T–G 56D–N 67S–K 78D–G 8, D–S 99S–M 10

1. Invariant: প্রতিটি ধাপের পরে A কোনো একটি MST-এর অংশ। শুরুতে A = ∅, যা সব MST-এর অংশ। — loop invariant (পর্ব ১৩)
2. ধরুন algorithm e = uv নেয়, যেখানে u-এর দল C_u আর v-এর দল আলাদা। Cut (C_u, V − C_u) নিন; C_u একটি component বলে A-এর কোনো edge এটি পার হয় না। — cut বাছাই
3. e এই cut-এর light edge: e-এর চেয়ে হালকা প্রতিটি edge g আগে দেখা হয়েছে। নেওয়া হলে g ∈ A, যা পার হয় না। বাদ পড়লে তখনই g-এর দুই প্রান্ত একই দলে ছিল; দল শুধু বড় হয়, তাই এখনো একই দলে, আর g পার হয় না। — দল কখনো ভাঙে না
4. Cut property অনুযায়ী A ∪ {e} কোনো একটি MST-এর অংশ: invariant বজায় থাকে। — উপপাদ্য ৩.১
5. শেষে A-তে cycle নেই (প্রতিটি নেওয়া edge দুটি দল জোড়ে)। A-তে দুটির বেশি দল থাকলে, G connected বলে তাদের মধ্যে একটি edge আছে, আর তা দেখার সময় দুই প্রান্ত আলাদা দলে থাকায় নেওয়া হতো। তাই A একটি spanning tree, আর একটি MST-এর অংশ হওয়ায় নিজেই MST. ∎

Prim-এর algorithm (Robert Prim, ১৯৫৭; Vojtěch Jarník ১৯৩০ সালে আগেই দেন বলে উল্লেখ করা হয়) অন্যভাবে এগোয়: একটি vertex থেকে একটি tree বাড়ান, প্রতিবার tree থেকে বাইরে যাওয়া সবচেয়ে হালকা edge জুড়ে। এর সঠিকতা আরও সরাসরি: tree-এর vertex-সেট S হলে cut (S, V − S) A-এর কোনো edge পার হয় না (A-এর সব edge S-এর ভেতরে), আর Prim ঠিক এই cut-এর light edge নেয়। তাই একই invariant, একই যুক্তি। নিচের stepper সাভার (S) থেকে শুরু করে।

1tree = {S}2+ K3+ D4+ T5+ N6+ G, তারপর M

নিচের ব্লক দুই algorithm বাজারঘরের graph-এ চালায়, সব spanning tree-এর brute-force সর্বনিম্নের সঙ্গে মেলায়, তারপর এমন এলোমেলো graph-এ পরীক্ষা করে যেখানে সমান ওজন ইচ্ছা করে রাখা (ওজন 1 থেকে 5). সমান ওজনে edge-সেট আলাদা হতে পারে, তাই তুলনা মোট ওজনের।

import random
from itertools import combinations
def find(p, x):
    while p[x] != x: x = p[x]                     # walk up to the root
    return x
def kruskal(V, W):
    p = {v: v for v in V}; T = []
    for e in sorted(W, key=W.get):
        a, b = find(p, e[0]), find(p, e[1])
        if a != b: p[a] = b; T.append(e)
    return T
def prim(V, W, root):
    inside, T = {root}, []
    while len(inside) < len(V):
        e = min((e for e in W if (e[0] in inside) != (e[1] in inside)), key=W.get)
        T.append(e); inside |= set(e)
    return T
def brute_min(V, W):                               # lightest of ALL spanning trees
    return min(sum(W[e] for e in T) for T in combinations(W, len(V) - 1)
               if len(kruskal(V, dict.fromkeys(T, 0))) == len(V) - 1)
hub = {("D", "K"): 2, ("D", "T"): 3, ("K", "N"): 4, ("T", "G"): 5, ("D", "N"): 6, ("S", "K"): 7,
       ("D", "G"): 8, ("D", "S"): 9, ("S", "M"): 10, ("G", "S"): 11, ("M", "K"): 12}
V = sorted({x for e in hub for x in e})
for name, T in (("Kruskal", kruskal(V, hub)), ("Prim from S", prim(V, hub, "S"))):
    print(f"{name:11}", " ".join(a + b for a, b in T), "total", sum(hub[e] for e in T))
print("brute force minimum:", brute_min(V, hub))
random.seed(67); checked = 0
for trial in range(150):
    n = random.randint(2, 6); V = list(range(n))
    W = {e: random.randint(1, 5) for e in combinations(V, 2) if random.random() < 0.7}
    if len(kruskal(V, W)) < n - 1: continue        # skip disconnected graphs
    k, p = kruskal(V, W), prim(V, W, random.choice(V))
    assert sum(W[e] for e in k) == sum(W[e] for e in p) == brute_min(V, W)
    checked += 1
print(checked, "random connected graphs (ties allowed): Kruskal = Prim = brute force")

Kruskal     DK DT KN TG SK SM total 31
Prim from S SK DK DT KN TG SM total 31
brute force minimum: 31
131 random connected graphs (ties allowed): Kruskal = Prim = brute force

৫ · MST-এর কাজ — কেবল টানা আর দল ভাগ

নেটওয়ার্ক নকশা। সবচেয়ে সরাসরি প্রয়োগ §১-এর গল্প: হাব, গুদাম বা গ্রাম জুড়তে মোট সবচেয়ে কম কেবল, পাইপ বা রাস্তা। একটি সতর্কতা: MST শুধু “সবাই যুক্ত” নিশ্চিত করে। Tree-তে প্রতিটি edge একটি bridge, তাই একটি কেবল কাটলেই নেটওয়ার্ক ভাগ হয়ে যায়। বাস্তবে তাই অনেক সময় MST-এর সঙ্গে কয়েকটি বাড়তি পথ রাখা হয়, যা পর্ব ৫৯-এর edge connectivity-র প্রশ্ন। মাঝপথে নতুন সংযোগ-বিন্দু বসানোর Steiner tree সমস্যা আরও কঠিন (প্র ০৫)।

Bottleneck. MST-এর একটি কম-জানা ধর্ম: যেকোনো দুই vertex-এর মধ্যে MST-এর পথে সবচেয়ে ভারী edge যতটা সম্ভব হালকা। অর্থাৎ G-এর যেকোনো u–v পথের “সবচেয়ে ভারী edge”-কে ছোট করতে চাইলে MST-এর পথ সেরা। প্রমাণ cycle property-র মতো: MST-এর পথের সবচেয়ে ভারী edge e সরালে দুই টুকরো হয়, আর যেকোনো u–v পথ কোথাও এই cut পার হয়, এমন একটি edge g দিয়ে যার ওজন ≥ w(e); নইলে T − e + g একটি হালকা spanning tree হতো। তবে সাবধান: এটি মোট দৈর্ঘ্যে সবচেয়ে ছোট পথ নয় (§৮-এর ভুল প্রমাণ)।

দল ভাগ বা clustering. বাজারঘর হাবগুলোকে k = 3টি অঞ্চলে ভাগ করতে চায়, যাতে আলাদা অঞ্চলের হাবগুলো যতটা সম্ভব দূরে থাকে। দুই অঞ্চলের সবচেয়ে কাছের দুই হাবের দূরত্বকে ভাগটির “spacing” বলি; চাই সবচেয়ে বড় spacing. উত্তর: Kruskal চালান, কিন্তু kটি দল থাকতেই থামুন। সমতুল্যভাবে MST থেকে সবচেয়ে ভারী k − 1টি edge মুছুন। এর নাম single-linkage clustering. আমাদের graph-এ S–M 10 আর S–K 7 মুছলে তিন অঞ্চল {M}, {S}, {D, G, K, N, T}, আর spacing 7 (অঞ্চলগুলোর মধ্যের edge 7, 9, 10, 11, 12; scratch-এ মেলানো)।

1. ধরুন Kruskal-এর ভাগ 𝒞-এর spacing d*: এটি Kruskal পরের যে edge নিত তার ওজন, অর্থাৎ মুছে ফেলা MST edge-গুলোর সবচেয়ে হালকাটি। অন্য যেকোনো k-ভাগ 𝒞′ নিন। — সংজ্ঞা
2. 𝒞′ ≠ 𝒞 হলে এমন দুই vertex p, q আছে যারা 𝒞-এ এক দলে কিন্তু 𝒞′-এ আলাদা দলে (𝒞-এর প্রতিটি দল 𝒞′-এর কোনো একটি দলের ভেতরে থাকলে, দুই ভাগেই kটি দল বলে ভাগ দুটি এক হতো)। — pigeonhole-ধাঁচের যুক্তি
3. 𝒞-এ p আর q-এর দলটি Kruskal-এর forest-এর একটি tree, যার প্রতিটি edge-এর ওজন ≤ d*. এই tree-তে p থেকে q-এর পথ কোথাও 𝒞′-এর দুই দলের সীমা পার হয়, তাই 𝒞′-এর spacing ≤ d*. ∎ — পথকে সীমা পার হতে হয়

৬ · Kirchhoff-এর matrix-tree theorem — spanning tree গোনা

এবার প্রশ্ন: কয়টি spanning tree আছে? Spanning tree বেশি মানে নেটওয়ার্কে বিকল্প সংযোগ বেশি। ছোট উদাহরণ হাতে করা যায়।

• Cycle C_n: n vertex আর n edge, তাই spanning tree ঠিক একটি edge বাদ দেয়; যেকোনো একটি edge বাদ দিলে একটি path থাকে, যা tree. উত্তর n.
• K_2,3: এক দিকে a, b; অন্য দিকে x, y, z. Spanning tree-তে 5 − 1 = 4টি edge, আর প্রতিটি edge x, y, z-এর ঠিক একটিকে ছোঁয়। প্রত্যেকের degree অন্তত 1 (নইলে একা থাকে), আর তিনজনের degree-এর যোগফল 4, তাই ঠিক একজনের degree 2 (সে a আর b দুজনকেই জোড়ে), বাকি দুজন a বা b-এর একটিতে ঝোলে। দুজনের degree 2 হলে cycle a–x–b–y–a হতো, তাই অন্য কোনো বিকল্প নেই। উত্তর 3 · 2 · 2 = 12.

বড় graph-এ এভাবে গোনা কঠিন। Gustav Kirchhoff বিদ্যুৎ-বর্তনী নিয়ে কাজের সময় (১৮৪৭ সালের প্রবন্ধ বলে উল্লেখ করা হয়) একটি determinant-এর সূত্র পান। দরকার একটি matrix. Graph-এর Laplacian matrix L = D − A, যেখানে D হলো degree-গুলোর diagonal matrix আর A হলো adjacency matrix (পর্ব ৫৮)। অর্থাৎ L_ii = deg(i), আর i ≠ j হলে L_ij = −(i আর j-এর মধ্যে edge-সংখ্যা)। প্রতিটি সারির যোগফল 0.

রূপরেখা। প্রতিটি edge-কে একটি দিক দিন, আর n × m “incidence” matrix B বানান: edge e = (u → v)-এর কলামে u-এর সারিতে +1, v-এর সারিতে −1. তাহলে BB^T = L (দিক যেভাবেই দেওয়া হোক)। B থেকে i-এর সারি বাদ দিয়ে B_i পেলে L_i = B_iB_i^T. Cauchy–Binet সূত্র বলে, det(B_iB_i^T) = সব (n − 1)-edge উপসেট S-এর ওপর det(B_i[S])²-এর যোগফল। শেষ ধাপ: S একটি spanning tree হলে det(B_i[S]) = ±1 (tree-এর পাতা ধরে ধরে বিস্তার করে দেখানো যায়), আর না হলে 0 (cycle থাকলে কলামগুলো linearly dependent). তাই যোগফল ঠিক tree-এর সংখ্যা। পূর্ণ প্রমাণের জন্য বীজগাণিতিক graph theory-র যেকোনো পাঠ্যবই দেখুন; নিচে আমরা সূত্রটি হাতে আর কোডে যাচাই করি।

উদাহরণ হিসেবে একটি বর্গ 1–2–3–4–1 আর তার একটি কর্ণ 1–3 নিন (৫টি edge). Determinant বের করার জন্য Gaussian elimination: একটি সারির গুণিতক নিচের সারি থেকে বিয়োগ করে diagonal-এর নিচের সব সংখ্যা শূন্য করা, যাতে determinant বদলায় না, তারপর diagonal-এর গুণফল। ভগ্নাংশ এড়ানো যায় না, তাই ঠিক ভগ্নাংশ (Fraction) রাখি।

1G: 1–2, 2–3, 3–4, 4–1, 1–32L = D − A3vertex 4-এর সারি ও কলাম বাদ4কলাম ১-এর নিচে শূন্য5কলাম ২-এর নিচে শূন্য6det = diagonal-এর গুণফল7সরাসরি গুনে যাচাই

1. K_n-এ প্রতিটি degree n − 1, তাই একটি vertex বাদ দিলে L-এর (n − 1) × (n − 1) অংশে diagonal-এ n − 1, বাকি সব ঘরে −1. — Laplacian-এর সংজ্ঞা
2. সব সারি প্রথম সারিতে যোগ করুন। প্রতিটি কলামের যোগফল (n − 1) + (n − 2)(−1) = 1, তাই প্রথম সারি হয় সব 1. Determinant বদলায় না। — সারি-ক্রিয়া
3. এই নতুন প্রথম সারি বাকি প্রতিটি সারিতে যোগ করুন: diagonal-এ n − 1 + 1 = n, অন্য ঘরে −1 + 1 = 0, প্রথম কলামে −1 + 1 = 0. — সারি-ক্রিয়া
4. Matrix এখন উপরের ত্রিভুজাকার, diagonal 1, n, n, …, n (n − 2 বার n). Determinant nⁿ⁻². ∎ — উপপাদ্য ৬.১

K₄-এ 4² = 16. Arthur Cayley ১৮৮৯ সালে সূত্রটি প্রকাশ করেন বলে নামটি তাঁর, তবে এর আগে Borchardt ১৮৬০ সালে এটি পেয়েছিলেন বলে উল্লেখ করা হয়। Prüfer code দিয়ে একটি bijective প্রমাণ পর্ব ৬৫ “Tree — ধর্ম, rooted tree আর m-ary tree-এর হিসাব”-এ। একই পদ্ধতিতে K_m,n-এ mⁿ⁻¹n^m−1টি tree পাওয়া যায়; K_2,3-এ 2² · 3 = 12, ওপরের হাতের গণনার সঙ্গে মিলল।

import random; random.seed(7)
from fractions import Fraction
from itertools import combinations
def det(M):                                        # exact Gaussian elimination
    M = [[Fraction(x) for x in row] for row in M]; n, d = len(M), Fraction(1)
    for c in range(n):
        piv = next((r for r in range(c, n) if M[r][c] != 0), None)
        if piv is None: return Fraction(0)
        if piv != c: M[c], M[piv] = M[piv], M[c]; d = -d
        d *= M[c][c]
        for r in range(c + 1, n):
            k = M[r][c] / M[c][c]
            M[r] = [a - k * b for a, b in zip(M[r], M[c])]
    return d
def kirchhoff(n, E):                               # Laplacian minus last row/col
    L = [[0] * n for _ in range(n)]
    for u, v in E:
        L[u][u] += 1; L[v][v] += 1; L[u][v] -= 1; L[v][u] -= 1
    return int(det([row[:-1] for row in L[:-1]]))
def is_tree(n, T):                                 # n - 1 edges, no cycle
    p = list(range(n))
    def f(x): return x if p[x] == x else f(p[x])
    for u, v in T:
        a, b = f(u), f(v)
        if a == b: return False
        p[a] = b
    return True
def K(n): return list(combinations(range(n), 2))   # complete graph K_n
print("K4:", kirchhoff(4, K(4)), " C4 + chord:", kirchhoff(4, [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)]))
print("K_n, n = 2..7:", [kirchhoff(n, K(n)) for n in range(2, 8)],
      "n^(n-2):", [n ** (n - 2) for n in range(2, 8)])
for trial in range(200):
    n = random.randint(2, 6); E = [e for e in K(n) if random.random() < 0.6]
    assert kirchhoff(n, E) == sum(is_tree(n, T) for T in combinations(E, n - 1))
print("200 random graphs: determinant = brute-force count (0 if disconnected)")

K4: 16  C4 + chord: 8
K_n, n = 2..7: [1, 3, 16, 125, 1296, 16807] n^(n-2): [1, 3, 16, 125, 1296, 16807]
200 random graphs: determinant = brute-force count (0 if disconnected)

৭ · MST দ্বিগুণ করে metric TSP — 2-approximation-এর পূর্ণ প্রমাণ

পর্ব ৬১-এ traveling salesperson problem (TSP) এসেছিল: সব শহর একবার ঘুরে শুরুতে ফেরার সবচেয়ে ছোট tour. সেখানে উপপাদ্য ৮.২-এর রূপরেখা ছিল; এখানে পূর্ণ প্রমাণ। Metric TSP মানে দূরত্ব D(a, b) ≥ 0, প্রতিসম, আর triangle inequality D(a, c) ≤ D(a, b) + D(b, c) মানে; প্রতিটি দুই শহরের মধ্যে সরাসরি পথ আছে (complete graph).

1. নিম্নসীমা: সবচেয়ে ছোট tour থেকে যেকোনো একটি edge সরালে একটি Hamilton path থাকে, যা একটি spanning tree; তার ওজন ≤ OPT (সরানো edge ≥ 0). MST সব spanning tree-এর চেয়ে হালকা, তাই w(T) ≤ OPT. — MST-এর সংজ্ঞা
2. দ্বিগুণ: T-এর প্রতিটি edge-এর দুটি কপি নিন। এই multigraph connected, আর প্রতিটি degree জোড় (T-এর degree-এর দ্বিগুণ), তাই পর্ব ৬০-এর উপপাদ্য অনুযায়ী এতে একটি Euler circuit W আছে, যা প্রতিটি কপি একবার ব্যবহার করে। দৈর্ঘ্য ঠিক 2 · w(T). DFS-এর “নামা আর ফেরা” ঠিক এমন একটি circuit, আর তাতে vertex-গুলো প্রথমবার আসে preorder ক্রমে। — Euler-এর শর্ত
3. Shortcut lemma: যেকোনো walk x₀, x₁, …, x_k-এর জন্য D(x₀, x_k) ≤ ∑ D(x_i−1, x_i). k-এর ওপর induction: k = 1 সরাসরি; k − 1 পর্যন্ত সত্য হলে D(x₀, x_k) ≤ D(x₀, x_k−1) + D(x_k−1, x_k), আর প্রথম পদে hypothesis. — triangle inequality, পর্ব ১০
4. Shortcutting: W থেকে প্রতিটি vertex-এর প্রথম আবির্ভাব রেখে বাকি মুছে H পাই। H-এর প্রতিটি ধাপ u → u′ W-এর একটি অংশকে প্রতিস্থাপন করে, যা u থেকে u′-এ যায়; lemma অনুযায়ী ধাপটি সেই অংশের চেয়ে লম্বা নয়। অংশগুলো W-এর আলাদা টুকরো, তাই len(H) ≤ len(W) = 2 · w(T). — ধাপ ৩
5. মিলিয়ে len(H) ≤ 2 · w(T) ≤ 2 · OPT. ∎

Metric শর্ত কেবল ধাপ ৩–৪-এ লেগেছে, কিন্তু সেটি অপরিহার্য: triangle inequality ছাড়া কোনো polynomial algorithm কোনো ধ্রুব গুণকের নিশ্চয়তা দিতে পারে না, যদি না P = NP (পর্ব ৬১-এ উল্লেখিত)। এমন নিশ্চয়তাকে approximation ratio 2 বলে। নিচের ব্লক ৭টি শহরের এলোমেলো সমতল বিন্দুতে (Euclidean দূরত্ব metric) সব 6! = 720টি ক্রম দেখে OPT বের করে, আর অনুপাত মাপে।

import random
from itertools import permutations
from math import dist
def tour_len(P, t): return sum(dist(P[a], P[b]) for a, b in zip(t, t[1:] + t[:1]))
def mst_prim(P):                                   # complete graph, Euclidean weights
    best = {v: (dist(P[0], P[v]), 0) for v in range(1, len(P))}
    children = {v: [] for v in range(len(P))}; total = 0
    while best:
        v = min(best, key=lambda x: best[x][0]); w, u = best.pop(v)
        children[u].append(v); total += w
        for x in best:
            if dist(P[v], P[x]) < best[x][0]: best[x] = (dist(P[v], P[x]), v)
    return children, total
def preorder(children, u=0):                       # doubled tree walk, shortcut
    out = [u]
    for c in children[u]: out += preorder(children, c)
    return out
random.seed(61); worst = 0
for trial in range(100):
    P = [(random.randint(0, 20), random.randint(0, 20)) for _ in range(7)]
    ch, wT = mst_prim(P); tour = preorder(ch)
    opt = min(tour_len(P, [0, *p]) for p in permutations(range(1, 7)))
    assert wT <= opt + 1e-9 and tour_len(P, tour) <= 2 * wT + 1e-9
    worst = max(worst, tour_len(P, tour) / opt)
print("100 random 7-city instances: w(T) <= OPT and tour <= 2 w(T)")
print("worst ratio tour/OPT =", round(worst, 3))

100 random 7-city instances: w(T) <= OPT and tour <= 2 w(T)
worst ratio tour/OPT = 1.32

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

অঙ্ক ১: Kruskal হাতে

Vertex A, B, C, D, E; edge-ওজন AB 1, AC 2, BC 3, CD 4, BD 5, DE 6, CE 7. MST আর তার ওজন বের করুন, আর বাদ পড়া প্রতিটি edge-এর কারণ বলুন।

1. AB 1 নিন; AC 2 নিন (C আলাদা দলে); BC 3 বাদ (cycle A–B–C, 3 সবচেয়ে ভারী)।
2. CD 4 নিন; BD 5 বাদ (cycle B–A–C–D–B, যাতে 1, 2, 4, 5); DE 6 নিন। চারটি edge, n − 1 = 4, শেষ।
3. MST = {AB, AC, CD, DE}, ওজন 1 + 2 + 4 + 6 = 13; CE 7 দেখার দরকারই হয়নি। সব ওজন আলাদা, তাই এটিই একমাত্র MST (scratch-এ ২১টি spanning tree গুনে মেলানো)।

অঙ্ক ২: Spanning tree গোনা

(ক) C₅, (খ) K₅, (গ) wheel W₄ (একটি কেন্দ্র h, চারপাশে বর্গ 0–1–2–3–0, আর h প্রত্যেকের সঙ্গে যুক্ত)।

1. (ক) 5: যেকোনো একটি edge বাদ। (খ) 5³ = 125 (Cayley).
2. (গ) h-এর সারি-কলাম বাদ দিলে বর্গের চারটি vertex থাকে, প্রত্যেকের degree 3: L_h = [3 −1 0 −1; −1 3 −1 0; 0 −1 3 −1; −1 0 −1 3]. Gaussian elimination-এ determinant 45.
3. তিনটিই scratch-এ সব উপসেট গুনে আর determinant দিয়ে মেলানো।

প্রমাণের ভুল ধরুন: “MST-এর পথই সবচেয়ে ছোট পথ”

একজন লিখলেন: “T একটি MST, আর u, v দুটি vertex. ধরুন G-তে u থেকে v-এর পথ Q, T-এর পথ P-এর চেয়ে ছোট। তাহলে T থেকে P সরিয়ে Q বসালে মোট ওজন কমে, যা T-এর সর্বনিম্নতার বিরোধী। তাই MST-এ যেকোনো দুই vertex-এর পথই তাদের সবচেয়ে ছোট পথ।”

ভুল কোথায়: “P সরিয়ে Q বসালে” যা থাকে তা সাধারণত spanning tree নয়: P-এর edge সরালে অন্য vertex-এরা বিচ্ছিন্ন হতে পারে, আর Q যোগ করলে cycle তৈরি হতে পারে। Edge-বদলের lemma শুধু একটি edge বদলের অনুমতি দেয়, তাও fundamental cycle-এর ভেতরে। আর তুলনাও ভুল: MST মোট ওজন কমায়, কোনো একটি জোড়ার দূরত্ব নয়। পাল্টা-উদাহরণ: ত্রিভুজ x–y–z, ওজন xy 2, yz 2, xz 3. MST = {xy, yz}, ওজন 4 (বাকি দুটি tree-র ওজন 5). MST-এ x থেকে z-এর পথ 2 + 2 = 4, অথচ সরাসরি edge 3. সঠিক কথা §৫-এর bottleneck ধর্ম, আর সবচেয়ে ছোট পথের জন্য আলাদা tree লাগে (Dijkstra-র shortest-path tree, পর্ব ৬১)।

৯ · AI-এর যুগে — spanning tree-এর প্রমাণ আর হিসাব যাচাই

MST-এর প্রশ্নে AI সহকারী algorithm-এর ধাপ সাধারণত ঠিক বলে, কিন্তু প্রমাণে সূক্ষ্ম ফাঁক রাখে আর হাতের গণনায় ভুল করে। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

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

• Graph connected কি না আর ওজন আলাদা কি না, শুরুতেই বলা আছে
• Edge-বদলের প্রতিটি ধাপে নতুন edge-সেট সত্যিই spanning tree, তার যুক্তি আছে
• “কোনো একটি MST” আর “প্রতিটি MST” গুলিয়ে যায়নি
• গোনার উত্তর ছোট graph-এ brute force আর Kirchhoff দুভাবেই মিলিয়েছি
• Approximation-এর দাবিতে triangle inequality কোথায় লেগেছে, তা খুঁজে পেয়েছি
• উদ্ধৃত নাম আর সাল বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি