Tree — ধর্ম, rooted tree আর m-ary tree-এর হিসাব

১ · Tree আর forest — cycle-হীন connected graph

এই পর্বে graph মানে সসীম undirected simple graph G = (V, E); n = |V| হলো vertex-সংখ্যা আর m = |E| edge-সংখ্যা। Path, cycle, connected graph আর component-এর সংজ্ঞা পর্ব ৫৯ “Connectivity — path, component, cut vertex আর Menger-এর ধারণা”-এ আছে; সেখানে প্রমাণিত দুটি তথ্য আমরা বারবার ব্যবহার করব।

সবুজ vertex-গুলো leaf. লক্ষ করুন, বাঁয়ের tree-তে তিনটি leaf, আর মাঝের forest-এর দুটি tree-এর প্রতিটিতে অন্তত দুটি leaf. এটি কাকতাল নয়।

প্রমাণ (সবচেয়ে লম্বা path দিয়ে):

1. Tree T connected আর n ≥ 2, তাই অন্তত একটি edge আছে। T-এর সব path-এর মধ্যে সবচেয়ে বেশি edge-ওয়ালা একটি নিন: P = v₀ v₁ … v_k, k ≥ 1. — সসীম graph-এ path সসীম সংখ্যক
2. ধরুন v₀-এর v₁ ছাড়া আরেকটি প্রতিবেশী w আছে। w যদি P-এর কোনো v_j (j ≥ 2) হয়, তবে v₀ v₁ … v_j v₀ একটি cycle, যা tree-তে অসম্ভব। — acyclic
3. w যদি P-এ না থাকে, তবে w v₀ v₁ … v_k একটি path, যা P-এর চেয়ে লম্বা; এটিও অসম্ভব। — P সবচেয়ে লম্বা
4. তাই deg(v₀) = 1; একই যুক্তিতে deg(v_k) = 1, আর k ≥ 1 বলে v₀ ≠ v_k. দুটি আলাদা leaf পাওয়া গেল। ∎

একটি নিখুঁত হিসাবও আছে, যা পরীক্ষায় খুব কাজের। পরের অংশে প্রমাণ হবে যে n vertex-এর tree-তে m = n − 1. পর্ব ৫৭-এর handshake lemma বলে degree-র যোগফল 2m = 2n − 2. দুই দিক থেকে 2n বাদ দিলে ∑(deg(v) − 2) = −2. Leaf-এর জন্য deg − 2 = −1, degree 2-এর জন্য 0. তাই leaf-এর সংখ্যা l হলে:

l = 2 + ∑_{deg(v) ≥ 3} (deg(v) − 2)

অর্থাৎ degree 2-এর vertex leaf-সংখ্যায় কিছু যোগ করে না, আর degree 3-এর প্রতিটি vertex একটি, degree 4-এর প্রতিটি দুটি বাড়তি leaf আনে। Path-এ ঠিক দুটি leaf; তারকা K_1,n−1-এ কেন্দ্রের degree n − 1, তাই l = 2 + (n − 3) = n − 1.

২ · ছয়টি সমতুল্য সংজ্ঞা — characterization উপপাদ্যের পূর্ণ প্রমাণ

“Tree” চেনার অনেক উপায় আছে, আর কাজের সময় যেটি সুবিধার, সেটিই ব্যবহার করা হয়। কোনো algorithm যদি n − 1টি edge বেছে নেয় আর cycle এড়ায়, তবে ফলটি tree কি না, তা নিশ্চিত করতে এই উপপাদ্যই লাগে (পর্ব ৬৭ “Spanning tree — DFS/BFS, minimum spanning tree আর Kirchhoff-এর গণনা”-এ Kruskal-এর algorithm ঠিক এভাবে চলে)। প্রথমে দুটি সহায়ক তথ্য।

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

1. ভিত্তি m = 0: প্রতিটি vertex নিজেই একটি component, c = n = n − 0, আর edge ছাড়া cycle নেই। দুই দাবিই সত্য। — base case
2. m ≥ 1 হলে যেকোনো edge e নিন, G′ = G − e. G′-এ m − 1টি edge, তাই hypothesis অনুযায়ী c(G′) ≥ n − m + 1, আর সমতা ঠিক তখন যখন G′ acyclic. — inductive hypothesis
3. লেমা ২.১ অনুযায়ী c(G) = c(G′) − 1 যদি e bridge, নইলে c(G) = c(G′). দুই ক্ষেত্রেই c(G) ≥ c(G′) − 1 ≥ n − m. — প্রথম দাবি
4. সমতা c(G) = n − m হয় ঠিক তখন, যখন দুটি অসমতাই সমতা: G′ acyclic আর e bridge, অর্থাৎ e কোনো cycle-এ নেই। — লেমা ২.১(ক)
5. G-এর প্রতিটি cycle হয় e ধারণ করে, নয়তো G′-এর cycle. তাই “G′ acyclic আর e কোনো cycle-এ নেই” ঠিক “G acyclic”-এর সমান। ∎

প্রমাণের পরিকল্পনা: (a) ⇒ (b) ⇒ (c) ⇒ (d) ⇒ (a) একটি চক্র, তারপর লেমা ২.২ দিয়ে (a) ⇔ (e) আর (a) ⇔ (f). চক্রটি পুরো হলে যেকোনো একটি থেকে বাকি সব আসে।

1. (a) ⇒ (b). Connected বলে প্রতি জোড়া u, v-এর মধ্যে অন্তত একটি path আছে। ধরুন দুটি আলাদা u–v path P আর Q. u থেকে দুটি পাশাপাশি চলে; x হোক প্রথম vertex, যার পরে তারা আলাদা হয়। P-তে x-এর পরের যে প্রথম vertex y আবার Q-এর x-এর পরের অংশে পড়ে, তা নিন (v নিজে পড়ে, তাই y আছে)। তাহলে P-এর x থেকে y অংশ আর Q-এর x থেকে y অংশ শুধু x আর y-তে মেলে, আর দুটির প্রথম edge আলাদা বলে একসঙ্গে অন্তত ৩টি vertex-এর একটি cycle তৈরি করে। Acyclic-এর বিরোধ। — দুই path থেকে cycle
2. (b) ⇒ (c). Path আছে বলে T connected. যেকোনো edge uv সরান। T − uv-তে যদি u থেকে v-তে কোনো path থাকত, তবে সেটি আর একক edge uv হতো T-তে দুটি আলাদা u–v path, যা (b)-এর বিরোধী। তাই T − uv disconnected. — অনন্য path
3. (c) ⇒ (d). T-তে cycle থাকলে তার একটি edge লেমা ২.১ অনুযায়ী bridge নয়; সেটি সরালেও T connected থাকত, যা (c)-এর বিরোধী। তাই T acyclic. এখন অ-সংলগ্ন u, v-এর মধ্যে নতুন edge যোগ করুন: T connected, তাই একটি u–v path P আছে, আর P-এর সঙ্গে নতুন edge uv একটি cycle. — bridge-এর লেমা
4. (d) ⇒ (a). শুধু connected দেখানো বাকি। ধরুন u আর v আলাদা component-এ। তাহলে তারা অ-সংলগ্ন; (d) অনুযায়ী uv যোগ করলে একটি cycle হয়, আর সেই cycle uv ধারণ করে (আগে cycle ছিল না)। Cycle থেকে uv বাদ দিলে T-তে একটি u–v path থাকে, যা “আলাদা component”-এর বিরোধী। — contradiction
5. (a) ⇔ (e), (a) ⇔ (f). (a) হলে c = 1 আর acyclic, তাই লেমা ২.২-এর সমতায় 1 = n − m, অর্থাৎ m = n − 1; এ থেকেই (e) আর (f). (e) হলে c = 1 = n − m, সমতা আছে, তাই লেমা ২.২ অনুযায়ী acyclic, অর্থাৎ tree. (f) হলে acyclic, তাই c = n − m = n − (n − 1) = 1, অর্থাৎ connected, তাই tree. ∎

লক্ষ করুন (e) আর (f)-এ দুটি শর্তই লাগে। শুধু “n − 1টি edge” যথেষ্ট নয়: একটি ত্রিভুজ আর একটি একা vertex মিলে ৪টি vertex আর ৩টি edge, অথচ graph-টি connected-ও নয়, acyclic-ও নয়। Forest-এর জন্য লেমা ২.২ সরাসরি বলে: c টি tree-এর forest-এ ঠিক n − c টি edge.

নিচের ব্লক ছোট এলোমেলো graph-এ ছয়টি শর্তই আলাদা আলাদা পদ্ধতিতে পরীক্ষা করে: (b)-এর জন্য প্রতি জোড়ার সব simple path গোনে, (c)-র জন্য প্রতিটি edge সরিয়ে দেখে, (d)-র জন্য প্রতিটি নতুন edge যোগ করে দেখে। উপপাদ্য সত্য হলে প্রতিটি graph-এ ছয়টি উত্তর হয় সব True, নয়তো সব False. প্রথমবার চালালে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import random
from itertools import combinations
def nbrs(E, u): return [b if a == u else a for a, b in E if u in (a, b)]
def connected(n, E):
    seen, stack = {0}, [0]
    while stack:
        for w in nbrs(E, stack.pop()):
            if w not in seen: seen.add(w); stack.append(w)
    return len(seen) == n
def acyclic(n, E):                  # union-find: an edge inside one set closes a cycle
    p = list(range(n))
    def find(x): return x if p[x] == x else find(p[x])
    for a, b in E:
        if find(a) == find(b): return False
        p[find(a)] = find(b)
    return True
def npaths(E, u, v, seen=()):       # number of simple u-v paths
    if u == v: return 1
    return sum(npaths(E, w, v, seen + (u,)) for w in nbrs(E, u) if w not in seen)
def six(n, E):
    con, acy, m = connected(n, E), acyclic(n, E), len(E)
    non = [e for e in combinations(range(n), 2) if e not in E]
    return (con and acy,
            all(npaths(E, u, v) == 1 for u, v in combinations(range(n), 2)),
            con and all(not connected(n, [f for f in E if f != e]) for e in E),
            acy and all(not acyclic(n, E + [e]) for e in non),
            con and m == n - 1, acy and m == n - 1)
random.seed(65); trees = 0
for trial in range(600):
    n = random.randint(1, 6); allE = list(combinations(range(n), 2))
    m = min(len(allE), max(0, n - 1 + random.choice([-1, 0, 0, 1])))
    s = six(n, sorted(random.sample(allE, m)))
    assert len(set(s)) == 1; trees += s[0]   # all six true or all six false
print(trial + 1, "random graphs: all six conditions agree;", trees, "were trees")
print("triangle + isolated vertex:", six(4, [(0, 1), (0, 2), (1, 2)]))

600 random graphs: all six conditions agree; 302 were trees
triangle + isolated vertex: (False, False, False, False, False, False)

৩ · Rooted tree — parent, সন্তান, পূর্বপুরুষ, level আর height

বংশতালিকা বা পণ্য-তালিকায় একটি vertex বিশেষ: যেখান থেকে সব শুরু। একটি tree-এর যেকোনো একটি vertex r বেছে নিলে, উপপাদ্য ২.৩(b) অনুযায়ী r থেকে প্রতিটি vertex-এ ঠিক একটি path, আর সেই path ধরে প্রতিটি edge-কে “r থেকে দূরের দিকে” মুখ করানো যায়। এভাবেই tree-এর পরিবার-সম্পর্কের ভাষা আসে।

একটি সূক্ষ্ম বিষয়: rooted tree-এ leaf মানে সন্তানহীন, তাই root-এর একটি মাত্র সন্তান থাকলে root-এর degree 1 হলেও তাকে leaf বলা হয় না। আরেকটি সতর্কতা: কিছু বই level গোনা 1 থেকে শুরু করে, আর কেউ কেউ height-কে edge নয়, vertex দিয়ে মাপে। পরীক্ষায় সংজ্ঞাটি প্রথমেই লিখে নিন। এই কোর্সে (আর পর্ব ১২-এ) height edge-এ মাপা, একক vertex-এর height 0.

ছবিতে পড়ুন: y-এর parent A2, পূর্বপুরুষ A2, A আর r; A-এর উত্তরসূরি A1, A2, A3, x, y, z; y-এর level 3, আর tree-এর height 3. B root-এর সন্তান হয়েও leaf (বইয়ের কোনো উপ-বিভাগ নেই)। “u, v-এর পূর্বপুরুষ অথবা u = v” সম্পর্কটি একটি partial order, আর rooted tree-এর ছবি আসলে তার Hasse diagram (পর্ব ৫৬), root-কে ওপরে রেখে।

ছবির tree-টি full ternary: r, A, C আর A2-এর প্রত্যেকের ঠিক তিনটি সন্তান। পরের অংশে এর গণনা।

৪ · Full m-ary tree-এর গণনা — n = mi + 1 আর leaf-এর সূত্র

ক্রিকেটের একটি নকআউট টুর্নামেন্ট ভাবুন: প্রতি ম্যাচে দুই দল খেলে, হারলে বাদ। প্রতিটি ম্যাচ একটি internal vertex, তার দুই সন্তান দুই খেলোয়াড় দল (বা আগের দুটি ম্যাচের বিজয়ী), আর leaf হলো শুরুর দলগুলো। ২৭টি দল থাকলে কয়টি ম্যাচ? প্রতিটি ম্যাচে ঠিক একটি দল বাদ পড়ে, আর শেষে একটিই থাকে, তাই ২৬টি ম্যাচ। এই সরল যুক্তির সাধারণ রূপই নিচের উপপাদ্য।

1. Root ছাড়া প্রতিটি vertex ঠিক একটি vertex-এর সন্তান: তার অনন্য parent. — সংজ্ঞা ৩.১
2. তাই n − 1 = সব vertex-এর সন্তান-সংখ্যার যোগফল (প্রতিটি অ-root vertex ঠিক একবার গোনা হয়)। — দুইভাবে গোনা
3. Leaf-এর সন্তান 0, আর full m-ary বলে প্রতিটি internal vertex-এর ঠিক m. তাই যোগফল = mi, অর্থাৎ n = mi + 1. — full-এর সংজ্ঞা
4. প্রতিটি vertex হয় leaf, নয় internal: l = n − i = mi + 1 − i = (m − 1)i + 1. ∎

তিনটি রাশির (n, i, l) যেকোনো একটি জানলে বাকি দুটি বের হয়:

নকআউটে m = 2, l = 27, তাই i = 26/1 = 26 ম্যাচ। আর একটি দ্রুত অসম্ভবতা-পরীক্ষা: full ternary tree-তে l − 1 = 2i জোড়, তাই leaf-সংখ্যা সবসময় বিজোড়; ১০০টি leaf-এর full ternary tree নেই। Full binary tree-এর জন্য বিশেষ রূপ: l = i + 1, n = 2i + 1, যা পর্ব ১২-এর structural induction দিয়েও প্রমাণ করা যায়।

নিচের stepper ছবির পণ্য-তালিকাটি এক এক করে গড়ে তোলে: প্রতিবার একটি leaf-কে “ভেঙে” তিনটি সন্তান দেওয়া হয়। প্রতিটি ধাপে সূত্র মেলে কি না, দেখুন।

1শুরু: শুধু root r2r ভাঙা: A, B, C3A ভাঙা: A1, A2, A34C ভাঙা: C1, C2, C35A2 ভাঙা: x, y, z6যাচাই: সন্তান গোনা

৫ · Height-এর সীমা, balanced tree আর decision tree

বাজারঘরের পণ্য-তালিকায় একজন ক্রেতা কয়টি ক্লিকে একটি পণ্যে পৌঁছান? যত ক্লিক, তত level, আর সবচেয়ে খারাপ ক্ষেত্রে height-এর সমান। প্রতিটি পাতায় বড়জোর mটি উপ-বিভাগ রাখলে l-টি পণ্যের জন্য height অন্তত কত হতে হবে?

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

1. h = 0: tree-টি শুধু root, leaf 1 = m⁰. — base case
2. h ≥ 1: root-এর সন্তান k ≤ mটি। প্রতিটি সন্তান-root subtree একটি m-ary tree, height বড়জোর h − 1, তাই hypothesis অনুযায়ী প্রতিটিতে leaf বড়জোর m^h−1. — inductive hypothesis
3. পুরো tree-এর leaf ঠিক এই subtree-গুলোর leaf-এর যোগফল (root নিজে leaf নয়), তাই l ≤ k · m^h−1 ≤ m^h. — যোগ
4. l ≤ m^h থেকে log_m l ≤ h, আর h পূর্ণসংখ্যা, তাই h ≥ ⌈log_m l⌉. ∎

সমতা কখন কাছাকাছি আসে? যখন tree “ভারসাম্যপূর্ণ”। একটি height-h rooted tree balanced, যদি সব leaf level h বা h − 1-এ থাকে।

1. উপপাদ্য ৫.১ থেকে l ≤ m^h. — ঊর্ধ্বসীমা
2. Balanced বলে level h − 2 বা তার ওপরে কোনো leaf নেই; full বলে সেখানকার প্রতিটি vertex-এর mটি সন্তান। তাই level h − 1-এ ঠিক m^h−1টি vertex. — level ধরে গোনা
3. Height h বলে level h − 1-এর অন্তত একটি vertex internal, তার mটি leaf সন্তান; বাকি m^h−1 − 1টি vertex হয় leaf, নয় আরও leaf দেয়। তাই l ≥ (m^h−1 − 1) + m > m^h−1. — m ≥ 2
4. m^h−1 < l ≤ m^h, অর্থাৎ h − 1 < log_m l ≤ h, তাই h = ⌈log_m l⌉. ∎

ছবির পণ্য-তালিকাটি balanced নয়: B level 1-এ, x level 3-এ। তার l = 9, আর ⌈log₃ 9⌉ = 2, অথচ h = 3. নয়টি পণ্য level 2-এ সাজালে (root-এর তিন সন্তান, প্রত্যেকের তিনটি) প্রতিটি পণ্য দুই ক্লিকে পাওয়া যেত। ডেটাবেসের index-এ ব্যবহৃত B-tree অনেক বড় m নিয়ে ঠিক এই সুবিধা নেয় (DSA কোর্সের পর্ব ৩০), আর binary search tree-কে ভারসাম্যে রাখার কৌশল DSA কোর্সের পর্ব ২৮-এ।

Decision tree আর sorting-এর নিম্নসীমা

একটি decision tree একটি প্রশ্ন-উত্তর প্রক্রিয়ার ছবি: প্রতিটি internal vertex একটি প্রশ্ন, প্রতিটি শাখা একটি সম্ভাব্য উত্তর, আর প্রতিটি leaf একটি চূড়ান্ত সিদ্ধান্ত। দাঁড়িপাল্লায় (তিনটি ফল: বাঁ ভারী, সমান, ডান ভারী) ternary tree আসে; দুটি সংখ্যার তুলনায় (a < b কি না) binary tree. সবচেয়ে খারাপ ক্ষেত্রে প্রশ্নের সংখ্যা tree-এর height, তাই উপপাদ্য ৫.১ সরাসরি নিম্নসীমা দেয়। মেশিন লার্নিং-এর “decision tree” মডেল একই কাঠামো, তবে সেখানে লক্ষ্য ডেটা থেকে প্রশ্ন শেখা (Machine Learning কোর্সের পর্ব ৩২)।

1. নির্দিষ্ট n-এর জন্য algorithm-টির আচরণ একটি binary decision tree: প্রতিটি internal vertex “a_i < a_j?” প্রশ্ন, উত্তর অনুযায়ী বাঁ বা ডান শাখা, আর leaf-এ algorithm থামে ও একটি সাজানোর নিয়ম (একটি permutation) দেয়। — মডেল
2. n!টি ইনপুট-ক্রমের প্রতিটির জন্য সঠিক উত্তর আলাদা permutation. দুটি আলাদা ইনপুট-ক্রম একই leaf-এ পৌঁছালে algorithm দুটিতে একই permutation প্রয়োগ করে, তাই অন্তত একটির উত্তর ভুল। অতএব অন্তত n!টি leaf. — pigeonhole
3. উপপাদ্য ৫.১ (m = 2) অনুযায়ী height h ≥ ⌈log₂ n!⌉, আর height = সবচেয়ে খারাপ ক্ষেত্রে তুলনার সংখ্যা। — leaf-এর সীমা
4. n! = 1 · 2 ⋯ n-এর শেষ ⌈n/2⌉টি গুণনীয়কের প্রত্যেকটি ≥ n/2, তাই n! ≥ (n/2)^n/2 আর log₂ n! ≥ (n/2) log₂(n/2), যা n ≥ 4-এ অন্তত (n/4) log₂ n. অতএব Ω(n log n). ∎

এই প্রমাণ একটি নির্দিষ্ট algorithm নয়, সব সম্ভাব্য algorithm-এর ওপর একসঙ্গে খাটে: এটাই lower bound-এর শক্তি। Merge sort-এর (DSA কোর্সের পর্ব ২১) সবচেয়ে খারাপ ক্ষেত্রের তুলনা-সংখ্যা জানা সূত্রে W(n) = n⌈log₂ n⌉ − 2^{⌈log₂ n⌉} + 1 (পর্ব ৪৭-এর recurrence থেকে আসে)। নিচের ব্লক দুটি সংখ্যা পাশাপাশি রাখে, আর ছোট n-এ সব ইনপুট-ক্রমে merge sort চালিয়ে সূত্রটিও মেলায়।

import math
from itertools import permutations
def merge_sort(a, cnt):                 # counts key comparisons in cnt[0]
    if len(a) <= 1: return a
    mid = (len(a) + 1) // 2
    L, R = merge_sort(a[:mid], cnt), merge_sort(a[mid:], cnt)
    out, i, j = [], 0, 0
    while i < len(L) and j < len(R):
        cnt[0] += 1
        if L[i] <= R[j]: out.append(L[i]); i += 1
        else: out.append(R[j]); j += 1
    return out + L[i:] + R[j:]
def worst_bruteforce(n):                # try every input order
    best = 0
    for p in permutations(range(n)):
        cnt = [0]; merge_sort(list(p), cnt); best = max(best, cnt[0])
    return best
def worst_formula(n):                   # n*ceil(lg n) - 2^ceil(lg n) + 1
    k = (n - 1).bit_length()            # exact ceil(log2 n) for n >= 1
    return n * k - 2 ** k + 1
print(" n  ceil(lg n!)  merge sort worst  (brute force)")
for n in range(2, 13):
    lb = (math.factorial(n) - 1).bit_length()   # exact ceil(log2 n!)
    bf = worst_bruteforce(n) if n <= 7 else "-"
    print(f"{n:2}  {lb:11}  {worst_formula(n):16}  {bf:>13}")
for n in (10**3, 10**6):
    lg_fact = math.lgamma(n + 1) / math.log(2)  # log2(n!) without n!
    print(f"n={n}: log2(n!) = {lg_fact:.0f}, n*log2(n) = {n*math.log2(n):.0f}")

 n  ceil(lg n!)  merge sort worst  (brute force)
 2            1                 1              1
 3            3                 3              3
 4            5                 5              5
 5            7                 8              8
 6           10                11             11
 7           13                14             14
 8           16                17              -
 9           19                21              -
10           22                25              -
11           26                29              -
12           29                33              -
n=1000: log2(n!) = 8529, n*log2(n) = 9966
n=1000000: log2(n!) = 18488885, n*log2(n) = 19931569

সীমাটি শুধু তুলনা-ভিত্তিক পদ্ধতির জন্য। Counting sort বা radix sort key-এর অঙ্ক সরাসরি পড়ে, তুলনা করে না, তাই নির্দিষ্ট পরিসরের key-এ রৈখিক সময়ে চলতে পারে (DSA কোর্সের পর্ব ২৪)। আর গড় ক্ষেত্রেও একই ধরনের নিম্নসীমা খাটে: n!টি leaf-এর binary tree-এ leaf-এর গড় depth অন্তত log₂ n!.

৬ · Labelled tree গোনা — Cayley-র সূত্র আর Prüfer code

বাজারঘরের সাতটি হাব (নাম 1 থেকে 7) ছয়টি রাস্তায় এমনভাবে জুড়তে হবে, যাতে সব হাব connected থাকে; উপপাদ্য ২.৩(e) অনুযায়ী প্রতিটি এমন নকশা একটি tree. কয়টি আলাদা নকশা সম্ভব? এখানে vertex-এর নাম আছে, তাই 1–2 রাস্তা আর 1–3 রাস্তা আলাদা নকশা, যদিও ছবির আকার একই। এমন গোনাকে বলে labelled গণনা; নাম মুছে শুধু আকার গুনলে unlabelled (পর্ব ৫৮-এর isomorphism প্রশ্ন)।

ছোট ক্ষেত্রে হাতে গুনুন। n = 2: একটি। n = 3: তিনটি path, মাঝের vertex বেছে নেওয়ার ৩ উপায়। n = 4: দুই আকার, path আর তারকা; path-এর 4!/2 = 12টি নামকরণ (উল্টো দিক একই), তারকার কেন্দ্র বাছার ৪ উপায়, মোট 16. ধারা 1, 3, 16 = 2⁰, 3¹, 4².

প্রমাণের ধারণা: প্রতিটি tree-কে {1, …, n}-এর সংখ্যা দিয়ে গড়া n − 2 দৈর্ঘ্যের একটি সারির সঙ্গে এক-এক মেলানো। এমন সারি ঠিক nⁿ⁻²টি (প্রতিটি ঘরে n বিকল্প, পর্ব ৩১-এর গুণের নিয়ম), তাই একটি bijection (পর্ব ১৬) পেলেই কাজ শেষ। সেই সারির নাম Prüfer code.

1leaf খুঁজুন21 মুছুন, লিখুন 532 মুছুন, লিখুন 643 মুছুন, লিখুন 554 মুছুন, লিখুন 665 মুছুন, লিখুন 77বাকি 6–7: থামুন

শেষ ধাপের পর্যবেক্ষণটিই চাবি।

1. v সারিতে লেখা হয় ঠিক তখন, যখন v-এর একটি প্রতিবেশী leaf হিসেবে মোছা হয়; অর্থাৎ v-এর গায়ে লাগা একটি edge সরে যায়, আর মোছা vertex-টি v নয়। — encoding-এর নিয়ম
2. যদি v নিজে কোনো ধাপে মোছা হয়, তখন তার শেষ edge সরে, কিন্তু সেবার v লেখা হয় না (লেখা হয় প্রতিবেশী)। আগের deg(v) − 1টি edge সরেছিল v-কে লিখে। — ক্ষেত্র ১
3. যদি v শেষের দুই vertex-এর একটি হয়, তবে শেষ edge কখনো সরে না, আর বাকি deg(v) − 1টি সরেছে v-কে লিখে। — ক্ষেত্র ২
4. দুই ক্ষেত্রেই উপস্থিতি deg(v) − 1; leaf-এর জন্য 0. ∎

এখন উল্টো দিক। সারি (a₁, …, a_n−2) দেওয়া আছে। লেমা বলে প্রথম মোছা leaf হলো সারিতে নেই এমন সবচেয়ে ছোট vertex b₁, আর তার প্রতিবেশী a₁. তাই প্রথম edge b₁–a₁ নিশ্চিতভাবে জানা যায়। b₁ সরালে বাকি tree-এর code হলো (a₂, …, a_n−2), আর একই যুক্তি চলতে থাকে।

1degree = উপস্থিতি + 12a1 = 33a2 = 14a3 = 35a4 = 76a5 = 77শেষ দুটি জোড়া

উপপাদ্য ৬.১-এর প্রমাণ (bijection, n-এর ওপর induction): দাবি: n ≥ 2 হলে যেকোনো n-উপাদানের ক্রমযুক্ত vertex-সেট V-এর জন্য encoding হলো V-এর ওপর সব tree থেকে Vⁿ⁻²-এ একটি bijection.

1. ভিত্তি n = 2: V-এর ওপর tree একটিই (একক edge), আর সারি একটিই (খালি)। — base case
2. One-to-one: দুটি tree T, T′-এর code একই (a₁, …) ধরুন। লেমা ৬.৩ অনুযায়ী দুটির leaf-সেট একই (সারিতে নেই এমন vertex), তাই প্রথম মোছা leaf b₁ একই, আর দুটিতেই b₁-এর প্রতিবেশী a₁. T − b₁ আর T′ − b₁-এর code (a₂, …) একই, তাই hypothesis অনুযায়ী তারা একই tree; edge b₁a₁ ফিরিয়ে দিলে T = T′. — inductive hypothesis
3. Onto: যেকোনো সারি (a₁, …, a_n−2) নিন; b₁ = সারিতে নেই এমন সবচেয়ে ছোট vertex (n − 2 < n বলে আছে)। (a₂, …) সারির সব সংখ্যা V − {b₁}-এ, তাই hypothesis অনুযায়ী V − {b₁}-এর ওপর একটি tree T′ আছে যার code (a₂, …). T = T′ + edge b₁a₁. — নির্মাণ
4. T-এর leaf: b₁, আর T′-এর leaf-গুলো a₁ বাদে। লেমা অনুযায়ী T′-এর leaf = সারি (a₂, …)-তে নেই এমন vertex. তাই T-এর leaf-সেট = V − {a₁, …, a_n−2}, যার সবচেয়ে ছোটটি b₁. ফলে T-এর encoding প্রথমে b₁ মুছে a₁ লেখে, তারপর T′-এর মতো চলে: code (a₁, a₂, …). — লেমা ৬.৩
5. Bijection পাওয়া গেল, তাই tree-সংখ্যা = |V|ⁿ⁻² = nⁿ⁻². ∎

লেমা ৬.৩ একটি বাড়তি উপহার দেয়: নির্দিষ্ট degree-তালিকা d₁, …, d_n (যোগফল 2n − 2, প্রতিটি ≥ 1) মেনে labelled tree-এর সংখ্যা হলো সারিতে v-কে ঠিক d_v − 1 বার রাখার উপায়, অর্থাৎ multinomial (n − 2)! / ∏(d_v − 1)! (পর্ব ৩৫)। যেমন vertex 1-এর degree n − 1 (তারকা) হলে সারি (1, 1, …, 1), উত্তর 1. নিচের ব্লক n ≤ 6-এ K_n-এর সব (n − 1)-edge উপসেট থেকে tree বেছে গোনে, প্রতিটিকে encode আর decode করে মূল tree ফেরে কি না দেখে, আর সব nⁿ⁻²টি সারি decode করে আবার encode করে।

from itertools import combinations, product
def encode(n, edges):                   # tree on 1..n  ->  Prufer sequence
    adj = {v: set() for v in range(1, n + 1)}
    for a, b in edges: adj[a].add(b); adj[b].add(a)
    seq = []
    for _ in range(n - 2):
        leaf = min(v for v in adj if len(adj[v]) == 1)   # smallest leaf
        nb = adj.pop(leaf).pop()
        seq.append(nb); adj[nb].discard(leaf)
    return tuple(seq)
def decode(seq):                        # Prufer sequence -> edge set
    n = len(seq) + 2
    deg, edges = {v: 1 + seq.count(v) for v in range(1, n + 1)}, []
    for a in seq:
        leaf = min(v for v in deg if deg[v] == 1)
        edges.append(frozenset((leaf, a))); deg[a] -= 1; del deg[leaf]
    edges.append(frozenset(deg))        # the last two vertices
    return frozenset(edges)
def is_tree(n, edges):                  # n-1 edges, no cycle (union-find)
    p = list(range(n + 1))
    def find(x): return x if p[x] == x else find(p[x])
    for a, b in edges:
        if find(a) == find(b): return False
        p[find(a)] = find(b)
    return True
print(encode(7, [(1, 5), (2, 6), (3, 5), (4, 6), (5, 7), (6, 7)]))
print(sorted(tuple(sorted(e)) for e in decode((3, 1, 3, 7, 7))))
for n in range(2, 7):
    trees = [t for t in combinations(combinations(range(1, n + 1), 2), n - 1)
             if is_tree(n, t)]
    codes = {encode(n, t) for t in trees}           # encode is one-to-one?
    ok = all(decode(encode(n, t)) == frozenset(map(frozenset, t)) for t in trees)
    onto = all(encode(n, [tuple(e) for e in decode(s)]) == s
               for s in product(range(1, n + 1), repeat=n - 2))
    print(n, len(trees), n ** (n - 2), len(codes), ok, onto)

(5, 6, 5, 6, 7)
[(1, 3), (1, 4), (2, 3), (3, 7), (5, 7), (6, 7)]
2 1 1 1 True True
3 3 3 3 True True
4 16 16 16 True True
5 125 125 125 True True
6 1296 1296 1296 True True

৭ · Binary tree গোনা, tree-এর কেন্দ্র, আর BST ও heap

Binary tree আর unlabelled tree গোনা

Cayley-র সূত্র নামযুক্ত vertex গোনে। Ordered binary tree (বাঁ আর ডান সন্তান আলাদা, vertex-এর নাম নেই) গোনা আরেক প্রশ্ন: n vertex-এর binary tree ঠিক Catalan সংখ্যা C_n = C(2n, n)/(n + 1)টি: 1, 1, 2, 5, 14, 42, … (n = 0 থেকে)। Root বাদে বাকি n − 1টি vertex বাঁ আর ডান subtree-তে ভাগ হয়, তাই C_n = ∑ C_iC_n−1−i; প্রমাণ আর বন্ধনীর সঙ্গে bijection পর্ব ৩৭ “গণনার কৌশল — lattice path, bijection আর double counting”-এ, আর generating function-এ সমাধান পর্ব ৫০-এ। আর নাম ও ক্রম দুটিই মুছে শুধু আকার গুনলে (unlabelled free tree) n = 1 থেকে 8-এ সংখ্যা 1, 1, 1, 2, 3, 6, 11, 23 (scratch-এ Prüfer দিয়ে সব labelled tree বানিয়ে আকার মিলিয়ে গোনা); এর কোনো সরল বদ্ধ সূত্র জানা নেই, symmetry-র কারণে গণনা কঠিন (পর্ব ৫১-এর Pólya-র পদ্ধতি এখানে কাজে লাগে)।

Tree-এর কেন্দ্র

বাজারঘর সাত হাবের tree-আকৃতির নেটওয়ার্কে একটি কেন্দ্রীয় গুদাম বসাতে চায়, যাতে সবচেয়ে দূরের হাবও যতটা সম্ভব কাছে থাকে। Vertex v-এর eccentricity e(v) = v থেকে সবচেয়ে দূরের vertex-এর দূরত্ব (edge-সংখ্যায়)। সবচেয়ে কম eccentricity-ওয়ালা vertex-গুলো মিলে কেন্দ্র (center) বলে। সাধারণ graph-এ কেন্দ্রে অনেক vertex থাকতে পারে (cycle C_n-এ সবাই কেন্দ্র), কিন্তু tree-তে নয়।

প্রমাণের রূপরেখা (পাতা ছাঁটাই):

1. n ≤ 2 হলে দাবি সরাসরি সত্য। n ≥ 3 হলে T-এর সব leaf একসঙ্গে মুছে T′ পান; T′ একটি tree (একটি leaf মুছলে connected আর acyclic থাকে), আর n ≥ 3-এ T′ খালি নয়। — উপপাদ্য ২.৩
2. যেকোনো v থেকে সবচেয়ে দূরের vertex w একটি leaf: w-এর আরেকটি প্রতিবেশী থাকলে v থেকে তার দূরত্ব আরও বেশি হতো, কারণ tree-তে path অনন্য। — অনন্য path
3. তাই T′-এর প্রতিটি v-এর জন্য e_T′(v) = e_T(v) − 1: সবচেয়ে দূরের leaf-গুলো চলে যায়, আর তাদের ঠিক আগের vertex (যা leaf নয়) এক কম দূরত্বে থেকে যায়। — দূরত্ব এক কমে
4. n ≥ 3-এ একটি leaf-এর eccentricity তার প্রতিবেশীর চেয়ে ঠিক 1 বেশি, তাই leaf কখনো কেন্দ্রে থাকে না। ফলে কেন্দ্র(T) = কেন্দ্র(T′). — সবার eccentricity সমান হারে কমে
5. বারবার ছাঁটাই করলে vertex-সংখ্যা কমতে কমতে 1 বা 2-এ থামে; 2 হলে তারা tree-তে সংলগ্ন। সেটিই কেন্দ্র। ∎

ছাঁটাইয়ের এই পদ্ধতি algorithm-ও: “প্রতিবার সব leaf মুছুন” রৈখিক সময়ে কেন্দ্র দেয়। Tree-এর diameter (সবচেয়ে বড় দূরত্ব) আর radius (কেন্দ্রের eccentricity) মেনে চলে diameter ∈ {2 · radius − 1, 2 · radius}, আর দুটি tree isomorphic কি না দেখতে কেন্দ্রকে root ধরা হয়, ভাবনার প্রশ্ন ৫ দেখুন। DSA কোর্সের পর্ব ৪৮-এ diameter বের করার দুই-BFS কৌশল আছে। নিচের ব্লক এলোমেলো tree-তে (এলোমেলো Prüfer সারি decode করে) কেন্দ্রের সংজ্ঞা আর ছাঁটাইয়ের ফল মেলায়, আর §১-এর leaf-সূত্রও পরীক্ষা করে।

import random
from collections import Counter
def random_tree(n):                     # decode a random Prufer sequence
    seq = [random.randint(1, n) for _ in range(n - 2)]
    V = range(1, n + 1)
    deg, adj = {v: 1 + seq.count(v) for v in V}, {v: set() for v in V}
    for a in seq:
        leaf = min(v for v in deg if deg[v] == 1)
        adj[leaf].add(a); adj[a].add(leaf); deg[a] -= 1; del deg[leaf]
    u, w = deg; adj[u].add(w); adj[w].add(u)
    return adj
def ecc(adj, s):                        # eccentricity by BFS
    dist, frontier = {s: 0}, [s]
    for u in frontier:
        for w in adj[u]:
            if w not in dist: dist[w] = dist[u] + 1; frontier.append(w)
    return max(dist.values())
def strip_leaves(adj):                  # peel off all leaves until 1 or 2 remain
    alive = set(adj)
    while len(alive) > 2:
        leaves = {v for v in alive if len(adj[v] & alive) == 1}
        alive -= leaves
    return alive
random.seed(65); sizes = Counter()
for trial in range(300):
    adj = random_tree(random.randint(2, 15))
    e = {v: ecc(adj, v) for v in adj}
    centre = {v for v in adj if e[v] == min(e.values())}
    assert centre == strip_leaves(adj)                       # Jordan
    assert len(centre) == 1 or max(centre) in adj[min(centre)]   # or an edge
    deg = [len(adj[v]) for v in adj]
    assert deg.count(1) == 2 + sum(d - 2 for d in deg if d >= 3)
    sizes[len(centre)] += 1
print("300 random trees: centre = leaf-stripping result; sizes", dict(sizes))

300 random trees: centre = leaf-stripping result; sizes {1: 138, 2: 162}

BST আর heap — data structure হিসেবে tree

প্রোগ্রামিংয়ে সবচেয়ে বেশি দেখা দুটি tree এই পর্বের হিসাবেই চলে। Binary search tree-এ প্রতিটি vertex-এ একটি key, আর বাঁ subtree-র সব key ছোট, ডান subtree-র সব key বড়; একটি key খুঁজতে root থেকে নিচে নামতে হয়, তাই সবচেয়ে খারাপ খরচ height + 1টি তুলনা। পর্ব ১২-এর n ≤ 2^h+1 − 1 (একই প্রমাণ যেকোনো binary tree-তে খাটে) থেকে h ≥ ⌈log₂(n + 1)⌉ − 1, তাই n key-এর কোনো BST log-এর চেয়ে ভালো নিশ্চয়তা দিতে পারে না, আর key ক্রমানুসারে ঢোকালে tree একটি path হয়ে h = n − 1 (DSA কোর্সের পর্ব ২৭)। Heap একটি complete binary tree (শেষ level ছাড়া সব level ভরা, শেষটি বাঁ থেকে ভরা), তাই তার height ঠিক ⌊log₂ n⌋, আর insert বা সবচেয়ে ছোটটি তুলে নেওয়া O(log n) (DSA কোর্সের পর্ব ২৩)। Tree-এর সাধারণ পরিভাষা আর কোডে উপস্থাপন DSA কোর্সের পর্ব ২৬-এ।

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

অঙ্ক ১: Degree থেকে leaf

একটি tree-তে দুটি vertex-এর degree 4, একটির 3, তিনটির 2, আর বাকি সব leaf. কয়টি leaf, কয়টি vertex, কয়টি edge?

1. সূত্র: l = 2 + (4 − 2) + (4 − 2) + (3 − 2) = 7.
2. n = 7 + 2 + 1 + 3 = 13, m = n − 1 = 12.
3. যাচাই (handshake): 4 + 4 + 3 + 3 · 2 + 7 · 1 = 24 = 2 · 12. এমন একটি tree সত্যিই বানানো যায় (scratch-এ একটি নির্দিষ্ট tree গড়ে মেলানো)।

অঙ্ক ২: Forest-এর edge

২০টি vertex-এর একটি forest-এ ৩টি component. কয়টি edge? উত্তর: লেমা ২.২ অনুযায়ী m = n − c = 20 − 3 = 17. উল্টো দিকে, ২০ vertex আর ১৭ edge-এর graph acyclic হলে component ঠিক ৩টি; acyclic না হলে c > 3.

অঙ্ক ৩: Full m-ary tree

(ক) একটি full 5-ary tree-তে ১০০টি internal vertex. মোট vertex আর leaf? (খ) একটি full 4-ary tree-তে ১০০টি leaf. Internal vertex কয়টি? (গ) ১০০টি leaf-এর full ternary tree সম্ভব?

1. (ক) n = 5 · 100 + 1 = 501, l = 4 · 100 + 1 = 401.
2. (খ) i = (100 − 1)/3 = 33, n = 4 · 33 + 1 = 133.
3. (গ) i = 99/2 পূর্ণসংখ্যা নয়, তাই অসম্ভব.

অঙ্ক ৪: দাঁড়িপাল্লার decision tree

১২টি দেখতে একই রকম মুদ্রার একটি নকল, যা বাকিদের চেয়ে হয় ভারী, নয় হালকা (কোনটি জানা নেই)। দাঁড়িপাল্লায় অন্তত কয়বার মাপতে হবে, নকলটি আর সেটি ভারী না হালকা বের করতে?

1. সম্ভাব্য উত্তর 12 · 2 = 24টি; প্রতিটির জন্য decision tree-এ আলাদা leaf লাগে। — উপপাদ্য ৫.৩-এর যুক্তি
2. প্রতিবার মাপায় তিনটি ফল, তাই tree ternary; h বার মাপায় বড়জোর 3^h leaf. 3² = 9 < 24, তাই h ≥ ⌈log₃ 24⌉ = 3. — উপপাদ্য ৫.১
3. তিনবারে সত্যিই হয়; এটি একটি পুরোনো বিখ্যাত ধাঁধা, যার সমাধান নিম্নসীমাকে ঠিক ছুঁয়ে দেয়। তুলনায় ৮টি মুদ্রার একটি শুধু ভারী হলে ⌈log₃ 8⌉ = 2: প্রথমে 3 বনাম 3; সমান হলে বাকি দুটি মাপুন, নইলে ভারী দিকের তিনটির দুটি মাপুন।

প্রমাণের ভুল ধরুন: “n − 1টি edge থাকলেই tree”

একজন লিখলেন: “দাবি: n vertex আর n − 1 edge-এর প্রতিটি graph একটি tree. n-এর ওপর induction. n = 1-এ সত্য। ধরুন n-এর জন্য সত্য, আর G-তে n + 1টি vertex, nটি edge. গড় degree 2n/(n + 1) < 2, তাই কোনো vertex v-এর degree ≤ 1; ধরি deg(v) = 1. v সরালে nটি vertex আর n − 1টি edge, hypothesis অনুযায়ী tree; v-কে একটি edge দিয়ে ফিরিয়ে দিলে আবার tree. ∎”

ভুল কোথায়: “degree ≤ 1” থেকে “ধরি deg(v) = 1” লাফটি অবৈধ: degree 0-ও হতে পারে। তখন v একা vertex, আর v সরালে nটি vertex কিন্তু n টি edge থাকে, hypothesis খাটেই না। দাবিটিই মিথ্যা: পাল্টা-উদাহরণ একটি ত্রিভুজ আর একটি একা vertex, যেখানে n = 4 আর m = 3. সঠিক উপপাদ্যে (উপপাদ্য ২.৩(e) বা (f)) “connected” বা “acyclic” শর্ত লাগে। দ্বিতীয় সতর্কতা: ছোট graph-এ একটি vertex যোগ করে বড় graph “গড়ার” induction সব বড় graph-কে ধরে কি না, তা আলাদা করে দেখাতে হয়; নিরাপদ পথ হলো যেকোনো বড় graph থেকে শুরু করে ছোট graph-এ নামা, যেমন লেমা ২.২-এ করা হয়েছে।

৯ · AI-এর যুগে — tree-এর প্রমাণ আর গণনা যাচাই

Tree-এর প্রশ্নে AI সহকারী সংজ্ঞা আর বিখ্যাত সূত্র সাধারণত ঠিক বলে, কিন্তু শর্ত বাদ দেয়, labelled আর unlabelled গুলিয়ে ফেলে, height আর level-এ এক কম-বেশি করে। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

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

• “n − 1 edge” ব্যবহারের সঙ্গে connected বা acyclic শর্তও আছে
• Labelled আর unlabelled গণনা আলাদা রাখা হয়েছে, ছোট n-এ সংখ্যা মিলিয়েছি
• m-ary সূত্র শুধু full tree-তে, balanced-এর সূত্র শুধু balanced full tree-তে
• Induction-এ base case আছে, আর step কোনো ফাঁক (যেমন degree 0) ছাড়েনি
• Prüfer বা অন্য encoding-এ decode করে আবার encode করে মূল সারি ফিরেছে
• উদ্ধৃত নাম, সাল আর উৎস বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

Tree-এর বেশির ভাগ দাবি ৭–৮টি vertex পর্যন্ত সব tree তৈরি করে (Prüfer দিয়ে সহজেই) পরীক্ষা করা যায়; AI-এর প্রমাণ পড়ার আগেই এই পরীক্ষা চালিয়ে নিলে ভুল দাবি দ্রুত ধরা পড়ে।