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