গ্রাফের representation আর isomorphism

১ · গ্রাফ লিখে রাখার উপায় — edge list, adjacency list আর adjacency matrix

পর্ব ৫৭ “গ্রাফ — সংজ্ঞা, degree আর handshake theorem”-এ গ্রাফকে ছবি হিসেবে দেখা হয়েছে: কিছু বিন্দু আর তাদের জোড়া দেওয়া রেখা। কিন্তু ছবি কম্পিউটারে রাখা যায় না, আর হাতে আঁকা ছবি দেখে বড় গ্রাফ সম্পর্কে কিছু প্রমাণও করা যায় না। তাই প্রথম প্রশ্ন: একই গ্রাফকে সংখ্যা আর তালিকা দিয়ে কীভাবে লিখি, আর প্রতিটি লেখার ধরন থেকে কোন তথ্য সহজে পড়া যায়?

এই পর্বে “গ্রাফ” বললে, আলাদা করে না বললে, বোঝাবে একটি simple graph G = (V, E): vertex-এর একটি সসীম সেট V, আর edge-এর সেট E, যার প্রতিটি সদস্য V-এর দুটি আলাদা উপাদানের একটি অক্রমজোড়া {u, v}. অর্থাৎ self-loop নেই, একই জোড়ার মধ্যে একাধিক edge নেই, আর edge-এর দিক নেই। n = |V| আর m = |E| লিখব। Vertex v-এর degree deg(v) হলো v যত edge-এর প্রান্ত, তার সংখ্যা। Multigraph আর directed graph-এর ক্ষেত্রে কী বদলায়, তা প্রতিটি উপপাদ্যের পরে আলাদা করে বলা হবে।

Adjacency matrix প্রথম দেখা গেছে পর্ব ১৯ “Discrete math-এ matrix — 0-1 matrix আর Boolean product”-এ, directed graph-এর জন্য; আর পর্ব ৫২-এ একটি relation-এর zero-one matrix হিসেবে। Undirected simple graph-এ এর দুটি বিশেষ ধর্ম আছে, যা সংজ্ঞা থেকেই আসে।

1. {v_i, v_j} অক্রমজোড়া, তাই {v_i, v_j} = {v_j, v_i}, অর্থাৎ a_ij = a_ji. Self-loop নেই, তাই a_ii = 0. — simple graph-এর সংজ্ঞা
2. সারি i-তে 1 ঠিক সেই j-গুলোতে, যেখানে v_j ∈ N(v_i); তাই সারির যোগফল |N(v_i)| = deg(v_i). — simple graph-এ প্রতিটি প্রতিবেশী একটি edge
3. প্রতিটি edge {v_i, v_j} matrix-এ ঠিক দুটি 1 দেয় (ঘর ij আর ji), তাই সব ঘরের যোগফল 2m; আর ধাপ ২ অনুযায়ী একই যোগফল ∑deg(v). ∎ — দুইভাবে গোনা

ধাপ ৩ আসলে handshake theorem (∑deg(v) = 2m)-এর আরেকটি প্রমাণ: একই সংখ্যা দুইভাবে গোনা, ঠিক পর্ব ৩৭-এর double counting. Directed graph-এ A সাধারণত symmetric নয়; সারির যোগফল out-degree আর কলামের যোগফল in-degree. Multigraph-এ a_ij হয় v_i আর v_j-এর মধ্যের edge-এর সংখ্যা, তখন A আর 0-1 matrix থাকে না।

A-এর ঘাত: walk গোনা

পর্ব ১৯-এ প্রমাণ হয়েছে: (A^k)_ij হলো v_i থেকে v_j-তে দৈর্ঘ্য k-এর walk-এর সংখ্যা। প্রমাণটি এখানে আবার করব না, শুধু তিনটি ফল নেব, যা এই পর্বে বারবার লাগবে।

1. (ক) v_i থেকে v_j-তে দৈর্ঘ্য 2-এর walk মানে v_i, w, v_j, যেখানে w দুজনেরই প্রতিবেশী। i = j হলে w যেকোনো প্রতিবেশী, তাই deg(v_i)টি। — পর্ব ১৯-এর walk উপপাদ্য
2. (খ) কর্ণের যোগফল ∑deg(v_i) = 2m. — (ক) আর উপপাদ্য ১.২
3. (গ) দৈর্ঘ্য 3-এর একটি বদ্ধ walk v, a, b, v নিন। Self-loop নেই বলে a ≠ v, b ≠ a, b ≠ v; তাই v, a, b তিনটি আলাদা vertex, প্রতি জোড়ায় edge: একটি triangle. — simple graph
4. উল্টো দিকে একটি triangle {x, y, z} থেকে ঠিক 6টি বদ্ধ walk আসে: শুরু ৩টি vertex-এর যেকোনোটি, আর ঘোরার দিক ২টি। তাই trace(A³) = ∑_i(A³)_ii = 6t. ∎ — গুণের নিয়ম

২ · Incidence matrix — vertex আর edge-এর সম্পর্ক

Adjacency matrix বলে কোন vertex কোন vertex-এর পাশে। অন্য একটি matrix বলে কোন vertex কোন edge-এর প্রান্ত। এটি কম ব্যবহৃত হয়, কিন্তু এর গঠন সুন্দর, আর বৈদ্যুতিক সার্কিট বা network flow-এর সমীকরণ লিখতে এটিই স্বাভাবিক।

1. (ক) কলাম j মানে edge e_j. প্রতিটি edge-এর ঠিক দুটি প্রান্ত, আর loop নেই বলে তারা আলাদা দুটি vertex, তাই কলামে ঠিক দুটি 1. — edge-এর সংজ্ঞা, loop নেই
2. (খ) সারি i-তে 1 ঠিক সেই কলামে, যার edge-এর একটি প্রান্ত v_i; তাদের সংখ্যাই deg(v_i). Parallel edge থাকলে প্রতিটি আলাদা কলাম, তাই আলাদাভাবে গোনা হয়। — degree-র সংজ্ঞা
3. (গ) B-এর সব ঘরের যোগফল কলাম ধরে গুনলে 2m, সারি ধরে গুনলে ∑deg(v). ∎ — double counting

Loop থাকলে নিয়ম বদলায়: কিছু বই loop-এর ঘরে 2 লেখে (যাতে কলামের যোগফল তখনও 2 থাকে), কিছু বই 1 লেখে। তাই loop-সহ গ্রাফে কোন রীতি মানা হচ্ছে, তা আগে দেখে নিন। Directed graph-এ সাধারণত oriented incidence matrix নেওয়া হয়: তীর যেখান থেকে বের হয় সেখানে −1, যেখানে ঢোকে সেখানে +1 (কিছু বইয়ে চিহ্ন উল্টো); তখন প্রতিটি কলামের যোগফল 0.

1. (BB^T)_ik = ∑_j b_ijb_kj. পদ b_ijb_kj = 1 ঠিক তখন, যখন v_i আর v_k দুজনেই e_j-এর প্রান্ত। — matrix গুণের সংজ্ঞা
2. i = k: যোগফল = v_i যত edge-এর প্রান্ত = deg(v_i). — উপপাদ্য ২.২(খ)
3. i ≠ k: e_j-এর দুই প্রান্তই v_i আর v_k, অর্থাৎ e_j তাদের সংযোগকারী edge; তাই যোগফল = a_ik. ∎ — প্রতিটি edge-এর ঠিক দুটি প্রান্ত

নিচের stepper একটি ছোট edge list থেকে A আর B একসঙ্গে বানায়। চারটি হাব: ঢাকা (D), গাজীপুর (G), নারায়ণগঞ্জ (N), সাভার (S); রুট e₁ = D–G, e₂ = D–N, e₃ = G–N, e₄ = D–S. সারির ক্রম D, G, N, S.

1A = 0 (4×4), B খালি2e1 = {D, G}3e2 = {D, N}4e3 = {G, N}5e4 = {D, S}6যোগফল যাচাই

এবার একটু বড় একটি নেটওয়ার্কে সব দাবি একসঙ্গে পরীক্ষা করি: বাজারঘরের ছয়টি হাব (ঢাকা DHK, গাজীপুর GZP, নারায়ণগঞ্জ NGJ, সাভার SVR, মানিকগঞ্জ MNK, মুন্সিগঞ্জ MSG) আর সাতটি রুট। এখানে নাম শুধু লেবেল, দূরত্ব বা রুট কাল্পনিক। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে; পরের ব্লকগুলো দ্রুত চলে।

hubs = ["DHK", "GZP", "NGJ", "SVR", "MNK", "MSG"]
edges = [("DHK", "GZP"), ("DHK", "NGJ"), ("DHK", "SVR"), ("GZP", "SVR"),
         ("NGJ", "MSG"), ("DHK", "MSG"), ("SVR", "MNK")]
n, m = len(hubs), len(edges)
idx = {h: i for i, h in enumerate(hubs)}
adj = {h: set() for h in hubs}               # adjacency list
A = [[0] * n for _ in range(n)]              # adjacency matrix (n x n)
B = [[0] * m for _ in range(n)]              # incidence matrix (n x m)
for j, (u, v) in enumerate(edges):
    adj[u].add(v); adj[v].add(u)
    A[idx[u]][idx[v]] = A[idx[v]][idx[u]] = 1
    B[idx[u]][j] = B[idx[v]][j] = 1

def mul(X, Y):                               # plain matrix product
    return [[sum(X[i][k] * Y[k][j] for k in range(len(Y)))
             for j in range(len(Y[0]))] for i in range(len(X))]

deg = [len(adj[h]) for h in hubs]
print("list of DHK:", sorted(adj["DHK"]), " degrees:", deg)
print("sum of degrees =", sum(deg), " 2m =", 2 * m)
print("A symmetric:", all(A[i][j] == A[j][i] for i in range(n) for j in range(n)))
print("row sums of A:", [sum(row) for row in A])
print("column sums of B:", [sum(B[i][j] for i in range(n)) for j in range(m)])
BBt = mul(B, [list(col) for col in zip(*B)])
DA = [[deg[i] if i == j else A[i][j] for j in range(n)] for i in range(n)]
print("B times B-transpose == D + A:", BBt == DA)
A2 = mul(A, A); A3 = mul(A2, A)
print("diagonal of A^2:", [A2[i][i] for i in range(n)])
tri = sum(1 for i in range(n) for j in range(i + 1, n) for k in range(j + 1, n)
          if A[i][j] and A[j][k] and A[i][k])
print("trace(A^3) =", sum(A3[i][i] for i in range(n)), " 6 x triangles =", 6 * tri)
print("matrix cells:", n * n, " list entries:", sum(deg), " incidence cells:", n * m)

list of DHK: ['GZP', 'MSG', 'NGJ', 'SVR']  degrees: [4, 2, 2, 3, 1, 2]
sum of degrees = 14  2m = 14
A symmetric: True
row sums of A: [4, 2, 2, 3, 1, 2]
column sums of B: [2, 2, 2, 2, 2, 2, 2]
B times B-transpose == D + A: True
diagonal of A^2: [4, 2, 2, 3, 1, 2]
trace(A^3) = 12  6 x triangles = 12
matrix cells: 36  list entries: 14  incidence cells: 42

৩ · কোন representation কখন — জায়গা আর সময়ের হিসাব

তিনটি representation গাণিতিকভাবে সমান (একটি থেকে অন্যটি বানানো যায়), কিন্তু খরচে নয়। n = 6-এ পার্থক্য চোখে পড়ে না; কিন্তু সারা দেশের রাস্তার মোড় নিয়ে গ্রাফ হলে n লাখের ঘরে, আর প্রতিটি মোড়ে গড়ে মাত্র কয়েকটি রাস্তা। এমন গ্রাফ, যেখানে m সম্ভাব্য সর্বোচ্চ C(n, 2)-এর তুলনায় খুব ছোট, তাকে বলে sparse graph; m যদি n²-এর কাছাকাছি হয়, তবে dense graph.

“n + 2m” কোথা থেকে এলো? প্রতিটি vertex-এর একটি তালিকা (n), আর undirected গ্রাফে প্রতিটি edge দুই প্রান্তের তালিকায় একবার করে, মোট ∑deg(v) = 2m এন্ট্রি; এখানেও handshake theorem. ১ লাখ vertex আর ৩ লাখ edge-এর একটি রাস্তার গ্রাফে matrix লাগবে 10¹⁰টি ঘর, অথচ list-এ প্রায় ৭ লাখ এন্ট্রি। অন্যদিকে প্রতিটি জোড়ায় edge আছে কি না বারবার জিজ্ঞাসা করতে হয় এমন ছোট dense গ্রাফে matrix-ই দ্রুত। Incidence matrix সবচেয়ে বড় (n × m), তাই এটি সাধারণত হিসাবের জন্য নয়, তত্ত্বের জন্য: যেমন উপপাদ্য ২.৩, বা Kirchhoff-এর সূত্রে সার্কিটের সমীকরণ লেখা।

এই হিসাবগুলো Big-O-এর ভাষায়, আর তাদের প্রোগ্রাম (C++ আর Python-এ গ্রাফ পড়া, CSR-এর মতো সংকুচিত রূপ) DSA কোর্সের পর্ব ৩৯ “গ্রাফ — উপস্থাপন আর পরিভাষা”-এ আছে। এখানে আমরা গণিতে থাকব: কোন representation কোন প্রমাণ সহজ করে। পরের অংশগুলোতে দেখবেন, isomorphism-এর প্রশ্নে adjacency matrix সবচেয়ে কাজের, কারণ “vertex-এর নাম বদলানো” মানে matrix-এর সারি আর কলাম একই ক্রমে সাজানো।

৪ · Isomorphism — একই গ্রাফ, ভিন্ন নাম

একই গ্রাফ দুজন মানুষ দুইভাবে আঁকতে পারেন, আর vertex-গুলোর নামও দিতে পারেন আলাদা। নিচের ছবির বাঁয়ের গ্রাফটি একটি পাঁচ-কোণ, ডানেরটি একটি তারা। দেখতে একেবারে আলাদা, তবু গাণিতিকভাবে এরা একই গ্রাফ। “একই” কথাটির নির্ভুল অর্থ কী?

Bijection-এর ধারণা পর্ব ১৬ “ফাংশন — one-to-one, onto, inverse আর composition”-এর। সংজ্ঞায় “⇔” চিহ্নটি জরুরি: শুধু “edge থেকে edge” চাইলে যথেষ্ট নয় (অনুশীলন ৪-এ এর একটি ভুল প্রমাণ আছে)। আর ≅ একটি equivalence relation: identity ফাংশন দেয় reflexive, f-এর inverse দেয় symmetric, আর দুটি isomorphism-এর composition দেয় transitive; তাই সব গ্রাফ “isomorphism শ্রেণি”-তে ভাগ হয়, ঠিক পর্ব ৫৫-এর partition-এর মতো।

Isomorphic প্রমাণের পথ সরাসরি: একটি f লিখে দিন, তারপর প্রতিটি edge পরীক্ষা করুন। দুটি গ্রাফের edge-সংখ্যা সমান হলে কাজ অর্ধেক: f bijection আর প্রতিটি edge-কে edge-এ পাঠালে, এটি E থেকে F-এ একটি injective ফাংশন দেয়; |E| = |F| বলে সেটি onto-ও, তাই H-এর প্রতিটি edge কোনো edge-এর ছবি, আর non-edge যায় non-edge-এ। নিচের stepper-এ f কীভাবে খুঁজে বের করা হয়, সেটি দেখুন: প্রতিবেশীকে প্রতিবেশীর কাছেই পাঠাতে হবে, এই শর্ত পছন্দগুলো দ্রুত কমিয়ে দেয়।

1n = 5, m = 5, সব deg 22f(1) = a3f(2) ∈ N(a) = {c, d}4f(5) = d5f(3) = e, f(4) = b6৫টি edge যাচাই

Matrix-এর ভাষায় একই কথা: vertex-এর নাম বদলানো মানে A-এর সারি আর কলাম একই permutation-এ সাজানো। f-এর permutation matrix P (প্রতি সারি আর প্রতি কলামে ঠিক একটি 1) নিলে G ≅ H ⇔ কোনো P-এর জন্য PA_GP^T = A_H. শুধু সারি বা শুধু কলাম সাজালে চলবে না; তাতে vertex-এর নাম দুই জায়গায় দুইভাবে বদলায়।

৫ · Invariant — “আলাদা” প্রমাণের হাতিয়ার

দুটি গ্রাফ isomorphic নয়, তা প্রমাণ করা কঠিন শোনায়: n! টি bijection-এর একটিও কাজ করে না, তা দেখাতে হবে। কিন্তু একটি চতুর পথ আছে: এমন কোনো সংখ্যা বা ধর্ম খুঁজুন, যা isomorphism-এ বদলায় না, অথচ দুটি গ্রাফে আলাদা।

ধরুন f : V → W একটি isomorphism.

1. (ক) f bijection, তাই |V| = |W|. f edge আর non-edge ঠিক রাখে, তাই e = {u, v} ↦ {f(u), f(v)} হলো E থেকে F-এ একটি bijection (উল্টোটি f⁻¹ দিয়ে), আর |E| = |F|. — সংজ্ঞা ৪.১
2. (খ) যেকোনো v-এর জন্য u ∈ N(v) ⇔ f(u) ∈ N(f(v)), তাই f, N(v)-কে N(f(v))-এর ওপর bijection-এ পাঠায়, আর deg(v) = deg(f(v)). f সব vertex-কে এক-এক মেলায়, তাই degree-গুলোর বহুসেট একই, অর্থাৎ degree sequence সমান। — isomorphism প্রতিবেশী ঠিক রাখে
3. (গ) {x, y, z} triangle ⇔ তিনটি জোড়াই edge ⇔ {f(x), f(y)}, {f(y), f(z)}, {f(x), f(z)} তিনটিই edge ⇔ {f(x), f(y), f(z)} triangle. তাই f, G-এর triangle-গুলোকে H-এর triangle-গুলোর ওপর bijection-এ পাঠায়। — সংজ্ঞা ৪.১, তিনবার
4. (ঘ) একই যুক্তি: একটি k-cycle-এর পরপর vertex-গুলোর ছবি পরপর যুক্ত, আর f injective বলে তারা আলাদা থাকে। — ধাপ ৩-এর সাধারণ রূপ
5. (ঙ, চ) G-এ u থেকে v-এর একটি path-এর ছবি H-এ f(u) থেকে f(v)-এর path; আর G-এর একটি দুই-রঙ করা (bipartite ভাগ) V = X ∪ Y থেকে W = f(X) ∪ f(Y) একটি দুই-রঙ করা দেয়। উল্টো দিক f⁻¹ দিয়ে। ∎ — প্রতিবেশী ঠিক থাকে

লক্ষ করুন, “vertex 1-এর degree 3” কোনো invariant নয়: নামটি f বদলে দেয়। Invariant হতে হলে ধর্মটি নামের ওপর নির্ভর করতে পারবে না। এবার দুটি পরিচিত জোড়া দেখি, যাদের প্রথম দুটি invariant মেলে।

• C₆ বনাম দুটি আলাদা triangle (2C₃): দুটিতেই ৬টি vertex, ৬টি edge, সব degree 2. কিন্তু C₆ connected আর তাতে triangle নেই; 2C₃ connected নয়, triangle ২টি। Isomorphic নয়।
• প্রিজম বনাম K_3,3: দুটিই connected, ৬টি vertex, ৯টি edge, সব degree 3. এখানে connectedness-ও মেলে; পার্থক্য ধরা পড়ে triangle-এ, নিচের ছবি আর stepper-এ।

1n: 6 বনাম 62m: 9 বনাম 93degree sequence4connected?5triangle গোনা6trace(A³) দিয়ে যাচাই

৬ · যন্ত্রে isomorphism পরীক্ষা — brute force, pruning আর জটিলতা

সংজ্ঞাটিই একটি algorithm দেয়: V থেকে W-এ সব n! টি bijection একে একে নিন, আর প্রতিটির জন্য সব জোড়া পরীক্ষা করুন। n = 10-এ 10! = 3,628,800 টি bijection, n = 20-এ প্রায় 2.4 × 10¹⁸. তাই দুটি সহজ বুদ্ধি লাগে, ঠিক §৪-এর stepper-এর মতো: (১) degree না মিললে সেই vertex-এ পাঠানোই যাবে না; (২) একটি একটি করে vertex বসান, আর প্রতিবার আগে বসানো সবার সঙ্গে edge/non-edge মিলছে কি না দেখুন; না মিললে সেই শাখা সেখানেই বাদ (backtracking, পর্ব ৩৬)। নিচের ব্লক দুটি পদ্ধতিই তিনটি জোড়ায় চালায়: C₅ বনাম তারা, প্রিজম বনাম K_3,3, আর একটি ঘনক (Q₃) বনাম তার এলোমেলো নামের আরেকটি কপি।

from itertools import permutations
def graph(text):                       # "a-b b-c ..." -> adjacency sets
    G = {}
    for u, v in (e.split("-") for e in text.split()):
        G.setdefault(u, set()).add(v); G.setdefault(v, set()).add(u)
    return G
def brute(G, H):                       # try all n! bijections in order
    for tried, img in enumerate(permutations(sorted(H)), 1):
        f = dict(zip(sorted(G), img))
        if all((f[v] in H[f[u]]) == (v in G[u]) for u in G for v in G):
            return True, tried
    return False, tried
def pruned(G, H, f, calls):            # backtracking: degree + edges so far
    calls[0] += 1
    if len(f) == len(G):
        return True
    u = sorted(G)[len(f)]
    for x in sorted(set(H) - set(f.values())):
        if len(H[x]) == len(G[u]) and \
           all((f[w] in H[x]) == (w in G[u]) for w in f):
            f[u] = x
            if pruned(G, H, f, calls): return True
            del f[u]
    return False

pairs = {"C5 vs star": ("1-2 2-3 3-4 4-5 5-1", "a-c c-e e-b b-d d-a"),
         "prism vs K33": ("1-2 2-3 3-1 4-5 5-6 6-4 1-4 2-5 3-6",
                          "a-x a-y a-z b-x b-y b-z c-x c-y c-z"),
         "cube vs cube": ("1-2 2-3 3-4 4-1 5-6 6-7 7-8 8-5 1-5 2-6 3-7 4-8",
                          "a-h a-c a-e h-b h-g c-b c-d e-g e-d b-f g-f d-f")}
for name, (g, h) in pairs.items():
    G, H, f, calls = graph(g), graph(h), {}, [0]
    (ok, tried), found = brute(G, H), pruned(G, H, f, calls)
    print(f"{name}: isomorphic={ok}, brute tried {tried}, pruned calls {calls[0]}")
    if found: print("   f =", f)

C5 vs star: isomorphic=True, brute tried 11, pruned calls 6
   f = {'1': 'a', '2': 'c', '3': 'e', '4': 'b', '5': 'd'}
prism vs K33: isomorphic=False, brute tried 720, pruned calls 25
cube vs cube: isomorphic=True, brute tried 823, pruned calls 9
   f = {'1': 'a', '2': 'c', '3': 'b', '4': 'h', '5': 'e', '6': 'd', '7': 'f', '8': 'g'}

জটিলতা: সমস্যাটি কতটা কঠিন?

Pruning ছোট গ্রাফে দারুণ কাজ করে, কিন্তু সবচেয়ে খারাপ ক্ষেত্রে এটিও exponential হতে পারে, বিশেষ করে খুব প্রতিসম (যেমন regular) গ্রাফে, যেখানে degree কোনো তথ্য দেয় না। Graph isomorphism (GI) সমস্যাটি জটিলতা-তত্ত্বে একটি অদ্ভুত জায়গায় আছে। এটি NP-তে আছে, কারণ একটি f দিলে তা polynomial সময়ে যাচাই করা যায় (DSA কোর্সের পর্ব ৬৪ “P বনাম NP — NP-complete আর reduction” দেখুন)। কিন্তু এটি NP-complete বলে প্রমাণিত নয়, আর polynomial সময়ের কোনো algorithm-ও জানা নেই। László Babai ২০১৫ সালে একটি quasi-polynomial সময়ের algorithm ঘোষণা করেন, অর্থাৎ সময় exp((log n)^c)-এর মতো, যা polynomial-এর চেয়ে সামান্য বেশি কিন্তু exponential-এর চেয়ে অনেক কম; ২০১৭ সালের শুরুতে বিশ্লেষণে একটি ত্রুটি ধরা পড়লে তিনি তা সংশোধন করেন বলে জানা যায়। পর্ব ৫১-এর প্র ০৪-এ এর প্রেক্ষাপট আছে: শ্রেণি গোনা সহজ, কিন্তু দুটি নির্দিষ্ট গ্রাফ একই শ্রেণিতে কি না, সেই সিদ্ধান্ত কঠিনতর।

৭ · Automorphism আর লেবেলযুক্ত বনাম লেবেলহীন গ্রাফ

§৪-এর stepper-এ f(1) = a নেওয়ার সময় বলা হয়েছিল “C₅-এর সব vertex একই রকম”। এই কথার নির্ভুল রূপ হলো symmetry: গ্রাফকে নিজের ওপর এমনভাবে সাজানো, যাতে edge-গুলো edge-ই থাকে।

উদাহরণ: K_n-এর প্রতিটি permutation একটি automorphism, তাই |Aut(K_n)| = n!. একা n টি vertex (কোনো edge নেই)-এরও n!. K_3,3-এ একটি সারির ভেতরে 3! রকম সাজানো, অন্য সারিতেও 3!, আর দুই সারি অদলবদল 2 রকম: 2 · 3! · 3! = 72. প্রিজমে 12. (শেষ দুটি সংখ্যা scratch-এ সব 720টি permutation পরীক্ষা করে মেলানো।)

C_n-এর vertex 1, 2, …, n, আর edge {i, i + 1}, যেখানে n + 1 মানে 1 ধরা হয়।

1. বড়জোর 2n: σ(1) বাছার n উপায়। 2 হলো 1-এর প্রতিবেশী, তাই σ(2) অবশ্যই σ(1)-এর দুই প্রতিবেশীর একটি: 2 উপায়। — automorphism প্রতিবেশী ঠিক রাখে
2. এরপর সব বাধ্য: 3 হলো 2-এর 1 ছাড়া অন্য প্রতিবেশী, তাই σ(3) = σ(2)-এর σ(1) ছাড়া অন্য প্রতিবেশী; একইভাবে σ(4), …, σ(n). তাই σ(1) আর σ(2) পুরো σ ঠিক করে দেয়। — cycle ধরে induction
3. অন্তত 2n: n টি rotation (i ↦ i + k) আর n টি reflection (i ↦ k − i), সব mod n, প্রতিটি edge {i, i + 1}-কে edge-এ পাঠায়, আর এই 2n টি ফাংশন আলাদা (σ(1), σ(2) জোড়া সবার আলাদা)। — সরাসরি যাচাই
4. তাই |Aut(C_n)| = 2n, আর n = 5-এ 10. ∎ এটিই পর্ব ৫১-এর dihedral group.

এবার গণনার প্রশ্ন। {1, 2, 3, 4, 5}-এর ওপর কয়টি আলাদা লেবেলযুক্ত গ্রাফ C₅-এর isomorphic, অর্থাৎ পাঁচটি নামকে একটি বৃত্তে সাজানোর কয়টি আলাদা উপায়ে আলাদা edge-সেট আসে? সব 5! = 120 সাজানো চেষ্টা করলে একই edge-সেট বারবার আসে; ঠিক কতবার, তা বলে automorphism.

1. V-এর প্রতিটি permutation σ থেকে একটি গ্রাফ σ(G) পাই, যার edge-সেট {{σ(u), σ(v)} : {u, v} ∈ E}; σ নিজেই G থেকে σ(G)-তে isomorphism. — সংজ্ঞা ৪.১
2. V-এর ওপর G ≅ H হলে, তার isomorphism f : V → V নিজেই একটি permutation আর H = f(G). তাই প্রতিটি কপি কোনো σ থেকে আসে। — onto
3. σ(G) = τ(G) ⇔ τ⁻¹σ(G) = G ⇔ τ⁻¹σ ∈ Aut(G) ⇔ σ ∈ τ·Aut(G). তাই একটি নির্দিষ্ট কপি τ(G) ঠিক |Aut(G)|টি permutation থেকে আসে। — group-এর সংজ্ঞা
4. n! টি permutation সমান মাপের (|Aut(G)|টি করে) দলে ভাগ হয়, প্রতিটি দল একটি কপি; কপি n!/|Aut(G)|টি। ∎ — ভাগের নিয়ম

এটি আসলে পর্ব ৫১-এর orbit–stabilizer উপপাদ্য: permutation-গুলো লেবেলযুক্ত গ্রাফের ওপর কাজ করে, G-এর orbit হলো তার সব কপি, আর stabilizer হলো Aut(G). C₅-এর ক্ষেত্রে 120/10 = 12টি লেবেলযুক্ত কপি; হাতে দেখুন: 1-কে স্থির রেখে বাকি চারটিকে বৃত্তে 4! = 24 ভাবে সাজানো যায়, আর প্রতিটি বৃত্ত দুই দিক থেকে পড়া যায়, 24/2 = 12. এখান থেকে একটি দরকারি সূত্র: n-vertex-এর লেবেলযুক্ত গ্রাফ মোট 2^C(n,2)টি (প্রতিটি জোড়ায় edge আছে বা নেই), আর লেবেলহীন গ্রাফ, অর্থাৎ isomorphism শ্রেণি, গুনতে হলে প্রতিটি শ্রেণির জন্য উপপাদ্য ৭.৩ বসিয়ে

∑_{শ্রেণি G} n!/|Aut(G)| = 2^C(n,2)

যাচাই করতে হবে। পরের অংশের Python ব্লক n = 4-এ এটিই করে।

৮ · Canonical form — প্রতিটি শ্রেণির একটি প্রতিনিধি

লাখ লাখ গ্রাফের একটি ডেটাবেসে নতুন গ্রাফ এলে প্রশ্ন: এটি কি আগে থেকেই আছে, শুধু অন্য নামে? প্রতিবার সবার সঙ্গে isomorphism পরীক্ষা অসম্ভব। ভালো উপায় হলো প্রতিটি গ্রাফকে একটি নির্দিষ্ট “আদর্শ নাম”-এ রূপান্তর করা, যাতে দুটি গ্রাফ isomorphic হলে এবং কেবল তখনই তাদের আদর্শ নাম এক হয়। তখন ডেটাবেসে শুধু সেই নাম খুঁজলেই চলে, যেমন অভিধানে শব্দ খোঁজা।

1. (⇒) G ≅ H হলে H = f(G) কোনো permutation f-এর জন্য (উপপাদ্য ৭.৩-এর ধাপ ২)। তাহলে {σ(H)} = {σf(G)} = {τ(G)}: permutation-গুলোর সেট একই, কারণ σ ↦ σf একটি bijection. একই string-সেটের সর্বনিম্ন একই। — group-এ গুণ bijection
2. (⇐) canon(G) = canon(H) = s হলে কোনো σ, τ-এর জন্য s(σ(G)) = s(τ(H)). String গ্রাফটিকে পুরো নির্ধারণ করে, তাই σ(G) = τ(H), আর G ≅ σ(G) = τ(H) ≅ H. ∎ — ≅ transitive

এটি canonical form-এর সবচেয়ে সরল রূপ। খরচ n! × C(n, 2), তাই শুধু ছোট n-এ চলে; বাস্তবের সফটওয়্যার একই ধারণা অনেক বুদ্ধি খাটিয়ে প্রয়োগ করে (প্র ০১)। নিচের ব্লক ৪টি vertex-এর সব 2⁶ = 64টি লেবেলযুক্ত গ্রাফের canonical form বের করে, শ্রেণিতে ভাগ করে, প্রতিটি শ্রেণির |Aut| গোনে, আর §৭-এর সূত্র যাচাই করে।

from itertools import combinations, permutations, product
from collections import defaultdict
from math import factorial

n = 4
pairs = list(combinations(range(n), 2))     # the 6 possible edges
perms = list(permutations(range(n)))        # the 24 relabellings

def code(E, p):                             # adjacency string after relabelling p
    F = {frozenset((p[u], p[v])) for u, v in E}
    return "".join("1" if frozenset(q) in F else "0" for q in pairs)

classes = defaultdict(list)
for bits in product((0, 1), repeat=len(pairs)):
    E = [q for q, b in zip(pairs, bits) if b]
    canon = min(code(E, p) for p in perms)  # canonical form = smallest string
    classes[canon].append(E)

print("labelled graphs:", sum(map(len, classes.values())),
      " isomorphism classes:", len(classes))
total = 0
for canon in sorted(classes, key=lambda c: (c.count("1"), c)):
    E = classes[canon][0]
    own = code(E, range(n))
    aut = sum(code(E, p) == own for p in perms)   # automorphisms of E
    size = len(classes[canon])
    total += factorial(n) // aut
    print(f"{canon}  m={canon.count('1')}  labelled={size:2}"
          f"  |Aut|={aut:2}  4!/|Aut|={factorial(n) // aut:2}")
print("sum of 4!/|Aut| over classes =", total)

labelled graphs: 64  isomorphism classes: 11
000000  m=0  labelled= 1  |Aut|=24  4!/|Aut|= 1
000001  m=1  labelled= 6  |Aut|= 4  4!/|Aut|= 6
000011  m=2  labelled=12  |Aut|= 2  4!/|Aut|=12
001100  m=2  labelled= 3  |Aut|= 8  4!/|Aut|= 3
000111  m=3  labelled= 4  |Aut|= 6  4!/|Aut|= 4
001011  m=3  labelled= 4  |Aut|= 6  4!/|Aut|= 4
001101  m=3  labelled=12  |Aut|= 2  4!/|Aut|=12
001111  m=4  labelled=12  |Aut|= 2  4!/|Aut|=12
011110  m=4  labelled= 3  |Aut|= 8  4!/|Aut|= 3
011111  m=5  labelled= 6  |Aut|= 4  4!/|Aut|= 6
111111  m=6  labelled= 1  |Aut|=24  4!/|Aut|= 1
sum of 4!/|Aut| over classes = 64

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

গ্রাফ তত্ত্বে একটি গ্রাফ এত বেশি অনুমানের পাল্টা-উদাহরণ যে তাকে প্রায় সব বইয়ে পাওয়া যায়: Petersen graph. এর সবচেয়ে পরিষ্কার সংজ্ঞা সেট দিয়ে: vertex হলো {1, 2, 3, 4, 5}-এর দশটি দুই-উপাদানের subset, আর দুটি subset-এর মধ্যে edge ঠিক তখন, যখন তারা বিচ্ছিন্ন (কোনো সাধারণ উপাদান নেই)। এই ধাঁচের গ্রাফকে বলে Kneser graph K(5, 2). ছবিতে এটি সাধারণত একটি বাইরের পাঁচ-কোণ আর ভেতরের তারা হিসেবে আঁকা হয়।

1. (ক) C(5, 2) = 10. একটি subset {a, b}-এর সঙ্গে বিচ্ছিন্ন subset বাকি তিনটি উপাদান থেকে নিতে হয়: C(3, 2) = 3, তাই 3-regular; handshake থেকে m = 10 · 3/2 = 15. — গণনা
2. (খ) Triangle মানে তিনটি পরস্পর বিচ্ছিন্ন দুই-উপাদানের subset, যাদের মোট 6টি আলাদা উপাদান লাগে; কিন্তু আছে মাত্র 5টি। — pigeonhole
3. 4-cycle x, y, z, w ধরুন। x আর z দুজনেই y আর w-এর সঙ্গে বিচ্ছিন্ন, অর্থাৎ x, z ⊆ {1,…,5} − (y ∪ w). y ≠ w বলে |y ∪ w| ≥ 3, তাই বাকি থাকে বড়জোর 2টি উপাদান, আর x = z হতে বাধ্য; কিন্তু cycle-এ x ≠ z. বিরোধ। — proof by contradiction
4. (গ) দুটি আলাদা, যুক্ত নয় এমন vertex মানে দুটি subset, যাদের ঠিক একটি উপাদান সাধারণ, যেমন {1, 2} আর {1, 3}. তাদের union-এ 3টি উপাদান, বাকি দুটি (এখানে {4, 5}) দুজনের সঙ্গেই বিচ্ছিন্ন: একটি সাধারণ প্রতিবেশী। দূরত্ব 2. — সরাসরি নির্মাণ
5. (ঘ) {1,…,5}-এর যেকোনো permutation π subset-গুলোকে subset-এ পাঠায় আর বিচ্ছিন্নতা ঠিক রাখে (π injective), তাই প্রতিটি π একটি automorphism দেয়; আলাদা π আলাদা automorphism দেয়। মোট অন্তত 5! = 120. ∎ — বিচ্ছিন্নতা নামের ওপর নির্ভর করে না

আসলে |Aut| ঠিক 120; উপরের সীমা প্রমাণে আরও কাজ লাগে, তাই এখানে brute-force backtracking দিয়ে গুনে দেখি। একই ব্লক girth আর diameter-ও সরাসরি যাচাই করে।

from itertools import combinations
from collections import deque
from math import factorial

V = [frozenset(s) for s in combinations(range(1, 6), 2)]  # 2-subsets of {1..5}
P = {v: {w for w in V if not v & w} for v in V}           # edge iff disjoint
n, m = len(V), sum(len(P[v]) for v in V) // 2
print("n =", n, " m =", m, " degrees:", sorted({len(P[v]) for v in V}))

def dist(s):                                 # BFS distances from s
    d, q = {s: 0}, deque([s])
    while q:
        u = q.popleft()
        for w in P[u] - d.keys():
            d[w] = d[u] + 1; q.append(w)
    return d
print("diameter =", max(max(dist(v).values()) for v in V))
tri = sum(1 for a, b, c in combinations(V, 3)
          if b in P[a] and c in P[a] and c in P[b])
quad = sum(1 for a, b, c, d in combinations(V, 4)
           for w, x, y, z in [(a, b, c, d), (a, b, d, c), (a, c, b, d)]
           if x in P[w] and y in P[x] and z in P[y] and w in P[z])
print("triangles =", tri, " 4-cycles =", quad, " so girth = 5")

def count(f):                                # extend partial automorphism f
    if len(f) == n:
        return 1
    u, total = V[len(f)], 0
    for x in V:
        if x not in f.values() and all((f[w] in P[x]) == (w in P[u]) for w in f):
            f[u] = x; total += count(f); del f[u]
    return total
aut = count({})
print("|Aut| =", aut, " labelled copies 10!/|Aut| =", factorial(10) // aut)

n = 10  m = 15  degrees: [3]
diameter = 2
triangles = 0  4-cycles = 0  so girth = 5
|Aut| = 120  labelled copies 10!/|Aut| = 30240

আরও কয়েকটি ধর্ম, যেগুলোর প্রমাণ পরের পর্বগুলোর বিষয় (scratch-এ brute force দিয়ে মেলানো): Petersen graph-এ কোনো Hamilton cycle নেই (পর্ব ৬০ “Euler আর Hamilton path — Königsberg থেকে NP-কঠিনতা”), এটি planar নয় (পর্ব ৬২ “Planar graph — Euler-এর সূত্র আর Kuratowski”), এর chromatic number 3, কিন্তু edge-গুলোকে ৩ রঙে এমনভাবে রাঙানো যায় না যাতে একই vertex-এ দুটি edge একই রঙের হয় (পর্ব ৬৩ “Graph coloring — chromatic number, scheduling আর চার রঙের উপপাদ্য”)। 5-cycle আছে বলে এটি bipartite-ও নয়।

অঙ্ক ১: Matrix থেকে তথ্য পড়া

একটি simple graph-এর vertex v₁, …, v₅ আর edge v₁v₂, v₁v₃, v₂v₃, v₃v₄, v₄v₅. (ক) incidence matrix-এর মাপ আর সব ঘরের যোগফল কত? (খ) (A²)₁₄ আর (A²)₃₃ কত? (গ) trace(A³) কত?

1. (ক) n = 5, m = 5, তাই B একটি 5 × 5 matrix; সব ঘরের যোগফল 2m = 10 (উপপাদ্য ২.২)।
2. (খ) (A²)₁₄ = v₁ আর v₄-এর সাধারণ প্রতিবেশী: শুধু v₃, তাই 1. (A²)₃₃ = deg(v₃) = 3.
3. (গ) Triangle শুধু {v₁, v₂, v₃}, তাই trace(A³) = 6 × 1 = 6 (scratch-এ matrix গুণ করে মেলানো)।

অঙ্ক ২: লেবেলযুক্ত গ্রাফ গোনা

{1, 2, 3, 4}-এর ওপর ঠিক ৩টি edge-যুক্ত লেবেলযুক্ত গ্রাফ কয়টি, আর তারা কয়টি isomorphism শ্রেণিতে পড়ে? উত্তর: C(6, 3) = 20টি, ৩টি শ্রেণিতে। Triangle + একা vertex: |Aut| = 3! = 6, কপি 24/6 = 4 (একা vertex বাছার ৪ উপায়)। তারা K_1,3: |Aut| = 6, কপি 4 (কেন্দ্র বাছার ৪ উপায়)। Path P₄: |Aut| = 2 (উল্টে পড়া), কপি 12. যোগফল 4 + 4 + 12 = 20 ✓ (canonical form ব্লকের m = 3 সারিগুলো)।

প্রমাণের ভুল ধরুন: “সব invariant মিলেছে”

একজন লিখলেন: “দুটি গ্রাফে vertex ৬টি, edge ৯টি, degree sequence (3, 3, 3, 3, 3, 3), আর দুটিই connected. isomorphism এই সব ধর্ম রক্ষা করে, তাই গ্রাফ দুটি isomorphic হবেই।”

ভুল কোথায়: উপপাদ্য ৫.২ বলে “isomorphic ⇒ invariant সমান”; লেখক ব্যবহার করেছেন উল্টো দিক “invariant সমান ⇒ isomorphic”, যা প্রমাণিত নয়, আর এখানে মিথ্যা: প্রিজম আর K_3,3 ঠিক এই সব ধর্ম মেনে চলে, তবু isomorphic নয়, যা §৫-এর stepper-এ দেখা গেছে। এটি পর্ব ৮-এর converse-এর ভুল। Isomorphic প্রমাণের একমাত্র নিরাপদ পথ একটি স্পষ্ট bijection দেখানো (বা একটি complete invariant, যেমন canonical form, মেলানো)।

১০ · AI-এর যুগে — isomorphism-এর দাবি যাচাই

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

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

• n, m আর degree sequence নিজে গুনে মিলিয়েছি
• দেওয়া bijection-এ প্রতিটি edge-এর ছবি H-এর edge, আর edge-সংখ্যা সমান
• “আলাদা” দাবির পেছনে একটি সত্যিকারের invariant আছে, নামের ওপর নির্ভরশীল ধর্ম নয়
• Triangle-এর সংখ্যা trace(A³)/6 দিয়ে আলাদাভাবে মিলিয়েছি
• ছোট গ্রাফে brute force বা backtracking চালিয়ে উত্তর পরীক্ষা করেছি
• জটিলতা আর ইতিহাসের দাবি বিশ্বস্ত পাঠ্যবই বা মূল প্রবন্ধে মিলিয়েছি

Isomorphism-এর প্রশ্নের একটি বড় সুবিধা: “হ্যাঁ” উত্তরের একটি সার্টিফিকেট আছে (bijection), আর “না” উত্তরেরও প্রায়ই একটি ছোট সার্টিফিকেট থাকে: একটি অমিল invariant-এর হিসাব। AI-এর কাছে সবসময় সেই সার্টিফিকেট চান; সার্টিফিকেট যাচাই করা উত্তর খুঁজে পাওয়ার চেয়ে অনেক সহজ।