পাঠ ২২ · ৪৪-এর মধ্যে · মডিউল ৪
Home / Courses / Discrete Mathematics / গ্রাফ কালারিং

গ্রাফ কালারিং ও ক্রোমাটিক নাম্বার

Graph coloring & chromatic number
৮ মিনিট পড়া শুরু · Beginner Python কোডসহ সম্পূর্ণ বাংলায়

এই পাঠে যা শিখবেন

  • Proper coloring ও ক্রোমাটিক নাম্বার $\chi(G)$-এর সংজ্ঞা
  • $\chi(K_n)=n$ এবং $\chi(C_n)$-এর জোড়/বিজোড় নিয়মের সম্পূর্ণ ব্যাখ্যা
  • Bipartite গ্রাফের সাথে ২-রঙা হওয়ার সম্পর্ক
  • Four Color Theorem-এর বিবৃতি ও বাস্তব প্রয়োগ (মানচিত্র রঙ করা)
  • Python-এ একটি greedy coloring অ্যালগরিদম বাস্তবায়ন

১ · Proper Coloring ও ক্রোমাটিক নাম্বার

একটি proper coloringProper Coloringএকটি গ্রাফের vertex-গুলোতে রং বসানোর এমন একটি পদ্ধতি যেখানে কোনো দুটি সংলগ্ন (edge দ্বারা যুক্ত) vertex একই রং পায় না। হলো গ্রাফের প্রতিটি vertex-এ এমনভাবে রং বসানো যাতে কোনো দুটি সংলগ্ন vertex একই রং না পায়। একটি গ্রাফের ক্রোমাটিক নাম্বার (χ)Chromatic Number, χ(G)একটি proper coloring তৈরি করতে ন্যূনতম যে সংখ্যক রং প্রয়োজন।, লেখা হয় $\chi(G)$, হলো একটি proper coloring তৈরি করতে ন্যূনতম প্রয়োজনীয় রং সংখ্যা।

Worked example ১ — Complete Graph $K_n$

$K_n$-এ প্রতিটি vertex বাকি সব $n-1$টি vertex-এর প্রতিবেশী (L18 দ্রষ্টব্য)। তাই যেকোনো দুটি vertex-ই সংলগ্ন — অর্থাৎ প্রতিটি vertex-কে অবশ্যই একে অপরের থেকে আলাদা রং পেতে হবে। ফলে $\chi(K_n) = n$ — এর কম রং দিয়ে কোনোভাবেই proper coloring সম্ভব নয়।

Worked example ২ — Cycle $C_n$

একটি cycle $C_n$-এ চেষ্টা করা যাক শুধু ২টি রং (1, 2) দিয়ে পালাক্রমে (alternate) রং করতে। যদি $n$ জোড় হয় (যেমন $C_4$: 1,2,1,2), তাহলে শেষ vertex ও প্রথম vertex-এর মধ্যেও রং আলাদা থাকে — সফলভাবে ২-রঙা হয়ে যায়, তাই $\chi(C_n)=2$।

কিন্তু $n$ বিজোড় হলে (যেমন $C_5$: 1,2,1,2,1), শেষ vertex (৫ম) রং পায় 1 — কিন্তু এটি প্রথম vertex-এর (যেও রং 1) সাথেও সংলগ্ন (cycle বন্ধ হয় সেখানে)! তাই দুটি ২-রঙা প্রচেষ্টা সবসময় এই "শেষ edge"-এ সংঘর্ষে পড়ে, এবং একটি তৃতীয় রং লাগে। তাই $\chi(C_n) = 3$ যখন $n$ বিজোড়।

সাধারণীকরণ — একটি bipartite graph (L18 দ্রষ্টব্য) ঠিক তখনই ২-রঙা করা যায় ($\chi(G)=2$) যখন গ্রাফে কোনো বিজোড়-দৈর্ঘ্যের cycle না থাকে। এটাই bipartite graph-এর একটি বিকল্প, সমতুল্য সংজ্ঞা — দুই দলে vertex ভাগ করা যাওয়া ঠিক তখনই সম্ভব যখন কোনো বিজোড় cycle এই ভাগকে "ভেঙে" না দেয়।

২ · Four Color Theorem

একটি বিখ্যাত ফলাফল, Four Color Theorem বলে — যেকোনো planar গ্রাফ (L23-এ যার সংজ্ঞা দেখব — এমন গ্রাফ যা কোনো edge ক্রস না করে সমতলে আঁকা যায়) সর্বদা মাত্র ৪টি রং দিয়ে proper coloring করা সম্ভব। এই উপপাদ্যটি ১৯৭৬ সালে কম্পিউটার-সহায়তায় প্রমাণিত হয়েছিল (হাজার হাজার আলাদা case কম্পিউটার দিয়ে যাচাই করে) — গণিতের ইতিহাসে কম্পিউটার-নির্ভর প্রথম বড় প্রমাণগুলোর একটি।

বাস্তব প্রয়োগ — মানচিত্রে (map) পাশাপাশি অঞ্চলগুলো (যেমন দেশ বা রাজ্য) একই রং না পাওয়া নিশ্চিত করতে সবসময় ৪টি রং-ই যথেষ্ট, চাই যত জটিলই মানচিত্র হোক না কেন।

Python
def greedy_coloring(graph, order):
    colors = {}
    for v in order:
        used = {colors[n] for n in graph[v] if n in colors}
        color = 0
        while color in used:
            color += 1
        colors[v] = color
    return colors

# A-B-C একটি ত্রিভুজ (triangle), D শুধু B ও C-এর সাথে সংযুক্ত
graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D"],
    "D": ["B", "C"],
}
order = ["A", "B", "C", "D"]
coloring = greedy_coloring(graph, order)

for v in order:
    print(f"{v} → রং {coloring[v]}")
print("ব্যবহৃত মোট রং সংখ্যা:", len(set(coloring.values())))

    


    

      এই কোডে A, B, C একটি triangle ($K_3$) তৈরি করে, যার জন্য অন্তত ৩টি রং লাগবেই ($\chi(K_3)=3$)। Greedy অ্যালগরিদম প্রতিটি vertex-কে ইতিমধ্যে-রং-করা প্রতিবেশীদের এড়িয়ে সবচেয়ে ছোট উপলব্ধ রং নম্বর দেয় — এখানে এটি ঠিক ৩টি রং ব্যবহার করবে (0, 1, 2), যা optimal। তবে মনে রাখা জরুরি — greedy সবসময় ন্যূনতম রং সংখ্যা দেয় না; ফলাফল vertex পরীক্ষা করার ক্রম (order)-এর উপর নির্ভরশীল, তাই এটি একটি দ্রুত কিন্তু আনুমানিক (heuristic) পদ্ধতি।
    


  


  

    
    
  


  

    
 ভাবনার প্রশ্ন

    
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।


    

      
        প্র ০১
        $\chi(K_n)=n$ প্রমাণে কেন বলা যায় $n$-এর কম রং দিয়ে কখনোই কাজ চলবে না?
      
      

        

          $K_n$-এ যেকোনো দুটি ভিন্ন vertex সরাসরি সংলগ্ন — অর্থাৎ কোনো দুটি vertex-ই একই রং পেতে পারে না (proper coloring-এর শর্ত ভঙ্গ হবে)। এর মানে $n$টি vertex-এর প্রতিটির জন্য একটি করে স্বতন্ত্র রং লাগবে — কবুতরের-খোপ নীতির (pigeonhole, L15) বিপরীত যুক্তি: যদি $n$-এর কম রং ব্যবহার করা হয়, তাহলে অন্তত দুটি vertex একই রং পেতে বাধ্য হবে, কিন্তু তারা সংলগ্ন হওয়ায় এটি অবৈধ। তাই ঠিক $n$টি রং-ই প্রয়োজনীয় ন্যূনতম।
        

      

    


    

      
        প্র ০২
        কেন একটি বিজোড়-দৈর্ঘ্যের cycle কখনো ২টি রং দিয়ে coloring করা সম্ভব নয় — শুধু "একবার চেষ্টা করে দেখলে চলে না" ধরনের ব্যাখ্যার বাইরে একটি যুক্তিসঙ্গত (general) কারণ কী?
      
      

        

          ২টি রং দিয়ে coloring মানেই গ্রাফটিকে দুটি দলে ভাগ করা (প্রতিটি রঙের জন্য একটি দল) যেখানে edge শুধু ভিন্ন দলের মধ্যে থাকে — এটাই bipartite-এর সংজ্ঞা। একটি cycle-এ ক্রমান্বয়ে vertex-গুলো ঘুরে আসতে আসতে দল পরিবর্তন হতে থাকে (1,2,1,2,...); $n$ ধাপ পর শুরুর vertex-এ ফিরে আসতে হলে, দল পরিবর্তনের সংখ্যা (যা $n$-এর সমান) জোড় হতে হবে যাতে শেষ vertex আবার প্রথম দলে ফিরে আসে ও প্রথম vertex-এর সাথে সামঞ্জস্যপূর্ণ থাকে। $n$ বিজোড় হলে এই "ফিরে আসা" ব্যর্থ হয় — শেষ vertex ভুল দলে পড়ে যায়, তাই ২-কালারিং কাঠামোগতভাবেই অসম্ভব হয়ে পড়ে।
        

      

    


    

      
        প্র ০৩
        Four Color Theorem কি বলে যে যেকোনো গ্রাফ ৪ রঙে রঙিন করা যায়, নাকি শুধু নির্দিষ্ট ধরনের গ্রাফের জন্য প্রযোজ্য?
      
      

        

          শুধু planar গ্রাফের জন্য প্রযোজ্য — L23-এ আমরা দেখব planar graph মানে এমন গ্রাফ যা কোনো edge অন্য edge-কে ক্রস না করে সমতলে আঁকা যায়। সাধারণ (non-planar) গ্রাফের ক্রোমাটিক নাম্বার সীমাহীন হতে পারে — যেমন $K_{100}$-এর জন্য $\chi(K_{100})=100$, কারণ এটি planar নয় (L23-এ $K_5$-এর non-planarity প্রমাণ দেখব, বড় $K_n$-এর ক্ষেত্রেও একই যুক্তি প্রযোজ্য)। মানচিত্র সবসময় planar গ্রাফ হিসেবে মডেল করা যায় (কোনো দুটি অঞ্চলের সীমানা একে অপরকে "ক্রস" করে না), তাই মানচিত্র রঙ করার বাস্তব সমস্যায় Four Color Theorem সরাসরি প্রযোজ্য।
        

      

    

  


  

    
 অনুশীলন

    
    
      
  1. 
        হাতে করুন: $C_6$ (৬-vertex cycle) ও $C_7$ (৭-vertex cycle)-এর ক্রোমাটিক নাম্বার কত হবে?
        
    
          
          
    
            
    
              $\chi(C_6)=2$ (৬ জোড় সংখ্যা, তাই ২ রং দিয়ে alternate করা সম্ভব: 1,2,1,2,1,2)। $\chi(C_7)=3$ (৭ বিজোড় সংখ্যা, শেষ vertex প্রথম vertex-এর সাথে সংঘর্ষে পড়ে, তৃতীয় রং লাগে)।
            
    
          
    
        
    
      
    2. 
      
  2. 
        পরীক্ষা করুন: উপরের কোড সেলে order-কে ["D", "B", "C", "A"]-তে বদলান (একই graph, ভিন্ন ক্রম)। ফলাফলের রং সংখ্যা কি বদলাবে?
        
    
          
          
    
            
    
              না, এই নির্দিষ্ট গ্রাফে মোট রং সংখ্যা তখনও ৩-ই থাকবে (D=0, B=1, C=2, A=2 — কারণ A শুধু B ও C-এর প্রতিবেশী, D-এর নয়), কারণ A-B-C triangle-টি যেকোনো ক্রমেই কমপক্ষে ৩টি রং দাবি করে। তবে সাধারণভাবে অন্য গ্রাফে vertex-ক্রম বদলালে greedy অ্যালগরিদমের ব্যবহৃত মোট রং সংখ্যা বদলে যেতে পারে — এটিই greedy পদ্ধতির একটি সীমাবদ্ধতা।
            
    
          
    
        
    
      
    3. 
    

  


  

    
 আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

    
  







  
  
     এই পাঠে ভুল পেয়েছেন? জানান
  





  
    
 আগের পাঠ

    
ট্রি ও স্প্যানিং ট্রি