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