Relation-এর closure আর Warshall-এর algorithm

১ · Closure কী — যত কম যোগ করে ধর্মটি আনা

পর্ব ৫২ “Relation আর তার ধর্ম — reflexive, symmetric, transitive”-এ একটি relation-কে দেখা হয়েছে A × A-এর একটি subset হিসেবে (পর্ব ১৪-এর Cartesian product), আর তার তিনটি প্রধান ধর্ম পরীক্ষা করা হয়েছে। এই পর্বের প্রশ্ন উল্টো দিক থেকে: একটি relation-এ কোনো ধর্ম নেই; তাকে সবচেয়ে কম বদলে ধর্মটি কীভাবে আনা যায়?

পর্ব ৫২-এর তিনটি ধর্ম এক লাইনে মনে করি। A-এর ওপর R হলো reflexive, যদি প্রতিটি a ∈ A-এর জন্য (a, a) ∈ R; symmetric, যদি (a, b) ∈ R হলে (b, a) ∈ R; আর transitive, যদি (a, b) ∈ R আর (b, c) ∈ R হলে (a, c) ∈ R. চতুর্থ একটি ধর্ম, antisymmetric: (a, b) আর (b, a) দুটিই R-এ থাকলে a = b.

শর্ত (গ) খুব কড়া: “সবচেয়ে ছোট” মানে শুধু “এর চেয়ে ছোট আর কিছু নেই” নয়, বরং “বাকি সবার ভেতরে ঢুকে যায়”। তাই closure থাকলে তা একটিই (দুটি থাকলে প্রত্যেকে অন্যটির subset, তাই সমান)। কিন্তু থাকবেই, এমন নিশ্চয়তা নেই। দুটি ব্যর্থতার উদাহরণ দেখি।

• কোনো উপযুক্ত বাড়তি নেই: A = {1, 2} আর R = {(1, 2), (2, 1)}. যেকোনো T ⊇ R-এ (1, 2) আর (2, 1) দুটিই থাকে, অথচ 1 ≠ 2; তাই কোনো superset antisymmetric নয়। জোড়া যোগ করে antisymmetric হওয়া যায় না, কারণ সমস্যাটি একটি জোড়া থাকার জন্য, না থাকার জন্য নয়। তাই সাধারণভাবে “antisymmetric closure” বলে কিছু নেই।
• বাড়তি আছে, কিন্তু সবচেয়ে ছোটটি নেই: ধর্ম P = “অন্তত একটি (a, a) জোড়া আছে”, A = {1, 2}, R = ∅. {(1, 1)} আর {(2, 2)} দুটিই P মানে আর কোনোটি থেকে কিছু বাদ দেওয়া যায় না, কিন্তু কোনোটি অন্যটির subset নয়। তাদের intersection ∅, যাতে P নেই। এখানে closure নেই।

তাহলে কোন ধর্মে closure নিশ্চিত? উত্তর একটি সাধারণ উপপাদ্য, যার প্রমাণ শুধু সেটের intersection (পর্ব ১৫) ব্যবহার করে।

1. পরিবার 𝓕 = {T : R ⊆ T, T-এর P আছে} অশূন্য, কারণ A × A ⊇ R আর (i) অনুযায়ী তার P আছে। — শর্ত (i)
2. c(R) = ⋂𝓕-এর P আছে। — শর্ত (ii)
3. 𝓕-এর প্রতিটি T-তে R আছে, তাই তাদের intersection-এও: R ⊆ c(R). — intersection-এর সংজ্ঞা
4. P ধর্মওয়ালা যেকোনো T ⊇ R নিজেই 𝓕-এর সদস্য, তাই ⋂𝓕 ⊆ T. তিনটি শর্তই মিলল। ∎ — intersection প্রতিটি সদস্যের subset

এবার তিনটি ধর্ম মিলিয়ে দেখি। A × A reflexive, symmetric আর transitive তিনটিই, তাই (i) মেলে। (ii)-এর জন্য transitive-এর প্রমাণটি দেখাই, বাকি দুটি একই ধাঁচের: ধরুন প্রতিটি T_i transitive, আর (a, b), (b, c) ∈ ⋂T_i. তাহলে প্রতিটি i-তে (a, b), (b, c) ∈ T_i, তাই (a, c) ∈ T_i; অর্থাৎ (a, c) ∈ ⋂T_i. Antisymmetric ধর্ম (ii) মানে, কিন্তু (i) মানে না (|A| ≥ 2 হলে A × A antisymmetric নয়), আর ঠিক সেই ফাঁকেই ওপরের প্রথম উদাহরণ পড়েছে। দ্বিতীয় উদাহরণের ধর্মে (i) আছে, কিন্তু (ii) ভেঙেছে।

উপপাদ্যটি অস্তিত্ব দেয়, কিন্তু হিসাবের উপায় দেয় না: সব superset-এর তালিকা করে intersection নেওয়া অবাস্তব। পরের তিনটি অংশে প্রতিটি closure-এর একটি সরাসরি সূত্র বের করব, আর §৩-এর শেষে Python দিয়ে মিলিয়ে দেখব যে সূত্র আর এই সংজ্ঞা সত্যিই একই জিনিস দেয়। দুটি ছোট ফলও সংজ্ঞা থেকে সরাসরি আসে: R-এ আগে থেকেই P থাকলে c(R) = R (R নিজেই সবচেয়ে ছোট), আর তাই c(c(R)) = c(R); দ্বিতীয়বার closure নিলে কিছু বদলায় না।

২ · Reflexive আর symmetric closure — এক লাইনের সূত্র

সেট A-এর diagonal relation Δ = {(a, a) : a ∈ A}, অর্থাৎ “প্রতিটি উপাদান নিজের সঙ্গে”। আর R-এর inverse R⁻¹ = {(b, a) : (a, b) ∈ R}, অর্থাৎ প্রতিটি তীর উল্টো দিকে (পর্ব ১৬-এর inverse function-এর relation রূপ, যা সবসময় থাকে)।

প্রমাণ (reflexive):

1. R ∪ Δ-তে প্রতিটি (a, a) আছে, তাই এটি reflexive; আর R ⊆ R ∪ Δ. — union-এর সংজ্ঞা
2. যেকোনো reflexive T ⊇ R-এ সব (a, a) আছে, অর্থাৎ Δ ⊆ T, আর R ⊆ T; তাই R ∪ Δ ⊆ T. ∎ — দুটি subset-এর union-ও subset

প্রমাণ (symmetric):

1. (x, y) ∈ R ∪ R⁻¹ হলে হয় (x, y) ∈ R, তখন (y, x) ∈ R⁻¹; নয়তো (x, y) ∈ R⁻¹, অর্থাৎ (y, x) ∈ R. দুই ক্ষেত্রেই (y, x) ∈ R ∪ R⁻¹, তাই এটি symmetric. — inverse-এর সংজ্ঞা
2. যেকোনো symmetric T ⊇ R নিন। (a, b) ∈ R হলে (a, b) ∈ T, আর symmetric বলে (b, a) ∈ T; তাই R⁻¹ ⊆ T, আর R ∪ R⁻¹ ⊆ T. ∎ — T-এর symmetry

0-1 matrix-এর ভাষায় (পর্ব ১৯) দুটিই এক নজরে: M_r(R) = M_R ∨ I (কর্ণে সব 1 বসানো), আর M_s(R) = M_R ∨ M_R^T (matrix আর তার transpose-এর ঘরে ঘরে OR). Digraph ছবিতে reflexive closure প্রতিটি বিন্দুতে একটি loop যোগ করে, আর symmetric closure প্রতিটি একমুখী তীরের পাশে উল্টো তীর।

উদাহরণ। A = {1, 2, 3, 4}, R = {(1, 2), (2, 2), (3, 4), (4, 1)}. r(R) = R ∪ {(1, 1), (3, 3), (4, 4)}: (2, 2) আগেই ছিল, তাই নতুন তিনটি, মোট ৭টি জোড়া। s(R) = R ∪ {(2, 1), (4, 3), (1, 4)}: (2, 2)-এর উল্টো সে নিজেই, তাই নতুন তিনটি, মোট ৭টি। দুটিই scratch-এ Python দিয়ে মেলানো। সাধারণভাবে |r(R)| = |R| + (কর্ণের ফাঁকা ঘর), আর |s(R)| = |R| + (যেসব জোড়ার উল্টোটি নেই, তাদের সংখ্যা)।

এই দুটি closure সহজ, কারণ নতুন জোড়া যোগ করলে নতুন কোনো দাবি তৈরি হয় না: (a, a) যোগ করলে আর কিছু যোগ করতে হয় না, (b, a) যোগ করলে তার উল্টো (a, b) তো আগেই আছে। Transitive closure-এ তা সত্য নয়। (1, 3) যোগ করলে, আর (3, 4) থাকলে, এখন (1, 4)-ও চাই; একটি যোগ আরেকটি যোগ ডেকে আনে। তাই transitive closure-এর জন্য একটি নতুন ধারণা লাগে: পথ।

৩ · Path আর connectivity relation — transitive closure = R*

A-এর ওপর R-কে একটি directed graph (digraph) হিসেবে আঁকা যায়: A-এর প্রতিটি উপাদান একটি বিন্দু, আর (a, b) ∈ R হলে a থেকে b-তে একটি তীর। বাজারঘরের চারটি গুদাম নিন: 1 = ঢাকা, 2 = গাজীপুর, 3 = ময়মনসিংহ, 4 = নেত্রকোনা। সরাসরি ট্রাকের relation

R = {(1, 2), (2, 1), (2, 3), (3, 4), (4, 3)}

অর্থাৎ ঢাকা ⇄ গাজীপুর, গাজীপুর → ময়মনসিংহ, আর ময়মনসিংহ ⇄ নেত্রকোনা। ময়মনসিংহ থেকে গাজীপুরে ফেরার কোনো ট্রাক নেই। এই পর্বের বেশিরভাগ হিসাব এই relation-এ।

1. Basis n = 1: দৈর্ঘ্য ১-এর path মানে একটি তীর (a, b) ∈ R = R¹. — সংজ্ঞা
2. Inductive step: n-এর জন্য সত্য ধরি। (a, c) ∈ Rⁿ⁺¹ ⇔ কোনো b-তে (a, b) ∈ R আর (b, c) ∈ Rⁿ ⇔ একটি তীর a → b, তারপর b থেকে c-তে দৈর্ঘ্য n-এর path (hypothesis) ⇔ a থেকে c-তে দৈর্ঘ্য n + 1-এর path (প্রথম তীরটি আলাদা করে)। ∎ — পর্ব ১০-এর induction

এটি পর্ব ১৯-এর উপপাদ্য ৪.২-এর relation রূপ, যেখানে একই কথা Boolean power M_R^[n] দিয়ে বলা হয়েছিল। তাই R* মানে “কোনো দৈর্ঘ্যের path দিয়ে পৌঁছানো যায়”, অর্থাৎ reachability.

1. R = R¹ ⊆ R*. — union-এর সংজ্ঞা
2. R* transitive: (a, b) ∈ R^m আর (b, c) ∈ R^k হলে lemma ৩.২ অনুযায়ী a থেকে b-তে দৈর্ঘ্য m-এর আর b থেকে c-তে দৈর্ঘ্য k-এর path আছে; জোড়া দিলে a থেকে c-তে দৈর্ঘ্য m + k-এর path, তাই (a, c) ∈ R^m+k ⊆ R*. — path জোড়া দেওয়া
3. যেকোনো transitive S ⊇ R নিন। দাবি: প্রতিটি n ≥ 1-এ Rⁿ ⊆ S. n = 1-এ এটি R ⊆ S. n-এ সত্য ধরলে, (a, c) ∈ Rⁿ⁺¹ মানে কোনো b-তে (a, b) ∈ R ⊆ S আর (b, c) ∈ Rⁿ ⊆ S, আর S transitive বলে (a, c) ∈ S. — n-এর ওপর induction
4. তাই R* = ⋃Rⁿ ⊆ S. ধাপ ১–৩ মিলিয়ে R* হলো R ধারণকারী সবচেয়ে ছোট transitive relation, অর্থাৎ t(R) = R*. ∎ — সংজ্ঞা ১.১

ধাপ ৩-এর একটি বিশেষ রূপ পর্ব ৫২-এর উপপাদ্য: R নিজে transitive হলে (S = R নিয়ে) সব Rⁿ ⊆ R, তাই R* = R. ছবিতে দেখুন: ঢাকা থেকে ঢাকা (loop) কেন closure-এ এল? ঢাকা → গাজীপুর → ঢাকা, দৈর্ঘ্য ২-এর একটি cycle. আর ময়মনসিংহ থেকে গাজীপুর কেন এল না? কারণ ময়মনসিংহ থেকে যে দুটি গুদামে যাওয়া যায় (নেত্রকোনা আর নিজে), তাদের কোনোটি থেকেই ওপরের সারিতে তীর নেই।

উপপাদ্য ১.২ আর ৩.৩ দুটি সম্পূর্ণ ভিন্ন পথে একই t(R)-কে বর্ণনা করে: একটি “সব transitive superset-এর intersection”, অন্যটি “সব দৈর্ঘ্যের path-এর union”. ছোট সেটে দুটিকে সরাসরি মেলানো যায়। নিচের ব্লক A = {1, 2, 3}-এর ওপর সব 2⁹ = 512টি relation নিয়ে প্রতিটির জন্য দুটি পথে হিসাব করে, আর antisymmetric ধর্মের ব্যর্থতাও গোনে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে; পরের ব্লকগুলো দ্রুত চলে।

from itertools import product, combinations
A = (1, 2, 3)
pairs = list(product(A, A))                        # 9 pairs, 2^9 relations
rels = [frozenset(c) for k in range(10) for c in combinations(pairs, k)]
def compose(R, S): return {(a, d) for a, b in R for c, d in S if b == c}
def transitive(R): return compose(R, R) <= R
def antisym(R): return all(a == b or (b, a) not in R for a, b in R)
TRANS = [T for T in rels if transitive(T)]
print("relations:", len(rels), "| transitive ones:", len(TRANS))

ok = 0
for R in rels:
    smallest = frozenset(pairs)                    # A x A is transitive
    for T in TRANS:
        if R <= T:
            smallest &= T                          # intersect all supersets
    R2 = compose(R, R); R3 = compose(R2, R)
    ok += smallest == R | R2 | R3 and transitive(smallest)
print("intersection == R U R^2 U R^3 (and transitive):", ok, "of", len(rels))

ANTI = [S for S in rels if antisym(S)]
none = sum(1 for R in rels if not any(R <= S for S in ANTI))
print("antisymmetric relations:", len(ANTI),
      "| relations with NO antisymmetric superset:", none)
R = frozenset({(1, 2), (2, 1)})
print("example", sorted(R), "antisymmetric supersets:",
      sum(R <= S for S in ANTI))

relations: 512 | transitive ones: 171
intersection == R U R^2 U R^3 (and transitive): 512 of 512
antisymmetric relations: 216 | relations with NO antisymmetric superset: 296
example [(1, 2), (2, 1)] antisymmetric supersets: 0

৪ · সসীম সেটে n ধাপই যথেষ্ট — Boolean power পদ্ধতি

R* একটি অসীম union, কিন্তু সসীম সেটে অসীম পর্যন্ত যেতে হয় না। কারণটি pigeonhole principle (পর্ব ৩২): দীর্ঘ পথে কোনো গুদাম দুবার আসতে বাধ্য, আর মাঝের ঘোরাটুকু কেটে দিলে পথ ছোট হয়।

1. (a, b) ∈ R* হলে path আছে; তাদের মধ্যে সবচেয়ে ছোটটি নিন, দৈর্ঘ্য m, ক্রম x₀, …, x_m. — well-ordering, পর্ব ১১
2. a ≠ b ধরুন আর ধরুন m ≥ n. তাহলে x₀, …, x_m-এ m + 1 ≥ n + 1টি অবস্থান, কিন্তু উপাদান মাত্র n-টি; তাই কোনো p < q-তে x_p = x_q. — pigeonhole
3. x_p+1, …, x_q অংশটি কেটে দিলে x₀, …, x_p, x_q+1, …, x_m একটি path, দৈর্ঘ্য m − (q − p) < m; শুরু a আর শেষ b ভিন্ন বলে দৈর্ঘ্য ≥ 1. এটি “সবচেয়ে ছোট”-এর বিরোধী, তাই m ≤ n − 1. — proof by contradiction
4. a = b হলে শুধু x₀, …, x_m−1 (m-টি অবস্থান) দেখুন। m > n হলে এদের মধ্যে x_p = x_q, 0 ≤ p < q ≤ m − 1; একই কাটায় দৈর্ঘ্য m − (q − p) ≥ 1 থাকে (কারণ q − p ≤ m − 1), আবার বিরোধ। তাই m ≤ n. — একই যুক্তি
5. দুই ক্ষেত্রেই m ≤ n, আর lemma ৩.২ অনুযায়ী (a, b) ∈ R^m ⊆ R ∪ ⋯ ∪ Rⁿ. উল্টো অন্তর্ভুক্তি সংজ্ঞা থেকেই। ∎

সীমা n আর কমানো যায় না: n উপাদানের একটি চক্র 1 → 2 → ⋯ → n → 1-এ (1, 1) প্রথম আসে ঠিক Rⁿ-এ। নিচের stepper n = 3-এ ঠিক এটিই দেখায়, 0-1 matrix আর Boolean product দিয়ে: M_R^k+1 = M_R^k ⊙ M_R, আর union মানে ঘরে ঘরে OR.

1R: 1→2, 2→3, 3→12R² = R ∘ R, সারি ধরে3R³ = R² ∘ R4R ∨ R² ∨ R³5R⁴ = R: নতুন কিছু নেই6সীমা n কেন দরকার

খরচ। উপপাদ্য ৪.১ থেকে সরাসরি একটি algorithm: M_R* = M_R ∨ M_R^[2] ∨ ⋯ ∨ M_R^[n]. প্রতিটি Boolean product-এ n²টি ঘর, প্রতিটি ঘরে n-টি AND আর n − 1টি OR, অর্থাৎ n²(2n − 1)টি bit-অপারেশন। এমন product n − 1টি, আর join n − 1টি (প্রতিটি n²টি OR). মোট

(n − 1) · n²(2n − 1) + (n − 1) · n² = 2n³(n − 1)

যা O(n⁴). n = 4-এ 384, n = 30-এ ১৫ লক্ষের বেশি। পর্ব ১৯-এর ভাবনার প্রশ্নে বারবার বর্গ করে n³ log n-এ নামানোর কৌশল আছে; কিন্তু আরও সরল আর দ্রুত একটি উপায় আছে, যা ধাপ গোনে না, মাঝের স্টপ গোনে।

৫ · Warshall-এর algorithm — মাঝের স্টপ একটি একটি করে খোলা

একটি path x₀, x₁, …, x_m-এর interior vertex (মাঝের বিন্দু) হলো x₁, …, x_m−1: শুরু আর শেষ বাদে যেসব গুদাম হয়ে মাল যায়। দৈর্ঘ্য ১-এর path-এ (একটি সরাসরি তীর) কোনো মাঝের বিন্দু নেই।

সূত্রটির অর্থ §৬-এ প্রমাণ হবে: W_k[i][j] = 1 ঠিক তখন, যখন i থেকে j-তে এমন একটি path আছে, যার সব মাঝের বিন্দু {1, …, k}-এর মধ্যে। আগে আমাদের গুদামে হাতে চালাই। কলাম-ক্রম ঢাকা, গাজীপুর, ময়মনসিংহ, নেত্রকোনা।

1W₀ = M_R (সরাসরি ট্রাক)2k = 1: ঢাকা হাব3k = 2: গাজীপুর হাব4k = 3: ময়মনসিংহ হাব5k = 4: নেত্রকোনা হাব6W₄ = M_R*

এবার একই হিসাব Python-এ, প্রতিটি W_k আর তাতে নতুন জোড়াসহ। শেষে ফলটিকে R ∪ R² ∪ R³ ∪ R⁴-এর সঙ্গে মেলানো হয়েছে (DHK = ঢাকা, GZP = গাজীপুর, MYM = ময়মনসিংহ, NET = নেত্রকোনা)।

names = ["DHK", "GZP", "MYM", "NET"]      # vertices 1, 2, 3, 4
R = {(1, 2), (2, 1), (2, 3), (3, 4), (4, 3)}
n = 4
W = [[1 if (i, j) in R else 0 for j in range(1, n + 1)]
     for i in range(1, n + 1)]

def show(W, k, new):
    print(f"W{k}:", "  ".join("".join(map(str, row)) for row in W),
          " new:", ", ".join(new) or "-")

show(W, 0, [])
for k in range(n):                        # allow vertex k+1 as interior
    new = []
    for i in range(n):
        for j in range(n):
            if not W[i][j] and W[i][k] and W[k][j]:
                W[i][j] = 1               # in place is safe (see the proof)
                new.append(f"{names[i]}->{names[j]}")
    show(W, k + 1, new)

closure = {(i + 1, j + 1) for i in range(n) for j in range(n) if W[i][j]}
R2 = {(a, d) for (a, b) in R for (c, d) in R if b == c}
R3 = {(a, d) for (a, b) in R2 for (c, d) in R if b == c}
R4 = {(a, d) for (a, b) in R3 for (c, d) in R if b == c}
print("pairs:", len(R), "->", len(closure))
print("equals R U R2 U R3 U R4:", closure == R | R2 | R3 | R4)

W0: 0100  1010  0001  0010  new: -
W1: 0100  1110  0001  0010  new: GZP->GZP
W2: 1110  1110  0001  0010  new: DHK->DHK, DHK->MYM
W3: 1111  1111  0001  0011  new: DHK->NET, GZP->NET, NET->NET
W4: 1111  1111  0011  0011  new: MYM->MYM
pairs: 5 -> 12
equals R U R2 U R3 U R4: True

৬ · Warshall-এর সঠিকতার প্রমাণ আর খরচ

Algorithm-টির হৃদয় একটি loop invariant (পর্ব ১৩): বাইরের loop-এর প্রতিটি k-এর পরে একটি নির্দিষ্ট দাবি সত্য থাকে।

প্রমাণ (k-এর ওপর induction):

1. Basis k = 0: {1, …, 0} = ∅, তাই শর্তটি মানে “কোনো interior vertex নেই”, অর্থাৎ path-টি একটি তীর (i, j) ∈ R, অর্থাৎ M_R[i][j] = W₀[i][j] = 1. — সংজ্ঞা
2. Hypothesis: k − 1-এর জন্য দাবি সব i, j-তে সত্য। দুই দিক দেখাই। — অনুমান
3. (⇐) W_k−1[i][j] = 1 হলে hypothesis অনুযায়ী interior {1, …, k − 1}-এ এমন path আছে, যা {1, …, k}-তেও পড়ে। আর W_k−1[i][k] = W_k−1[k][j] = 1 হলে i থেকে k আর k থেকে j-তে দুটি path, interior {1, …, k − 1}-এ; জোড়া দিলে i থেকে j-তে path, যার interior-এ শুধু ওগুলো আর k. — hypothesis, path জোড়া
4. (⇒) i থেকে j-তে interior {1, …, k}-এ একটি path x₀, …, x_m নিন। k যদি কোনো interior অবস্থানে না আসে, interior {1, …, k − 1}-এ, আর hypothesis অনুযায়ী W_k−1[i][j] = 1. — ক্ষেত্র ১
5. k যদি interior-এ আসে, ধরুন প্রথমবার অবস্থান p-তে আর শেষবার অবস্থান q-তে (1 ≤ p ≤ q ≤ m − 1). x₀, …, x_p হলো i থেকে k-তে দৈর্ঘ্য p ≥ 1-এর path, যার interior x₁, …, x_p−1-এ k নেই, তাই সেগুলো {1, …, k − 1}-এ; একইভাবে x_q, …, x_m হলো k থেকে j-তে। Hypothesis অনুযায়ী W_k−1[i][k] = W_k−1[k][j] = 1. — ক্ষেত্র ২: প্রথম আর শেষ k-তে কাটা
6. দুই ক্ষেত্রেই সূত্রের ডান দিক 1, তাই W_k[i][j] = 1. Induction সম্পূর্ণ। k = n-এ শর্তটি কোনো বাধা নয়, তাই W_n[i][j] = 1 ⇔ কোনো path আছে ⇔ (i, j) ∈ R* (lemma ৩.২)। ∎ — উপপাদ্য ৩.৩

ধাপ ৫-এ “প্রথম আর শেষ” বাছাই জরুরি: path-এ k একাধিকবার আসতে পারে, আর তখন মাঝের যেকোনো দুই k-এর মধ্যে কাটলে বাঁ বা ডান টুকরোর ভেতরে k থেকে যেতে পারত। প্রথম k-এর আগের অংশে আর শেষ k-এর পরের অংশে k থাকা অসম্ভব। i = k হলেও যুক্তি চলে: তখন প্রথম টুকরোটি k থেকে k-তে একটি cycle.

1. j = k বসালে সূত্রটি W_k−1[i][k] ∨ (W_k−1[i][k] ∧ W_k−1[k][k]). — প্রতিস্থাপন
2. Absorption law x ∨ (x ∧ y) = x (পর্ব ০৩) অনুযায়ী এটি W_k−1[i][k]. সারির ক্ষেত্রে i = k বসিয়ে একই যুক্তি। ∎ — absorption

তাই ধাপ k-তে যে ঘরগুলো পড়া হয় (সারি k আর কলাম k), সেগুলো ওই ধাপে লেখা হয় না; একটি matrix-এই সব কাজ চলে, বাড়তি মেমরি লাগে না।

খরচ। n-টি ধাপ, প্রতিটিতে n²টি ঘর, প্রতিটি ঘরে একটি AND আর একটি OR: মোট 2n³, অর্থাৎ O(n³). n = 4-এ 128, যেখানে Boolean power পদ্ধতিতে 384; n বাড়লে অনুপাত n − 1 গুণ। প্রতিটি সারিকে একটি পূর্ণসংখ্যার bit হিসেবে রাখলে (পর্ব ১৯-এর আলোচনা) “সারি i OR সারি k” একটি অপারেশন হয়, যা নিচের ব্লকে ব্যবহার করা হয়েছে।

Reachability-র তৃতীয় একটি পথও আছে: প্রতিটি বিন্দু থেকে একটি breadth-first search (BFS) চালানো (DSA কোর্সের পর্ব ৪০)। নিচের ব্লক এলোমেলো digraph-এ (n ≤ 30, প্রতিটি সম্ভাব্য তীর 1.5/n সম্ভাবনায়, seed স্থির) তিনটি পদ্ধতির ফল মেলায়, আর পাঠ্যবইয়ের দুই matrix পদ্ধতির bit-অপারেশনের সংখ্যা সূত্র থেকে ও BFS-এর তীর-পরীক্ষা সরাসরি গুনে দেখায়।

import random
from functools import reduce
rng = random.Random(54)
def by_powers(rows, n):            # R U R^2 U ... U R^n, rows are bitsets
    P, acc = rows[:], rows[:]
    for _ in range(n - 1):         # P = R^m  ->  R^m o R = R^(m+1)
        P = [reduce(int.__or__, (rows[t] for t in range(n) if p >> t & 1), 0)
             for p in P]
        acc = [a | p for a, p in zip(acc, P)]
    return acc
def warshall(W, n):                # W: a copy of the rows
    for k in range(n):
        for i in range(n):         # i reaches k: add everything k reaches
            if W[i] >> k & 1: W[i] |= W[k]
    return W
def by_bfs(adj, n):
    res, checks = [], 0
    for s in range(n):
        seen, q = 0, [s]
        for u in q:                # q grows while we walk it: BFS order
            for v in adj[u]:
                checks += 1
                if not seen >> v & 1: seen |= 1 << v; q.append(v)
        res.append(seen)
    return res, checks
for n in (5, 10, 20, 30):
    agree = checks = 0
    for _ in range(25):
        adj = [[v for v in range(n) if v != u and rng.random() < 1.5 / n]
               for u in range(n)]
        rows = [sum(1 << v for v in a) for a in adj]
        b, c = by_bfs(adj, n); checks += c
        agree += by_powers(rows, n) == warshall(rows[:], n) == b
    print(f"n={n:2} agree {agree}/25 | powers {2*n**3*(n-1):>7}"
          f" | warshall {2*n**3:>5} | bfs checks {checks // 25}")

n= 5 agree 25/25 | powers    1000 | warshall   250 | bfs checks 20
n=10 agree 25/25 | powers   18000 | warshall  2000 | bfs checks 75
n=20 agree 25/25 | powers  304000 | warshall 16000 | bfs checks 250
n=30 agree 25/25 | powers 1566000 | warshall 54000 | bfs checks 496

৭ · Closure-এর ক্রম গুরুত্বপূর্ণ — equivalence closure

প্রায়ই একাধিক ধর্ম একসঙ্গে চাই। যেমন বাজারঘর জানতে চায়, কোন গ্রাহক-অ্যাকাউন্টগুলো “একই ব্যক্তির”: একই ফোন নম্বর বা একই ঠিকানা থাকলে দুটি অ্যাকাউন্ট যুক্ত, আর এই যোগাযোগ ধরে ধরে যতদূর যাওয়া যায়। এর জন্য symmetric আর transitive দুটিই চাই। প্রশ্ন: আগে কোনটি নেব? উত্তর: ক্রমে ফল বদলে যায়।

1R = {(1,2), (3,2)}2s(R)3t(s(R))4t(R)5s(t(R))6তুলনা

উদাহরণটি কাকতালীয় নয়। তিনটি সাধারণ উপপাদ্য পুরো ছবিটি দেয়। প্রথমে একটি সহায়ক তথ্য: closure monotone, অর্থাৎ R ⊆ S হলে c(R) ⊆ c(S); কারণ c(S) একটি P ধর্মওয়ালা relation, যাতে R আছে, তাই সংজ্ঞা ১.১(গ) অনুযায়ী c(R) ⊆ c(S).

1. (ক) (a, b) ∈ t(R) = R* হলে a থেকে b-তে একটি path x₀, …, x_m আছে। R symmetric বলে প্রতিটি (x_i, x_i−1) ∈ R, তাই উল্টো ক্রম x_m, …, x₀ হলো b থেকে a-তে path, আর (b, a) ∈ R*. — উপপাদ্য ৩.৩, path উল্টানো
2. (খ) T = t(s(R)) transitive, আর R ⊆ s(R) ⊆ T; তাই t(R) ⊆ T. (ক) অনুযায়ী T symmetric (কারণ s(R) symmetric), আর তাতে t(R) আছে, তাই s(t(R)) ⊆ T. Stepper-এ সমতা ভেঙেছে। — closure-এর minimality
3. (গ) প্রথমে, t(R) ∪ Δ transitive: (a, b), (b, c) তাতে থাকলে কোনোটি Δ-তে হলে (a, c) অন্যটিরই সমান, আর দুটিই t(R)-এ হলে (a, c) ∈ t(R). এতে R ∪ Δ আছে, তাই t(r(R)) ⊆ t(R) ∪ Δ = r(t(R)). — ক্ষেত্র ভাগ, minimality
4. উল্টো দিকে Δ ⊆ R ∪ Δ ⊆ t(R ∪ Δ), আর monotone বলে t(R) ⊆ t(R ∪ Δ); তাই r(t(R)) = t(R) ∪ Δ ⊆ t(r(R)). ∎ — monotonicity

1. r(R) reflexive, s(r(R)) reflexive আর symmetric (জোড়া যোগে reflexivity হারায় না), আর t(s(r(R))) তিনটিই: reflexive কারণ superset, symmetric উপপাদ্য ৭.১(ক) অনুযায়ী, transitive সংজ্ঞায়। — ৭.১(ক)
2. যেকোনো equivalence E ⊇ R reflexive, তাই E ⊇ r(R); symmetric, তাই E ⊇ s(r(R)); transitive, তাই E ⊇ t(s(r(R))). ∎ — প্রতিটি ধাপে minimality

উপপাদ্য ৭.১(গ) বলে r-কে যেকোনো জায়গায় সরানো যায়, কিন্তু t-কে s-এর আগে নিলে ভুল হতে পারে। Equivalence relation আর তার শ্রেণি (partition) নিয়ে পুরো আলোচনা পরের পর্ব ৫৫ “Equivalence relation আর partition”-এ; সেখানে এই closure দিয়েই শ্রেণি বানানো হবে, আর পর্ব ৫১-এর orbit-গুলোও এমন শ্রেণি। নিচের ব্লক উপপাদ্যগুলো এলোমেলো ২০০০টি relation-এ পরীক্ষা করে।

import random
from itertools import product
A = range(1, 5)
def r(R): return R | {(a, a) for a in A}           # reflexive closure
def s(R): return R | {(b, a) for (a, b) in R}      # symmetric closure
def t(R):                                          # transitive (Warshall)
    T = set(R)
    for k in A:
        T |= {(i, j) for i, j in product(A, A) if (i, k) in T and (k, j) in T}
    return T
def sym(R): return R == s(R)
def trans(R): return all((a, d) in R for a, b in R for c, d in R if b == c)

R = {(1, 2), (3, 2)}
print("s(t(R)):", sorted(s(t(R))), "transitive:", trans(s(t(R))))
print("t(s(R)) has", len(t(s(R))), "pairs, symmetric:", sym(t(s(R))))

rng = random.Random(2026)
pairs = list(product(A, A))
differ = subset = rt_tr = rs_sr = ts_sym = 0
for _ in range(2000):
    R = {p for p in pairs if rng.random() < 0.2}
    differ += s(t(R)) != t(s(R))
    subset += s(t(R)) <= t(s(R))
    rt_tr += r(t(R)) == t(r(R))
    rs_sr += r(s(R)) == s(r(R))
    ts_sym += sym(t(s(R)))
print("of 2000 random R on {1,2,3,4}:")
print(" st != ts:", differ, "| st <= ts:", subset, "| ts symmetric:", ts_sym)
print(" rt == tr:", rt_tr, "| rs == sr:", rs_sr)

s(t(R)): [(1, 2), (2, 1), (2, 3), (3, 2)] transitive: False
t(s(R)) has 9 pairs, symmetric: True
of 2000 random R on {1,2,3,4}:
 st != ts: 1667 | st <= ts: 2000 | ts symmetric: 2000
 rt == tr: 2000 | rs == sr: 2000

৮ · প্রয়োগ, পরীক্ষার অঙ্ক আর একটি ভুল যুক্তি

প্রয়োগ ১: ডেলিভারির reachability আর ফেরার পথ

W₄-এর সারি পড়লে প্রতিটি গুদাম থেকে কোথায় মাল পাঠানো যায়, আর কলাম পড়লে কোথা থেকে মাল আসতে পারে। কর্ণের ঘর (i, i) = 1 মানে i থেকে বেরিয়ে আবার i-তে ফেরার একটি পথ আছে, অর্থাৎ ফেরত পণ্য (return) একই রুটে ফেরানো সম্ভব। দুটি গুদাম i আর j পরস্পর পৌঁছানো যায় (R*-এ (i, j) আর (j, i) দুটিই) এমন দলগুলো হলো {ঢাকা, গাজীপুর} আর {ময়মনসিংহ, নেত্রকোনা}; graph তত্ত্বে এদের বলে strongly connected component (DSA কোর্সের পর্ব ৪৬), আর connectivity নিয়ে বিস্তারিত পর্ব ৫৯ “Connectivity — path, component, cut vertex আর Menger-এর ধারণা”-এ। দূরত্ব বা খরচসহ সবচেয়ে ছোট পথ চাইলে একই তিন-loop কাঠামোয় ∨, ∧-এর জায়গায় min আর + বসে: সেটিই Floyd–Warshall algorithm (DSA কোর্সের পর্ব ৪৪)।

প্রয়োগ ২: dependency closure আর cycle ধরা

বাজারঘরের অর্ডার-প্রসেসিংয়ে কাজগুলোর একটি dependency graph আছে: (x, y) মানে “x শুরুর আগে y শেষ হতে হবে”। যেমন invoice → payment, payment → stock-check, packing → stock-check, delivery → packing. কোনো কাজের আগে মোট কী কী শেষ হতে হবে, তা transitive closure-এর সারি: delivery-র আগে packing আর stock-check. নিজেকেসহ গুনতে চাইলে reflexive-transitive closure r(t(R)) = R* ∪ Δ, যাকে অনেক বইয়ে reflexive-transitive closure বলে। সফটওয়্যার build system আর package manager একই হিসাব করে: একটি package-এর “transitive dependency” মানে এই closure-এর সারি।

একটি সহজ কিন্তু কাজের উপপাদ্য: R-এ কোনো cycle আছে ⇔ t(R)-এর কর্ণে অন্তত একটি 1 আছে। প্রমাণ: (a, a) ∈ R* মানে lemma ৩.২ অনুযায়ী a থেকে a-তে দৈর্ঘ্য ≥ 1-এর path, যা সংজ্ঞায় একটি cycle; উল্টোটিও একই কারণে। Dependency-তে cycle মানে কাজগুলো কখনো শুরুই করা যাবে না (x-এর আগে y, y-এর আগে x), তাই build system এটিকে ত্রুটি হিসেবে জানায়। Cycle না থাকলে কাজগুলোকে একটি সারিতে সাজানো যায়, যা topological sort (DSA কোর্সের পর্ব ৪২, আর গাণিতিক দিক পর্ব ৫৬ “Partial order, Hasse diagram, topological sort আর lattice”-এ)।

অঙ্ক ১: Warshall হাতে

A = {1, 2, 3, 4}, R = {(1, 3), (2, 1), (3, 2), (3, 4), (4, 1)}. Warshall দিয়ে t(R) বের করুন।

1. W₀ = M_R: সারিগুলো 0010, 1000, 0101, 1000.
2. k = 1: কলাম ১-এ 1 আছে সারি 2 আর 4-এ; দুটির সঙ্গেই সারি 1 (0010) OR: সারি 2 = 1010, সারি 4 = 1010. W₁: 0010, 1010, 0101, 1010.
3. k = 2: কলাম ২-এ 1 শুধু সারি 3-এ; সারি 3 = 0101 ∨ 1010 = 1111. W₂: 0010, 1010, 1111, 1010.
4. k = 3: কলাম ৩-এ চারটি সারিতেই 1; প্রতিটির সঙ্গে সারি 3 = 1111 OR, তাই W₃ সব 1. k = 4-এ আর কিছু বদলায় না।
5. উত্তর: t(R) = A × A, ১৬টি জোড়া। কারণ 1 → 3 → 2 → 1 একটি cycle, যাতে 1, 2, 3 আছে, আর 3 ⇄ 4 পথ (3 → 4 → 1 → 3) 4-কেও চক্রে আনে। (scratch-এ Python দিয়ে মেলানো।)

অঙ্ক ২: অপারেশনের হিসাব

১০টি গুদামের relation-এর transitive closure Boolean power দিয়ে আর Warshall দিয়ে করতে কতগুলো bit-অপারেশন লাগে? Boolean power: 2n³(n − 1) = 2 · 1000 · 9 = 18000. Warshall: 2n³ = 2000. অনুপাত 9 = n − 1 (তুলনার ব্লকের n=10 সারির সঙ্গে মেলে)।

অঙ্ক ৩: closure-এর জোড়া গোনা

A = {1, 2, 3}, R = {(1, 2), (2, 3), (3, 1)}. |r(R)|, |s(R)|, |t(R)| কত? r(R)-এ R-এর ৩টি আর কর্ণের ৩টি, মোট ৬. s(R)-এ প্রতিটি তীরের উল্টো নতুন, মোট ৬. t(R): §৪-এর stepper অনুযায়ী R ∪ R² ∪ R³ = A × A, মোট ৯.

যুক্তির ভুল ধরুন: “আগে transitive, তারপর symmetric”

একজন লিখলেন: “R-এর equivalence closure পেতে আগে reflexive, তারপর transitive, শেষে symmetric closure নিই: s(t(r(R))). তিনটি ধর্মই যোগ হলো, তাই এটি equivalence relation.” R = {(1, 2), (3, 2)}, A = {1, 2, 3}-এ দেখি।

ভুল কোথায়: “তিনটি ধর্মই যোগ হলো” কথাটি মিথ্যা, কারণ শেষের symmetric closure নতুন তীর যোগ করে transitive ধর্ম ভাঙতে পারে। এখানে r(R) = R ∪ Δ, t(r(R)) = R ∪ Δ (কোনো নতুন path নেই), আর s(t(r(R))) = Δ ∪ {(1, 2), (2, 1), (3, 2), (2, 3)}, ৭টি জোড়া। এতে (1, 2) আর (2, 3) আছে, কিন্তু (1, 3) নেই: transitive নয়। সঠিক ক্রম t(s(r(R))) দেয় পুরো A × A, ৯টি জোড়া (দুটিই scratch-এ Python দিয়ে মেলানো)। শিক্ষা: “প্রতিটি ধাপ একটি ধর্ম যোগ করে” যথেষ্ট নয়; দেখাতে হয় যে পরের ধাপ আগের ধর্ম নষ্ট করে না। r আর s জোড়া যোগ করে transitivity নষ্ট করতে পারে, কিন্তু t symmetry বা reflexivity নষ্ট করে না (উপপাদ্য ৭.১(ক))।

৯ · AI-এর যুগে — closure আর Warshall-এর উত্তর যাচাই

Closure-এর হিসাবে AI সহকারী সাধারণত সূত্র ঠিক বলে, কিন্তু হাতে হিসাবের মাঝপথে বা প্রমাণে ভুল করে, আর ভুলটি আত্মবিশ্বাসী ভাষায় আসে। এই বিষয়ের কয়েকটি নিয়মিত ভুল:

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

• প্রতিটি W_k-এ শুধু কলাম k-এ 1 থাকা সারিগুলোই বদলেছে কি না দেখেছি
• W_k-এর সারি k আর কলাম k আগের মতোই আছে কি না মিলিয়েছি (lemma ৬.২)
• ফলটি transitive কি না নিজে পরীক্ষা করেছি, আর R-এর সব জোড়া তাতে আছে কি না দেখেছি
• ছোট একটি চক্রে বা brute force-এ (R ∪ ⋯ ∪ Rⁿ) উত্তর মিলিয়েছি
• একাধিক closure-এর প্রশ্নে ক্রম (t শেষে) ঠিক আছে কি না দেখেছি
• প্রমাণে প্রতিটি ধাপের কারণ আর প্রতিটি উপপাদ্যের শর্ত লেখা আছে কি না দেখেছি

Warshall-এর হিসাব যাচাইয়ের সবচেয়ে সস্তা উপায় দুটি স্বাধীন পথ: Warshall আর BFS, বা Warshall আর R ∪ ⋯ ∪ Rⁿ. দুটি একই ফল দিলে তবেই ভরসা করুন; আর প্রমাণের ক্ষেত্রে invariant-টি নিজে লিখে দেখুন, AI-এর যুক্তি সেই invariant ধরে চলছে কি না।