এখানে আমরা দেখব কিভাবে একটি ট্রি গ্রাফ রৈখিক কিনা তা পরীক্ষা করা যায়। একটি লিনিয়ার ট্রি গ্রাফ এক লাইনে প্রকাশ করা যেতে পারে, ধরুন এটি একটি লিনিয়ার ট্রি গ্রাফের উদাহরণ৷
কিন্তু এটি লিনিয়ার নয় -
একটি গ্রাফ রৈখিক কিনা তা পরীক্ষা করতে, আমরা দুটি শর্ত অনুসরণ করতে পারি
- নোডের সংখ্যা 1 হলে, ট্রি গ্রাফটি রৈখিক হয়
- যদি (n – 2) এর নোডের ইন-ডিগ্রি 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
