পাঠ ২১ · ৪৪-এর মধ্যে · মডিউল ৪
Home / Courses / Discrete Mathematics / ট্রি ও স্প্যানিং ট্রি

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

Trees & spanning trees
৮ মিনিট পড়া শুরু · Beginner Python কোডসহ সম্পূর্ণ বাংলায়

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

  • Tree-এর গাণিতিক সংজ্ঞা এবং $n-1$ edge উপপাদ্য
  • Tree-এর তিনটি মূল বৈশিষ্ট্য — edge যোগ করলে cycle, edge সরালে বিচ্ছিন্নতা
  • Rooted tree পরিভাষা — root, parent/child, leaf, height, depth
  • Spanning tree ও Minimum Spanning Tree (MST)-এর সংজ্ঞা
  • Python-এ একটি হাতে-তৈরি tree-তে $n-1$ edge শর্ত যাচাই

১ · Tree কী?

একটি treeTreeএকটি connected (সংযুক্ত) এবং acyclic (কোনো cycle নেই) গ্রাফ — গ্রাফ থিওরির সবচেয়ে গুরুত্বপূর্ণ বিশেষ কাঠামোগুলোর একটি। হলো এমন একটি গ্রাফ যা connected (L19 দ্রষ্টব্য — প্রতিটি জোড়া vertex-এর মধ্যে path আছে) এবং acyclic (কোনো cycle নেই — কোনো vertex থেকে শুরু করে ঘুরে আবার সেই vertex-এ ফিরে আসার কোনো path নেই)।

মূল সূত্র — $n-1$ Edge

$n$টি vertex-বিশিষ্ট একটি tree-তে ঠিক $n-1$টি edge থাকে — এর বেশিও না, কমও না। সংক্ষিপ্ত ইনডাকশন-যুক্তি (L06 দ্রষ্টব্য): base case $n=1$-এ কোনো edge নেই ($1-1=0$ ✓)। ইনডাক্টিভ ধাপ — একটি $k$-vertex tree-তে $k-1$টি edge থাকলে, একটি নতুন leaf vertex যোগ করলে (যা ঠিক একটি existing vertex-এর সাথে যুক্ত হয়, নতুন কোনো cycle না বানিয়ে) মোট vertex হয় $k+1$ এবং edge হয় $(k-1)+1=k=(k+1)-1$ ✓ — সূত্রটি বজায় থাকে।

এই সংজ্ঞা থেকে সরাসরি আরও দুটি গুরুত্বপূর্ণ বৈশিষ্ট্য বেরিয়ে আসে —

নতুন edge → ঠিক একটি cycle
যেকোনো দুটি vertex $u,v$-এর মধ্যে tree-তে ইতিমধ্যেই একটি অদ্বিতীয় (unique) path আছে। সরাসরি $u$-$v$ edge যোগ করলে সেই path-টি বন্ধ হয়ে ঠিক একটি cycle তৈরি হয় — আর কোনো নতুন cycle নয়, কারণ অন্য কোনো বিকল্প path ছিল না।
Edge সরালে বিচ্ছিন্নতা
একটি tree-তে দুটি vertex-এর মধ্যে সংযোগের একমাত্র মাধ্যম তাদের unique path — কোনো বিকল্প (redundant) path নেই। তাই সেই path-এর যেকোনো একটি edge সরালে গ্রাফটি দুই ভাগে বিচ্ছিন্ন হয়ে যায়।
Rooted tree পরিভাষা — একটি tree-কে একটি নির্দিষ্ট vertex-কে root ধরে "উপর থেকে নিচে" সাজানো যায়। তখন প্রতিটি vertex-এর একটি parent (উপরের প্রতিবেশী) ও শূন্য বা একাধিক child (নিচের প্রতিবেশী) থাকে; child-বিহীন vertex-কে বলা হয় leaf। root থেকে কোনো vertex-এর দূরত্বকে বলা হয় তার depth, আর সবচেয়ে দূরের leaf-এর depth-কে বলা হয় tree-এর height। এই পরিভাষাগুলোর সম্পূর্ণ বাস্তবায়ন (binary tree, BST ইত্যাদি) DSA কোর্সে বিস্তারিত কভার হয় — এখানে আমরা শুধু গ্রাফ-থিওরিটিক ভিত্তিটুকু দেখছি।
Python
tree = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B"],
    "F": ["C"],
}

vertices = list(tree.keys())
edge_count = sum(len(neighbors) for neighbors in tree.values()) // 2
print("Vertex সংখ্যা (n):", len(vertices))
print("Edge সংখ্যা:", edge_count)
print("n-1 edge শর্ত মিলছে?", edge_count == len(vertices) - 1)

    


    
২ · Spanning Tree

    

      একটি connected গ্রাফ $G$-এর
      spanning treeSpanning Treeএকটি connected গ্রাফ $G$-এর উপ-গ্রাফ যা নিজে একটি tree, এবং $G$-এর প্রতিটি vertex ধারণ করে (কিন্তু সব edge নয়)।
      হলো $G$-এরই একটি উপ-গ্রাফ যা (ক) নিজে একটি tree, এবং (খ) $G$-এর সবকটি vertex ধারণ করে (কিন্তু $G$-এর সব edge রাখার দরকার নেই, বরং cycle তৈরি করে এমন অতিরিক্ত edge বাদ দেওয়া হয়)।
    

    

      প্রতিটি connected গ্রাফের অন্তত একটি spanning tree থাকে — সহজভাবে বলতে গেলে, যতক্ষণ গ্রাফে কোনো cycle থাকে, সেই cycle-এর যেকোনো একটি edge সরিয়ে ফেললেও গ্রাফ connected থেকে যায় (কারণ cycle-এর বাকি অংশ দিয়ে বিকল্প path থাকে); এই প্রক্রিয়া বারবার চালিয়ে সব cycle দূর করলে যা অবশিষ্ট থাকে তা-ই একটি spanning tree।
    


    

      Minimum Spanning Tree (MST)
      

        যদি গ্রাফের প্রতিটি edge-এর একটি ওজন (weight) থাকে (যেমন দুটি শহরের মধ্যে দূরত্ব), তাহলে একাধিক ভিন্ন spanning tree সম্ভব হতে পারে, প্রতিটির মোট ওজন ভিন্ন। যে spanning tree-এর মোট edge-ওজনের যোগফল সবচেয়ে কম, তাকে বলা হয় Minimum Spanning Tree (MST)। বাস্তবে network design (যেমন সর্বনিম্ন খরচে সব শহরকে সংযুক্ত করা) এর সরাসরি প্রয়োগ। Kruskal's ও Prim's অ্যালগরিদম MST বের করার জন্য ব্যবহৃত হয় — এদের সম্পূর্ণ বাস্তবায়ন ও জটিলতা বিশ্লেষণ DSA কোর্সের বিষয়।
      

    


  


  

    
    
  


  

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

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


    

      
        প্র ০১
        একটি tree-তে নতুন edge যোগ করলে কেন ঠিক একটি cycle তৈরি হয় — একাধিক নয় কেন?
      
      

        

          একটি tree-তে যেকোনো দুই vertex $u,v$-এর মধ্যে একটি অদ্বিতীয় (unique) path থাকে — যদি একাধিক ভিন্ন path থাকত, সেগুলো মিলে একটি cycle তৈরি করত, যা tree-এর acyclic শর্ত ভঙ্গ করত। যখন আমরা সরাসরি $u$-$v$ edge যোগ করি, এটি সেই একমাত্র বিদ্যমান path-এর সাথে মিলে ঠিক একটি নতুন cycle তৈরি করে — এর বাইরে আর কোনো বিকল্প path না থাকায় দ্বিতীয় কোনো cycle তৈরি হওয়ার সুযোগ নেই।
        

      

    


    

      
        প্র ০২
        একটি সাধারণ (tree নয় এমন, cycle-যুক্ত) connected গ্রাফ থেকে একটি edge সরালে কি গ্রাফটি সবসময় বিচ্ছিন্ন হয়ে যাবে?
      
      

        

          না — এটাই tree ও সাধারণ গ্রাফের মধ্যে একটি মূল পার্থক্য। যদি সরানো edge-টি কোনো cycle-এর অংশ হয়, তাহলে সেই cycle-এর বাকি অংশ দিয়ে এখনো একটি বিকল্প path থাকে, তাই গ্রাফ connected-ই থেকে যায়। কিন্তু tree-তে যেহেতু কোনো cycle নেই (তাই কোনো "বিকল্প path" নেই), প্রতিটি edge-ই একমাত্র সংযোগ — তাই tree-তে যেকোনো edge সরালেই বিচ্ছিন্নতা নিশ্চিত। এই পার্থক্যটিই স্প্যানিং ট্রি তৈরির মূল ধারণা — cycle-এর "অতিরিক্ত" edge বাদ দিলে গ্রাফ এখনো connected থাকে।
        

      

    


    

      
        প্র ০৩
        একটি connected গ্রাফে $|E|$টি edge ও $|V|$টি vertex থাকলে, একটি spanning tree তৈরি করতে ঠিক কতগুলো edge বাদ দিতে হবে?
      
      

        

          একটি spanning tree-তে (এটিও একটি tree হওয়ায়) ঠিক $|V|-1$টি edge থাকবে। তাই মূল গ্রাফ থেকে বাদ দিতে হবে $|E| - (|V|-1)$টি edge — এই সংখ্যাটিকে গ্রাফের circuit rank বা cyclomatic numberও বলা হয়, যা মূলত গ্রাফে "স্বাধীন" cycle-এর সংখ্যা নির্দেশ করে। উদাহরণ — $K_4$ (৪-vertex complete graph)-এ $|E|=\binom{4}{2}=6$, তাই spanning tree তৈরি করতে $6-(4-1)=3$টি edge বাদ দিতে হবে।
        

      

    

  


  

    
 অনুশীলন

    
    
      
  1. 
        হাতে করুন: একটি সাইকেল গ্রাফ $C_5$ (৫টি vertex, একটি বৃত্তাকার শৃঙ্খল A-B-C-D-E-A)-কে একটি spanning tree-তে রূপান্তর করতে কোন এক-টি edge বাদ দিতে হবে? বাদ দেওয়ার পর কতগুলো edge অবশিষ্ট থাকবে?
        
    
          
          
    
            
    
              $C_5$-এ ৫টি edge আছে (A-B, B-C, C-D, D-E, E-A)। যেকোনো একটি edge বাদ দিলেই (যেমন E-A) বাকি ৪টি edge একটি path $P_5$ তৈরি করবে যা এখনো সব ৫টি vertex-কে সংযুক্ত রাখে এবং কোনো cycle নেই — এটিই একটি বৈধ spanning tree, যেখানে edge সংখ্যা $5-1=4$, সূত্রের সাথে মিলে যায়।
            
    
          
    
        
    
      
    2. 
      
  2. 
        পরীক্ষা করুন: উপরের কোড সেলে tree-এ D-এর সাথে একটি নতুন child "G" যোগ করুন ("D": ["B", "G"], এবং নতুন এন্ট্রি "G": ["D"])। নতুন vertex ও edge সংখ্যা কী হবে এবং $n-1$ শর্ত এখনো মিলবে কিনা যাচাই করুন।
        
    
          
          
    
            
    
              নতুন vertex সংখ্যা $n=7$ (A,B,C,D,E,F,G)। নতুন edge সংখ্যা $6$ (আগের ৫টি + D-G)। যাচাই: $6 = 7-1$ ✓ — শর্তটি এখনো মিলছে, কারণ একটি leaf যোগ করা tree-এর গঠন অক্ষুণ্ণ রাখে (কোনো cycle তৈরি হয়নি, connectivity-ও অক্ষুণ্ণ)।
            
    
          
    
        
    
      
    3. 
    

  


  

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

    
  







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





  
    
 আগের পাঠ

    
ইউলারিয়ান ও হ্যামিলটোনিয়ান পথ