2025-11-23T16:49:17.147369

2-Factors in Graphs

Heuvel, Toft

An account of 2-factors in graphs and their history is presented. We give a direct graph-theoretic proof of the 2-Factor Theorem and a new variant of it, and also a new complete characterisation of the maximal graphs without 2-factors. This is based on the important works of Tibor Gallai on 1-factors and of Hans-Boris Belck on k-factors, both published in 1950 and independently containing the theory of alternating chains. We also present an easy proof that a $(2k+1)$-regular graph with at most $2k$ leaves has a 2-factor, and we describe all connected $(2k+1)$-regular graphs with exactly $2k+1$ leaves without a 2-factor. This generalises Julius Petersen's famous theorem, that any 3-regular graph with at most two leaves has a 1-factor, and it generalises the extremal graphs Sylvester discovered for that theorem.

academic

ग्राफ़ में 2-कारक

मूल जानकारी

पेपर ID: 2510.11486
शीर्षक: ग्राफ़ में 2-कारक
लेखक: Jan van den Heuvel (लंदन स्कूल ऑफ इकोनॉमिक्स), Bjarne Toft (दक्षिणी डेनमार्क विश्वविद्यालय)
वर्गीकरण: math.CO (संयोजन गणित)
प्रकाशन समय: 13 अक्टूबर 2025 (arXiv प्रीप्रिंट)
पेपर लिंक: https://arxiv.org/abs/2510.11486

सारांश

यह पेपर ग्राफ़ सिद्धांत में 2-कारकों के सिद्धांत और उनके ऐतिहासिक विकास को व्यवस्थित रूप से प्रस्तुत करता है। लेखकों ने Tibor Gallai के 1950 के 1-कारकों पर महत्वपूर्ण कार्य और Hans-Boris Belck के k-कारकों पर समकालीन अनुसंधान (दोनों में स्वतंत्र रूप से वैकल्पिक श्रृंखला सिद्धांत शामिल है) के आधार पर, 2-कारक प्रमेय का प्रत्यक्ष ग्राफ़-सैद्धांतिक प्रमाण और एक नया प्रकार प्रदान किया है। साथ ही, लेखकों ने पहली बार 2-कारक रहित अधिकतम ग्राफ़ का संपूर्ण लक्षण वर्णन किया है। पेपर यह भी प्रमाणित करता है कि अधिकतम 2k पत्तियों वाले (2k+1)-नियमित ग्राफ़ में 2-कारक होता है, और सभी ठीक 2k+1 पत्तियों वाले और 2-कारक रहित जुड़े (2k+1)-नियमित ग्राफ़ का वर्णन करता है। ये परिणाम Julius Petersen के प्रसिद्ध प्रमेय (किसी भी अधिकतम दो पत्तियों वाले 3-नियमित ग्राफ़ में 1-कारक होता है) को सामान्यीकृत करते हैं और Sylvester द्वारा खोजे गए इस प्रमेय के चरम ग्राफ़ को प्रस्तुत करते हैं।

अनुसंधान पृष्ठभूमि और प्रेरणा

मूल समस्या

यह पेपर ग्राफ़ के 2-कारक समस्या का अध्ययन करता है, अर्थात्, दिए गए ग्राफ़ में एक 2-नियमित जनक उपग्राफ़ (प्रत्येक शीर्ष की डिग्री 2 वाला उपग्राफ़) खोजना। 2-कारक अनिवार्य रूप से ग्राफ़ में असंयुक्त चक्रों का समुच्चय है, जो ग्राफ़ सिद्धांत में एक मौलिक संरचना है।

समस्या की महत्ता

सैद्धांतिक मौलिकता: चक्र और 2-कारक ग्राफ़ सिद्धांत में सबसे मौलिक संरचनाएं हैं, जो ग्राफ़ के गुणों को समझने के लिए मौलिक हैं
ऐतिहासिक विरासत: यह समस्या ग्राफ़ सिद्धांत के संस्थापकों में से एक Julius Petersen के 1891 के अग्रणी कार्य से उत्पन्न होती है
सैद्धांतिक पूर्णता: हालांकि संबंधित अनुसंधान 70 से अधिक वर्षों से चल रहा है, 2-कारक रहित अधिकतम ग्राफ़ का संपूर्ण लक्षण वर्णन हमेशा से अनुपस्थित रहा है

मौजूदा विधियों की सीमाएं

प्रमाण विधि जटिल: प्रारंभिक प्रमाण अधिकतर बीजगणितीय विधियों (जैसे विषम सारणिक) पर निर्भर करते हैं
संरचना लक्षण वर्णन अधूरा: हालांकि Tutte, Belck, Gallai आदि ने कारक सिद्धांत की नींव स्थापित की है, अधिकतम ग्राफ़ का संपूर्ण विवरण अभाव है
ऐतिहासिक अनसुलझे प्रश्न: Gallai ने दावा किया था कि उन्होंने 2-कारकों का एक सामान्य सिद्धांत प्राप्त किया है, लेकिन कभी प्रकाशित नहीं किया

अनुसंधान प्रेरणा

लेखकों का उद्देश्य इस सैद्धांतिक अंतराल को भरना है, Belck और Gallai के वैकल्पिक श्रृंखला सिद्धांत का उपयोग करके सरल ग्राफ़-सैद्धांतिक प्रमाण प्रदान करना, और अधिकतम ग्राफ़ का संपूर्ण लक्षण वर्णन पूरा करना।

मुख्य योगदान

2-कारक प्रमेय का सरल प्रत्यक्ष ग्राफ़-सैद्धांतिक प्रमाण प्रदान किया, जटिल बीजगणितीय विधियों से बचा
पहली बार 2-कारक रहित अधिकतम ग्राफ़ संरचना का संपूर्ण लक्षण वर्णन किया (प्रमेय 1.8)
(2k+1)-नियमित ग्राफ़ के 2-कारक अस्तित्व प्रमेय को प्रमाणित किया (प्रमेय 1.9), Petersen के शास्त्रीय प्रमेय को सामान्यीकृत किया
सभी ठीक 2k+1 पत्तियों वाले और 2-कारक रहित (2k+1)-नियमित ग्राफ़ का वर्णन किया
Hans-Boris Belck के जीवन और योगदान को उजागर और प्रस्तुत किया, ग्राफ़ सिद्धांत के इतिहास के अंतराल को भरा

विधि विवरण

कार्य परिभाषा

इनपुट: अप्रत्यक्ष परिमित ग्राफ़ G (बहु-किनारों और स्व-लूप की अनुमति) आउटपुट: यह निर्धारित करना कि G में 2-कारक है या नहीं बाधा: वर्ग M₂ में कार्य करना (किनारे की बहुलता अधिकतम 2, प्रत्येक शीर्ष पर अधिकतम एक स्व-लूप)

मुख्य प्रमेय

2-कारक प्रमेय (प्रमेय 1.7)

ग्राफ़ G में 2-कारक है यदि और केवल यदि किसी भी असंयुक्त समुच्चय A,B ⊆ V(G) के लिए, जहां A स्वतंत्र समुच्चय है, C = V(G)(A∪B) को परिभाषित करते हुए, GC में A के साथ विषम संख्या में किनारों से जुड़े जुड़े घटकों की संख्या अधिकतम है:

-2|A| + 2|B| + e(A,C)

अधिकतम ग्राफ़ लक्षण वर्णन (प्रमेय 1.8)

मान लीजिए G वर्ग M₂ में 2-कारक रहित अधिकतम ग्राफ़ है, परिभाषित करें:

A: सभी स्व-लूप रहित शीर्ष
B: स्व-लूप वाले और अन्य सभी शीर्षों के साथ दो किनारों से जुड़े शीर्ष
C = V(G)(A∪B), q जुड़े घटकों के साथ

तब G निम्नलिखित गुणों को संतुष्ट करता है:

A स्वतंत्र समुच्चय है
C के प्रत्येक घटक पूर्ण ग्राफ़ हैं (प्रत्येक शीर्ष पर स्व-लूप, किन्हीं दो शीर्षों के बीच दो किनारे)
प्रत्येक घटक Cᵢ और A के बीच के किनारे विषम मिलान बनाते हैं
2|A| + q = 2|B| + e(A,C) + 2
सभी गैर-रिक्त A' ⊆ A और C' ⊆ C के लिए: 2|A'| + |C'| ≥ 2 + Σ(e(A', V(Cᵢ)))

तकनीकी विधि

वैकल्पिक श्रृंखला सिद्धांत

मुख्य उपकरण Belck-Gallai वैकल्पिक श्रृंखला सिद्धांत है:

वैकल्पिक श्रृंखला: लाल-नीले रंग में वैकल्पिक रूप से रंगे गए किनारों की पुनरावृत्ति-रहित यात्रा
शीर्ष वर्गीकरण: निश्चित प्रारंभिक बिंदु p से, शीर्षों को BR-शीर्ष (लाल और नीले दोनों तक पहुंचने योग्य), B-शीर्ष (केवल नीले तक पहुंचने योग्य), R-शीर्ष (केवल लाल तक पहुंचने योग्य) और अप्राप्य शीर्षों में वर्गीकृत करें
मुख्य लेम्मा (प्रमेय 2.2): BR-घटक में ठीक एक प्रवेश किनारा है

प्रमाण रणनीति

"केवल यदि" दिशा: यदि G में 2-कारक F है, तो F में पथ प्रकारों का विश्लेषण करके शर्त की आवश्यकता को प्रमाणित करें
"यदि और केवल यदि" दिशा: शर्त को संतुष्ट न करने वाले ग्राफ़ के लिए, अधिकतम विस्तारित ग्राफ़ का निर्माण करें, वैकल्पिक श्रृंखला सिद्धांत का उपयोग करके इसकी संरचना का विश्लेषण करें

तकनीकी नवाचार बिंदु

शुद्ध ग्राफ़-सैद्धांतिक विधि: पूरी तरह से बीजगणितीय तकनीकों से बचा, प्रमाण अधिक सहज है
एकीकृत ढांचा: 1-कारक और 2-कारक सिद्धांत को वैकल्पिक श्रृंखला ढांचे के तहत एकीकृत करें
रचनात्मक प्रमाण: न केवल अस्तित्व को प्रमाणित करें, बल्कि विशिष्ट अधिकतम ग्राफ़ संरचना दें
ऐतिहासिक एकीकरण: बिखरे हुए ऐतिहासिक परिणामों को संपूर्ण सैद्धांतिक प्रणाली में एकीकृत करें

प्रायोगिक सेटअप

यह पेपर शुद्ध सैद्धांतिक पेपर है, प्रायोगिक सत्यापन में शामिल नहीं है। सभी परिणाम कठोर गणितीय प्रमाण के माध्यम से स्थापित किए गए हैं।

मुख्य परिणाम

सैद्धांतिक परिणाम

नियमित ग्राफ़ के 2-कारक अस्तित्व

प्रमेय 1.9: यदि (2k+1)-नियमित ग्राफ़ G में अधिकतम 2k पत्तियां हैं, तो G में 2-कारक है।

यह Petersen के शास्त्रीय प्रमेय को सामान्यीकृत करता है (k=1 की स्थिति)।

चरम ग्राफ़ लक्षण वर्णन

प्रमेय 3.1: k≥2 के लिए, ठीक 2k+1 पत्तियों वाले और 2-कारक रहित (2k+1)-नियमित ग्राफ़ में विशिष्ट द्विपक्षीय संरचना होती है, जहां |A| = |B| + 1।

संपूर्ण अधिकतम ग्राफ़ सिद्धांत

प्रमेय 1.8 वर्ग M₂ में सभी अधिकतम 2-कारक रहित ग्राफ़ का संपूर्ण लक्षण वर्णन देता है, यह इस क्षेत्र में 70 से अधिक वर्षों का पहला संपूर्ण परिणाम है।

प्रमाण तकनीकों में सुधार

सरलीकृत 2-कारक प्रमेय प्रमाण: शास्त्रीय बीजगणितीय प्रमाण की तुलना में, नया प्रमाण अधिक सहज है
एकीकृत सैद्धांतिक ढांचा: दिखाता है कि विभिन्न कारक समस्याओं को कैसे वैकल्पिक श्रृंखला सिद्धांत से संभाला जाए
रचनात्मक विधि: न केवल अस्तित्व को प्रमाणित करें, बल्कि विशिष्ट निर्माण दें

सैद्धांतिक पूर्णता: पहली बार 2-कारक सिद्धांत में अधिकतम ग्राफ़ का संपूर्ण लक्षण वर्णन पूरा किया
विधि की श्रेष्ठता: वैकल्पिक श्रृंखला विधि बीजगणितीय विधि से अधिक सहज और एकीकृत है
ऐतिहासिक मूल्य: इस क्षेत्र के ऐतिहासिक विकास को स्पष्ट किया, विशेषकर Belck के योगदान को

सीमाएं

जटिलता: सामान्य k-कारकों (k≥3) के लिए, समान विश्लेषण अधिक जटिल हो जाता है
कम्प्यूटेशनल जटिलता: पेपर मुख्य रूप से अस्तित्व पर केंद्रित है, एल्गोरिथ्मिक जटिलता समस्या में शामिल नहीं है
अनुप्रयोग सीमा: मुख्य रूप से सैद्धांतिक योगदान, व्यावहारिक अनुप्रयोग चर्चा कम है

भविष्य की दिशाएं

सामान्य k-कारक: विधि को k≥3 की स्थिति में सामान्यीकृत करना
एल्गोरिथ्मिक अनुसंधान: संरचना लक्षण वर्णन के आधार पर कुशल एल्गोरिथ्म विकसित करना
हैमिल्टनियन चक्र: 2-कारक रहित अधिकतम ग्राफ़ और हैमिल्टनियन चक्र रहित अधिकतम ग्राफ़ के बीच संबंध का अध्ययन करना

गहन मूल्यांकन

लाभ

सैद्धांतिक पूर्णता: इस क्षेत्र में दीर्घकालीन सैद्धांतिक अंतराल को भरता है
विधि नवाचार: शास्त्रीय विधि से अधिक सरल प्रमाण पथ प्रदान करता है
ऐतिहासिक मूल्य: इस क्षेत्र के विकास का व्यवस्थित समीक्षा, विशेषकर Belck के कार्य की खोज
लेखन स्पष्टता: तर्क स्पष्ट, प्रमाण विस्तृत, समझने में आसान

कमियां

व्यावहारिक सीमा: मुख्य रूप से सैद्धांतिक योगदान, एल्गोरिथ्म और अनुप्रयोग पक्ष की चर्चा अपर्याप्त है
सामान्यीकरण कठिनाई: हालांकि विधि सुरुचिपूर्ण है, अधिक सामान्य स्थितियों में सामान्यीकरण स्पष्ट नहीं है
आधुनिक संबंध: आधुनिक ग्राफ़ सिद्धांत विकास के साथ संबंध की चर्चा पर्याप्त नहीं है

प्रभाव

सैद्धांतिक योगदान: मौलिक ग्राफ़ सिद्धांत में महत्वपूर्ण सैद्धांतिक पहेली को पूरा करता है
शिक्षण मूल्य: संबंधित पाठ्यक्रमों के लिए बेहतर शिक्षण सामग्री प्रदान करता है
ऐतिहासिक महत्व: इस क्षेत्र के विकास को स्पष्ट करता है, विशेषकर भूले हुए महत्वपूर्ण योगदानकर्ताओं को

लागू परिदृश्य

सैद्धांतिक अनुसंधान: ग्राफ़ सिद्धांत में कारक सिद्धांत का आगे विकास
शिक्षण अनुप्रयोग: ग्राफ़ सिद्धांत पाठ्यक्रम में शास्त्रीय सामग्री के रूप में
एल्गोरिथ्म डिजाइन: 2-कारक संबंधित एल्गोरिथ्म डिजाइन के लिए सैद्धांतिक आधार प्रदान करता है

विशेष मूल्य

Hans-Boris Belck की पुनः खोज

पेपर Hans-Boris Belck (1929-2007) के जीवन का परिचय देने के लिए एक पूरा खंड समर्पित करता है, यह गणितज्ञ जिन्होंने 21 साल की उम्र में महत्वपूर्ण सैद्धांतिक योगदान दिया लेकिन बाद में इंजीनियरिंग अनुप्रयोग की ओर मुड़ गए। यह न केवल इतिहास का स्पष्टीकरण है, बल्कि लेखकों द्वारा शैक्षणिक विरासत के प्रति सम्मान को भी दर्शाता है।

पद्धति संबंधी योगदान

यह पेपर दिखाता है कि कैसे शुद्ध ग्राफ़-सैद्धांतिक विधि का उपयोग करके उन समस्याओं को हल किया जाए जिनके लिए मूल रूप से बीजगणितीय तकनीकों की आवश्यकता थी। विधि में यह परिवर्तन पूरे क्षेत्र के लिए प्रेरणादायक है।

यह पेपर ग्राफ़ सिद्धांत के मौलिक सिद्धांत में एक महत्वपूर्ण योगदान है। यह न केवल दीर्घकालीन अनसुलझी सैद्धांतिक समस्या को हल करता है, बल्कि अधिक सुरुचिपूर्ण प्रमाण विधि भी प्रदान करता है, जो इस क्षेत्र के सैद्धांतिक पूर्णता के लिए महत्वपूर्ण है।