ग्राफ सिद्धांत में द्विविभाजन को समझना
ग्राफ सिद्धांत में, एक ग्राफ का द्विविभाजन उसके शीर्ष सेट का दो असंयुक्त सेटों (जिन्हें पार्टाइट सेट कहा जाता है) में एक विभाजन होता है, जैसे कि सभी किनारे अलग-अलग पार्टाइट सेट से कोने को जोड़ते हैं। दूसरे शब्दों में, एक ही आंशिक सेट में शीर्षों के बीच कोई किनारा नहीं है। उदाहरण के लिए, 4 शीर्षों {ए,बी,सी,डी} वाले एक ग्राफ पर विचार करें और हम शीर्ष सेट को दो भागों में विभाजित करते हैं: {ए,बी} और {सी,डी}. ग्राफ द्विदलीय है क्योंकि सभी किनारे अलग-अलग हिस्सों से कोने को जोड़ते हैं। ग्राफ ट्रैवर्सल, सबसे छोटा पथ खोज और ग्राफ मिलान जैसी ग्राफ समस्याओं के लिए एल्गोरिदम की जटिलता को कम करने के लिए द्विदलीय का उपयोग किया जा सकता है।
मुझे यह पसंद है
मुझे यह नापसंद है
सामग्री त्रुटि की रिपोर्ट करें
शेयर करें
