Graph coloring — chromatic number, scheduling আর চার রঙের উপপাদ্য

১ · রং করার সমস্যা — proper colouring আর chromatic number

বাজারঘর তার কর্মীদের জন্য সাতটি প্রশিক্ষণ চালায়: Excel, Packing, Safety, Rider, Cash, Stock আর Service. প্রতিটি প্রশিক্ষণের শেষে একটি পরীক্ষা। একজন কর্মী দুটি প্রশিক্ষণে থাকলে সেই দুটির পরীক্ষা একই সময়ে রাখা যায় না। প্রশ্ন: সবচেয়ে কম কয়টি সময়-স্লটে সব পরীক্ষা নেওয়া যায়?

এভাবে পাওয়া graph-কে বলে conflict graph: প্রতিটি প্রশিক্ষণ একটি vertex, আর দুটি প্রশিক্ষণে অন্তত একজন সাধারণ কর্মী থাকলে তাদের মধ্যে একটি edge. নিচের সারণিতে আটজন কর্মীর ভর্তি (কাল্পনিক), আর ছবিতে তার conflict graph.

একই রঙের সব vertex মিলে একটি colour class. কোনো দুটি একই রঙের vertex পাশাপাশি নয়, তাই প্রতিটি colour class একটি independent set (যাদের কোনো দুজনের মধ্যে edge নেই)। সুতরাং একটি k-colouring মানে V-কে বড়জোর k টি independent set-এ ভাগ করা: পর্ব ৫৫-এর partition-এর ভাষায়, প্রতিটি ব্লক independent. Loop থাকলে কোনো proper colouring নেই (একটি vertex নিজের প্রতিবেশী), তাই loop বাদ।

1. (ক) K_n-এ যেকোনো দুটি vertex পাশাপাশি, তাই সব রং আলাদা হতে হয়: অন্তত n টি। প্রত্যেককে আলাদা রং দিলে n টিতেই হয়। — সংজ্ঞা
2. (খ) জোড় n: পরপর 1, 2, 1, 2, … দিলে শেষ vertex v_n পায় 2, আর তার প্রতিবেশী v₁-এর রং 1; সঠিক। একটি edge আছে বলে 1 রঙে হয় না। — নির্মাণ
3. বিজোড় n: ধরি দুই রঙে হয়। v₁-এর রং 1 হলে পাশাপাশি রং বদলাতে হয়, তাই v_i-এর রং 1 ঠিক যখন i বিজোড়। n বিজোড়, তাই v_n-এর রং 1, অথচ v_n আর v₁ পাশাপাশি। বিরোধ। তিন রং যথেষ্ট: শেষ vertex-কে 3 দিন। — contradiction
4. (গ) পর্ব ৫৭ “গ্রাফ — সংজ্ঞা, degree আর handshake theorem”-এ প্রমাণিত: bipartite ⇔ 2-colourable ⇔ odd cycle নেই। দুটি দল মানেই দুটি colour class. — সংজ্ঞার অনুবাদ
5. (ঘ) Rim-এর C_n-এ (খ)-এর মতো রং দিন; hub সবার প্রতিবেশী, তাই তার জন্য একটি নতুন রং লাগে আর যথেষ্ট: χ(W_n) = χ(C_n) + 1. ∎ — hub-এর কোনো রং rim-এ থাকতে পারে না

লক্ষ করুন, “χ(G) = k” প্রমাণ করতে সবসময় দুটি কাজ: একটি k-colouring দেখানো (ওপরের সীমা), আর k − 1 রঙে যে অসম্ভব তার যুক্তি (নিচের সীমা)। প্রথমটি সহজ, একটি উদাহরণই যথেষ্ট; দ্বিতীয়টিই আসল গণিত। ছবির graph-এ ৩টি রং দেখানো হয়েছে; E, C, K তিনজন পরস্পর যুক্ত (মিতু তিনটিতেই আছেন), তাই ২টিতে অসম্ভব, আর χ = 3.

২ · নিচের আর ওপরের সীমা — clique, independent set আর greedy

সাধারণ graph-এ χ নির্ভুলভাবে বের করা কঠিন (§৮)। তাই আগে দুই দিক থেকে সীমা টানা হয়, ঠিক যেমন মাপার আগে আন্দাজ: “কমপক্ষে এত, বড়জোর এত”।

1. একটি clique-এর প্রতিটি জোড়া পাশাপাশি, তাই তার ω টি vertex-এর রং সব আলাদা; ফলে যেকোনো proper colouring-এ অন্তত ω টি রং। — উপপাদ্য ১.২(ক)-এর যুক্তি
2. একটি χ-colouring-এর colour class V₁, …, V_χ সবাই independent, তাই প্রতিটির আকার ≤ α. — α-এর সংজ্ঞা
3. n = |V₁| + ⋯ + |V_χ| ≤ χ · α, তাই χ ≥ n/α, আর χ পূর্ণসংখ্যা বলে ⌈n/α⌉. ∎ — partition-এর আকার যোগ

ওপরের সীমার জন্য একটি পদ্ধতি। Greedy colouring: vertex-গুলোকে কোনো একটি ক্রমে v₁, v₂, …, v_n সাজান; ক্রমানুসারে প্রত্যেককে এমন সবচেয়ে ছোট রং দিন, যা তার আগে রং পাওয়া প্রতিবেশীদের কারও নেই। এটি greedy: একবার রং দিলে আর বদলায় না।

1. v_i-এর পালায় তার রং-পাওয়া প্রতিবেশী b_i জন, তারা বড়জোর b_iটি আলাদা রং আটকায়। — শুধু আগের vertex-এর রং আছে
2. তাই {1, …, b_i + 1}-এর অন্তত একটি রং খালি, আর greedy তার মধ্যে সবচেয়ে ছোটটি দেয়: c(v_i) ≤ b_i + 1. — pigeonhole-এর সরল রূপ
3. রং দেওয়ার সময় কোনো আগের প্রতিবেশীর সঙ্গে মেলে না, আর পরের প্রতিবেশী পরে নিজেই এড়িয়ে চলে; তাই প্রতিটি edge-এর দুই প্রান্ত আলাদা। — সঠিকতা
4. b_i ≤ deg(v_i) ≤ Δ, তাই সব রং ≤ Δ + 1. ∎

দুটি সীমাই কখনো কখনো ঠিক সমান: K_n-এ ω = χ = Δ + 1 = n, আর odd cycle-এ Δ + 1 = 3 = χ. কিন্তু সাধারণত ফাঁক থাকে। W₅-এ ω = 3 (hub আর rim-এর একটি edge), অথচ χ = 4; C₅-এ ω = 2, χ = 3. অর্থাৎ বড় clique না থাকলেও বেশি রং লাগতে পারে (প্র ০৩-এ এর চরম রূপ)। ওপরের দিকে প্রায় সব ক্ষেত্রে Δ + 1-এর চেয়ে ভালো করা যায়:

প্রমাণটি দীর্ঘ (একটি বিশেষ ক্রম বেছে greedy চালানো, যাতে শেষ vertex-এর দুটি প্রতিবেশী একই রং পায়); এখানে বাদ রাখা হলো, Diestel বা West-এর graph theory পাঠ্যবইয়ে পাবেন। ব্যবহার দেখুন: Petersen graph (১০টি vertex, ৩-regular) connected, complete নয়, cycle নয়, তাই χ ≤ 3; আর এতে একটি ৫-cycle আছে, তাই χ ≥ 3. ফল χ = 3. এর α = 4, তাই উপপাদ্য ২.২ দেয় শুধু χ ≥ ⌈10/4⌉ = 3, এখানে সেটিও খাপ খায়।

৩ · Greedy-র ক্রম, crown graph আর Welsh–Powell

উপপাদ্য ২.৩ বলে greedy কখনো Δ + 1-এর বেশি রং নেয় না। কিন্তু χ-এর কত কাছে আসে? উত্তর পুরোপুরি ক্রমের ওপর নির্ভর করে, আর দুই দিকেই চরম।

1. একটি সেরা colouring নিন, colour class V₁, …, V_χ. ক্রম: আগে V₁-এর সবাই, তারপর V₂-এর সবাই, …, শেষে V_χ. — নির্মাণ
2. দাবি: V_i-এর প্রতিটি vertex greedy-তে রং পায় ≤ i. i-এর ওপর induction (পর্ব ১০)। — induction-এর কাঠামো
3. V_i-এর একটি vertex x-এর পালায় আগের প্রতিবেশীরা V_i-এ থাকতে পারে না (V_i independent), তাই তারা V₁ ∪ ⋯ ∪ V_i−1-এ, আর hypothesis অনুযায়ী তাদের রং ≤ i − 1. — hypothesis
4. তাই রং i খালি, আর greedy সবচেয়ে ছোট খালি রং দেয়: c(x) ≤ i. ফলে মোট রং ≤ χ, আর χ-এর চেয়ে কম অসম্ভব। ∎

সমস্যা হলো, এই ক্রম বানাতে আগেই একটি সেরা colouring জানা লাগে। অচেনা ক্রমে কী হতে পারে, তা দেখায় crown graph S_n: দুই দল a₁, …, a_n আর b₁, …, b_n; a_i আর b_j যুক্ত ঠিক তখন, যখন i ≠ j. এটি K_n,n থেকে n টি “নিজের জোড়া” edge সরানো, তাই bipartite, χ = 2.

1ক্রম ১: a1 b1 a2 b2 …2a1, b13a2, b24a3, b35a4, b4: ৪টি রং6ক্রম ২: a1 a2 a3 a47b1 b2 b3 b4: ২টি রং

সাধারণ n-এ একই যুক্তি (i-এর ওপর induction): খারাপ ক্রমে a_i-এর আগের প্রতিবেশী b₁, …, b_i−1, যাদের রং 1, …, i − 1, তাই a_i পায় i; b_i-এর ক্ষেত্রেও তাই। অর্থাৎ 2n টি vertex-এর একটি bipartite graph-এ greedy n টি রং নেয়: greedy-র ফল আর χ-এর অনুপাত যত খুশি বড় হতে পারে।

Welsh–Powell ক্রম। Dominic Welsh আর Martin Powell ১৯৬৭ সালে প্রস্তাব করেন বলে জানা যায়: degree অনুযায়ী বড় থেকে ছোট সাজিয়ে (d₁ ≥ d₂ ≥ ⋯ ≥ d_n) greedy চালান। যুক্তি সহজ: যার প্রতিবেশী বেশি, তার হাতে বিকল্প কম, তাই তাকে আগে রং দিন। নিশ্চয়তাটি এই:

χ(G) ≤ max_i min(d_i + 1, i)

প্রমাণ। i-তম vertex-এর আগের প্রতিবেশী বড়জোর i − 1 জন (তার আগে মোটে i − 1টি vertex) আর বড়জোর d_i জন; উপপাদ্য ২.৩-এর যুক্তিতে তার রং ≤ min(d_i, i − 1) + 1 = min(d_i + 1, i). ∎ এই সীমা Δ + 1-এর চেয়ে কখনো খারাপ নয়, আর কয়েকটি vertex-এর degree খুব বড় হলে অনেক ভালো। কিন্তু crown graph-এ সবার degree n − 1, ফলে সীমা n, আর জোড়ায় জোড়ায় ক্রমটিও বৈধ Welsh–Powell ক্রম (সমান degree-তে যেকোনো ক্রম চলে)। অর্থাৎ এটি একটি ভালো অনুমাননির্ভর নিয়ম (heuristic), সর্বোত্তমের নিশ্চয়তা নয়। Daniel Brélaz-এর DSatur (১৯৭৯) প্রতি ধাপে “সবচেয়ে বেশি আলাদা রঙের প্রতিবেশী যার” তাকে বাছে, বাস্তবে সাধারণত আরও ভালো করে।

নিচের ব্লক চারটি graph-এ backtracking দিয়ে নির্ভুল χ বের করে, আর greedy-কে সব সম্ভাব্য ক্রমে চালিয়ে (৮টি vertex পর্যন্ত সব n! ক্রম; Petersen-এ ১০! = 3628800টি ক্রম অনেক, তাই ৫০০০টি এলোমেলো ক্রম) সবচেয়ে কম আর বেশি রং দেখায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে; পরের ব্লকগুলো দ্রুত চলে।

import random, itertools
random.seed(63)
def greedy(G, order):                   # smallest colour not used by a neighbour
    c = {}
    for v in order:
        used = {c[u] for u in G[v] if u in c}
        c[v] = min(k for k in range(1, len(G) + 2) if k not in used)
    return max(c.values())
def exact_chi(G):                       # backtracking for k = 1, 2, 3, ...
    V = sorted(G, key=lambda v: -len(G[v]))
    def fill(i, c, k):
        if i == len(V): return True
        for col in range(k):
            if all(c.get(u) != col for u in G[V[i]]):
                c[V[i]] = col
                if fill(i + 1, c, k): return True
                del c[V[i]]
        return False
    return next(k for k in range(1, len(G) + 1) if fill(0, {}, k))
def und(edges):
    G = {}
    for a, b in edges:
        G.setdefault(a, set()).add(b); G.setdefault(b, set()).add(a)
    return G
cyc = [(i, (i + 1) % 5) for i in range(5)]
graphs = {'C5': und(cyc), 'W5': und(cyc + [(i, 'h') for i in range(5)]),
          'crown4': und((f'a{i}', f'b{j}') for i in range(4) for j in range(4) if i != j),
          'petersen': und(cyc + [(i, i+5) for i in range(5)] + [(5+i, 5+(i+2) % 5) for i in range(5)])}
for name, G in graphs.items():
    V = sorted(G, key=str)
    orders = itertools.permutations(V) if len(V) <= 8 else (random.sample(V, len(V)) for _ in range(5000))
    counts = [greedy(G, o) for o in orders]
    wp = greedy(G, sorted(V, key=lambda v: -len(G[v])))        # Welsh-Powell order
    D = max(len(G[v]) for v in G)
    print(f"{name:8} chi={exact_chi(G)} Delta+1={D + 1} greedy min={min(counts)} max={max(counts)} WP={wp}")

C5       chi=3 Delta+1=3 greedy min=3 max=3 WP=3
W5       chi=4 Delta+1=6 greedy min=4 max=4 WP=4
crown4   chi=2 Delta+1=4 greedy min=2 max=4 WP=2
petersen chi=3 Delta+1=4 greedy min=3 max=4 WP=3

৪ · প্রয়োগ — পরীক্ষার সময়সূচি, register, frequency আর Sudoku

Graph colouring-এর শক্তি এর সাধারণতায়: “কিছু জিনিসকে কয়েকটি দলে ভাগ করুন, যাতে সংঘাতে থাকা দুটি একই দলে না যায়”। সংঘাতকে edge আর দলকে রং ধরলেই একই গণিত। §১-এর প্রশিক্ষণ-পরীক্ষায় ফিরে যাই: নিচের ব্লক ভর্তির তালিকা থেকে conflict graph বানায়, সব সম্ভাব্য স্লট-পরিকল্পনা brute force-এ দেখে সবচেয়ে কম স্লট বের করে, আর একটি clique দিয়ে প্রমাণ দেয় যে এর কম সম্ভব নয়।

from itertools import combinations, product
enrol = {'Rafi': 'ES', 'Mitu': 'ECK', 'Sajib': 'RS', 'Nila': 'CV',
         'Tanim': 'KR', 'Joya': 'VE', 'Arif': 'PSC', 'Lima': 'PK'}
names = {'E': 'Excel', 'P': 'Packing', 'S': 'Safety', 'R': 'Rider',
         'C': 'Cash', 'K': 'Stock', 'V': 'Service'}
G = {t: set() for t in names}
for courses in enrol.values():          # same person in both -> conflict edge
    for a, b in combinations(courses, 2):
        G[a].add(b); G[b].add(a)
print("trainings:", len(G), " conflict edges:", sum(map(len, G.values())) // 2)
V = sorted(G)
def plans(k):                           # brute force over all k^n slot plans
    for c in product(range(k), repeat=len(V)):
        s = dict(zip(V, c))
        if all(s[a] != s[b] for a in G for b in G[a]):
            yield s
k = 1
while next(plans(k), None) is None:
    k += 1
plan = next(plans(k))
print("minimum number of slots chi =", k)
for slot in range(k):
    print(f"  slot {slot + 1}:", ", ".join(names[t] for t in V if plan[t] == slot))
Q = next(Q for r in range(len(V), 0, -1) for Q in combinations(V, r)
         if all(b in G[a] for a, b in combinations(Q, 2)))
print("largest clique:", [names[t] for t in Q], "-> at least", len(Q), "slots")
print("number of proper 3-slot plans:", sum(1 for _ in plans(3)))

trainings: 7  conflict edges: 12
minimum number of slots chi = 3
  slot 1: Cash, Rider
  slot 2: Excel, Packing
  slot 3: Stock, Safety, Service
largest clique: ['Cash', 'Excel', 'Stock'] -> at least 3 slots
number of proper 3-slot plans: 12

Register allocation. Compiler একটি ফাংশনের প্রতিটি চলককে CPU-র সীমিত register-এ বসাতে চায়। দুটি চলক একই সময়ে “জীবিত” (পরে আবার লাগবে) থাকলে তারা একই register ভাগ করতে পারে না। চলক = vertex, একসাথে জীবিত = edge (interference graph), register = রং। Register-এর সংখ্যার চেয়ে বেশি রং লাগলে কিছু চলককে মেমরিতে পাঠাতে হয়, যাকে বলে spill. ১৯৮০-এর দশকের শুরুতে IBM-এর Gregory Chaitin ও সহকর্মীরা এই পদ্ধতি জনপ্রিয় করেন বলে জানা যায় (Computer Architecture কোর্সের পর্ব ৩১)।

Frequency assignment. কাছাকাছি দুটি রেডিও টাওয়ার একই frequency ব্যবহার করলে সংকেত মিশে যায়। টাওয়ার = vertex, “কাছাকাছি” = edge, frequency = রং। বাস্তব ব্যবস্থায় শর্ত আরও জটিল (পাশের frequency-ও এড়াতে হয়), কিন্তু মূল কাঠামো colouring.

Sudoku. ৮১টি ঘর = vertex; একই সারি, কলাম বা ৩×৩ বাক্সের দুটি ঘর = edge. প্রতিটি ঘরের প্রতিবেশী 8 (সারি) + 8 (কলাম) + 4 (বাক্সের বাকি, যা সারি-কলামে আগে গোনা হয়নি) = 20, তাই handshake অনুযায়ী edge 81 · 20 / 2 = 810. সমাধান করা Sudoku মানে এই graph-এর একটি proper 9-colouring, যা দেওয়া সূত্রগুলোর (আগে থেকে রং করা কিছু vertex) সঙ্গে মেলে: precolouring extension. পর্ব ০৭-এ একই ধাঁধা SAT solver দিয়ে সমাধানের কথা আছে।

৫ · Planar graph — ছয় রং সহজে, পাঁচ রং Kempe chain দিয়ে

মানচিত্রে পাশাপাশি দুটি জেলাকে আলাদা রং দিতে হলে কয়টি রং লাগে? প্রতিটি জেলাকে একটি vertex আর “একটি সীমানা-রেখা ভাগ করে” সম্পর্ককে একটি edge ধরলে যে graph পাওয়া যায়, তা কাগজে কোনো edge না কেটে আঁকা যায় (প্রতিটি জেলার ভেতরে একটি বিন্দু, আর সীমানা পেরিয়ে রেখা)। এমন graph-কে বলে planar graph. পর্ব ৬২ “Planar graph — Euler-এর সূত্র আর Kuratowski”-এ Euler-এর সূত্র v − e + f = 2 থেকে প্রমাণ হয়েছে: প্রতিটি simple planar graph-এ degree ≤ 5-এর একটি vertex আছে (সংক্ষেপে: v ≥ 3-এ e ≤ 3v − 6, তাই degree-র যোগফল 2e ≤ 6v − 12 < 6v, অর্থাৎ গড় degree ৬-এর কম)। এই একটি তথ্য থেকেই প্রথম ফল।

1. vertex-সংখ্যা n-এর ওপর induction. n ≤ 6 হলে প্রত্যেককে আলাদা রং দিন। — ভিত্তি
2. n > 6: degree ≤ 5-এর একটি vertex v নিন (পর্ব ৬২)। G − v (v আর তার edge সরানো) এখনো simple planar, n − 1টি vertex, তাই hypothesis অনুযায়ী 6-colourable. — planar graph-এর subgraph planar
3. v-এর প্রতিবেশী বড়জোর ৫ জন, তারা বড়জোর ৫টি রং আটকায়; ষষ্ঠ রংটি v-কে দিন। ∎ — উপপাদ্য ২.৩-এর যুক্তি

পাঁচে নামতে একটি নতুন হাতিয়ার লাগে: রং অদলবদল।

1. Chain-এর ভেতরের একটি edge-এর দুই প্রান্ত আগে ছিল i, j (বা j, i), পরে j, i: এখনো আলাদা। — H_ij-এ শুধু i, j রং
2. Chain-এর একটি vertex x আর বাইরের প্রতিবেশী y: y-এর রং i বা j হলে y-ও H_ij-এ থাকত আর x-এর সঙ্গে যুক্ত বলে একই component-এ। তাই y-এর রং i, j ছাড়া অন্য কিছু, আর x-এর নতুন রং (i বা j) তার সঙ্গে মেলে না। ∎ — component-এর সংজ্ঞা

1. n-এর ওপর induction; n ≤ 5 সহজ। n > 5: G-কে সমতলে কোনো crossing ছাড়া আঁকা ধরি, আর degree ≤ 5-এর vertex v নিই। G − v-এর একটি 5-colouring hypothesis থেকে পাই। — পর্ব ৬২, induction
2. v-এর প্রতিবেশীরা ৫টির কম রং ব্যবহার করলে খালি রংটি v-কে দিন, শেষ। তাই ধরি deg(v) = 5, আর প্রতিবেশী v₁, …, v₅ (ছবিতে v-এর চারপাশে ঘড়ির কাঁটার দিকে এই ক্রমে) পাঁচটি আলাদা রং 1, …, 5 পেয়েছে। — কঠিন ক্ষেত্রটিই বাকি
3. v₁-এর H₁₃-chain দেখুন। তাতে v₃ না থাকলে chain-টিতে 1 ↔ 3 অদলবদল করুন (lemma ৫.২): v₁ হয় 3, v₃ থাকে 3, তাই রং 1 খালি, v-কে দিন। — প্রথম ক্ষেত্র
4. অন্যথায় v₁ থেকে v₃ পর্যন্ত একটি path P আছে, যার সব vertex-এর রং 1 বা 3. P আর edge v₃v, vv₁ মিলে একটি বন্ধ বক্ররেখা C, যা সমতলকে ভেতর আর বাইরে ভাগ করে; এটি Jordan curve theorem. v-এর চারপাশের ক্রমের কারণে vv₂ একদিকে যায় আর vv₄ অন্যদিকে: v₂ আর v₄ C-এর দুই পাশে। — আঁকার ক্রম
5. G − v-এ v₂ থেকে v₄-এর যেকোনো path-কে C পার হতে হয়, আর crossing নেই বলে C-এর কোনো vertex দিয়েই পার হয়; সেই vertex-এর রং 1 বা 3 (v নিজে G − v-এ নেই)। তাই v₂ থেকে v₄-এর কোনো 2-4 রঙের path নেই: তারা ভিন্ন H₂₄-chain-এ। — planarity এখানেই লাগে
6. v₂-এর H₂₄-chain-এ 2 ↔ 4 অদলবদল করুন: v₂ হয় 4, v₄ থাকে 4. রং 2 খালি, v-কে দিন। ∎ — lemma ৫.২

নিচের ছবিটি দ্বিতীয় (কঠিন) ক্ষেত্রের একটি ছোট উদাহরণ: ৯টি vertex-এর একটি planar graph, যেখানে v-কে বাদ দিয়ে বাকিদের একটি 5-colouring দেওয়া আছে।

1G − v-এর 5-colouring2H13: v1-এর chain3বন্ধ রেখা C4H24: v2-এর chain52 ↔ 4 অদলবদল6v পায় রং 2

৬ · চার রঙের উপপাদ্য — Kempe-র ভুল থেকে কম্পিউটারের প্রমাণ

সীমাটি নিখুঁত: K₄ planar (একটি ত্রিভুজের ভেতরে একটি বিন্দু, তিন কোণের সঙ্গে যুক্ত), আর তার χ = 4. শুধু এক বিন্দুতে মেলা দুটি দেশকে পাশাপাশি ধরা হয় না; ধরলে কেকের টুকরোর মতো ভাগ করা মানচিত্রে যত খুশি রং লাগত।

প্রমাণের কৌশল (শুধু রূপরেখা)। ধরা যাক উপপাদ্যটি মিথ্যা, আর G সবচেয়ে কম vertex-এর একটি পাল্টা-উদাহরণ, যাকে বলে minimal counterexample. দুটি তালিকা লাগে। (১) একটি unavoidable set: কয়েকটি ছোট কাঠামোর (configuration) তালিকা, যাতে প্রতিটি planar triangulation-এ অন্তত একটি থাকবেই; Euler-এর সূত্র থেকে degree-র “চার্জ” সরিয়ে (discharging) এটি দেখানো হয়, ঠিক যেমন “degree ≤ 5-এর vertex আছেই” একটি অতি ছোট unavoidable set. (২) প্রতিটি কাঠামো reducible: minimal counterexample-এ এটি থাকলে তাকে ছোট করে 4-colour করা আর Kempe chain-এর অদলবদলে ফিরিয়ে আনা যায়, যা অসম্ভব। Kempe-র মূল যুক্তি ঠিক এই কাঠামো মানে: degree ≤ 4-এর vertex-এর জন্য তাঁর যুক্তি সঠিক (উপপাদ্য ৫.৩-এর মতোই একটি অদলবদল যথেষ্ট); ভুলটি ছিল degree 5-এর ক্ষেত্রে (অনুশীলন ৪)। কম্পিউটারের কাজ ছিল হাজার হাজার কাঠামোর reducibility যাচাই, যা হাতে অসম্ভব।

পাঁচ আর চার রঙের মধ্যে ফাঁকটিই শিক্ষণীয়। পাঁচ রঙে প্রতিবেশী ৫ জন হলে রং একটি “বাড়তি” থাকে, তাই একটি মাত্র অদলবদল যথেষ্ট; চার রঙে degree 5-এর vertex-এর প্রতিবেশীদের মধ্যে একটি রং দুবার থাকে, আর দুটি অদলবদল একসঙ্গে লাগে, যারা একে অন্যকে নষ্ট করতে পারে।

৭ · Chromatic polynomial — deletion–contraction

χ শুধু বলে “রং করা যায় কি না”। বাজারঘরের ব্যবস্থাপক জানতে চাইতে পারেন: ৩টি স্লটে কতভাবে পরিকল্পনা করা যায়? §৪-এর ব্লক উত্তর দিয়েছিল ১২। এই গণনাকে k-এর ফাংশন হিসেবে দেখার ধারণা George Birkhoff-এর (১৯১২, চার রঙের সমস্যায় আক্রমণের চেষ্টায়), আর Hassler Whitney ১৯৩২ সালে একে সাধারণ graph-এ বিস্তৃত করেন বলে জানা যায়।

দুটি সরাসরি গণনা (পর্ব ৩১-এর গুণের নিয়ম)। edge-হীন n-vertex graph-এ প্রত্যেকে স্বাধীনভাবে k রং পায়: P = kⁿ. K_n-এ একে একে রং দিলে প্রথমজন k, দ্বিতীয়জন k − 1, …, n-তমজন k − n + 1 বিকল্প পায়:

P(K_n, k) = k(k − 1)(k − 2) ⋯ (k − n + 1)

k < n হলে একটি গুণনীয়ক 0, তাই P = 0, যা χ(K_n) = n-এর সঙ্গে মেলে। সাধারণ graph-এ এমন সরাসরি গুণ চলে না, কারণ একজনের বিকল্প নির্ভর করে আগের প্রতিবেশীরা একই রং পেয়েছে কি না তার ওপর। সমাধান একটি recurrence.

1. G − e-এর proper colouring দুই ধরনের: (ক) c(u) ≠ c(v), (খ) c(u) = c(v). দুটি আলাদা, আর মিলে সবগুলো। — deletion–contraction-এর মূল ভাগ
2. (ক)-এর colouring-গুলো ঠিক G-এর proper colouring: e-এর শর্ত c(u) ≠ c(v) পূরণ হয়েছে, বাকি edge একই। — সংজ্ঞা
3. (খ)-এর colouring আর G / e-এর proper colouring-এর মধ্যে একটি bijection: u, v-এর সাধারণ রং জোড়া vertex-কে দিন; উল্টো দিকে জোড়া vertex-এর রং u আর v দুজনকে দিন। u-এর প্রতিবেশী আর v-এর প্রতিবেশী সবাই জোড়া vertex-এর প্রতিবেশী, তাই proper থাকা দুই দিকে একই শর্ত। — পর্ব ১৬-এর bijection
4. তাই P(G − e, k) = P(G, k) + P(G / e, k). সাজালে ফল। ∎ — যোগের নিয়ম

অনুসিদ্ধান্ত। P(G, k) সবসময় k-এর একটি polynomial: edge-সংখ্যা m-এর ওপর induction; m = 0-তে kⁿ, আর G − e ও G / e দুটিতেই edge কম (G / e-তে vertex-ও কম)। একই induction দেখায় n-vertex, m-edge graph-এ P-এর degree n, প্রথম সহগ 1, kⁿ⁻¹-এর সহগ −m, আর ধ্রুবক পদ 0 (অন্তত একটি vertex থাকলে)। অঙ্কের উত্তর যাচাইয়ে এই তিনটি দ্রুত পরীক্ষা খুব কাজের।

1. (ক) n-এর ওপর induction; n = 1-এ k. n ≥ 2-এর tree-তে একটি leaf ℓ (degree 1) আছে: সবচেয়ে লম্বা path-এর শেষ vertex-এর আর কোনো প্রতিবেশী থাকলে path লম্বা হতো বা cycle তৈরি হতো (বিস্তারিত পর্ব ৬৫ “Tree — ধর্ম, rooted tree আর m-ary tree-এর হিসাব”-এ)। — leaf-এর অস্তিত্ব
2. T − ℓ একটি n − 1 vertex-এর tree; তাকে k(k − 1)ⁿ⁻² ভাবে রং করুন, induction hypothesis অনুযায়ী। ℓ-এর একমাত্র প্রতিবেশীর রং বাদে k − 1টি বিকল্প। গুণ: k(k − 1)ⁿ⁻¹. — গুণের নিয়ম
3. (খ) n-এর ওপর induction. n = 3: C₃ = K₃, P = k(k − 1)(k − 2), আর (k − 1)³ − (k − 1) = (k − 1)((k − 1)² − 1) = (k − 1)(k − 2)k. মেলে। — ভিত্তি
4. n ≥ 4: C_n-এর একটি edge e-তে উপপাদ্য ৭.২. C_n − e হলো n-vertex path (একটি tree), আর C_n / e হলো C_n−1. — deletion–contraction
5. P(C_n) = k(k − 1)ⁿ⁻¹ − (k − 1)ⁿ⁻¹ − (−1)ⁿ⁻¹(k − 1) = (k − 1)ⁿ⁻¹(k − 1) + (−1)ⁿ(k − 1) = (k − 1)ⁿ + (−1)ⁿ(k − 1). ∎ — বীজগণিত

যাচাই: k = 2-এ জোড় n-এ P = 1 + 1 = 2 (দুটি পর্যায়ক্রমিক রং), বিজোড় n-এ 1 − 1 = 0. উপপাদ্য ১.২(খ)-এর সঙ্গে হুবহু মেলে। নিচের stepper C₄-এ একটি deletion–contraction ধাপ হাতে করে।

1G = C4, e = ab2G − e: path3G / e: K34বিয়োগ5বিস্তার6যাচাই

নিচের ব্লক deletion–contraction-কে সরাসরি recursion হিসেবে চালায় (polynomial রাখা হয়েছে সহগের তালিকা হিসেবে), আর k = 1, 2, 3, 4-এ সব kⁿটি রং-বিন্যাস গুনে মিলিয়ে দেখে।

from itertools import product
def sub(p, q):                          # coefficient lists, index = power of k
    n = max(len(p), len(q))
    p, q = p + [0] * (n - len(p)), q + [0] * (n - len(q))
    return [a - b for a, b in zip(p, q)]
def P(V, E):                            # deletion-contraction recursion
    if not E:
        return [0] * len(V) + [1]       # no edges: k^n
    e = min(E, key=sorted)
    u, v = sorted(e)
    E1 = E - {e}                        # G - e
    E2 = frozenset(frozenset(u if x == v else x for x in f) for f in E1)
    return sub(P(V, E1), P(V - {v}, E2))  # G / e: v merged into u
def brute(V, E, k):
    V = sorted(V)
    return sum(all(c[V.index(a)] != c[V.index(b)] for a, b in map(sorted, E))
               for c in product(range(k), repeat=len(V)))
def graph(edges):
    E = frozenset(frozenset(e) for e in edges)
    return frozenset(x for e in E for x in e), E
cyc = lambda n: [(i, (i + 1) % n) for i in range(n)]
tests = {'C4': cyc(4), 'C5': cyc(5), 'K4': [(a, b) for a in range(4) for b in range(a)],
         'W4': cyc(4) + [(i, 4) for i in range(4)], 'path5': [(i, i + 1) for i in range(4)]}
for name, edges in tests.items():
    V, E = graph(edges)
    p = P(V, E)
    val = lambda k: sum(c * k ** i for i, c in enumerate(p))
    same = all(val(k) == brute(V, E, k) for k in range(1, 5))
    chi = next(k for k in range(1, 9) if val(k) > 0)
    print(f"{name:5} coeffs={p[::-1]} P(3)={val(3)} chi={chi} brute ok={same}")

C4    coeffs=[1, -4, 6, -3, 0] P(3)=18 chi=2 brute ok=True
C5    coeffs=[1, -5, 10, -10, 4, 0] P(3)=30 chi=3 brute ok=True
K4    coeffs=[1, -6, 11, -6, 0] P(3)=0 chi=4 brute ok=True
W4    coeffs=[1, -8, 24, -31, 14, 0] P(3)=6 chi=3 brute ok=True
path5 coeffs=[1, -4, 6, -4, 1, 0] P(3)=48 chi=2 brute ok=True

৮ · গণনার কঠিনতা, এক নজরে তুলনা আর পরীক্ষার প্রশ্ন

“G কি 2-colourable?” প্রশ্নটি সহজ: BFS দিয়ে স্তরে স্তরে পর্যায়ক্রমে রং দিন, কোথাও দুই প্রতিবেশী একই রং পেলে একটি odd cycle পাওয়া যায় (পর্ব ৫৭; DSA কোর্সের পর্ব ৩৯)। কিন্তু “G কি 3-colourable?” প্রশ্নটি NP-complete. Richard Karp-এর ১৯৭২ সালের তালিকায় chromatic number-এর সিদ্ধান্ত-প্রশ্ন ছিল, আর 3-colouring-এর NP-completeness Larry Stockmeyer (১৯৭৩) দেখান বলে জানা যায়; এমনকি planar, সর্বোচ্চ degree 4-এর graph-এও প্রশ্নটি NP-complete থাকে (Garey, Johnson ও Stockmeyer, ১৯৭৬, বলে উল্লেখ করা হয়)। মজার বৈপরীত্য: planar graph-এ “৪ রঙে হয় কি?” প্রশ্নের উত্তর সবসময় হ্যাঁ (চার রঙের উপপাদ্য), “২ রঙে?” সহজ, আর মাঝের “৩ রঙে?” কঠিন। তাই χ বের করাও NP-hard (DSA কোর্সের পর্ব ৬৪), আর χ-এর কাছাকাছি অনুমানও সাধারণভাবে কঠিন বলে প্রমাণিত। নির্ভুল χ-এর জন্য সবচেয়ে দ্রুত জানা পদ্ধতিগুলোর একটি পর্ব ৪৯-এর inclusion–exclusion দিয়ে প্রায় 2ⁿ সময়ে চলে; বাস্তবের বড় রুটিনে heuristic আর local search ব্যবহার হয় (DSA কোর্সের পর্ব ৬৫)।

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

Graph colouring-এর প্রশ্নে AI সহকারী দ্রুত কোড লেখে, কিন্তু প্রমাণে, শর্তে আর ইতিহাসে আত্মবিশ্বাসী ভুল করে। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

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

• দেওয়া colouring-এর প্রতিটি edge-এ দুই প্রান্তের রং আলাদা কি না নিজে দেখেছি
• নিচের সীমার যুক্তি (clique, odd cycle, n/α) আলাদা করে আছে
• ব্যবহৃত প্রতিটি উপপাদ্যের শর্ত (planar, connected, complete নয়) মিলিয়েছি
• Induction-এ ছোট graph-টি সত্যিই একই শ্রেণির (যেমন planar) কি না দেখেছি
• Polynomial-এর মান ছোট k-তে brute force গণনার সঙ্গে মিলিয়েছি
• Greedy-র দাবি একটি খারাপ ক্রমে (crown graph) পরীক্ষা করেছি
• উদ্ধৃত নাম আর সাল বিশ্বস্ত উৎসে মিলিয়েছি