ग्राफ के द्विदलीय होने का क्या अर्थ है?

2024 लेखक: Miles Stephen | [email protected]. अंतिम बार संशोधित: 2023-12-15 23:36

के गणितीय क्षेत्र में ग्राफ सिद्धांत, ए द्विदलीय ग्राफ (या बिग्राफ) a. है ग्राफ जिसके शीर्षों को दो असंयुक्त और स्वतंत्र समुच्चयों में विभाजित किया जा सकता है और ऐसा कि प्रत्येक किनारा एक शीर्ष को एक में जोड़ता है। वर्टेक्स सेट और। आमतौर पर के हिस्से कहलाते हैं ग्राफ.

फिर, आप कैसे जानते हैं कि एक ग्राफ द्विदलीय है?

इसलिए अगर आप अपने को 2-रंग कर सकते हैं ग्राफ , यह द्विपक्षीय . स्पष्ट रूप से, अगर आपके पास एक त्रिभुज है, इसे रंगने के लिए आपको 3 रंगों की आवश्यकता है। कब आपके पास 2-रंग है, दो रंग वर्ग (लाल शिखर, नीला शिखर), आपको द्विदलीयता देते हैं। ए ग्राफ द्विदलीय है यदि और केवल अगर के भीतर एक विषम चक्र मौजूद नहीं है ग्राफ.

इसके बाद प्रश्न यह उठता है कि द्विदलीय होने का क्या अर्थ है? ए द्विपक्षीय ग्राफ एक ग्राफ है जिसमें ग्राफ के शीर्षों के एक सेट को दो स्वतंत्र सेटों में विभाजित किया जा सकता है, और एक ही सेट के भीतर कोई भी दो ग्राफ शिखर आसन्न नहीं होते हैं। दूसरे शब्दों में, द्विपक्षीय ग्राफ को दो रंगीन ग्राफ के बराबर माना जा सकता है।

इसके अतिरिक्त, द्विदलीय ग्राफ का क्या अर्थ है?

ए द्विदलीय ग्राफ , जिसे बिग्राफ भी कहा जाता है, का एक समुच्चय है ग्राफ दो अलग-अलग सेटों में विघटित शिखर इस तरह से कि कोई दो नहीं ग्राफ एक ही सेट के भीतर कोने आसन्न हैं। ए द्विदलीय ग्राफ k-partite. का एक विशेष मामला है ग्राफ साथ।

क्या एक पूरा ग्राफ द्विदलीय हो सकता है?

ए पूर्ण द्विदलीय ग्राफ एक है ग्राफ जिसका शीर्ष कर सकते हैं दो उपसमुच्चय V. में विभाजित किया जा सकता है₁ और वी₂ जैसे कि किसी भी किनारे का एक ही उपसमुच्चय में दोनों समापन बिंदु नहीं हैं, और हर संभव किनारा है कि सकता है विभिन्न उपसमुच्चयों में कनेक्ट वर्टिस का हिस्सा है ग्राफ.