स्मूथिंग द्वारा दिए गए ग्राफ में सबसे छोटे ग्राफ होमोमोर्फिक का निर्माण करें

Question

होमोमोर्फिज्म वर्ग $ \mathcal{H}(G) $ एक ग्राफ के $G$ रेखांकन के होमोमोर्फिक हैं जो रेखांकन के आइसोमॉर्फिज़्म वर्गों का एक सेट है $G$। यह पूछना स्वाभाविक है: क्या होमियोमॉर्फिज़्म क्लास में "सबसे छोटा" प्रतिनिधि है? यदि हाँ, तो इसे कैसे खोजें? दुर्भाग्य से, मुझे त्वरित Google खोज के बाद इस समस्या पर कोई उपयोगी परिणाम नहीं मिला।

फिर भी, अंतर्ज्ञान द्वारा निर्देशित, मेरे पास निम्नलिखित परिकल्पना है:

एक ग्राफ में सबसे छोटा ग्राफोमोर्फिक हर अधिकतम कान को चिकना करके प्राप्त किया जाता है।

इस पोस्ट में मैं एक सबूत को स्केच करने का प्रयास करता हूं, लेकिन सबूत में एक अंतर है, इसलिए मुझे नहीं पता कि मेरी परिकल्पना वास्तव में सही है या नहीं। मैं अपनी गलतियों को इंगित करने और अंतर को भरने के लिए किसी की भी सराहना करूंगा।

चेतावनी: यह एक लंबी पोस्ट होगी

सबसे पहले, कुछ शब्दावली को स्पष्ट करते हैं। "कान" शब्द का अर्थ विभिन्न ग्राफ सिद्धांत की पाठ्यपुस्तकों में अलग-अलग चीजें हैं। इस पोस्ट में, हम निम्नलिखित परिभाषा को अपनाते हैं:

परिभाषा 1

एक ग्राफ में एक कान है:

• एक चक्र जिसका सभी सिवाय संभवतः एक कोने में डिग्री हो $2$, या
• एक पथ जिसका सभी आंतरिक कोने डिग्री के हैं $2$।

एक अधिकतम कान एक कान है जो एक बड़े कान का उचित उपसमूह नहीं है। समान रूप से, एक अधिकतम कान निम्नलिखित में से एक है:

• एक चक्र जो अपने आप में एक संपूर्ण जुड़ा हुआ घटक है
• एक चक्र जिसमें बिल्कुल एक शीर्ष डिग्री है $ \geq 3 $, जबकि अन्य सभी कोने डिग्री के हैं $2$
• एक पथ जिसमें सभी आंतरिक कोने डिग्री के हैं $2$, जबकि दोनों छोर लंबवत हैं $ \neq 2 $

ग्राफ़ पर टोपोलॉजी को संरक्षित करने वाले दो सामान्य ऑपरेशन उपविभाजन और चौरसाई हैं:

परिभाषा २

एक किनारे को उप-विभाजित करने का मतलब है कि इसे एक कान से बदलना। अधिक ठीक है, चलो$e = uv$ एक छोर हो।

अगर $u = v$, तो आत्म-पाश को उपविभाजित करना $e$ इसका मतलब है कि इसे एक चक्र से बदलना है $C$, तथा $u = v$ पर एक शीर्ष बन जाता है $C$, जिसके पास डिग्री हो या न हो $2$, इस पर निर्भर $e$ अलग-थलग है।

दूसरी ओर, यदि $u \neq v$, फिर उप-विभाजन $e$ इसका मतलब यह एक रास्ते से बदल रहा है $P$, तथा $u, v$ के अंत कोने बन जाते हैं $P$।

एक ग्राफ को उपविभाजित करने का अर्थ है किनारों पर उप-विभाजन का एक क्रम पूर्ववर्ती करना।

परिभाषा ३

एक कान को चिकना करने का मतलब है कि इसे एक किनारे से बदलना। अधिक ठीक है, चलो$C$ एक कान बनो।

अगर $C$ एक चक्र है, फिर चौरसाई $C$ इसका मतलब है कि यह एक आत्म पाश द्वारा प्रतिस्थापित किया जाता है $e$, और डिग्री के शीर्ष $ \neq 2 $ पर $C$ पर केवल शीर्ष घटना बन जाती है $e$ (यदि सभी लंबवत हैं $C$ डिग्री के हैं $2$, बस किसी भी शीर्ष चुनें)।

दूसरी ओर, अगर $C$ वास्तव में एक रास्ता है $P$, फिर चौरसाई $P$ इसका मतलब यह है कि एक पाश रहित किनारे से $e$, और के अंतिम छोर $P$ के अंत कोने बन जाते हैं $e$।

एक ग्राफ को चौरसाई करने का अर्थ है कानों पर चिकनाई का एक क्रम पहिले।

अगला, हमारे पास रेखांकन की टोपोलॉजी पर निम्नलिखित क्लासिक परिणाम हैं:

प्रमेय १

दो रेखांकन होमोमोर्फिक हैं यदि और केवल यदि उनमें से एक को दूसरे पर उप-विभाजन और चौरसाई संचालन के अनुक्रम से प्राप्त किया जा सकता है।

प्रमाण: इस पोस्ट को देखें ।

प्रमेय २

चलो $G$ तथा $H$दो होमोमोर्फिक रेखांकन बनें। फिर$ |V(G)| = |V(H)| $ अगर और केवल अगर $ |E(G)| = |E(H)| $।

प्रमाण का स्केच: सबडिविडिंग (सम्मान। चौरसाई) हमेशा बढ़ता है (सम्मान कम हो जाता है) एक ही संख्या द्वारा कोने और किनारों की संख्या।$\square$

प्रमेय 2 के प्रकाश में, हम एक ग्राफ के होमोमोर्फिज्म वर्ग पर एक क्रम को परिभाषित कर सकते हैं:

परिभाषा ४

चलो $ \mathcal{H}(G) $ एक ग्राफ के homeomorphism वर्ग हो $G$। आदेश को परिभाषित करें$\preceq$ पर $ \mathcal{H}(G) $ द्वारा द्वारा: $$ G_1 \preceq G_2 \iff |V(G_1)| \leq |V(G_2)| $$ किसी के लिए $ G_1, G_2 \in \mathcal{H}(G) $।

अगर $ G_1 \preceq G_2 $ तथा $ G_2 \preceq G_1 $, तो हम निरूपित करते हैं $ G_1 \sim G_2 $।

आदेश $\preceq$कुल प्रीऑर्डर है, जिसका अर्थ है कि यह सकर्मक है और कोई भी दो होमियोमॉर्फिक ग्राफ तुलनीय हैं। दुर्भाग्य से, यह कुल आदेश नहीं है, क्योंकि$ G_1 \sim G_2 $ मतलब नहीं है $ G_1, G_2 $ थेओमॉर्फिक हैं, यहां तक ​​कि प्रमेय 2 के माध्यम से भी $ |E(G_1)| = |E(G_2)| $।

प्रमेय ३

अलग-थलग शीर्ष के बिना किसी भी ग्राफ को अधिकतम रूप से अधिकतम कानों के किनारे-असंतुष्ट संघ में विघटित किया जा सकता है।

सबूत के स्केच:

चलो $G$अलग-थलग शीर्ष के बिना एक ग्राफ हो। संबंध को परिभाषित करें$R$ पर $E(G)$ द्वारा द्वारा: $$ eRf \iff \exists \text{ ear } C \subseteq{G} \text{ s.t. } e, f \in E(C) $$ किसी के लिए $ e, f \in E(G) $।

फिर $R$ पर एक तुलनीय संबंध है $E(G)$, जिसमें प्रत्येक समतुल्य वर्ग में एक अधिकतम कान के किनारों होते हैं। इस प्रकार,$R$ के अपघटन को प्रेरित करता है $G$अधिकतम कानों के किनारे-असंतुष्ट संघ में। इसके विपरीत, इस तरह के किसी भी अपघटन द्वारा प्रेरित किया जाना चाहिए$R$, इसलिए अपघटन अद्वितीय है। $\square$

उपरोक्त अपघटन के आधार पर, हम निम्नलिखित को परिभाषित कर सकते हैं:

परिभाषा ५

बिना अलग किए शीर्ष के ग्राफ को चिकना कहा जाता है यदि प्रत्येक अधिकतम कान लंबाई का हो $1$। एक ग्राफ के लिए$G$ अलग-थलग शीर्ष के बिना, प्रत्येक अधिकतम कान को चिकना करने से प्राप्त चिकनी ग्राफ $G$ के रूप में चिह्नित किया जाता है $ \text{Smooth} (G) $।

"सुचारू ग्राफ़" शब्द मानक नहीं है, लेकिन मुझे इस तरह के ग्राफ़ के लिए कोई मौजूदा शब्द नहीं मिला, इसलिए मैं इसे अपने दम पर बनाता हूं।

प्रमेय ४

चलो $G$ पृथक शीर्ष के बिना एक चिकनी ग्राफ हो $ H \in \mathcal{H}(G) $, तब फिर $ G \preceq H $। इसके अलावा,$ G \sim H $ अगर और केवल अगर $H$ एक चिकना ग्राफ है।

सबूत के स्केच:

1 प्रमेय द्वारा, $H$ उप-विभाजन और सुचारू संचालन के अनुक्रम से प्राप्त किया जा सकता है $G$। ऑपरेशन के प्रत्येक चरण केवल अधिकतम कान के एक हिस्से को संभवतः भिन्न लंबाई के दूसरे अधिकतम कान में बदल सकते हैं।

दूसरी ओर, एक चिकने ग्राफ में, सभी अधिकतम कानों में पहले से ही सबसे कम संभव लंबाई होती है (अर्थात, $1$), इसलिए उप-विभाजन और चौरसाई का कोई भी क्रम कभी भी चक्कर की संख्या को कम नहीं कर सकता है। इस प्रकार,$ |V(G)| \leq |V(H)| $ और समानता रखती है अगर और केवल अगर $H$ चिकनी है। $\square$

निम्नलिखित दावा अंतर्ज्ञान पर आधारित है, लेकिन मुझे नहीं पता कि इसे कैसे साबित किया जाए। यह वह जगह है जहां मेरे पूरे प्रमाण का अंतर निहित है।

दावा ०

चलो $G$ तथा $H$पृथक शीर्ष के बिना दो चिकने रेखांकन हो सकते हैं। यदि वे होमियोमॉर्फिक हैं, तो वे आइसोमोर्फिक हैं।

अंत में, उपरोक्त दावे को मानते हुए, हम मुख्य परिकल्पना को सिद्ध कर सकते हैं:

मुख्य परिकल्पना

दावा मान लें कि 0 सही है और बता दें $G$अलग-थलग शीर्ष के बिना एक ग्राफ हो। फिर$ \text{Smooth} (G) $ में सबसे छोटा ग्राफ है $ \mathcal{H} (G) $ आदेश के संबंध में $ \preceq $।

सबूत:

यह तथ्य कि $ \text{Smooth} (G) \preceq H $ सबके लिए $ H \in \mathcal{H} (G) $ प्रमेय 4 से निम्नानुसार है।

विशिष्टता साबित करने के लिए, चलो $ H \in \mathcal{H} (G) $ ऐसा हो $ \text{Smooth} (G) \sim H $। जबसे$ \text{Smooth} (G) $ चिकनी है और $ H \in \mathcal{H} (\text{Smooth} (G)) $, प्रमेय 4 द्वारा, $H$साथ ही चिकनी है। दावा 0 तब तात्पर्य है$H$ isomorphic है $ \text{Smooth} (G) $। $\square$

प्रशन:

1. क्या क्लेम ० सही है? इसे कैसे साबित करें?
2. भले ही दावा 0 गलत हो, लेकिन क्या मेरी मुख्य परिकल्पना अभी भी सही है?
3. क्या मेरे प्रमाण में कोई अन्य गलतियाँ हैं?
4. क्या ग्राफ़ के लिए एक बेहतर शब्द है जिसका प्रत्येक अधिकतम कान लंबाई का है $1$, "चिकनी रेखांकन" के अलावा?

Answer 1

आपका प्रमाण मेरे लिए सही प्रतीत होता है। मैं यह नहीं देखता कि आप यह क्यों मान लेते हैं कि ग्राफ़ में कोई अलग-थलग कोने नहीं हैं - क्या इससे कहीं फर्क पड़ता है? इसके अलावा, "चिकनी ग्राफ" एक ग्राफ के लिए एक फैंसी नाम लगता है जिसमें डिग्री दो के कोने नहीं होते हैं। (अधिक सटीक रूप से, डिग्री दो के केवल कोने एक लूप के साथ अलग-अलग कोने हैं।)

मैं आपके दावे का प्रमाण दूंगा। हम मान सकते हैं कि विचाराधीन ग्राफ जुड़े हुए हैं और उनके पास कम से कम एक किनारा है। किसी भी ग्राफ के लिए$G$, एक शीर्ष-रंगीन ग्राफ़ को संबद्ध करें $Ear(G)$ इस अनुसार:

• के सिरों $Ear(G)$ के अद्वितीय अपघटन में कान के अनुरूप हैं $G$अधिकतम कानों में। वे नीले और लाल रंग के होते हैं चाहे कान एक मार्ग हो या चक्र।
• यदि दो कानों में एक सामान्य वर्टेक्स हो तो दो कोने समीप होते हैं; यदि उनके दो सामान्य कोने हैं, तो हम दो समानांतर किनारों को खींचते हैं। (यह केवल तभी हो सकता है जब संबंधित कान पथ हों।)

वहाँ दो अवलोकन किए जा सकते हैं जो आपके सिद्धांत 4 के प्रमाण में कम या ज्यादा निहित हैं:

1. अगर $G$ तथा $H$ होमोमोर्फिक हैं, तब $Ear(G)$ तथा $Ear(H)$आइसोमोर्फिक हैं, आइसोमॉर्फिज्म के साथ वर्टेक्स रंगों को संरक्षित करते हैं। यह प्रमेय 1 से जाँच के बाद कि दोनों चौरसाई और उप-विभाजन संरक्षित करते हैं$Ear(G)$।
2. अगर $G$ चिकनी है, तो (रंग की उपेक्षा) $Ear(G)$की लाइन ग्राफ है$G$, छोरों और कई किनारों के साथ रेखांकन के लिए उचित रूप से परिभाषित किया गया है।

आसानी से, व्हिटनी के एक प्रमेय में कहा गया है कि यदि दो जुड़े हुए सरल ग्राफों की रेखा रेखाएँ आइसोमॉर्फिक हैं, तो ग्राफ़ स्वयं आइसोमॉर्फिक हैं, सिवाय इसके कि ग्राफ त्रिभुज हैं$K_3$ और पंजा $K_{1,3}$। ध्यान दें कि त्रिकोण चिकना नहीं है। छोरों और समानांतर किनारों के साथ रेखांकन के मामले में, स्थिति अधिक जटिल है (हालांकि बहुत नहीं तो इस लेख के अनुसार * जिससे मैं केवल एक भुगतान लिंक पा सकता था; मजेदार रूप से पर्याप्त, व्हिटनी का नाम शीर्षक में गलत लिखा गया है) , लेकिन हमारे मामले में शीर्ष-रंग और प्रमेय 4 हमें मूल ग्राफ को फिर से संगठित करने के लिए पर्याप्त जानकारी देते हैं। आप शायद इसे स्वयं सुलझा सकते हैं, लेकिन मैं पूर्णता के लिए विवरण दूंगा।

तो मान लीजिए कि $G$ तथा $H$ चिकनी हैं और वह $Ear(G)$ तथा $Ear(H)$समद्विबाहु हैं। सबसे पहले, हम छोरों से निपटते हैं: ये ठीक लाल कोने के अनुरूप हैं$Ear(G)$ तथा $Ear(H)$। यह इस प्रकार है कि अगर हम द्वारा निरूपित करते हैं$G'$ तथा $H'$ में छोरों को हटाने के द्वारा प्राप्त रेखांकन $G$ तथा $H$, तब फिर $Ear(G')$ तथा $Ear(H')$ से लाल कोने को हटाकर प्राप्त किया जाता है $Ear(G)$ तथा $Ear(H)$; विशेष रूप से, वे आइसोमॉर्फिक हैं। अब यह दिखाने के लिए पर्याप्त है$G'$ तथा $H'$ आइसोमॉर्फिक हैं, तब से छोरों की स्थिति विशिष्ट रूप से निर्धारित होती है $Ear(G)$: में एक शीर्ष $G'$ एक लूप है अगर और केवल अगर वहाँ एक किनारे की घटना है जो एक लाल शीर्ष के निकट है $Ear(G)$, या अगर $G'$ इस एकल शीर्ष के होते हैं (क्योंकि हमने मान लिया था कि हमारे रेखांकन में कम से कम एक किनारे है)।

इस प्रकार, हम यह मान सकते हैं $G$ तथा $H$लूप नहीं हैं। अब हमें सिर्फ समानांतर किनारों का ध्यान रखना है। अगर दो किनारों में समानांतर है$G$, तो हमारे निर्माण द्वारा इसी कोने में खड़ी है $Ear(G)$दो समानांतर किनारों से जुड़े हुए हैं। अधिक आम तौर पर, दो या अधिक समानांतर किनारों में$G$ में एक समूह के अनुरूप $Ear(G)$जिसमें हर बढ़त दोगुनी है। हर वार में$Ear(G)$ एक अद्वितीय अधिकतम में समाहित है, जैसे "डबल क्लिक" (संभवतः एक आकार), और इन क्लिक्स को अनुबंधित करके और नए बने समानांतर किनारों को एकल लोगों द्वारा प्रतिस्थापित करने से, हम अंतर्निहित सरल ग्राफ की लाइन ग्राफ प्राप्त करते हैं $G$। चूंकि यह पीछे की ओर भी काम करता है (यानी सरल ग्राफ से और$Ear(G)$ हम ठीक हो सकते हैं $G$), हम यह मान सकते हैं $G$ तथा $H$ सरल हैं।

तो हम व्हिटनी के प्रमेय द्वारा किया जाता है, है ना? खैर, इतनी जल्दी नहीं। ऐसा हो सकता है कि छोरों और समानांतर किनारों को छोड़ने के बाद$G$ तथा $H$, हम एक त्रिकोण और $K_{1,3}$: आखिरकार, डबल किनारों वाला एक त्रिकोण चिकना है। लेकिन यह प्रमेय 4: मूल द्वारा खारिज किया गया है$G$ तथा $H$समान संख्या में कोने थे, और किनारों को छोड़ने से यह नहीं बदलता है। इसलिए$G$ तथा $H$ वास्तव में isomorphic हैं।

^{* ध्यान दें, जहाँ तक मैं बता सकता हूँ, लेख में प्रयुक्त लाइन ग्राफ की धारणा यहाँ प्रयुक्त एक से भिन्न है, जिसमें समानांतर किनारों के संगत कोने अभी भी केवल एक किनारे से जुड़े हुए हैं।}