Graph Theory — সংযোগের গণিত

না।

Handshake lemma: $\sum \deg(v) = 2|E|$

$7 \times 3 = 21$

কিন্তু 21 বিজোড়, আর 2|E| সবসময় জোড়। বিরোধ। ∎

সাধারণ নিয়ম: বিজোড় degree-র vertex সংখ্যা অবশ্যই জোড় হতে হবে। এখানে ৭টা vertex-ই বিজোড় degree-র — ৭ বিজোড়, তাই অসম্ভব।

সংশোধন: ৬টা vertex-এর প্রতিটার degree ৩ হলে সম্ভব (6 × 3 = 18 = 2 × 9, অর্থাৎ ৯টা edge)। যেমন K₃,₃ বা একটা prism graph।

এই check-টা কোথায় কাজে লাগে:

একটা network topology config parse করার পর এটা একটা সস্তা sanity check:

def validate_topology(degrees):
    total = sum(degrees)
    if total % 2:
        raise ValueError(f"degree যোগফল {total} বিজোড় — config-এ ভুল আছে")
    odd = sum(1 for d in degrees if d % 2)
    assert odd % 2 == 0
    return total // 2      # edge সংখ্যা

কোনো graph না বানিয়েই ভুল ধরা পড়ে।

Erdős–Gallai theorem আরো এগিয়ে যায়: একটা degree sequence কখন realizable সেটার সম্পূর্ণ শর্ত দেয়। Handshake শুধু প্রয়োজনীয় শর্ত, যথেষ্ট নয় — যেমন (3, 1, 1, 1) যোগফল জোড় কিন্তু তবু অসম্ভব simple graph-এ।

প্রমাণ (contradiction).

ধরি একটা tree T-তে n ≥ 2 vertex আছে কিন্তু সর্বোচ্চ একটা leaf।

তাহলে অন্তত n − 1 টা vertex-এর degree ≥ 2।

Degree-র যোগফল: $\sum \deg(v) \ge 2(n-1) + 1 = 2n - 1$

(সবচেয়ে ভালো ক্ষেত্রে: n−1 টা vertex-এর degree ২, আর একটা leaf-এর ১)

Handshake lemma অনুযায়ী: $\sum \deg(v) = 2|E|$

Tree-তে |E| = n − 1 (আগে প্রমাণিত), তাই: $\sum \deg(v) = 2(n-1) = 2n - 2$

কিন্তু আমরা পেয়েছিলাম ≥ 2n − 1।

$2n - 2 \ge 2n - 1 \implies -2 \ge -1$

মিথ্যা। বিরোধ। ∎

বিকল্প প্রমাণ (constructive) — অনেক বেশি অন্তর্দৃষ্টিপূর্ণ:

T-এর একটা দীর্ঘতম path নিন: v₀ → v₁ → … → vₖ (k ≥ 1 যেহেতু n ≥ 2 এবং connected)।

দাবি: v₀ আর vₖ দুটোই leaf।

ধরুন v₀-এর degree ≥ 2। তাহলে v₁ ছাড়াও আরেকটা প্রতিবেশী u আছে।

• যদি u path-এ না থাকে → path বাড়ানো যেত (u → v₀ → … → vₖ), কিন্তু আমরা দীর্ঘতম নিয়েছিলাম। বিরোধ।
• যদি u path-এ থাকে → v₀ থেকে u পর্যন্ত path আর নতুন edge মিলে একটা cycle। কিন্তু tree acyclic। বিরোধ।

তাই v₀ leaf। একই যুক্তিতে vₖ leaf। ∎

তাৎপর্য: এই leaf-এর অস্তিত্বই বহু tree algorithm-এর ভিত্তি — আপনি সবসময় একটা leaf খুঁজে সরিয়ে ছোট tree-তে নামতে পারবেন।

• Tree-র edge সংখ্যার induction প্রমাণে এটাই ব্যবহার করেছি
• Huffman coding leaf থেকে শুরু করে উপরে ওঠে
• Tree DP প্রায়ই leaf থেকে root-এর দিকে চলে
• Topological sort-এর Kahn’s algorithm একই ধারণার DAG-রূপ

মডেল:

• Vertex = service
• Edge A → B = A, B-র উপর নির্ভর করে (B fail করলে A প্রভাবিত)

Blast radius of X = যেসব service X-এ পৌঁছাতে পারে = reverse graph-এ X থেকে reachable set

def blast_radius(deps, service):
    """deps: {service: [যাদের উপর নির্ভর করে]}"""
    reverse = defaultdict(set)
    for s, targets in deps.items():
        for t in targets:
            reverse[t].add(s)          # t fail → s প্রভাবিত

    seen, q = set(), deque([service])
    while q:
        u = q.popleft()
        for v in reverse[u]:
            if v not in seen:
                seen.add(v); q.append(v)
    return seen

একটা BFS — O(V + E)।

আরো দরকারি metric গুলো:

শেষটা বিশেষভাবে দরকারি — articulation point (বা cut vertex) খোঁজার জন্য Tarjan-এর O(V+E) algorithm আছে। এগুলোই আপনার প্রকৃত single point of failure।

তিনটা সূক্ষ্মতা যা প্রায়ই বাদ পড়ে:

১. Hard বনাম soft dependency। A, B-র উপর নির্ভর করে — কিন্তু B fail করলে A কি পুরো বন্ধ হয়, নাকি degraded mode-এ চলে? Edge-এ একটা weight বা label দিন।

edges = {("api", "auth"): "hard",
         ("api", "recommendations"): "soft"}

Soft edge blast radius-এ গোনা উচিত নয় (বা কম ওজনে)।

২. লুকানো dependency। আপনার service graph-এ DNS, নেই? Certificate authority? Cloud provider-এর metadata service? এগুলো প্রায় সব service-এর dependency, আর প্রায়ই diagram-এ থাকে না — অথচ এগুলোই বাস্তব outage-এর কারণ হয়।

৩. Transitive weight। A → B → C -তে C fail করলে A প্রভাবিত, কিন্তু হয়তো B-র caching-এর কারণে কম। Probability দিয়ে মডেল করা যায়:

$P(A \text{ প্রভাবিত}) = 1 - \prod_{\text{path}} (1 - P(\text{path fail}))$

ব্যবহারিক সুপারিশ:

1. Service manifest থেকে graph auto-generate করুন (distributed tracing data সবচেয়ে নির্ভরযোগ্য উৎস — declared নয়, actual call)
2. CI-তে cycle detection চালান
3. Blast radius একটা dashboard metric বানান
4. উচ্চ blast radius-এর service-এ বেশি SLO, বেশি redundancy, staged rollout

Level 12-এ আমরা distributed tracing থেকে এই graph বানাব।

Matrix গুণের সংজ্ঞা:

$(M^2)_{ij} = \sum_{k} M_{ik} \cdot M_{kj}$

M boolean (0/1) হলে, M[i][k] × M[k][j] = 1 তখনই যখন i → k এবং k → j — অর্থাৎ i থেকে j-তে k হয়ে একটা ২-দৈর্ঘ্যের path আছে।

যোগফলটা সব সম্ভাব্য মধ্যবর্তী k-এর উপর, তাই:

$(M^2)_{ij} = i \text{ থেকে } j \text{-তে ঠিক ২ দৈর্ঘ্যের walk-এর সংখ্যা}$

সাধারণভাবে:

$(M^k)_{ij} = i \text{ থেকে } j \text{-তে ঠিক } k \text{ দৈর্ঘ্যের walk-এর সংখ্যা}$

লক্ষ্য করুন “walk”, “path” নয় — vertex পুনরাবৃত্তি অনুমোদিত।

প্রয়োগ:

১. ত্রিভুজ গোনা। trace(M³)/6 = undirected graph-এ ত্রিভুজের সংখ্যা।

কারণ (M³)ᵢᵢ = i থেকে i-তে ৩-দৈর্ঘ্যের walk = i জড়িত ত্রিভুজ। প্রতিটা ত্রিভুজ ৩টা vertex-এ গোনা হয়, আর প্রতিটা ২ দিকে — তাই 6 দিয়ে ভাগ।

Social network-এ ত্রিভুজ গোনা = clustering coefficient মাপা = “আমার বন্ধুরা কি একে অপরের বন্ধু?”

২. Reachability। Boolean semiring-এ (+ → OR, × → AND):

$M \vee M^2 \vee \cdots \vee M^{n-1} = \text{transitive closure}$

কারণ n vertex-এর graph-এ যেকোনো path সর্বোচ্চ n−1 দৈর্ঘ্যের।

৩. Shortest path। Min-plus semiring-এ (+ → min, × → +):

$(M^{\otimes k})_{ij} = \text{সর্বোচ্চ } k \text{ edge-এর shortest path}$

এটাই Floyd–Warshall-এর matrix রূপ, আর একই কারণে repeated squaring দিয়ে O(n³ log n)-এ all-pairs shortest path করা যায়।

৪. PageRank। Transition matrix-এর বারবার গুণ, যা eigenvector power iteration। Google-এর মূল algorithm।

৫. Markov chain। M যদি transition probability matrix হয়, তাহলে M^k = k ধাপ পরের distribution।

BFS কেন কাজ করে:

BFS স্তরে স্তরে অগ্রসর হয় — প্রথমে দূরত্ব ১-এর সব vertex, তারপর দূরত্ব ২, ইত্যাদি।

Invariant: যখন একটা vertex প্রথমবার queue-তে ঢোকে, তখন তার দূরত্ব চূড়ান্ত।

প্রমাণ (induction on distance).

Base: dist(s) = 0, স্পষ্ট।

Step: ধরি দূরত্ব ≤ d-এর সব vertex সঠিক দূরত্বে আবিষ্কৃত। Queue-তে এখন শুধু দূরত্ব d ও d+1-এর vertex আছে (FIFO ধর্ম)।

দূরত্ব d+1-এর একটা vertex v নিন। তার একটা প্রতিবেশী u আছে যার দূরত্ব d। u প্রক্রিয়াকৃত হলে v আবিষ্কৃত হবে, আর dist[v] = dist[u] + 1 = d+1 ✓ ∎

DFS কেন ব্যর্থ:

DFS একটা শাখায় যতদূর সম্ভব যায়। তাই একটা vertex-এ পৌঁছাতে পারে একটা দীর্ঘ ঘুরপথে, আর সেটা “visited” চিহ্নিত করে দেয়। পরে ছোট path পাওয়া গেলেও আর update হয় না।

    a
   / \
  b   c
  |   |
  d   |
   \ /
    e

a → e-এর shortest path হলো a → c → e (দৈর্ঘ্য ২)।

DFS যদি b আগে দেখে: a → b → d → e (দৈর্ঘ্য ৩) দিয়ে e পৌঁছাবে আর visited করে দেবে। ভুল উত্তর।

DFS-কে বাধ্য করা যায়?

হ্যাঁ, কিন্তু দাম দিয়ে।

বিকল্প ১ — visited না রেখে সব path দেখুন:

def all_paths_dfs(adj, u, target, path=None, best=None):
    path = (path or []) + [u]
    if u == target:
        return path if not best or len(path) \< len(best) else best
    for v in adj[u]:
        if v not in path:                    # শুধু বর্তমান path-এ চেক
            best = all_paths_dfs(adj, v, target, path, best)
    return best

সঠিক, কিন্তু exponential — সব path enumerate করে।

বিকল্প ২ — Iterative Deepening DFS (IDDFS):

def iddfs(adj, s, t, max_depth):
    def dls(u, t, depth, path):
        if u == t: return path
        if depth == 0: return None
        for v in adj[u]:
            if v not in path:
                r = dls(v, t, depth-1, path + [v])
                if r: return r
        return None
    for d in range(max_depth + 1):
        r = dls(s, t, d, [s])
        if r: return r
    return None

গভীরতা ১, ২, ৩… করে বারবার DFS চালান। প্রথম যেটা পায় সেটাই shortest।

খরচ: উপরের স্তরগুলো বারবার visit হয়। কিন্তু branching factor b হলে মোট কাজ:

$\sum_{i=0}^{d} b^i \approx \frac{b^{d+1}}{b-1} = O(b^d)$

অর্থাৎ শেষ স্তরটাই খরচের প্রায় পুরোটা — পুনরাবৃত্তির overhead ধ্রুবক গুণক মাত্র।

IDDFS কেন ব্যবহার হয়:

Memory-টাই আসল সুবিধা। BFS-কে পুরো frontier রাখতে হয়, যা exponential হতে পারে। IDDFS শুধু বর্তমান path রাখে।

তাই বিশাল search space-এ (chess, puzzle solver, game AI) IDDFS প্রামাণ্য — আর তার heuristic-সহ সংস্করণ IDA* বহু puzzle solver-এর ভিত্তি।

Level 6-এ আমরা এগুলো implement করব।