Connectivity — path, component, cut vertex আর Menger-এর ধারণা

১ · Walk, trail আর path — “পৌঁছানো যায়” কথার নির্ভুল ভাষা

বাজারঘরের একজন রাইডার সাভারের গুদাম থেকে কেরানীগঞ্জে একটি পার্সেল নিয়ে যাবেন। তিনি পথে কোনো মোড় দুবার পার হতে পারেন, একই রাস্তা দুবার ধরতে পারেন; তবু তিনি পৌঁছান। প্রশ্ন হলো: “পৌঁছানো যায়” বললে আমরা ঠিক কী দাবি করি, আর কখন বলতে পারি “সবচেয়ে ছোট রাস্তায় কোনো মোড় দুবার আসে না”?

এই পর্বে graph মানে সাধারণত undirected simple graph G = (V, E): vertex-এর একটি সসীম সেট V আর edge-এর সেট E, যেখানে প্রতিটি edge দুটি আলাদা vertex-এর একটি জোড়া {u, v}। Loop বা একই জোড়ার একাধিক edge (multigraph) যেখানে চলে, সেখানে আলাদা করে বলা আছে। সংজ্ঞাগুলোর বিস্তারিত পর্ব ৫৭ “গ্রাফ — সংজ্ঞা, degree আর handshake theorem”-এ। নিচের সংজ্ঞায় v₀, v₁, …, v_k এমন vertex-ক্রম, যার পরপর প্রতিটি জোড়া {v_i−1, v_i} একটি edge; k হলো তার দৈর্ঘ্য (edge-এর সংখ্যা)।

সাবধান: বইভেদে নাম বদলায়। কোনো বইয়ে “path” মানে আমাদের walk, আর আমাদের path-কে বলে “simple path”. পরীক্ষায় উত্তর লেখার আগে কোন সংজ্ঞা ব্যবহার করছেন, তা এক লাইনে লিখে নিন। এখানে দৈর্ঘ্য ০-এর walk (শুধু একটি vertex v₀) বৈধ, আর তা একটি path.

1. W-এর edge দিয়ে গঠিত সব u–v walk-এর সংগ্রহ খালি নয় (W নিজেই আছে)। দৈর্ঘ্যগুলো অঋণাত্মক পূর্ণসংখ্যা, তাই সবচেয়ে ছোট দৈর্ঘ্যের একটি walk P = (u = v₀, …, v_k = v) আছে। — well-ordering, পর্ব ১১
2. ধরুন P-তে কোনো vertex দুবার আছে: v_i = v_j, i < j. — বিরোধের জন্য অনুমান
3. মাঝের অংশ v_i+1, …, v_j বাদ দিলে v₀, …, v_i, v_j+1, …, v_k আবার একটি u–v walk, কারণ v_i = v_j আর {v_j, v_j+1} একটি edge. এর edge-গুলো W-এর, আর দৈর্ঘ্য k − (j − i) < k. — লুপ কাটা
4. এটি P-এর ন্যূনতমতার বিরোধী, তাই P-তে কোনো vertex ফেরে না: P একটি path. Path-এর vertex সব আলাদা, তাই k + 1 ≤ n. ∎ — বিরোধ

প্রমাণটি আসলে একটি algorithm-ও: প্রথম পুনরাবৃত্ত vertex খুঁজুন, মাঝের লুপ কাটুন, আবার করুন। প্রতিবার দৈর্ঘ্য কমে, তাই কাজটি থামে। নিচের stepper ডেলিভারি graph-এর একটি ১০-edge walk থেকে এভাবে path বের করে।

1W = S M U G M G T D K T D2প্রথম পুনরাবৃত্তি: M3M … M লুপ কাটা4পরের পুনরাবৃত্তি: T5T … T লুপ কাটা

২ · Connected graph আর component — একটি equivalence relation

G-এর vertex-এর ওপর সম্পর্ক সংজ্ঞায়িত করুন: u ~ v ⇔ G-তে u থেকে v-তে একটি walk আছে (উপপাদ্য ১.১ অনুযায়ী, সমতুল্যভাবে একটি path আছে)।

1. Reflexive: দৈর্ঘ্য ০-এর walk (v) v থেকে v-তে যায়। — ০-দৈর্ঘ্যের walk বৈধ
2. Symmetric: u থেকে v-এর walk উল্টো ক্রমে পড়লে v থেকে u-এর walk, কারণ edge-এর দিক নেই। — undirected
3. Transitive: u থেকে v আর v থেকে w-এর walk পরপর জুড়লে u থেকে w-এর walk. ∎ — জোড়া লাগানো

ধাপ ৩-এ walk দরকার, path নয়: দুটি path জুড়লে vertex ফিরতে পারে, ফলে তা path না-ও হতে পারে। এই কারণেই সংজ্ঞায় walk নেওয়া সুবিধাজনক। পর্ব ৫৫ “Equivalence relation আর partition”-এর মৌলিক উপপাদ্য অনুযায়ী component-গুলো V-কে ভাগ করে, আর প্রতিটি component সবচেয়ে বড় connected subgraph: তাতে আরেকটি vertex যোগ করলে আর connected থাকে না। Relation-এর ভাষায় ~ হলো edge-relation-এর reflexive-transitive closure, যার connectivity relation R* আর Warshall-এর হিসাব পর্ব ৫৪-এ আছে।

হিসাবের দুটি সহজ পথ। এক, প্রতিটি না-দেখা vertex থেকে BFS চালানো, প্রতিবার যত vertex পৌঁছায় সেটাই একটি component. দুই, edge একটি একটি করে নিয়ে union-find দিয়ে দুই প্রান্তের দল জোড়া, পর্ব ৫৫-এর equivalence closure. নিচের ব্লক ৩০০টি এলোমেলো graph-এ দুই পদ্ধতির উত্তর মেলায়, আর পরের অংশের উপপাদ্য ৩.১-ও পরীক্ষা করে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import random; from collections import deque
def bfs_components(n, adj):            # comp[v] = number of v's component
    comp, c = [-1] * n, 0
    for s in range(n):
        if comp[s] == -1:
            comp[s] = c; q = deque([s])
            while q:
                x = q.popleft()
                for y in adj[x]:
                    if comp[y] == -1:
                        comp[y] = c; q.append(y)
            c += 1
    return comp, c
def uf_roots(n, edges):                # union-find: root = class name
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]; x = parent[x]
        return x
    for u, v in edges:
        parent[find(u)] = find(v)
    return [find(x) for x in range(n)]
random.seed(59); equal = 0
for trial in range(300):
    n = random.randint(1, 15)
    pairs = [(random.randrange(n), random.randrange(n)) for _ in range(n)]
    edges = [(u, v) for u, v in pairs if u != v]     # no loops
    adj = [[] for _ in range(n)]
    for u, v in edges: adj[u].append(v); adj[v].append(u)
    comp, c = bfs_components(n, adj); root = uf_roots(n, edges)
    assert all((comp[i] == comp[j]) == (root[i] == root[j])
               for i in range(n) for j in range(n))
    assert c >= n - len(edges)                       # theorem 3.1
    equal += (c == n - len(edges))
print("300 random graphs: BFS == union-find, c >= n - m; equality in", equal)

300 random graphs: BFS == union-find, c >= n - m; equality in 72

৩ · কয়টি edge লাগে — n − 1 আর C(n − 1, 2)-এর সীমা

বাজারঘর নতুন ১০টি হাব খুলবে। সবগুলোকে জুড়তে কমপক্ষে কয়টি রাস্তা লাগবে? আর উল্টো প্রশ্ন: এলোমেলোভাবে কতগুলো রাস্তা বানালে connected হওয়া নিশ্চিত? দুটি প্রশ্নের উত্তর দুটি উপপাদ্য।

প্রমাণ (m-এর ওপর induction, পর্ব ১০):

1. ভিত্তি m = 0: কোনো edge নেই, প্রতিটি vertex নিজেই একটি component, c = n = n − 0. — base case
2. ধরুন m − 1টি edge-এর সব graph-এ দাবি সত্য (m ≥ 1). এখন m edge-এর যেকোনো graph G নিন, আর তার যেকোনো একটি edge e = {u, v} সরিয়ে G − e বানান। G − e-তে m − 1টি edge, তাই c(G − e) ≥ n − m + 1. — inductive hypothesis
3. e ফিরিয়ে দিলে শুধু u আর v-এর component বদলাতে পারে: তারা G − e-তে একই component-এ থাকলে কিছু বদলায় না, আলাদা থাকলে দুটি component এক হয়। তাই c(G) ≥ c(G − e) − 1. — একটি edge দুটির বেশি component জোড়ে না
4. মিলিয়ে c(G) ≥ n − m + 1 − 1 = n − m. Connected মানে c = 1, তাই 1 ≥ n − m, অর্থাৎ m ≥ n − 1. ∎

লক্ষ করুন ধাপ ২-এর দিক: আমরা m edge-এর একটি যেকোনো graph থেকে শুরু করে ছোট graph-এ নেমেছি। উল্টো পথে, অর্থাৎ m − 1 edge-এর graph-এ একটি edge “যোগ করে” সব m-edge graph পাওয়া গেছে ধরে নেওয়া graph-এর induction-এর সবচেয়ে পরিচিত ভুল; অনুশীলন ৪-এ এমন একটি ভুল প্রমাণ আছে। এখানে সমস্যা নেই, কারণ যেকোনো G-এর ক্ষেত্রেই G − e একটি বৈধ ছোট graph.

1. ধরুন G connected নয়। একটি component-এর vertex-সেট X নিন, |X| = k, আর Y = V − X; তাহলে 1 ≤ k ≤ n − 1, আর X ও Y-এর মধ্যে কোনো edge নেই। — বিরোধের জন্য অনুমান
2. সব edge হয় X-এর ভেতরে, নয়তো Y-এর ভেতরে, আর simple graph-এ k vertex-এর ভেতরে সর্বোচ্চ C(k, 2)টি edge থাকে। তাই m ≤ C(k, 2) + C(n − k, 2). — simple graph-এ প্রতিটি জোড়ায় সর্বোচ্চ একটি edge
3. বীজগণিত: C(n − 1, 2) − C(k, 2) − C(n − k, 2) = (k − 1)(n − k − 1) ≥ 0, কারণ 1 ≤ k ≤ n − 1. — দুই পাশ খুলে মেলানো
4. তাই m ≤ C(n − 1, 2), যা অনুমান m > C(n − 1, 2)-এর বিরোধী। ∎

ধাপ ৩ একটি সুন্দর তথ্য দেয়: (k − 1)(n − k − 1) শূন্য হয় শুধু k = 1 বা k = n − 1-এ, অর্থাৎ disconnected graph-এ সবচেয়ে বেশি edge থাকে যখন একটি vertex একা আর বাকিরা পূর্ণ graph. ১০টি হাবে উত্তর তাই: connected হতে কমপক্ষে ৯টি রাস্তা লাগে, কিন্তু রাস্তার সংখ্যা ছাড়া আর কিছু না জানলে connected নিশ্চিত হতে চাই C(9, 2) + 1 = 37টি। দুই সংখ্যার বিশাল ফারাক দেখায়, edge-এর সংখ্যা একা connectivity-র দুর্বল নির্দেশক; কোথায় edge আছে সেটাই আসল কথা।

৪ · Bridge আর cut vertex — নেটওয়ার্কের দুর্বল জায়গা

ডেলিভারি নেটওয়ার্কে কোন একটি রাস্তা বন্ধ হলে কিছু হাব বিচ্ছিন্ন হয়ে যায়? কোন একটি হাব বন্ধ হলে? এই প্রশ্নগুলোর নাম:

সংজ্ঞা অনুযায়ী bridge খুঁজতে প্রতিটি edge সরিয়ে component গুনতে হয়। কিন্তু একটি পরিষ্কার চরিত্র-বর্ণনা আছে, যা হাতে-কলমে অনেক দ্রুত।

1. Lemma: e bridge ⇔ G − e-তে কোনো u–v path নেই। G − e-তে u–v path P থাকলে G-এর যেকোনো walk-এ e-এর জায়গায় P বসানো যায়, তাই “একই component” সম্পর্ক বদলায় না আর e bridge নয়। আর P না থাকলে u, v G-তে একই component-এ কিন্তু G − e-তে আলাদা; G − e-এর component-গুলো G-এর component ভেঙে আসে, তাই সংখ্যা বাড়ে। — উপপাদ্য ২.১
2. (⇐ দিক, contrapositive) ধরুন e কোনো cycle u, v, w₁, …, w_r, u-তে আছে। e বাদ দিলে v, w₁, …, w_r, u একটি u–v path যাতে e নেই। Lemma অনুযায়ী e bridge নয়। — cycle থেকে বিকল্প পথ
3. (⇒ দিক, contrapositive) ধরুন e bridge নয়। Lemma অনুযায়ী G − e-তে একটি u–v walk, আর উপপাদ্য ১.১ অনুযায়ী একটি u–v path P = (u, …, v). P-তে e নেই, আর G simple বলে u–v-এর একমাত্র edge e, তাই P-এর দৈর্ঘ্য ≥ 2. P-এর শেষে e জুড়লে কোনো vertex না ফিরিয়ে u-তে ফেরা যায়: একটি cycle যাতে e আছে। ∎ — path + edge = cycle

ডেলিভারি graph-এ উপপাদ্যটি কীভাবে কাজ করে, তা নিচের stepper-এ দেখুন। প্রতিটি edge-এর জন্য প্রশ্ন একটাই: এটি কোনো ত্রিভুজ বা অন্য cycle-এ আছে কি?

1V = {S,M,U,G,T,D,K}, ৮টি edge2S–M: কোনো cycle-এ?3M–U, U–G, G–M4G–T: কোনো cycle-এ?5T–D, D–K, K–T6ফল: bridge আর cut vertex

Cut vertex-এর জন্যও একই ধাঁচের তথ্য আছে। দুটি দরকারি কথা, সংক্ষিপ্ত প্রমাণসহ:

• Bridge-এর প্রান্ত: connected G-তে bridge {u, v}-এর প্রান্ত u-এর degree ≥ 2 হলে u একটি cut vertex. কারণ: u-এর আরেক প্রতিবেশী w নিন; w থেকে v-তে u এড়িয়ে কোনো path থাকলে তার সঙ্গে v–u–w জুড়ে e-যুক্ত একটি cycle হতো, যা উপপাদ্য ৪.২-এর বিরোধী। তাই G − u-তে w আর v আলাদা component-এ।
• সবাই cut vertex হতে পারে না: অন্তত ২টি vertex-এর connected graph-এ অন্তত দুটি vertex cut vertex নয়। কারণ: সবচেয়ে লম্বা path v₀, …, v_k নিন। v₀-এর সব প্রতিবেশী এই path-এর ওপর (নইলে path আরও লম্বা করা যেত)। তাই কোনো walk v₀ দিয়ে গেলে ঢোকা আর বের হওয়ার দুই প্রতিবেশীকে path-এর বাকি অংশ দিয়েই জোড়া যায়, v₀ বাদ দিয়ে। একই যুক্তি v_k-এর জন্য।

নিচের ব্লক উপপাদ্য ৪.২ একেবারে আলাদা পথে পরীক্ষা করে। “Bridge” বের হয় সংজ্ঞা থেকে (edge সরিয়ে component গোনা), আর “কোনো cycle-এ আছে” বের হয় সব edge-সেট খুঁজে: একটি edge-সেট একটি cycle যদি তার প্রতিটি vertex-এর degree ঠিক ২ আর সেটটি connected.

import random
from itertools import combinations
def n_comps(V, E):                     # count components by search
    adj = {v: set() for v in V}
    for u, v in E:
        adj[u].add(v); adj[v].add(u)
    seen, c = set(), 0
    for s in V:
        if s not in seen:
            c += 1; stack = [s]; seen.add(s)
            while stack:
                for y in adj[stack.pop()] - seen:
                    seen.add(y); stack.append(y)
    return c
def is_cycle(F):                       # edge set = one cycle?
    deg = {}
    for u, v in F:
        deg[u] = deg.get(u, 0) + 1; deg[v] = deg.get(v, 0) + 1
    return all(d == 2 for d in deg.values()) and n_comps(list(deg), F) == 1
random.seed(59)
stats = [0, 0, 0]                      # edges, bridges, cut vertices
for trial in range(150):
    V = list(range(6))
    E = [e for e in combinations(V, 2) if random.random() < 0.4]
    c = n_comps(V, E); stats[0] += len(E)
    for e in E:                        # bridge <=> on no cycle
        bridge = n_comps(V, [f for f in E if f != e]) > c
        on_cycle = any(is_cycle(F) for k in range(3, 7)
                       for F in combinations(E, k) if e in F)
        assert bridge == (not on_cycle); stats[1] += bridge
    for v in V:                        # cut vertex: removal splits
        W = [x for x in V if x != v]
        stats[2] += n_comps(W, [f for f in E if v not in f]) > c
print("edges, bridges, cut vertices:", stats)
print("every bridge is on no cycle, every non-bridge on a cycle")

edges, bridges, cut vertices: [867, 290, 207]
every bridge is on no cycle, every non-bridge on a cycle

৫ · কতটা মজবুত — κ, λ, δ আর Whitney-এর অসমতা

Bridge বা cut vertex থাকা মানে একটি ব্যর্থতাতেই নেটওয়ার্ক ভাঙে। কিন্তু দুটি রাস্তা একসঙ্গে বন্ধ হলে? “কতগুলো ব্যর্থতা সহ্য করা যায়” তা মাপার জন্য দুটি সংখ্যা।

ডেলিভারি graph-এ κ = λ = δ = 1 (S-এর degree 1, M একটি cut vertex, S–M একটি bridge). K_n-এ তিনটিই n − 1. তিনটির সম্পর্ক সবসময় একই দিকে:

1. λ ≤ δ: সবচেয়ে ছোট degree-র vertex v-এর δটি edge সরালে v একা হয়ে যায়, আর বাকি অন্তত একটি vertex আছে, তাই graph disconnected. — একটি সরাসরি edge cut
2. κ ≤ λ, সহজ ক্ষেত্র: G disconnected হলে দুটিই 0. এখন ধরুন G connected, আর F একটি সবচেয়ে ছোট edge cut, |F| = λ। G − F-এর vertex-গুলোকে দুই ভাগ X আর Y-তে সাজান, যাতে X থেকে Y-এ যাওয়া প্রতিটি edge F-এ থাকে। — সংজ্ঞা
3. যদি X-এর প্রতিটি vertex Y-এর প্রতিটির সঙ্গে যুক্ত হয়, তবে |F| ≥ |X|·|Y| ≥ n − 1 (দুটি ধনাত্মক পূর্ণসংখ্যার যোগফল n হলে গুণফল ≥ n − 1). আর যেকোনো graph-এ κ ≤ n − 1, তাই κ ≤ λ। — পূর্ণ দ্বিভাগ
4. নইলে x ∈ X আর y ∈ Y আছে যারা সংলগ্ন নয়। F-এর প্রতিটি edge থেকে একটি প্রান্ত বাছুন: edge-টি x-কে না ছুঁলে তার X-প্রান্ত, ছুঁলে তার Y-প্রান্ত। বাছাই করা vertex-গুলোর সেট S; |S| ≤ |F|, আর S-এ x নেই, y-ও নেই (x আর y সংলগ্ন নয় বলে x-এর কোনো edge y-তে যায় না)। — প্রতিটি cut edge থেকে একটি প্রান্ত
5. যেকোনো x–y path-কে X থেকে Y-এ যেতে F-এর কোনো edge ধরতে হয়, আর সেই edge-এর বাছাই করা প্রান্ত path-এর ওপর আছে। তাই G − S-এ x থেকে y-তে path নেই, G − S disconnected, আর κ ≤ |S| ≤ λ। ∎ — প্রতিটি পথ আটকানো

অসমতা দুটি কঠোরও হতে পারে। দুটি আলাদা K₄ নিন (a1–a4 আর b1–b4), আর a1–b1, a1–b2 দুটি edge জুড়ুন। a1 সরালে দুই দল আলাদা, তাই κ = 1; দুই দলের মধ্যে দুটি edge, তাই λ = 2; আর সবচেয়ে ছোট degree 3, তাই δ = 3. নিচের ব্লক এই উদাহরণ আর ২০০টি এলোমেলো graph-এ brute force দিয়ে তিনটি সংখ্যা বের করে।

import random
from itertools import combinations
def connected(V, E):
    seen, stack = {V[0]}, [V[0]]
    while stack:
        x = stack.pop()
        for u, v in E:
            for a, b in ((u, v), (v, u)):
                if a == x and b not in seen:
                    seen.add(b); stack.append(b)
    return len(seen) == len(V)
def kld(V, E):                         # brute force kappa, lambda, delta
    delta = min(sum(v in e for e in E) for v in V)
    lam = next(k for k in range(len(E) + 1) if any(not connected(V,
               [e for e in E if e not in S]) for S in combinations(E, k)))
    if len(E) == len(V) * (len(V) - 1) // 2:
        return len(V) - 1, lam, delta  # complete graph: kappa = n - 1
    kap = next(k for k in range(len(V)) if any(not connected(
               [v for v in V if v not in S],
               [e for e in E if not set(e) & set(S)])
               for S in combinations(V, k)))
    return kap, lam, delta
a, b = ["a1", "a2", "a3", "a4"], ["b1", "b2", "b3", "b4"]
E = list(combinations(a, 2)) + list(combinations(b, 2))
E += [("a1", "b1"), ("a1", "b2")]               # two edges join the K4s
print("two K4 + 2 edges:", kld(a + b, E))
random.seed(59); gaps = [0, 0]
for trial in range(200):
    V = list(range(random.randint(2, 7)))
    E = [e for e in combinations(V, 2) if random.random() < 0.6]
    k, l, d = kld(V, E)
    assert k <= l <= d                 # Whitney's inequality
    gaps[0] += k < l; gaps[1] += l < d
print("200 random graphs: kappa <= lambda <= delta; kappa < lambda in",
      gaps[0], "graphs, lambda < delta in", gaps[1])

two K4 + 2 edges: (1, 2, 3)
200 random graphs: kappa <= lambda <= delta; kappa < lambda in 5 graphs, lambda < delta in 1

৬ · Menger-এর উপপাদ্য — আলাদা পথ গোনা আর পথ কাটা একই সংখ্যা

দুটি নির্দিষ্ট vertex s আর t-এর কথা ভাবুন: সাভারের গুদাম থেকে একটি গ্রাহক-এলাকা। “কতটা মজবুত সংযোগ” দুইভাবে মাপা যায়। এক, এমন কয়টি পথ আছে যারা মাঝপথে কোনো vertex ভাগ করে না, যাতে একটি হাব বন্ধ হলে বড়জোর একটি পথ নষ্ট হয়? দুই, s থেকে t আলাদা করতে সবচেয়ে কম কয়টি হাব বন্ধ করতে হয়?

সহজ দিকের প্রমাণ (সর্বোচ্চ ≤ সর্বনিম্ন):

1. k-টি internally disjoint s–t path আর যেকোনো s–t separator S নিন। S সরালে কোনো path থাকে না, তাই প্রতিটি path-এর মাঝখানের (s, t নয় এমন) অন্তত একটি vertex S-এ আছে। — separator-এর সংজ্ঞা
2. Path-গুলোর মাঝখানের vertex পরস্পর আলাদা, তাই এই k-টি vertex-ও আলাদা, আর |S| ≥ k. সব path-সংগ্রহ আর সব separator-এ এটি খাটে, তাই সর্বোচ্চ ≤ সর্বনিম্ন। ∎ — প্রতিটি পথে একটি আলাদা প্রতিনিধি

কঠিন দিক (সবচেয়ে ছোট separator-এর আকারের সমান সংখ্যক path সত্যিই পাওয়া যায়) এখানে প্রমাণ করা হলো না। একটি পথ হলো edge-গুলোকে capacity 1 দিয়ে একটি flow network বানিয়ে max-flow min-cut theorem প্রয়োগ করা (vertex রূপে প্রতিটি vertex-কে “ঢোকা” আর “বের হওয়া” দুই ভাগে ভেঙে মাঝে capacity 1-এর edge), যার algorithm আর প্রমাণ DSA কোর্সের পর্ব ৪৭-এ। Menger-এর উপপাদ্য ১৯২৭ সালের বলে সাধারণত উল্লেখ করা হয়, max-flow min-cut-এর প্রায় তিন দশক আগে; সরাসরি induction-ভিত্তিক প্রমাণ প্রায় সব graph theory পাঠ্যবইয়ে আছে।

1সব s–t path তালিকা2প্রথম পথ বাছাই3দ্বিতীয় পথ, d আর a এড়িয়ে4তৃতীয় পথ সম্ভব?5separator খোঁজা

Menger থেকে একটি সামগ্রিক রূপ আসে, যা Hassler Whitney-এর ১৯৩২ সালের কাজের সঙ্গে যুক্ত বলে উল্লেখ করা হয়: অন্তত k + 1 vertex-এর G k-connected যদি এবং কেবল যদি প্রতিটি জোড়া আলাদা vertex-এর মধ্যে k-টি internally disjoint path থাকে; একইভাবে k-edge-connected ⇔ প্রতিটি জোড়ার মধ্যে k-টি edge-disjoint path. পুরো graph-এর λ(G) আসলে সবচেয়ে ছোট global minimum cut, যা পর্ব ৪৩ “Probabilistic method আর randomized algorithm”-এর Karger-এর algorithm এলোমেলো edge contraction দিয়ে খোঁজে। নিচের ব্লক vertex রূপটি ছোট এলোমেলো graph-এ দুই দিক থেকেই brute force দিয়ে মেলায়।

import random
from itertools import combinations
def paths(adj, s, t, p=None):          # every simple s-t path
    p = p or [s]
    if p[-1] == t:
        yield p; return
    for y in adj[p[-1]]:
        if y not in p:
            yield from paths(adj, s, t, p + [y])
def most_disjoint(inner):              # largest set of disjoint interiors
    if not inner: return 0
    first, rest = inner[0], inner[1:]
    return max(most_disjoint(rest),
               1 + most_disjoint([q for q in rest if not q & first]))
def min_separator(V, P, s, t):         # smallest vertex set hitting all
    others = [v for v in V if v not in (s, t)]
    return next(k for k in range(len(others) + 1)
                for S in combinations(others, k)
                if all(set(S) & p for p in P))
random.seed(59); checked = 0
for trial in range(120):
    V = list(range(7))
    adj = {v: set() for v in V}
    for u, v in combinations(V, 2):
        if random.random() < 0.45:
            adj[u].add(v); adj[v].add(u)
    s, t = 0, 6
    if t in adj[s]: continue           # vertex form needs s, t non-adjacent
    P = [set(p[1:-1]) for p in paths(adj, s, t)]
    assert most_disjoint(P) == min_separator(V, P, s, t)
    checked += 1
print(checked, "non-adjacent pairs: max disjoint paths == min separator")

59 non-adjacent pairs: max disjoint paths == min separator

৭ · Directed graph — strongly আর weakly connected

শহরে একমুখী রাস্তা থাকলে “পৌঁছানো যায়” আর দুই দিকে সমান থাকে না: মতিঝিল থেকে গুলশান যাওয়া গেলেও উল্টোটা না-ও যেতে পারে। Directed graph-এ walk মানে তীরের দিক মেনে চলা, আর reachability সাধারণত symmetric নয়।

1. Reflexive: দৈর্ঘ্য ০-এর walk. Symmetric: সংজ্ঞাটি u আর v-তে প্রতিসম। — সংজ্ঞা
2. Transitive: u ↔ v আর v ↔ w হলে u → v → w-এর walk জুড়ে u থেকে w, আর w → v → u জুড়ে w থেকে u. ∎ — walk জোড়া

এটি পর্ব ৫৪-এর reachability relation R* আর তার উল্টো (R*)⁻¹-এর intersection (Δ-সহ), আর পর্ব ৫৫-এর উপপাদ্য অনুযায়ী intersection-এ equivalence টিকে থাকে। প্রতিটি SCC-কে একটি বিন্দুতে গুটিয়ে নিলে যে directed graph পাওয়া যায়, তাকে বলে condensation; এটি সবসময় একটি DAG (directed acyclic graph). কারণ: দুই বা ততোধিক SCC-এর মধ্যে একটি directed cycle থাকলে cycle-এর সব vertex পরস্পরের কাছে দুই দিকে পৌঁছাতে পারত, তাই তারা একই SCC-তে থাকত, বিরোধ। ফলে যেকোনো directed graph হলো “SCC-গুলোর একটি topological ক্রম”, যার গণিত পর্ব ৫৬-এ। একটি DAG-এ প্রতিটি SCC একটি মাত্র vertex, তাই n-vertex DAG-এ SCC ঠিক nটি। SCC বের করার Kosaraju আর Tarjan-এর algorithm DSA কোর্সের পর্ব ৪৬-এ আছে।

উদাহরণ: হাব A → B → C → A আর C → D → E → D. SCC: {A, B, C}, {D, E}; D থেকে C-তে ফেরা যায় না, তাই graph weakly connected কিন্তু strongly connected নয়; condensation হলো দুটি বিন্দু আর একটি তীর।

৮ · দূরত্ব, diameter, matrix-এর ঘাত আর BFS-এর প্রমাণ

Connected graph-এ distance d(u, v) = u থেকে v-এর সবচেয়ে ছোট path-এর দৈর্ঘ্য (edge-এর সংখ্যা); path না থাকলে d = ∞। উপপাদ্য ১.১ অনুযায়ী এটি সবচেয়ে ছোট walk-এর দৈর্ঘ্যও। d একটি metric: d(u, v) = 0 ⇔ u = v; d(u, v) = d(v, u) (path উল্টানো); আর ত্রিভুজ অসমতা d(u, w) ≤ d(u, v) + d(v, w), কারণ দুটি সবচেয়ে ছোট path জুড়লে d(u, v) + d(v, w) দৈর্ঘ্যের একটি u–w walk পাওয়া যায়, আর সবচেয়ে ছোট u–w walk তার চেয়ে লম্বা নয়। Diameter হলো সব জোড়ার মধ্যে সর্বোচ্চ distance.

ডেলিভারি graph-এ (scratch-এ BFS দিয়ে গুনে মেলানো) সাভার থেকে দূরত্ব: M 1; U আর G 2; T 3; D আর K 4. Diameter 4 (যেমন S থেকে K: S, M, G, T, K). G থেকে প্রতিটি হাব বড়জোর ২ দূরে, তাই গুদাম বসানোর সেরা জায়গা গুলশান: “সবচেয়ে দূরের হাব কত দূরে” প্রশ্নে G-এর উত্তর ২, যা সব vertex-এর মধ্যে সবচেয়ে কম।

Adjacency matrix-এর ঘাত। পর্ব ১৯-এ প্রমাণ হয়েছে, A^k-এর (u, v) ঘর = u থেকে v-এর দৈর্ঘ্য-k walk-এর সংখ্যা। উপপাদ্য ১.১-এর সঙ্গে মিলিয়ে: d(u, v) = সবচেয়ে ছোট k, যার জন্য (A^k)_uv > 0. ডেলিভারি graph-এ S থেকে K-এর ঘর A, A², A³-এ 0 আর A⁴-এ 1, তাই d(S, K) = 4. আর M থেকে T: A²-এ 1 (M, G, T), A⁴-এ 7, কারণ লম্বা walk-এ ত্রিভুজের চারপাশে ঘোরা যায়। (A³-এর কর্ণের যোগফল ÷ 6 = ত্রিভুজের সংখ্যা; এখানে 12 ÷ 6 = 2.)

1. দাবি P(k): স্তর k-এর vertex-গুলো ঠিক {v : d(s, v) = k}। k = 0-তে দুই পাশেই শুধু s. — base case
2. BFS-এর queue FIFO, তাই স্তর 0-এর সব vertex, তারপর স্তর 1-এর সব, এভাবে ক্রমে প্রক্রিয়া হয়; স্তর k + 1-এর vertex শুধু স্তর k-এর vertex থেকে আবিষ্কৃত হয়। — queue-এর ধর্ম
3. ধরুন P(0), …, P(k) সত্য। v স্তর k + 1-এ থাকলে তার একটি প্রতিবেশী x স্তর k-এ, তাই d(s, v) ≤ k + 1; আর v আগের কোনো স্তরে নেই, তাই inductive hypothesis অনুযায়ী d(s, v) > k. অতএব d(s, v) = k + 1. — strong induction, পর্ব ১১
4. উল্টো দিকে d(s, v) = k + 1 হলে একটি সবচেয়ে ছোট path-এ v-এর আগের vertex x-এর d(s, x) = k, তাই x স্তর k-এ। x প্রক্রিয়ার সময় v আগে না দেখা হলে স্তর k + 1-এ আবিষ্কৃত হয়; আর আগে দেখা হতে পারে না, কারণ স্তর ≤ k-তে শুধু দূরত্ব ≤ k-এর vertex. ∎ — দুই দিকের অন্তর্ভুক্তি

প্রমাণে edge-এর “ওজন নেই” কথাটি ধাপ ৩-এ লেগেছে: প্রতিটি edge ঠিক ১ দূরত্ব যোগ করে। রাস্তায় সময় বা দূরত্বের ওজন থাকলে BFS ভুল উত্তর দিতে পারে, তখন Dijkstra লাগে, যার প্রমাণ পর্ব ৬১ “Shortest path-এর গণিত — Dijkstra-র প্রমাণ আর traveling salesperson”-এ।

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

অঙ্ক ১: Edge গুনে সিদ্ধান্ত

(ক) ১০ vertex-এর একটি simple graph-এ ৩৭টি edge. এটি কি অবশ্যই connected? (খ) ৩৬টি হলে? (গ) ১২ vertex আর ৮ edge-এর graph-এ অন্তত কয়টি component?

1. (ক) C(9, 2) = 36 < 37, তাই উপপাদ্য ৩.২ অনুযায়ী হ্যাঁ।
2. (খ) না, অবশ্যই নয়: K₉ আর একটি একা vertex, ঠিক ৩৬টি edge, connected নয়।
3. (গ) উপপাদ্য ৩.১: c ≥ 12 − 8 = 4; সমতা হয় যেমন ৮টি edge-এর একটি path আর ৩টি একা vertex নিলে (9 + 3 = 12 vertex, component 4).

অঙ্ক ২: κ, λ, δ

দুটি K₄, {a1, a2, a3, a4} আর {b1, b2, b3, b4}, তার সঙ্গে a1–b1 আর a1–b2. κ, λ, δ বের করুন।

1. δ: b3, b4, a2, a3, a4-এর degree 3; a1-এর 5; b1, b2-এর 4. তাই δ = 3.
2. λ: দুই দলের মধ্যে ঠিক দুটি edge, সরালে graph ভাঙে, তাই λ ≤ 2. একটি edge সরালে ভাঙে না: দুই দলের মধ্যে আরেকটি edge থাকে, আর K₄-এর ভেতর থেকে একটি edge সরালেও K₄ connected (λ(K₄) = 3). তাই λ = 2.
3. κ: a1 সরালে দুই দলের মধ্যে কোনো edge থাকে না, তাই κ = 1. (১ < ২ < ৩, তৃতীয় Python ব্লকে মেলানো।)

অঙ্ক ৩: দূরত্ব matrix থেকে

ডেলিভারি graph-এ (A³)_SK = 0 আর (A⁴)_SK = 1. d(S, K) কত, আর দৈর্ঘ্য-৪ walk-টি কোনটি? উত্তর: d(S, K) = 4 (§৮-এর সূত্র), আর একমাত্র walk S, M, G, T, K (S-এর একমাত্র প্রতিবেশী M, আর G–T bridge পেরোতেই হয়)।

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

একজন লিখলেন: “e = {u, v} যেকোনো edge নিন। deg(u) ≥ 2, তাই u-এর আরেকটি প্রতিবেশী w আছে; একইভাবে v-এর আরেকটি প্রতিবেশী x. e সরালেও u আর v দুজনেই অন্যদের সঙ্গে যুক্ত থাকে, তাই graph connected থাকে। সুতরাং কোনো edge bridge নয়।”

ভুল কোথায়: “u আর v দুজনেই কারও সঙ্গে যুক্ত” থেকে “u থেকে v-তে e ছাড়া পথ আছে” আসে না; §৪-এর lemma অনুযায়ী দরকার ঠিক দ্বিতীয়টি। পাল্টা-উদাহরণ: দুটি ত্রিভুজ {1, 2, 3} আর {4, 5, 6}, মাঝে edge 3–4. সব degree ≥ 2, অথচ 3–4 কোনো cycle-এ নেই, তাই উপপাদ্য ৪.২ অনুযায়ী bridge (scratch-এ component গুনে মেলানো)। সঠিক কথা: δ ≥ 2 হলে graph-এ অন্তত একটি cycle আছে (সবচেয়ে লম্বা path-এর শেষ vertex-এর যুক্তি), কিন্তু প্রতিটি edge cycle-এ থাকবে, এমন কোনো নিশ্চয়তা নেই।

১০ · AI-এর যুগে — graph-এর প্রমাণ আর হিসাব যাচাই

Connectivity-র প্রশ্নে AI সহকারী সংজ্ঞা সাধারণত ঠিক বলে, কিন্তু প্রমাণে আর সংখ্যায় আত্মবিশ্বাসী ভুল করে। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

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

• Walk, path আর cycle-এর সংজ্ঞা লেখা আছে, আর graph-এর ধরন (simple, multi, directed) স্পষ্ট
• Induction-এর ধাপ যেকোনো বড় graph থেকে শুরু হয়ে ছোটটিতে নেমেছে, উল্টো পথে নয়
• ব্যবহৃত প্রতিটি উপপাদ্যের শর্ত (অসংলগ্ন s, t; unweighted; simple) মিলিয়েছি
• ছোট graph-এ brute force দিয়ে উত্তর মিলিয়েছি (component, bridge, κ, λ)
• দাবির উল্টো কথাটি আলাদাভাবে পরীক্ষা করেছি, যাতে converse প্রমাণ হয়ে না যায়
• উদ্ধৃত নাম, সাল আর উৎস বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

Graph-এর দাবি যাচাইয়ের বড় সুবিধা: ৬টি vertex-এ মাত্র 2¹⁵ = 32768টি labelled simple graph, যা এক মুহূর্তে সব পরীক্ষা করা যায়। ভুল প্রমাণ সাধারণত এত ছোট graph-এই ধরা পড়ে; তাই আগে পাল্টা-উদাহরণ খুঁজুন, তারপর প্রমাণে ভরসা করুন।