এখানে আমরা দেখব কিভাবে একটি ট্রি গ্রাফ লিনিয়ার কিনা তা নির্ধারণ করা যায়। একটি লিনিয়ার ট্রি গ্রাফকে একক রেখায় প্রকাশ করা সম্ভব। নিচে একটি লিনিয়ার ট্রি গ্রাফের উদাহরণ দেওয়া হলো:
এবং এটি লিনিয়ার নয়:
একটি গ্রাফ লিনিয়ার কিনা তা যাচাই করার জন্য আমরা দুটি শর্ত অনুসরণ করতে পারি:
- নোডের সংখ্যা ১ হলে, ট্রি গ্রাফটি লিনিয়ার।
- যদি (n – 2) টি নোডের ইন-ডিগ্রি ২ হয়।
উদাহরণ
#include <iostream> #include <vector> #define N 4 using namespace std; class Graph{ private: int V; vector<int> *adj; public: Graph(int v){ V = v; adj = new vector<int>[v]; } void addEdge(int u, int v){ adj[u].push_back(v); adj[v].push_back(u); } bool isLinear() { if (V == 1) return true; int count = 0; for (int i = 0; i < V; i++) { if (adj[i].size() == 2) count++; } if (count == V - 2) return true; else return false; } }; int main() { Graph g1(3); g1.addEdge(0, 1); g1.addEdge(0, 2); if (g1.isLinear()) cout << "The graph is linear"; else cout << "The graph is not linear"; }আউটপুট
The graph is linear
