Vertex separator
ग्राफ सिद्धांत में, एक शीर्ष उपसमुच्चय गैर-आसन्न शीर्षों के लिए एक शीर्ष विभाजक (या शीर्ष कट, अलग करने वाला सेट) है और यदि ग्राफ से हटाने से अलग और अलग जुड़े घटकों में होता है। उदाहरण पंक्तियों और स्तंभों के साथ एक ग्रिड ग्राफ पर विचार करें; शीर्षों की कुल संख्या है। उदाहरण के लिए, चित्रण में, और। यदि विषम है, तो एक एकल केंद्रीय पंक्ति है, और अन्यथा दो पंक्तियाँ केंद्र के समान रूप से करीब हैं; इसी तरह, यदि विषम है, तो एक एकल केंद्रीय स्तंभ है, और अन्यथा केंद्र के समान रूप से करीब दो स्तंभ हैं। इनमें से किसी भी केंद्रीय पंक्ति या स्तंभ को चुनते हुए, और ग्राफ से हटाते हुए, ग्राफ को दो छोटे जुड़े हुए उप-ग्राफों में विभाजित करता है और जिनमें से प्रत्येक में अधिक से अधिक शीर्ष होते हैं। यदि (जैसा कि चित्रण में है), तो एक केंद्रीय स्तंभ चुनने से शीर्षों के साथ एक विभाजक मिलेगा, और इसी तरह यदि तब एक केंद्रीय पंक्ति चुनने से अधिकांश शीर्षों के साथ एक विभाजक मिलेगा। इस प्रकार, प्रत्येक ग्रिड ग्राफ में अधिक से अधिक आकार का एक विभाजक होता है जिसे हटाने से यह दो जुड़े घटकों में विभाजित हो जाता है, जिनमें से प्रत्येक का आकार अधिक से अधिक होता है। उदाहरणों के एक अन्य वर्ग को देने के लिए, प्रत्येक मुक्त वृक्ष में एक विभाजक होता है जिसमें एक ही शीर्ष होता है, जो दो या दो से अधिक जुड़े घटकों में विभाजन को हटाता है, प्रत्येक का आकार अधिक से अधिक होता है। अधिक सटीक रूप से, हमेशा एक या ठीक दो शीर्ष होते हैं, जो इस तरह के विभाजक के बराबर होते हैं, यह इस बात पर निर्भर करता है कि वृक्ष केंद्रित है या द्वि-केंद्रित है। इन उदाहरणों के विपरीत, सभी शीर्ष विभाजक संतुलित नहीं हैं, लेकिन यह गुण कंप्यूटर विज्ञान में अनुप्रयोगों के लिए सबसे उपयोगी है, जैसे कि समतलीय विभाजक प्रमेय। न्यूनतम विभाजक मान लीजिए कि वे एक-विभाजक हैं, अर्थात एक शीर्ष उपसमुच्चय जो दो गैर-आसन्न शीर्षों को अलग करता है और। फिर एक न्यूनतम-विभाजक है यदि अलग और का कोई उचित उपसमुच्चय नहीं है। अधिक आम तौर पर, एक न्यूनतम विभाजक कहा जाता है यदि यह गैर-आसन्न शीर्षों की कुछ जोड़ी के लिए एक न्यूनतम विभाजक है। ध्यान दें कि यह न्यूनतम पृथक्करण समुच्चय से अलग है जो कहता है कि शीर्षों की किसी भी जोड़ी के लिए कोई उचित उपसमुच्चय न्यूनतम-विभाजक नहीं है। निम्नलिखित एक प्रसिद्ध परिणाम है जो न्यूनतम विभाजक की विशेषता हैः लेम्मा। एक शीर्ष विभाजक न्यूनतम होता है यदि और केवल तभी जब हटाने से प्राप्त ग्राफ में दो जुड़े हुए घटक होते हैं और ऐसा होता है कि प्रत्येक शीर्ष दोनों किसी शीर्ष के निकट और किसी शीर्ष के निकट होता है। न्यूनतम-विभाजक भी एक बीजगणितीय संरचना बनाते हैंः दो निश्चित शीर्षों और दिए गए ग्राफ के लिए, एक-विभाजक को दूसरे-विभाजक का पूर्ववर्ती माना जा सकता है, यदि प्रत्येक पथ से मिलने से पहले मिलता है। अधिक सख्ती से, पूर्ववर्ती संबंध को निम्नानुसार परिभाषित किया गया हैः दो-विभाजक होने दें। फिर एक पूर्ववर्ती है, प्रतीकों में, यदि प्रत्येक के लिए, मिलने से जुड़ने वाला प्रत्येक मार्ग। यह इस परिभाषा का अनुसरण करता है कि पूर्ववर्ती संबंध सभी-विभाजक के समूह पर एक पूर्व आदेश देता है। इसके अलावा, यह साबित किया कि पूर्ववर्ती संबंध एक पूर्ण जाली को जन्म देता है जब न्यूनतम-विभाजक के सेट तक सीमित होता है। कॉर्डल ग्राफ भी देखें, एक ग्राफ जिसमें प्रत्येक न्यूनतम विभाजक एक गुट है। के-वर्टेक्स से जुड़ा ग्राफ नोट्स संदर्भ। .. ग्राफ कनेक्टिविटी