Graph pebbling
ग्राफ कंकड़ एक गणितीय खेल है जो एक ग्राफ पर खेला जाता है जिसके प्रत्येक शीर्ष पर शून्य या अधिक कंकड़ होते हैं। 'गेम प्ले' कंकड़ चालों की एक श्रृंखला से बना है। एक ग्राफ पर एक कंकड़ चाल में कम से कम दो कंकड़ के साथ एक शीर्ष का चयन करना, उसमें से दो कंकड़ को हटाना और एक को बगल के शीर्ष में जोड़ना शामिल है (दूसरे हटाए गए कंकड़ को खेल से हटा दिया जाता है)। π (G), एक ग्राफ G की कंकड़ संख्या, सबसे कम प्राकृतिक संख्या n है जो निम्नलिखित शर्तों को संतुष्ट करती हैः ग्राफ में किसी भी लक्ष्य या 'मूल' शीर्ष और ग्राफ पर n कंकड़ के किसी भी प्रारंभिक विन्यास को देखते हुए, कंकड़ चालों की एक श्रृंखला के बाद, एक नए विन्यास तक पहुंचना संभव है जिसमें निर्दिष्ट मूल शीर्ष में एक या अधिक कंकड़ होते हैं। उदाहरण के लिए, 2 शीर्षों और उन्हें जोड़ने वाले 1 किनारे वाले ग्राफ पर कंकड़ संख्या 2 है। इससे कोई फर्क नहीं पड़ता कि दो कंकड़ को ग्राफ के शीर्षों पर कैसे रखा जाता है, एक कंकड़ को ग्राफ में किसी भी शीर्ष पर ले जाना हमेशा संभव है। ग्राफ पेब्लिंग के केंद्रीय प्रश्नों में से एक दिए गए ग्राफ जी के लिए π (G) का मूल्य है। पेब्लिंग में अन्य विषयों में कवर पेब्लिंग, इष्टतम पेब्लिंग, वर्चस्व कवर पेब्लिंग, सीमाएं और पेब्लिंग संख्याओं के लिए सीमाएं, साथ ही साथ गहरे ग्राफ शामिल हैं। π (G)-एक ग्राफ की कंकड़ संख्या कंकड़ के खेल का सुझाव सबसे पहले लगारियास और साक्स ने संख्या सिद्धांत में एक विशेष समस्या को हल करने के लिए एक उपकरण के रूप में दिया था। 1989 में एफ. आर. के. चुंग ने साहित्य में अवधारणा की शुरुआत की और कंकड़ संख्या, π (G) को परिभाषित किया। एन शीर्षों पर एक पूर्ण ग्राफ के लिए कंकड़ संख्या आसानी से एन होने के लिए सत्यापित की जाती हैः यदि हमारे पास ग्राफ पर रखने के लिए (एन-1) कंकड़ थे, तो हम लक्ष्य को छोड़कर प्रत्येक शीर्ष पर एक कंकड़ लगा सकते थे। चूँकि किसी भी शीर्ष में दो या अधिक कंकड़ नहीं होते हैं, इसलिए कोई चाल संभव नहीं है, इसलिए लक्ष्य पर कंकड़ रखना असंभव है। इस प्रकार, कंकड़ संख्या n-1 से अधिक होनी चाहिए। कंकड़ को देखते हुए, दो संभावित मामले हैं। यदि प्रत्येक शीर्ष में एक कंकड़ है, तो किसी चाल की आवश्यकता नहीं है। यदि कोई भी शीर्ष खुला है, तो कम से कम एक अन्य शीर्ष पर दो कंकड़ होने चाहिए, और एक कंकड़ चाल एक कंकड़ को पूरे ग्राफ में किसी भी लक्ष्य शीर्ष पर जोड़ने की अनुमति देती है। ग्राफ के परिवारों के लिए π (G) कंकड़ संख्या को ग्राफ के निम्नलिखित परिवारों के लिए जाना जाता हैः, जहाँ n शीर्षों पर एक पूर्ण ग्राफ है। , जहाँ n शीर्षों पर एक पथ ग्राफ है। , जहाँ n शीर्षों पर एक पहिया ग्राफ है। ग्राहम के कंकड़ अनुमान ने रोनाल्ड ग्राहम को इस अनुमान का श्रेय दिया कि ग्राफ के कार्टेशियन उत्पाद की कंकड़ संख्या उत्पाद में कारकों की कंकड़ संख्या के उत्पाद के बराबर है। यह ग्राहम के कंकड़ अनुमान के रूप में जाना जाने लगा है। यद्यपि विशेष मामले ज्ञात हैं, यह अभी भी अनसुलझा है। γ (G)-एक ग्राफ क्रुल एट अल की आवरण कंकड़ संख्या। आवरण कंकड़कारी की अवधारणा की शुरुआत की। γ (G), एक ग्राफ की आवरण कंकड़ संख्या कंकड़ की न्यूनतम संख्या है जिसकी आवश्यकता होती है ताकि कंकड़ की किसी भी प्रारंभिक व्यवस्था से, कंकड़ चालों की एक श्रृंखला के बाद, ग्राफ को कवर किया जाएः प्रत्येक शीर्ष पर कम से कम एक कंकड़ हो। स्टैकिंग थ्योरम नामक एक परिणाम किसी भी ग्राफ के लिए आवरण कंकड़ संख्या पाता है। स्टैकिंग थ्योरम स्टैकिंग थ्योरम के अनुसार, कंकड़ का प्रारंभिक विन्यास जिसमें सबसे अधिक कंकड़ को हल करने की आवश्यकता होती है, तब होता है जब सभी कंकड़ को एक ही शीर्ष पर रखा जाता है। इस अवलोकन के आधार पर, G में प्रत्येक शीर्ष v के लिए परिभाषित करें, जहाँ d (u, v) u से v तक की दूरी को दर्शाता है। ग्राफ के परिवारों के लिए γ (G) आवरण कंकड़ संख्या को ग्राफ के निम्नलिखित परिवारों के लिए जाना जाता हैः, जहाँ n शीर्षों पर एक पूर्ण ग्राफ है। , जहाँ n शीर्षों पर एक पथ है। , जहाँ n शीर्षों पर एक पहिया ग्राफ है। पेबल खेल अंतरिक्ष संदर्भों का प्रमाण आगे पढ़ने के लिए ग्राफ अपरिवर्तनीय भी देखें