यहां हम देखेंगे कि कैसे जांचा जाता है कि एक ट्री ग्राफ रैखिक है या नहीं। एक रैखिक वृक्ष ग्राफ को एक पंक्ति में व्यक्त किया जा सकता है, मान लीजिए कि यह एक रैखिक वृक्ष ग्राफ का एक उदाहरण है।
लेकिन यह रैखिक नहीं है -
यह जांचने के लिए कि ग्राफ रैखिक है या नहीं, हम दो शर्तों का पालन कर सकते हैं
- यदि नोड्स की संख्या 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