গ্রাফ — সংজ্ঞা, degree আর handshake theorem

১ · গ্রাফ কী — vertex, edge আর চার ধরনের গ্রাফ

বাজারঘরের ডেলিভারি বিভাগের দেয়ালে একটি মানচিত্র ঝোলে: ঢাকার আশেপাশের কয়েকটি হাব, আর কোন দুটি হাবের মধ্যে সরাসরি ভ্যান চলে, তা দাগ টেনে দেখানো। দাগগুলো কত লম্বা, মানচিত্রে হাবটি ঠিক কোথায় আঁকা, এসব এখানে গুরুত্বহীন। প্রশ্ন শুধু একটি: কে কার সঙ্গে সরাসরি যুক্ত? এই “কে কার সঙ্গে যুক্ত” তথ্যটুকুর গাণিতিক রূপের নাম graph (গ্রাফ)। এখানে “graph” মানে ফাংশনের লেখচিত্র নয়, বরং একটি সংযোগ-কাঠামো।

সংজ্ঞার দুটি শব্দ গুরুত্বপূর্ণ। “দুই-উপাদানের” মানে u ≠ v, তাই কোনো vertex নিজের সঙ্গে যুক্ত নয়। আর E একটি সেট, তাই একই জোড়া দুবার থাকতে পারে না। বাস্তবের অনেক নেটওয়ার্কে এই দুটি শর্তই ভাঙে, তাই আরও তিন ধরনের graph দরকার হয়:

Multigraph-এ একই দুই vertex-এর মধ্যের একাধিক edge-কে বলে parallel edge, আর pseudograph-এর v থেকে v-তে ফেরা edge-কে loop (self-loop). এই দুটি সম্ভব করতে edge-কে আর শুধু একটি জোড়া হিসেবে দেখা যায় না; প্রতিটি edge-এর নিজস্ব নাম থাকে, আর একটি ফাংশন বলে দেয় তার দুই প্রান্ত কোন দুটি vertex. বইভেদে নামগুলো একটু আলাদা: অনেক বই “multigraph” বলতে loop-সহ graph-ও বোঝায়। তাই প্রতিটি উপপাদ্যের সঙ্গে স্পষ্ট লেখা থাকা দরকার কোন ধরনের graph-এর কথা হচ্ছে; এই পর্বে প্রতিটি উপপাদ্যে তা লেখা আছে, আর কিছু না বললে “graph” মানে simple, undirected graph.

Adjacency সম্পর্কটি আসলে V-এর ওপর একটি relation: simple graph-এ এটি symmetric আর irreflexive, আর উল্টো দিকে V-এর ওপর যেকোনো symmetric, irreflexive relation একটি simple graph দেয়। Directed graph আর relation-এর একই সম্পর্ক পর্ব ৫২ “Relation আর তার ধর্ম”-এ দেখানো হয়েছে, আর graph-কে matrix হিসেবে লেখা পর্ব ১৯-এর adjacency matrix, যার বিস্তারিত পর্ব ৫৮ “গ্রাফের representation আর isomorphism”-এ আসবে।

নিচের ছবিটি এই পর্বের প্রথম চলমান উদাহরণ: বাজারঘরের ৬টি হাব আর ৮টি সরাসরি ভ্যান-রুট। হাবের নামগুলো শুধু লেবেল; রুটগুলো কাল্পনিক, বাস্তব রাস্তার মানচিত্র নয়।

ছবিতে N(D) = {G, T, N, S, M}, N(N) = {D, S, M}. G আর T adjacent, কিন্তু G আর N নয়। কোনো isolated vertex নেই। গাণিতিকভাবে পুরো ছবিটি মাত্র দুটি সেট: V = {D, G, T, N, S, M} আর E = {DG, DT, DN, DS, DM, GT, NS, NM}.

২ · Degree আর handshake theorem

Loop দুবার গোনার নিয়মটি খেয়ালখুশি নয়: একটি loop v-কে দুটি “প্রান্ত” দেয়, ঠিক অন্য যেকোনো edge-এর মতো। এই নিয়মেই নিচের উপপাদ্যটি loop-সহ সব graph-এ সত্য থাকে।

প্রমাণ (double counting). পর্ব ৩৭ “গণনার কৌশল”-এর double counting কৌশলে একটি সেট দুইভাবে গুনি। সেটটি হলো সব “প্রান্ত-জোড়া” (v, e), যেখানে v হলো edge e-এর একটি প্রান্ত; loop-এর ক্ষেত্রে v-কে দুটি আলাদা প্রান্ত হিসেবে ধরা হয়।

1. Vertex ধরে গুনলে: v-কে প্রান্ত হিসেবে পাওয়া যায় ঠিক deg(v)বার, কারণ degree-র সংজ্ঞায় loop দুবার গোনা হয়। মোট ∑ deg(v). — সংজ্ঞা ২.১
2. Edge ধরে গুনলে: প্রতিটি edge-এর ঠিক দুটি প্রান্ত (loop-এর দুটি প্রান্ত একই vertex), তাই মোট 2|E|. — edge-এর সংজ্ঞা
3. একই সসীম সেট দুইভাবে গোনা হয়েছে, আর প্রতিটি পদ্ধতিতে প্রতিটি প্রান্ত-জোড়া ঠিক একবার এসেছে, তাই দুটি সংখ্যা সমান। ∎ — double counting

1. V-কে দুই ভাগে ভাগ করুন: V_odd (বিজোড় degree) আর V_even (জোড় degree). — partition
2. উপপাদ্য ২.২ থেকে ∑_Vodd deg(v) = 2|E| − ∑_Veven deg(v). ডানের দুটি পদই জোড়, তাই বাঁ দিক জোড়। — জোড় − জোড় = জোড়
3. বাঁ দিকটি |V_odd|টি বিজোড় সংখ্যার যোগফল। বিজোড় সংখ্যক বিজোড় সংখ্যার যোগফল বিজোড়, তাই |V_odd| জোড় হতেই হবে। ∎ — parity

নিচের stepper হাব-নেটওয়ার্কের ৮টি edge দুটি দুটি করে যোগ করে, আর প্রতি ধাপে degree, তাদের যোগফল আর বিজোড় vertex-এর সংখ্যা দেখায়। লক্ষ করুন, প্রতিটি নতুন edge যোগফলে ঠিক 2 যোগ করে, আর বিজোড় vertex-এর সংখ্যা 2 বাড়ে, 2 কমে বা একই থাকে, কখনো 1 বদলায় না।

1শুরু: কোনো edge নেই2+ DG, DN3+ DS, DT4+ GT, NM5+ DM, NS6∑deg = 2m যাচাই

এবার দাবিটি অনেক graph-এ একসঙ্গে পরীক্ষা করি: loop আর parallel edge-সহ এলোমেলো pseudograph, একটি এলোমেলো directed graph, আর ৫টি নামযুক্ত vertex-এর সব 2¹⁰ = 1024টি simple graph. প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে; পরের ব্লকগুলো দ্রুত চলে।

import random
from collections import Counter
from itertools import combinations, product
random.seed(57)
def degrees(n, edges):                  # a loop (v, v) adds 2 to deg(v)
    deg = [0] * n
    for u, v in edges:
        deg[u] += 1
        deg[v] += 1
    return deg
for trial in range(5):                  # random multigraphs with loops
    n, m = random.randint(4, 9), random.randint(3, 15)
    edges = [(random.randrange(n), random.randrange(n)) for _ in range(m)]
    deg = degrees(n, edges)
    odd = sum(d % 2 for d in deg)
    loops = sum(u == v for u, v in edges)
    print(f"n={n} m={m:2} loops={loops} degrees={deg}"
          f" sum={sum(deg):2} 2m={2 * m:2} odd={odd}")
n, m = 7, 12                            # a random directed graph
arcs = [(random.randrange(n), random.randrange(n)) for _ in range(m)]
out_deg = Counter(u for u, v in arcs)
in_deg = Counter(v for u, v in arcs)
print("digraph: sum out =", sum(out_deg.values()),
      " sum in =", sum(in_deg.values()), " m =", m)
pairs = list(combinations(range(5), 2))  # all 2^10 simple graphs, n = 5
tally = Counter()
for bits in product((0, 1), repeat=len(pairs)):
    deg = degrees(5, [p for p, b in zip(pairs, bits) if b])
    tally[sum(d % 2 for d in deg)] += 1
print("graphs on 5 vertices by number of odd vertices:",
      dict(sorted(tally.items())))

n=4 m= 8 loops=1 degrees=[3, 3, 4, 6] sum=16 2m=16 odd=2
n=8 m= 5 loops=0 degrees=[0, 0, 3, 2, 1, 1, 3, 0] sum=10 2m=10 odd=4
n=7 m=13 loops=2 degrees=[6, 1, 5, 7, 4, 2, 1] sum=26 2m=26 odd=4
n=6 m=13 loops=1 degrees=[5, 5, 3, 3, 2, 8] sum=26 2m=26 odd=4
n=4 m= 7 loops=2 degrees=[4, 7, 1, 2] sum=14 2m=14 odd=2
digraph: sum out = 12  sum in = 12  m = 12
graphs on 5 vertices by number of odd vertices: {0: 64, 2: 640, 4: 320}

৩ · Directed graph — in-degree আর out-degree

বাজারঘরের কিছু রুট একমুখী: ভ্যান মূল গুদাম থেকে হাবে যায়, ফেরে অন্য পথে। এমন সংযোগের জন্য edge-কে ক্রমজোড়া (u, v) হিসেবে লেখা হয়, যার অর্থ u থেকে v-তে একটি তীর (arc). u হলো তীরের শুরু (tail), v শেষ (head).

1. প্রতিটি তীরের ঠিক একটি শুরু আছে। তাই তীরগুলোকে শুরুর vertex অনুযায়ী ভাগ করলে v-এর ভাগে deg⁺(v)টি তীর, আর ভাগগুলো মিলে সব তীর: ∑ deg⁺(v) = |E|. — partition ধরে গোনা
2. প্রতিটি তীরের ঠিক একটি শেষ আছে; একই যুক্তিতে ∑ deg⁻(v) = |E|. ∎ — একই যুক্তি

উদাহরণ: তীরগুলো D→G, D→N, G→T, T→D, N→M, M→D, S→D. তাহলে deg⁺: D 2, G 1, T 1, N 1, M 1, S 1 (যোগফল 7); deg⁻: D 3, G 1, N 1, T 1, M 1, S 0 (যোগফল 7). S থেকে শুধু বের হওয়া যায়, ঢোকা যায় না: এমন vertex (in-degree 0)-কে source বলে, আর out-degree 0 হলে sink. পর্ব ৫৬-এর topological sort ঠিক in-degree 0 vertex থেকে শুরু করে।

৪ · চেনা পরিবার — K_n, C_n, W_n, Q_n আর regular graph

কিছু graph এত ঘনঘন আসে যে তাদের নিজস্ব নাম আছে। নিচের প্রতিটি simple graph, আর প্রতিটির edge-সংখ্যা handshake theorem থেকে এক লাইনে বের হয়।

একটি উদাহরণ প্রমাণ: Q_n-এ প্রতিটি vertex একটি n-বিট string, আর প্রতিটি বিট উল্টে ঠিক n জন প্রতিবেশী পাওয়া যায়। তাই ∑ deg = n · 2ⁿ = 2|E|, অর্থাৎ |E| = n · 2ⁿ⁻¹. Q₃ সাধারণ ঘনক (৮টি কোণ, ১২টি ধার)। পর্ব ৩৬-এর Gray code আসলে Q_n-এর সব vertex একবার করে ছুঁয়ে যাওয়া একটি পথ, যা পর্ব ৬০ “Euler আর Hamilton path”-এ আবার আসবে। নামকরণে সাবধান: এখানে (Rosen-এর বইয়ের মতো) W_n-এ n + 1টি vertex; কিছু বই W_n বলতে মোট n vertex-এর wheel বোঝায়। পরীক্ষায় প্রশ্নের সংজ্ঞাটি আগে দেখে নিন।

1. প্রয়োজনীয়তা: simple graph-এ একটি vertex-এর প্রতিবেশী বড়জোর বাকি n − 1 জন, তাই k ≤ n − 1. আর handshake theorem অনুযায়ী nk = ∑ deg = 2|E|, জোড়। — উপপাদ্য ২.২
2. যথেষ্টতা, k জোড় হলে: vertex 0, 1, …, n − 1 নিন, আর i-কে i ± 1, i ± 2, …, i ± k/2 (mod n)-এর সঙ্গে যুক্ত করুন। k/2 < n/2, তাই এই k-টি সংখ্যা আলাদা আর 0 নয় (mod n), অর্থাৎ প্রত্যেকের ঠিক k জন প্রতিবেশী। — mod n হিসাব (পর্ব ২২)
3. k বিজোড় হলে nk জোড় হওয়ায় n জোড়। ধাপ ২-এর গঠন k − 1-এর জন্য করে প্রতিটি i-কে i + n/2-এর সঙ্গেও যুক্ত করুন। (k − 1)/2 < n/2, তাই এই নতুন প্রতিবেশী আগের কারও সঙ্গে মেলে না, আর i + n/2 + n/2 ≡ i বলে সম্পর্কটি দুই দিকে একই। সবার degree k. ∎ — গঠন দিয়ে প্রমাণ

তাই ৭টি vertex-এ কোনো 3-regular graph নেই (7 × 3 = 21 বিজোড়), কিন্তু 2-, 4- বা 6-regular আছে। বাজারঘরের ভাষায়: ৭টি হাবের প্রত্যেককে ঠিক ৩টি অন্য হাবের সঙ্গে সরাসরি জোড়ার পরিকল্পনা কাগজে যত সুন্দরই দেখাক, বাস্তবায়ন অসম্ভব। §৭-এর কোডে ছোট n-এর জন্য সব regular graph গুনে এই উপপাদ্য মেলানো হয়েছে।

৫ · Bipartite graph — দুই দল, দুই রং আর বিজোড় cycle

বাজারঘরের কর্মী-শিফট তালিকায় দুই ধরনের বস্তু: কর্মী আর শিফট। একজন কর্মী যে শিফটে কাজ করতে পারেন, সেখানে একটি edge. এখানে কোনো edge দুজন কর্মীকে বা দুটি শিফটকে জোড়ে না। এই ধরনের graph-এর নাম bipartite graph, আর কর্মীদের শিফটে বসানোর গণিত (matching) আসবে পর্ব ৬৪ “Matching — bipartite graph, Hall-এর উপপাদ্য আর stable matching”-এ।

উদাহরণ: C₆ bipartite (vertex একটির পর একটি নীল-হলুদ), C₅ নয়। Q_n bipartite: যে string-এ 1-এর সংখ্যা জোড় সেগুলো এক দলে, বিজোড়গুলো অন্য দলে, আর একটি বিট উল্টালে parity বদলায়। K₃ (ত্রিভুজ) নয়, তাই কোনো wheel নয়, কারণ hub আর রিমের দুটি পাশাপাশি vertex একটি ত্রিভুজ বানায়।

(ক) ⇔ (খ). V₁-এর সবাইকে নীল আর V₂-এর সবাইকে হলুদ রং দিলে proper colouring পাওয়া যায়; উল্টো দিকে একটি 2-colouring-এর দুই রঙের vertex-গুলোই দুটি দল। দুটি কথা আসলে একই তথ্যের দুই নাম। ∎

(খ) ⇒ (গ).

1. ধরুন v₀v₁⋯v_k−1v₀ একটি cycle, দৈর্ঘ্য k, আর একটি proper 2-colouring আছে। — অনুমান
2. পরপর দুটি vertex edge দিয়ে যুক্ত, তাই রং পালাক্রমে বদলায়: v_i-এর রং v₀-এর রঙের সমান ঠিক যখন i জোড়। — proper colouring, i-এর ওপর induction
3. শেষ edge v_k−1v₀, তাই v_k−1-এর রং v₀-এর থেকে আলাদা, অর্থাৎ k − 1 বিজোড়, k জোড়। কোনো cycle বিজোড় নয়। ∎ — ধাপ ২

(গ) ⇒ (খ). এটিই আসল কাজের দিক, কারণ এখানে রং “বানাতে” হয়।

1. প্রতিটি connected অংশ (component) আলাদাভাবে রং করলেই হয়, কারণ ভিন্ন অংশের মধ্যে কোনো edge নেই। তাই ধরুন G connected; একটি vertex r বেছে নিন। — অংশে ভাগ (পর্ব ৫৫-এর equivalence class)
2. প্রতিটি v-এর জন্য d(v) = r থেকে v-এর সবচেয়ে ছোট path-এর দৈর্ঘ্য। d(v) জোড় হলে v নীল, বিজোড় হলে হলুদ। — দূরত্বের parity দিয়ে রং
3. ধরুন কোনো edge uv-এর দুই প্রান্তে একই রং। যেকোনো edge uv-এর জন্য |d(u) − d(v)| ≤ 1 (u পর্যন্ত পথের সঙ্গে uv জুড়লে v-তে পৌঁছানো যায়), তাই একই parity মানে d(u) = d(v) = d. — বিপরীত অনুমান
4. r থেকে u-তে একটি সবচেয়ে ছোট path P আর v-তে একটি সবচেয়ে ছোট path Q নিন। P আর Q-এর সাধারণ vertex-গুলোর মধ্যে r থেকে সবচেয়ে দূরেরটি w. যেকোনো সাধারণ vertex x দুটি path-এই r থেকে ঠিক d(x) দূরত্বে বসে, তাই w-এর পরে P আর Q আর মেলে না। — সবচেয়ে ছোট path-এর অংশও সবচেয়ে ছোট
5. P-এর w থেকে u পর্যন্ত অংশ (দৈর্ঘ্য d − d(w)), edge uv, আর Q-এর v থেকে w পর্যন্ত অংশ (দৈর্ঘ্য d − d(w)) মিলে একটি cycle, কারণ তারা শুধু w-এ মেলে আর u ≠ v. তার দৈর্ঘ্য 2(d − d(w)) + 1, বিজোড়। — ধাপ ৪
6. এটি অনুমান (গ)-এর বিরোধী। তাই কোনো edge-এর দুই প্রান্তে একই রং নেই, আর ধাপ ২-এর রং একটি proper 2-colouring. ∎ — contradiction

প্রমাণটি গঠনমূলক: এটি একটি algorithm বলে দেয়। BFS (breadth-first search) r থেকে স্তরে স্তরে vertex খুঁজে ঠিক d(v) বের করে (DSA কোর্সের পর্ব ৪০-এ কোড আর জটিলতা)। স্তরের parity দিয়ে রং দিন; কোথাও একই রঙের দুই প্রান্তের edge পেলে ধাপ ৪–৫ অনুযায়ী parent-এর শিকল ধরে পেছনে গিয়ে একটি odd cycle বের করুন। নিচের stepper এটি ৭টি হাবের একটি graph-এ দেখায়, যার edge AB, AC, BD, CE, DE, DF, FG.

1A লাল, queue = [A]2A বের: B, C নীল3B বের: D লাল4C বের: E লাল5D বের: D–E দুজনেই লাল!6parent ধরে odd cycle

এই “প্রমাণপত্র” (certificate) ধারণাটি গুরুত্বপূর্ণ। “হ্যাঁ, bipartite” উত্তরের সঙ্গে একটি 2-colouring দেওয়া যায়, যা প্রতিটি edge দেখে যাচাই হয়। “না” উত্তরের সঙ্গে একটি odd cycle দেওয়া যায়, যা (খ) ⇒ (গ) অনুযায়ী যেকোনো 2-colouring-কে অসম্ভব করে। দুই দিকেই উত্তর বিশ্বাস করতে algorithm-এর কোড পড়তে হয় না। নিচের কোড ঠিক এটি করে, আর ফলাফল 2ⁿটি রং-বিন্যাস সব পরীক্ষা করা brute force-এর সঙ্গে মেলায়।

from collections import deque
def two_colour(adj):                    # (colouring, None) or (None, odd cycle)
    colour, parent = {}, {}
    for s in adj:                       # restart in every component
        if s in colour: continue
        colour[s], parent[s] = 0, None
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if v not in colour:
                    colour[v], parent[v] = 1 - colour[u], u
                    q.append(v)
                elif colour[v] == colour[u]:      # same BFS level
                    pu, pv = [u], [v]
                    while parent[pu[-1]] is not None: pu.append(parent[pu[-1]])
                    while parent[pv[-1]] is not None: pv.append(parent[pv[-1]])
                    w = next(x for x in pu if x in pv)   # last common ancestor
                    return None, pu[:pu.index(w) + 1] + pv[:pv.index(w)][::-1]
    return colour, None
def graph(edges):
    adj = {}
    for u, v in edges: adj.setdefault(u, []).append(v); adj.setdefault(v, []).append(u)
    return {u: sorted(adj[u]) for u in sorted(adj)}
def brute(adj):                         # try all 2^n colourings
    return any(all(c[u] != c[v] for u in adj for v in adj[u])
               for c in ({v: m >> i & 1 for i, v in enumerate(adj)} for m in range(2 ** len(adj))))
tests = {"hubs": graph(zip("AABCDDF", "BCDEEFG")),
         "Q3": graph((x, x ^ b) for x in range(8) for b in (1, 2, 4)),
         "Petersen": graph([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
                           + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])}
for name, adj in tests.items():
    col, cyc = two_colour(adj)
    ok = cyc is None or (len(cyc) % 2 == 1 and all(cyc[i - 1] in adj[cyc[i]] for i in range(len(cyc))))
    print(f"{name}: bipartite={col is not None} brute={brute(adj)} certificate={cyc} checked={ok}")

hubs: bipartite=False brute=False certificate=['D', 'B', 'A', 'C', 'E'] checked=True
Q3: bipartite=True brute=True certificate=None checked=True
Petersen: bipartite=False brute=False certificate=[2, 1, 0, 4, 3] checked=True

৬ · Degree sequence — কোন তালিকা দিয়ে graph বানানো যায়?

একটি graph-এর সব degree বড় থেকে ছোট সাজিয়ে লিখলে পাওয়া যায় তার degree sequence; হাব-graph-এর জন্য (5, 3, 2, 2, 2, 2). উল্টো প্রশ্নটি বেশি মজার: একজন ম্যানেজার বললেন “৭টি হাবের রুট-সংখ্যা হবে 3, 3, 2, 2, 2, 1, 1”, এমন simple graph কি আছে? যে তালিকার জন্য আছে, তাকে graphical বলে।

Handshake থেকে প্রথম শর্ত: যোগফল জোড় হতে হবে। কিন্তু শর্তটি যথেষ্ট নয়। (3, 3, 3, 1)-এর যোগফল 10, জোড়, অথচ graph নেই: তিনটি degree-3 vertex-এর প্রত্যেককে বাকি তিনজনের সবার সঙ্গে যুক্ত হতে হবে, তাহলে চতুর্থজনের degree 3 হয়, 1 নয়। সাধারণ উত্তর দেয় নিচের উপপাদ্য, যা Václav Havel (১৯৫৫) আর S. L. Hakimi (১৯৬২) আলাদাভাবে প্রকাশ করেন বলে সাধারণত উল্লেখ করা হয়।

এই উপপাদ্য একটি algorithm দেয়, যার নাম Havel–Hakimi algorithm: বারবার সবচেয়ে বড় পদ সরিয়ে পরের পদগুলো কমান আর নতুন করে সাজান। কোনো পদ ঋণাত্মক হলে, বা বাকি পদের চেয়ে বেশি কমাতে হলে “না”; সব পদ 0 হলে “হ্যাঁ”. প্রমাণের রূপরেখা (পূর্ণ প্রমাণ নিচের ধাপগুলোতে প্রায় সম্পূর্ণ):

1. (⇐) d′ কোনো graph H-এ বাস্তবায়িত হলে H-এ একটি নতুন vertex v₁ যোগ করে d′-এর প্রথম d₁টি vertex-এর সঙ্গে যুক্ত করুন। তাদের degree 1 করে বাড়ে, v₁-এর degree d₁: d পাওয়া গেল। — সরাসরি গঠন
2. (⇒) d কোনো graph G-এ বাস্তবায়িত হলে, সব বাস্তবায়নের মধ্যে এমন G নিন যেখানে v₁-এর প্রতিবেশীদের মধ্যে “পরের d₁টি সবচেয়ে বড় degree-র vertex”-এর সেট S থেকে যত বেশি সম্ভব আছে। — extremal পছন্দ
3. যদি N(v₁) = S হয়, তাহলে G থেকে v₁ মুছলেই d′ পাওয়া যায়, কাজ শেষ। না হলে কোনো x ∈ S, x ∉ N(v₁), আর কোনো y ∉ S, y ∈ N(v₁) আছে, যেখানে deg x ≥ deg y. — S-এর সংজ্ঞা
4. y-এর v₁ ছাড়া প্রতিবেশী deg y − 1 জন, যা deg x-এর চেয়ে কম; তাই x-এর এমন একজন প্রতিবেশী z আছে যে y-এর প্রতিবেশী নয় আর z ≠ y (x আর y নিজেরা যুক্ত হলে দুই পাশ থেকে y আর x বাদ দিয়ে একই তুলনা: deg x − 1 > deg y − 2). — pigeonhole ধরনের গোনা
5. Edge v₁y আর xz মুছে v₁x আর yz যোগ করুন (2-switch). কোনো degree বদলায় না, graph simple থাকে, অথচ v₁-এর S-প্রতিবেশী একজন বাড়ল: ধাপ ২-এর পছন্দের বিরোধ। তাই N(v₁) = S. ∎ — contradiction

1যোগফল 14, Δ = 3 ≤ 62v1 (3) সরানো → 2,2,1,1,1,13v2 (2) সরানো → 1,1,1,1,04v5 (1) সরানো → 1,1,0,05v6 (1) সরানো → 0,0,06উল্টো পথে graph

প্রয়োজনীয়তার দিকটি সহজ: সবচেয়ে বড় k-টি vertex-এর degree-যোগফল তাদের নিজেদের মধ্যের edge (বড়জোর k(k − 1), কারণ প্রতিটি edge দুবার গোনা) আর বাইরের প্রতিটি vertex i-এর সঙ্গে edge (বড়জোর min(d_i, k)) দিয়ে সীমিত। উল্টো দিকটি কঠিন; Paul Erdős আর Tibor Gallai ১৯৬০ সালে এটি প্রকাশ করেন বলে উল্লেখ করা হয়। নিচের কোড দুটি পরীক্ষাকেই সত্যিকারের brute force-এর সঙ্গে মেলায়: n ≤ 6-এর প্রতিটি নামযুক্ত simple graph তৈরি করে তার degree sequence জমা রাখে।

from itertools import combinations, product
def havel_hakimi(seq, trace=False):
    d = sorted(seq, reverse=True)
    while d and d[0] > 0:
        k = d.pop(0)
        if k > len(d): return False
        d = sorted([x - 1 for x in d[:k]] + d[k:], reverse=True)
        if trace:
            print(f"  remove {k} -> {d}")
        if d[-1] < 0:
            return False
    return True
def erdos_gallai(seq):
    d = sorted(seq, reverse=True)
    if sum(d) % 2:
        return False
    return all(sum(d[:k]) <= k * (k - 1) + sum(min(x, k) for x in d[k:])
               for k in range(1, len(d) + 1))
for s in ([3, 3, 2, 2, 2, 1, 1], [5, 5, 4, 3, 2, 1]):
    print(s, "sum", sum(s))
    print("  graphical:", havel_hakimi(s, trace=True))
for n in range(1, 7):                   # brute force: degree sequences of all graphs
    pairs = list(combinations(range(n), 2))
    real = set()
    for bits in product((0, 1), repeat=len(pairs)):
        deg = [0] * n
        for (u, v), b in zip(pairs, bits):
            if b:
                deg[u] += 1; deg[v] += 1
        real.add(tuple(sorted(deg, reverse=True)))
    cands = [s for s in product(range(n), repeat=n) if list(s) == sorted(s, reverse=True)]
    hh = sum(havel_hakimi(s) == (s in real) for s in cands)
    eg = sum(erdos_gallai(s) == (s in real) for s in cands)
    print(f"n={n}: {len(cands):3} candidates, {len(real):3} graphical,"
          f" HH agrees {hh}, EG agrees {eg}")

[3, 3, 2, 2, 2, 1, 1] sum 14
  remove 3 -> [2, 2, 1, 1, 1, 1]
  remove 2 -> [1, 1, 1, 1, 0]
  remove 1 -> [1, 1, 0, 0]
  remove 1 -> [0, 0, 0]
  graphical: True
[5, 5, 4, 3, 2, 1] sum 20
  remove 5 -> [4, 3, 2, 1, 0]
  remove 4 -> [2, 1, 0, -1]
  graphical: False
n=1:   1 candidates,   1 graphical, HH agrees 1, EG agrees 1
n=2:   3 candidates,   2 graphical, HH agrees 3, EG agrees 3
n=3:  10 candidates,   4 graphical, HH agrees 10, EG agrees 10
n=4:  35 candidates,  11 graphical, HH agrees 35, EG agrees 35
n=5: 126 candidates,  31 graphical, HH agrees 126, EG agrees 126
n=6: 462 candidates, 102 graphical, HH agrees 462, EG agrees 462

৭ · নতুন graph বানানো আর graph গোনা

পার্থক্যটি মনে রাখার উপায়: subgraph-এ যেকোনো edge ফেলে দেওয়া যায়, induced subgraph-এ যায় না। হাব-graph-এ W = {D, G, T} নিলে G[W] একটি ত্রিভুজ (DG, DT, GT), আর শুধু {DG, DT} নিয়ে বানানো graph একটি subgraph যা induced নয়। Complement-এ প্রতিটি vertex-এর degree n − 1 − deg(v), কারণ বাকি n − 1 জনের মধ্যে যারা G-এ প্রতিবেশী নয়, তারাই Ḡ-এ প্রতিবেশী। হাব-graph-এর complement-এ 15 − 8 = 7টি edge আর degree (0, 3, 2, 3, 3, 3) (ক্রম D, G, N, S, T, M): D সবার সঙ্গে যুক্ত বলে Ḡ-এ একা।

1. Vertex সেট নির্দিষ্ট, তাই একটি simple graph পুরোপুরি তার edge-সেট E দিয়ে নির্ধারিত, আর E হলো সম্ভাব্য C(n, 2)টি জোড়ার সেটের একটি subset. — সংজ্ঞা ১.১
2. উল্টো দিকে, সেই জোড়াগুলোর প্রতিটি subset একটি simple graph দেয়। তাই graph ↔ subset একটি bijection (পর্ব ১৬)। — দুই দিকের রূপান্তর
3. C(n, 2)-উপাদানের সেটের subset 2^C(n,2)টি, আর ঠিক m-উপাদানের subset C(C(n, 2), m)টি (পর্ব ৩৩)। ∎ — bijection আকার রক্ষা করে

৫টি vertex-এ তাই 2¹⁰ = 1024টি graph, আর ঠিক ৪টি edge-এর C(10, 4) = 210টি। “নামযুক্ত” (labelled) শব্দটি জরুরি: vertex-এর নাম ভুলে গিয়ে শুধু আকৃতি গুনলে ৪টি vertex-এ মাত্র ১১টি আলাদা graph, যা পর্ব ৫১-এ Burnside দিয়ে গোনা হয়েছে, আর “একই আকৃতি”-র নির্ভুল সংজ্ঞা graph isomorphism, পর্ব ৫৮-এর বিষয়।

নিচের কোড n ≤ 6-এর প্রতিটি নামযুক্ত graph তৈরি করে তিনটি জিনিস গোনে: মোট সংখ্যা (2^C(n,2)-এর সঙ্গে তুলনা), প্রতিটি k-এর জন্য k-regular graph (উপপাদ্য ৪.১), আর যেসব graph-এ কোনো isolated vertex নেই (δ ≥ 1) তাদের মধ্যে কয়টি এক টুকরো নয়, যা §৮-এর ভুল প্রমাণের জন্য লাগবে। “connected” মানে যেকোনো দুটি vertex-এর মধ্যে path আছে; বিস্তারিত পর্ব ৫৯-এ।

from itertools import combinations, product
from collections import Counter
from math import comb
def connected(n, edges):
    adj = {v: [] for v in range(n)}
    for u, v in edges:
        adj[u].append(v); adj[v].append(u)
    seen, stack = {0}, [0]
    while stack:
        for w in adj[stack.pop()]:
            if w not in seen:
                seen.add(w); stack.append(w)
    return len(seen) == n
print(" n  graphs  2^C(n,2)  k-regular for k = 0..n-1   min deg>=1  disconnected")
for n in range(1, 7):
    pairs = list(combinations(range(n), 2))
    total, reg, pos, bad = 0, Counter(), 0, 0
    for bits in product((0, 1), repeat=len(pairs)):
        E = [p for p, b in zip(pairs, bits) if b]
        deg = [0] * n
        for u, v in E:
            deg[u] += 1; deg[v] += 1
        total += 1
        if len(set(deg)) == 1:
            reg[deg[0]] += 1
        if min(deg) >= 1:
            pos += 1
            bad += not connected(n, E)
    print(f"{n:2} {total:7} {2 ** comb(n, 2):9}  {[reg[k] for k in range(n)]!s:26}"
          f" {pos:10} {bad:12}")

 n  graphs  2^C(n,2)  k-regular for k = 0..n-1   min deg>=1  disconnected
 1       1         1  [1]                                 0            0
 2       2         2  [1, 1]                              1            0
 3       8         8  [1, 0, 1]                           4            0
 4      64        64  [1, 3, 3, 1]                       41            3
 5    1024      1024  [1, 0, 12, 0, 1]                  768           40
 6   32768     32768  [1, 15, 70, 70, 15, 1]          27449          745

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

কোথায় কোথায় graph

• সামাজিক নেটওয়ার্ক: মানুষ vertex, বন্ধুত্ব edge (undirected), আর “অনুসরণ করা” তীর (directed). degree মানে বন্ধুর সংখ্যা।
• ওয়েব: পাতা vertex, লিংক তীর; in-degree বেশি মানে অনেক পাতা এই পাতাকে দেখায়, যা সার্চ ইঞ্জিনের পুরোনো একটি সংকেত হিসেবে পরিচিত।
• রাস্তা আর ডেলিভারি: বাজারঘরের মতো হাব আর রুট; একমুখী রাস্তা থাকলে directed, একাধিক বিকল্প রাস্তা থাকলে multigraph.
• অণুর মডেল: রসায়নে পরমাণু vertex আর রাসায়নিক বন্ধন edge হিসেবে আঁকা হয়; এক-বন্ধনের সরল ক্ষেত্রে একটি পরমাণুর degree তার যোজ্যতার সঙ্গে মেলে (যেমন কার্বন 4), আর দ্বিবন্ধন parallel edge হিসেবে আঁকলে graph-টি multigraph হয়। এটি একটি সরলীকৃত মডেল; বাস্তব রসায়নের সব খুঁটিনাটি এতে আসে না।

অঙ্ক ১: Handshake দিয়ে vertex গোনা

একটি simple graph-এ ১৫টি edge; তিনটি vertex-এর degree 4, বাকি সবার 3. vertex কয়টি? এমন graph কি সত্যিই আছে?

1. n-টি vertex ধরলে ∑ deg = 3 · 4 + (n − 3) · 3 = 2 · 15 = 30.
2. 12 + 3n − 9 = 30, তাই 3n = 27, n = 9.
3. অস্তিত্ব: তালিকা (4, 4, 4, 3, 3, 3, 3, 3, 3)-এ Havel–Hakimi চালালে সব পদ 0-তে পৌঁছায়, তাই আছে (scratch-এ যাচাই করা)।

অঙ্ক ২: edge গোনা

Q₄, K_3,4 আর W₆-এ কয়টি edge? উত্তর: Q₄-এ 4 · 2³ = 32; K_3,4-এ 3 · 4 = 12; W₆-এ রিমে ৬টি আর hub থেকে ৬টি, মোট 12, যা handshake দিয়েও মেলে: (6 · 3 + 6)/2 = 12.

অঙ্ক ৩: Bipartite কি না

C₇, Q₃, K_2,3 আর K₄-এর কোনগুলো bipartite? C₇ নিজেই একটি odd cycle, তাই নয়; K₄-এ ত্রিভুজ আছে, তাই নয়; Q₃ (1-এর সংখ্যার parity) আর K_2,3 (সংজ্ঞা অনুযায়ী) bipartite.

প্রমাণের ভুল ধরুন: graph-এ induction-এর ফাঁদ

একজন লিখলেন: “দাবি: n ≥ 2 vertex-এর যে simple graph-এ কোনো isolated vertex নেই (δ ≥ 1), সেটি connected. প্রমাণ (n-এর ওপর induction): n = 2-এ δ ≥ 1 মানে একমাত্র edge-টি আছে, graph connected. এখন ধরুন n-vertex-এর জন্য সত্য। δ ≥ 1-এর একটি n-vertex graph G নিন; induction hypothesis অনুযায়ী G connected. একটি নতুন vertex v যোগ করে তাকে G-এর অন্তত একটি vertex-এর সঙ্গে যুক্ত করুন; নতুন graph-এও δ ≥ 1, আর v পুরোনো connected অংশে যুক্ত বলে নতুন graph connected. তাই দাবিটি সব n-এর জন্য সত্য।”

ভুল কোথায়: Inductive step-কে প্রমাণ করতে হয় যে প্রতিটি (n + 1)-vertex graph যার δ ≥ 1, সেটি connected. এখানে উল্টো পথে হাঁটা হয়েছে: একটি ছোট graph থেকে “বানানো” কিছু বড় graph দেখা হয়েছে। কিন্তু সব বড় graph এভাবে আসে না। পাল্টা-উদাহরণ: n = 4-এ দুটি আলাদা edge {12, 34}. এর যেকোনো vertex মুছলে একটি isolated vertex থাকে, তাই এটি “δ ≥ 1-এর ৩-vertex graph + একটি নতুন vertex” হিসেবে কখনো তৈরি হয় না, আর এটি connected-ও নয়। §৭-এর কোডের শেষ কলাম দেখায় এমন graph n = 4-এ ৩টি, n = 5-এ ৪০টি, n = 6-এ ৭৪৫টি; দাবিটি শুধু n = 2 আর 3-এ সত্য। সঠিক পদ্ধতি (“shrink down, grow back”): যেকোনো (n + 1)-vertex graph নিয়ে শুরু করুন, একটি vertex মুছে দেখান যে ছোট graph-টি hypothesis-এর শর্ত মানে, তারপর induction hypothesis প্রয়োগ করে মুছে ফেলা vertex ফিরিয়ে আনুন। এখানে প্রথম ধাপেই আটকে যায়, আর আটকে যাওয়াই সংকেত যে দাবিটি মিথ্যা। Graph-এর ওপর induction-এর এই ফাঁদ পর্ব ১১-এর strong induction-এর ক্ষেত্রেও একই।

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

Graph-এর প্রশ্নে AI সহকারী সংজ্ঞা সাধারণত ঠিক লেখে, কিন্তু কোন ধরনের graph-এর কথা হচ্ছে তা গুলিয়ে ফেলে, আর induction-এর প্রমাণে আত্মবিশ্বাসী ভুল করে। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

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

• Graph-এর ধরন (simple, multi, pseudo, directed) আর loop গোনার নিয়ম লেখা আছে
• প্রতিটি উপপাদ্যের শর্ত (যেমন loop নেই, simple, সসীম) উল্লেখ আছে
• Induction-এর step যেকোনো বড় graph থেকে শুরু হয়েছে
• n ≤ 6-এ সব graph তৈরি করে brute force-এ দাবিটি মিলিয়েছি
• সংখ্যাগুলো (edge, degree-যোগফল) handshake দিয়ে আবার গুনেছি
• উদ্ধৃত নাম, সাল আর উৎস বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

Graph-এর সুবিধা হলো ছোট ক্ষেত্রে সবকিছু গোনা যায়: ৬টি vertex-এ মাত্র ৩২,৭৬৮টি graph, যা ব্রাউজারেই এক মুহূর্তে পরীক্ষা হয়। ছোট ক্ষেত্রে টিকে গেলেই দাবি সত্য হয় না, কিন্তু ভুল দাবি প্রায়ই ৪ বা ৫টি vertex-এই ধরা পড়ে। তাই আগে পাল্টা-উদাহরণ খুঁজুন, তারপর প্রমাণে ভরসা করুন।