यह कैसे निर्धारित किया जाए कि क्या डिग्री अनुक्रम द्वारा एक प्लैनर ग्राफ उत्पन्न किया जा सकता है?

Question

ग्राफ़ के निम्नलिखित डिग्री अनुक्रमों के लिए,

$2,2,2,3,3,3,3,4,5,5\\1,1,1,1,2,2,2,2,3,3$

जो एक साधारण अप्रत्यक्ष ग्राफ का डिग्री अनुक्रम हो सकता है जो जुड़ा हुआ है और प्लानर है?

मुझे लगता है कि केवल दूसरा ही एक वैध अनुक्रम हो सकता है। क्या यह निर्धारित करने के लिए एक सामान्य नियम है कि क्या डिग्री अनुक्रम एक प्लैनर ग्राफ उत्पन्न कर सकता है?

Answer 1

सामान्य तौर पर इस पर कुछ विचार करने की आवश्यकता होगी कि क्या कोई डिग्री अनुक्रम एक प्लैनर ग्राफ है। उदाहरण के लिए, कुछ संभावित रणनीतियों के लिए इस प्रश्न को देखें , जिसमें कुराटोस्की के प्रमेय का उपयोग करना शामिल है, या अच्छी तरह से ज्ञात धार$3n - 6$। आप औसत डिग्री की गणना भी कर सकते हैं, जो कि एक प्लानर ग्राफ के लिए कड़ाई से कम होनी चाहिए 6. ( प्लानरिटी मानदंड देखें ।) आप यह देखने के लिए बहुत समय देखेंगे कि अगर ग्राफ किसी भी मानदंड का उल्लंघन करता है।

दोनों क्रम एक प्लैनर ग्राफ का प्रतिनिधित्व कर सकते हैं।

के लिये $2,2,2,3,3,3,3,4,5,5$, आप कई चीजों को नोटिस कर सकते हैं। चूंकि हम ग्रहण कर रहे हैं$G$ जुड़ा हुआ है, $G$ एक पेड़ नहीं हो सकता (कोई डिग्री नहीं है $1$कोने) और इस तरह एक चक्र है। तथापि,$|E(G)| = 16 \le 3(10) - 6 = 24$, तो कोई किस्मत नहीं है (याद रखें, हम केवल इस बात का उपयोग कर सकते हैं कि कोई ग्राफ़ गैर-प्लानर साबित हो सकता है ।) शायद आपके चारों ओर खेलने के बाद आप सोच सकते हैं कि कोई प्लानर ग्राफ है, और आप सही होंगे। हवलदार - हकीमी एल्गोरिथ्म का उपयोग करते हुए , जब मैंने रास्ते का डिग्री अनुक्रम प्राप्त किया, तो रोकना$8$ कोने, हम निम्नलिखित ग्राफ पाते हैं:

इस उदाहरण से हम देखते हैं कि जरूरी नहीं कि ऐसा ही हो $G$ एक चक्र है, लेकिन कोई त्रिकोण नहीं है (जिसने हमें बेहतर बाउंड का उपयोग करने में सक्षम बनाया है $2n-4$)। लेकिन फिर भी,$|E(G)| = 16 = 2(10) - 4$।

के लिये $1,1,1,1,2,2,2,2,3,3$, आप जल्दी से नोटिस कर सकते हैं कि यह ग्राफ़ नहीं हो सकता $K_5$ या $K_{3,3}$एक उपखंड के रूप में और इस प्रकार प्लानर होना चाहिए। यह Kuratowski के प्रमेय का उपयोग करता है। यह भी इस डिग्री अनुक्रम के साथ एक पेड़ खोजने के लिए बहुत मुश्किल नहीं होना चाहिए।

पहले अनुक्रम के लिए, आप तुरंत उस पर ध्यान दे सकते हैं $G$ नहीं हो सकता $K_5$ उपखंड, हालांकि $K_{3,3}$अधिक तर्क की आवश्यकता हो सकती है। यानी, दूसरे अनुक्रम के विपरीत, हमने दिखाया है कि पहला अनुक्रम एक प्लानर ग्राफ का प्रतिनिधित्व कर सकता है , हमने नहीं दिखाया है कि यह होना चाहिए ।