एक ग्राफ को द्विभाजित ग्राफ कहा जाता है, जब उस ग्राफ के शीर्षों को दो स्वतंत्र समुच्चयों में विभाजित किया जा सकता है जैसे कि ग्राफ में प्रत्येक किनारा या तो पहले समुच्चय से शुरू होकर दूसरे समुच्चय में समाप्त होता है, या दूसरे समुच्चय से शुरू होकर पहले समुच्चय से जुड़ा होता है, दूसरे शब्दों में, हम कह सकते हैं कि कोई भी किनारा एक ही समुच्चय में नहीं पाया जा सकता।
द्विभाजित ग्राफ की जांच शीर्ष रंगाई का उपयोग करके संभव है। जब एक शीर्ष एक ही समुच्चय में होता है, तो उसका रंग समान होता है, दूसरे समुच्चय के लिए रंग बदल जाएगा।
इनपुट और आउटपुट
इनपुट: आसन्नता मैट्रिक्स। 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 आउटपुट: ग्राफ द्विभाजित है।
एल्गोरिदम
isBipartite(source)
इनपुट: स्रोत शीर्ष।
आउटपुट: ग्राफ द्विभाजित होने पर सच।
शुरू एक खाली कतार qu और एक रंग सूची colorArray परिभाषित करें प्रारंभ में किसी भी नोड को किसी रंग से रंगा नहीं गया है स्रोत शीर्ष को लाल रंग दें स्रोत को qu में जोड़ें जब qu खाली नहीं है, करें qu से आइटम हटाएं और u में लें यदि कोई सेल्फ-लूप है, तो वापस करें गलत u से जुड़े सभी शीर्ष v के लिए, करें यदि v का कोई रंग नहीं है, तो यदि colorArray[u] = लाल, तो colorArray[v] := नीला अन्यथा यदि colorArray[u] = नीला, तो colorArray[v] := लाल v को कतार में जोड़ें यदि colorArray[v] = colorArray[u], तो वापस करें गलत किया किया वापस करें सच अंत
उदाहरण
#include<iostream> #include<string> #include<queue> #define NODE 6 using namespace std; /*int graph[NODE][NODE] = { {0, 1, 1, 1, 0, 0}, {1, 0, 0, 1, 1, 0}, {1, 0, 0, 1, 0, 1}, {1, 1, 1, 0, 1, 1}, {0, 1, 0, 1, 0, 1}, {0, 0, 1, 1, 1, 0} }; */ int graph[NODE][NODE] = { {0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 0, 0}, {0, 0, 1, 0, 1, 0}, {0, 0, 0, 1, 0, 1}, {1, 0, 0, 0, 1, 0} }; bool isBipartite(int source) { queue<int> qu; string colorArray[NODE]; for(int i = 0; i< NODE; i++) colorArray[i] = "No Color"; //प्रारंभ में सभी शीर्षों के लिए कोई रंग सेट नहीं colorArray[source] = "Red"; //स्रोत शीर्ष के साथ लाल असाइन करें qu.push(source); //स्रोत को कतार में जोड़ें। while(!qu.empty()) { int u = qu.front(); qu.pop(); if(graph[u][u] == 1) //सेल्फ लूप है return false; for(int v = 0; v < NODE; v++) { if(graph[u][v] != 0 && colorArray[v] == "No Color") { if(colorArray[u] == "Red") //आसन्न सूची को वैकल्पिक रंग के साथ असाइन करें colorArray[v] = "Blue"; else if(colorArray[u] == "Blue") colorArray[v] = "Red"; qu.push(v); //नया आसन्न नोड कतार में जोड़ा गया } else if(graph[u][v] != 0 && colorArray[v] == colorArray[u]) { return false; //जब u और आसन्न एक ही रंग के हों। } } } return true; } int main() { bool check; check = isBipartite(0); if(check) cout << "The graph is bipartite." << endl; else cout << "The graph is not bipartite." << endl; }
आउटपुट
The graph is bipartite.
