পাঠ ১৮ · ৪৪-এর মধ্যে · মডিউল ৪
Home / Courses / Discrete Mathematics / গ্রাফের সংজ্ঞা

গ্রাফ — সংজ্ঞা, টার্মিনোলজি ও প্রকারভেদ

Graphs — definitions, terminology & types
৮ মিনিট পড়া শুরু · Beginner Python কোডসহ সম্পূর্ণ বাংলায়

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

  • গ্রাফের আনুষ্ঠানিক সংজ্ঞা এবং vertex/edge পরিভাষা
  • Undirected বনাম directed গ্রাফ, simple graph বনাম multigraph
  • Degree ও Handshake theorem — এবং তার প্রমাণ ও corollary
  • $K_n$, $C_n$, $P_n$, bipartite ও $K_{m,n}$ — এই কোর্সে বারবার ব্যবহৃত বিশেষ গ্রাফ প্রকার
  • Python-এ adjacency dict দিয়ে degree গণনা ও Handshake theorem যাচাই

১ · গ্রাফ কী?

একটি গ্রাফ (Graph)Graphএকটি গাণিতিক কাঠামো $G=(V,E)$ — vertex (নোড)-এর একটি সেট $V$ এবং edge (সংযোগ)-এর একটি সেট $E$, যেখানে প্রতিটি edge দুটি vertex-কে যুক্ত করে। হলো $G=(V,E)$ — এখানে $V$ হলো vertex/nodeVertex (বহুবচনে vertices)গ্রাফের একটি বিন্দু বা নোড — একটি বস্তু, ব্যক্তি, শহর, বা যেকোনো সত্তা যাকে গ্রাফে উপস্থাপন করা হয়।-এর সেট, আর $E$ হলো edgeEdgeদুটি vertex-এর মধ্যে একটি সংযোগ — একটি জোড়া $(u,v)$ যেখানে $u,v \in V$।-এর সেট, যেখানে প্রতিটি edge দুটি vertex-কে সংযুক্ত করে। উদাহরণ — একটি সোশ্যাল নেটওয়ার্কে প্রতিটি ব্যবহারকারী একটি vertex, আর দুজনের বন্ধুত্ব একটি edge।

গ্রাফ দুই ধরনের হতে পারে। Undirected graph-এ একটি edge $(u,v)$ দুই দিকেই কাজ করে — Facebook-এর বন্ধুত্ব undirected (দুজনেই একে অপরের বন্ধু)। Directed graph (digraph)-এ প্রতিটি edge-এর একটি নির্দিষ্ট দিক থাকে — Twitter/X-এর "ফলো" সম্পর্ক directed (আপনি কাউকে ফলো করলে সে আপনাকে ফলো করে তা জরুরি নয়)।

Simple graph বনাম Multigraph

একটি simple graph-এ কোনো self-loop (একই vertex-এর সাথে নিজের edge) থাকে না, এবং দুটি vertex-এর মধ্যে সর্বোচ্চ একটি edge থাকে। এই কোর্সে আমরা মূলত simple graph নিয়ে কাজ করব। যদি একাধিক edge বা loop অনুমোদিত হয়, তাকে বলা হয় multigraph।

২ · Degree ও Handshake Theorem

একটি vertex $v$-এর degreeDegree, deg(v)একটি vertex-এর সাথে সংযুক্ত edge-এর সংখ্যা। Handshake theorem অনুযায়ী সকল vertex-এর ডিগ্রির যোগফল সবসময় edge সংখ্যার দ্বিগুণ।, লেখা হয় $\deg(v)$, হলো তার সাথে সংযুক্ত edge-এর সংখ্যা। উদাহরণস্বরূপ, নিচের ৩ নং সেকশনের গ্রাফে vertex B-এর সাথে তিনটি edge যুক্ত, তাই $\deg(B)=3$।

Handshake Theorem

যেকোনো গ্রাফের জন্য $$\sum_{v \in V} \deg(v) = 2|E|$$ কারণ প্রতিটি edge-এর ঠিক দুটি প্রান্তবিন্দু (endpoint) থাকে — তাই যখন আমরা প্রতিটি vertex-এর ডিগ্রি গুনি, প্রতিটি edge দুইবার গোনা হয় (একবার তার প্রতিটি প্রান্তের জন্য)। ফলে মোট যোগফল সবসময় edge সংখ্যার ঠিক দ্বিগুণ।

Corollary: যেহেতু $2|E|$ সবসময় জোড় সংখ্যা, তাই যেকোনো গ্রাফে বিজোড় ডিগ্রি-বিশিষ্ট vertex-এর সংখ্যা সবসময় জোড় হতে বাধ্য — কারণ জোড়-ডিগ্রি vertex-গুলোর যোগফল এমনিতেই জোড়, তাই বিজোড়-ডিগ্রি vertex-গুলোর যোগফলও জোড় হতে হবে, আর জোড় সংখ্যক বিজোড় পদের যোগফলই কেবল জোড় হতে পারে।

A deg = 2 B deg = 3 C deg = 2 D deg = 2 E deg = 1
৫টি vertex, ৫টি edge — ডিগ্রির যোগফল $2+3+2+2+1=10=2\times5$, Handshake theorem যাচাই হলো।
Python
graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B"],
    "D": ["B", "E"],
    "E": ["D"],
}

degrees = {v: len(neighbors) for v, neighbors in graph.items()}
for v, d in degrees.items():
    print(f"deg({v}) = {d}")

total_degree = sum(degrees.values())
edge_count = sum(len(n) for n in graph.values()) // 2
print("মোট ডিগ্রি যোগফল:", total_degree)
print("এজ সংখ্যা |E|:", edge_count)
print("Handshake theorem (Σdeg == 2|E|)?", total_degree == 2 * edge_count)

    


    
৩ · বিশেষ গ্রাফ প্রকার

    

      কিছু নির্দিষ্ট গ্রাফ-গঠন এত বেশি ব্যবহৃত হয় যে তাদের আলাদা নাম আছে — এই কোর্সের বাকি পাঠগুলোতে (বিশেষত L20-L23) এগুলো বারবার ফিরে আসবে।
    


    

      
Complete graph $K_n$
প্রতিটি জোড়া vertex সরাসরি সংযুক্ত। মোট edge সংখ্যা $|E| = \binom{n}{2} = \frac{n(n-1)}{2}$।

      
Cycle $C_n$
$n$টি vertex একটি বৃত্তাকার শৃঙ্খলে যুক্ত — প্রতিটির ডিগ্রি ঠিক ২।

      
Path $P_n$
$n$টি vertex একটি সরলরেখায় যুক্ত — দুই প্রান্তের ডিগ্রি ১, বাকিদের ডিগ্রি ২।

      
Bipartite graph
vertex-গুলো দুটি দলে ভাগ করা যায় এমনভাবে যে edge শুধু দুই দলের মধ্যে থাকে, একই দলের ভেতরে নয়।

      
Complete bipartite $K_{m,n}$
দুই দলের সাইজ $m$ ও $n$; প্রথম দলের প্রতিটি vertex দ্বিতীয় দলের সবগুলোর সাথে সংযুক্ত — মোট $|E|=m \times n$।

    


    

      উদাহরণ — $K_5$ (৫টি vertex-বিশিষ্ট complete graph)-এ edge সংখ্যা $\binom{5}{2} = \frac{5 \times 4}{2} = 10$। L23-এ আমরা দেখব ঠিক এই $K_5$ গ্রাফটিই একটি বিখ্যাত non-planar গ্রাফের উদাহরণ।
    


  


  

    
    
  


  

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

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


    

      
        প্র ০১
        Handshake theorem থেকে কেন এই সিদ্ধান্তে আসা যায় যে যেকোনো গ্রাফে বিজোড়-ডিগ্রি vertex-এর সংখ্যা সবসময় জোড়?
      
      

        

          মূল উত্তর। Handshake theorem বলে $\sum \deg(v) = 2|E|$, যা সবসময় একটি জোড় সংখ্যা। এখন সব vertex-কে দুই দলে ভাগ করুন — জোড়-ডিগ্রি vertex ও বিজোড়-ডিগ্রি vertex। জোড়-ডিগ্রি vertex-গুলোর যোগফল স্বতঃসিদ্ধভাবেই জোড় (জোড় সংখ্যার যোগফল সবসময় জোড়)।
        

        

          যেহেতু সম্পূর্ণ যোগফল ($2|E|$) জোড়, এবং একটি অংশ (জোড়-ডিগ্রি vertex-গুলোর যোগফল) জোড়, তাই বাকি অংশ (বিজোড়-ডিগ্রি vertex-গুলোর যোগফল)-ও জোড় হতে হবে। কিন্তু বিজোড় সংখ্যার যোগফল তখনই জোড় হয় যখন ঠিক জোড় সংখ্যক পদ যোগ করা হয় — তাই বিজোড়-ডিগ্রি vertex-এর সংখ্যা অবশ্যই জোড়।
        

      

    


    

      
        প্র ০২
        Directed graph (digraph)-এ "degree" ধারণাটি কীভাবে বদলে যায়?
      
      

        

          একটি directed graph-এ প্রতিটি edge-এর একটি নির্দিষ্ট দিক থাকে, তাই একক "degree"-এর বদলে দুটি আলাদা সংখ্যা লাগে — in-degree (কতগুলো edge ওই vertex-এর দিকে ঢুকছে) এবং out-degree (কতগুলো edge ওই vertex থেকে বের হচ্ছে)। প্রতিটি edge ঠিক একটি vertex-এর out-degree এবং ঠিক একটি vertex-এর in-degree-তে অবদান রাখে, তাই একটি digraph-এ সব vertex-এর in-degree-এর যোগফল = সব vertex-এর out-degree-এর যোগফল = মোট edge সংখ্যা $|E|$ (২ গুণ নয়, কারণ প্রতিটি edge এখানে শুধু একবারই "গণনা" হচ্ছে, দুই ভিন্ন হিসাবে ভাগ হয়ে)।
        

      

    


    

      
        প্র ০৩
        Complete bipartite graph $K_{m,n}$-এ edge সংখ্যা $m \times n$ কেন — Complete graph $K_n$-এর $\binom{n}{2}$ সূত্রের সাথে এর পার্থক্য কী?
      
      

        

          $K_{m,n}$-এ প্রথম দলের প্রতিটি vertex দ্বিতীয় দলের প্রতিটি vertex-এর সাথে ঠিক একবার সংযুক্ত, আর একই দলের ভেতরে কোনো edge নেই। তাই প্রথম দলের $m$টি vertex-এর প্রতিটির জন্য $n$টি সম্ভাব্য সংযোগ — মোট $m \times n$টি edge, product rule-এর সরাসরি প্রয়োগ (L12 দ্রষ্টব্য)।
        

        

          $K_n$-এর ক্ষেত্রে সব vertex একই দলে, তাই প্রতিটি জোড়ার মধ্যে edge সম্ভব — যা $\binom{n}{2}$ (order গুরুত্বপূর্ণ নয় এমন জোড়া বাছাই, L14 দ্রষ্টব্য)। বিপরীতে $K_{m,n}$-এ শুধু আন্তঃ-দলীয় জোড়াই গোনা হয়, একই দলের অভ্যন্তরীণ জোড়া নয়।
        

      

    

  


  

    
 অনুশীলন

    
    
      
  1. 
        হাতে করুন: একটি ৪-vertex গ্রাফ কল্পনা করুন যেখানে vertex-গুলো {P, Q, R, S} এবং edge-গুলো {P-Q, Q-R, R-S, S-P, P-R}। প্রতিটি vertex-এর degree বের করুন এবং Handshake theorem দিয়ে যাচাই করুন।
        
    
          
          
    
            
    
              $\deg(P)=3$ (Q, S, R), $\deg(Q)=2$ (P, R), $\deg(R)=3$ (Q, S, P), $\deg(S)=2$ (R, P)। যোগফল $=3+2+3+2=10$। এজ সংখ্যা $|E|=5$, তাই $2|E|=10$ — Handshake theorem মিলে গেল।
            
    
          
    
        
    
      
    2. 
      
  2. 
        গণনা করুন: $K_6$ (৬-vertex complete graph)-এ মোট edge সংখ্যা কত? এবং $K_{3,4}$ (৩ ও ৪ সাইজের দুই দলবিশিষ্ট complete bipartite graph)-এ মোট edge সংখ্যা কত?
        
    
          
          
    
            
    
              $K_6$: $\binom{6}{2} = \frac{6 \times 5}{2} = 15$টি edge। $K_{3,4}$: $3 \times 4 = 12$টি edge — কারণ প্রথম দলের প্রতিটি vertex দ্বিতীয় দলের সবগুলোর সাথে সংযুক্ত, একই দলের ভেতরে কোনো edge নেই।
            
    
          
    
        
    
      
    3. 
    

  


  

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

    
  







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





  
    
 আগের পাঠ

    
ডিসক্রিট প্রোবাবিলিটি বেসিকস