कॉप-विन ग्राफ: Difference between revisions
(Created page with "{{good article}} {{Short description|Type of graph related to pursuit–evasion}} ग्राफ सिद्धांत में, एक कॉप-विन ग्र...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Type of graph related to pursuit–evasion}} | {{Short description|Type of graph related to pursuit–evasion}} | ||
[[ग्राफ सिद्धांत]] में, | [[ग्राफ सिद्धांत]] में, कॉप-विन ग्राफ़ एक [[अप्रत्यक्ष ग्राफ]]़ होता है, जिस पर पीछा करने वाला (पुलिस) हमेशा एक लुटेरे के खिलाफ पीछा-चोरी का खेल जीत सकता है, जिसमें खिलाड़ी बारी-बारी से मोड़ लेते हैं, जिसमें वे एक किनारे के साथ चलना चुन सकते हैं। ग्राफ या डटे रहो, जब तक कि पुलिस वाला लुटेरे के शीर्ष पर न आ जाए।{{r|bn}} परिमित कॉप-विन ग्राफ़ को विघटित करने योग्य ग्राफ़ या निर्माण योग्य ग्राफ़ भी कहा जाता है, क्योंकि वे बार-बार एक वर्चस्व वाले शीर्ष को हटाकर नष्ट किए जा सकते हैं (जिसका पड़ोस (ग्राफ़ सिद्धांत) किसी अन्य शीर्ष के पड़ोस का एक सबसेट है) या इस तरह के शीर्ष को बार-बार जोड़कर बनाया गया . कॉप-विन ग्राफ़ को बहुपद समय में एक ग्रीडी एल्गोरिथ्म द्वारा पहचाना जा सकता है जो एक विखंडन क्रम का निर्माण करता है। इनमें [[कॉर्डल ग्राफ]]़ और वे ग्राफ़ सम्मिलित हैं जिनमें एक सार्वभौमिक शीर्ष होता है। | ||
== परिभाषाएँ == | == परिभाषाएँ == | ||
=== पीछा-चोरी === | === पीछा-चोरी === | ||
कॉप-विन ग्राफ़ को पीछा-चोरी के खेल द्वारा परिभाषित किया जा सकता है जिसमें दो खिलाड़ी, एक सिपाही और एक डाकू, एक दिए गए अप्रत्यक्ष ग्राफ़ के अलग-अलग प्रारंभिक शिखर पर स्थित होते हैं। पुलिस वाला पहले एक प्रारंभिक शीर्ष चुनता है, और फिर लुटेरा चुनता है। इसके बाद, वे बारी-बारी से खेलते हैं, फिर से पहले पुलिस वाले के साथ। प्रत्येक खिलाड़ी की बारी पर, खिलाड़ी या तो आसन्न शीर्ष पर जा सकता है या रुका रह सकता है। खेल समाप्त हो जाता है, और पुलिस वाला जीत जाता है, यदि पुलिस डाकू के समान शीर्ष पर एक मोड़ को समाप्त कर सकता है। पुलिस वाले को अनिश्चित काल के लिए चकमा देकर लुटेरा जीत जाता है। एक कॉप-विन ग्राफ संपत्ति के साथ एक ग्राफ है, जब खिलाड़ी | कॉप-विन ग्राफ़ को पीछा-चोरी के खेल द्वारा परिभाषित किया जा सकता है जिसमें दो खिलाड़ी, एक सिपाही और एक डाकू, एक दिए गए अप्रत्यक्ष ग्राफ़ के अलग-अलग प्रारंभिक शिखर पर स्थित होते हैं। पुलिस वाला पहले एक प्रारंभिक शीर्ष चुनता है, और फिर लुटेरा चुनता है। इसके बाद, वे बारी-बारी से खेलते हैं, फिर से पहले पुलिस वाले के साथ। प्रत्येक खिलाड़ी की बारी पर, खिलाड़ी या तो आसन्न शीर्ष पर जा सकता है या रुका रह सकता है। खेल समाप्त हो जाता है, और पुलिस वाला जीत जाता है, यदि पुलिस डाकू के समान शीर्ष पर एक मोड़ को समाप्त कर सकता है। पुलिस वाले को अनिश्चित काल के लिए चकमा देकर लुटेरा जीत जाता है। एक कॉप-विन ग्राफ संपत्ति के साथ एक ग्राफ है, जब खिलाड़ी प्रारंभिक स्थिति चुनते हैं और फिर इस तरह से आगे बढ़ते हैं, पुलिस हमेशा जीत को मजबूर कर सकती है। यदि एक अप्रत्यक्ष ग्राफ कॉप-विन ग्राफ नहीं है, तो इसे डाकू-जीत ग्राफ कहा जाता है।{{r|nw}} | ||
===निराकरण=== | ===निराकरण=== | ||
[[File:Dominated vertex.svg|thumb|इस ग्राफ में, वर्टेक्स {{mvar|v}} शीर्ष पर हावी है {{mvar|w}}: का बंद पड़ोस {{mvar|v}}, {{math|''N''[''v'']}} (आंतरिक छायांकित क्षेत्र) के बंद पड़ोस का एक सबसेट है {{mvar|w}}, {{math|''N''[''w'']}} (बाहरी छायांकित क्षेत्र)]]पड़ोस (ग्राफ सिद्धांत) {{math|''N''[''v'']}} एक शीर्ष का {{mvar|v}} किसी दिए गए ग्राफ़ में शीर्षों का समूह है जिसमें | [[File:Dominated vertex.svg|thumb|इस ग्राफ में, वर्टेक्स {{mvar|v}} शीर्ष पर हावी है {{mvar|w}}: का बंद पड़ोस {{mvar|v}}, {{math|''N''[''v'']}} (आंतरिक छायांकित क्षेत्र) के बंद पड़ोस का एक सबसेट है {{mvar|w}}, {{math|''N''[''w'']}} (बाहरी छायांकित क्षेत्र)]]पड़ोस (ग्राफ सिद्धांत) {{math|''N''[''v'']}} एक शीर्ष का {{mvar|v}} किसी दिए गए ग्राफ़ में शीर्षों का समूह है जिसमें सम्मिलित हैं {{mvar|v}} खुद और इसके आस-पास के सभी कोने {{mvar|v}}<nowiki>. शिखर {{mvar|v} कहा जाता है कि } किसी अन्य शीर्ष का प्रभुत्व है </nowiki>{{mvar|w}} कब {{math|''N''[''v''] ⊂ ''N''[''w'']}}. वह है, {{mvar|v}} और {{mvar|w}} आसन्न हैं, और के हर दूसरे पड़ोसी हैं {{mvar|v}} का भी पड़ोसी है {{mvar|w}}.{{r|c}} {{harvtxt|Nowakowski|Winkler|1983}} किसी ऐसे शीर्ष को कहते हैं जिस पर किसी अन्य शीर्ष का प्रभुत्व है, उसे इरेड्यूसिबल शीर्ष कहते हैं।{{r|nw}} | ||
किसी दिए गए ग्राफ़ का डिसमेंटलिंग ऑर्डर या डोमिनेशन एलिमिनेशन ऑर्डर वर्टिकल का ऐसा क्रम है कि, यदि इस क्रम में वर्टिकल को एक-एक करके हटा दिया जाता है, तो प्रत्येक वर्टेक्स (अंतिम को छोड़कर) को हटाते समय हावी हो जाता है। एक ग्राफ़ को विघटित किया जा सकता है यदि और केवल यदि उसका विखंडन क्रम हो।{{r|nw|c}} | किसी दिए गए ग्राफ़ का डिसमेंटलिंग ऑर्डर या डोमिनेशन एलिमिनेशन ऑर्डर वर्टिकल का ऐसा क्रम है कि, यदि इस क्रम में वर्टिकल को एक-एक करके हटा दिया जाता है, तो प्रत्येक वर्टेक्स (अंतिम को छोड़कर) को हटाते समय हावी हो जाता है। एक ग्राफ़ को विघटित किया जा सकता है यदि और केवल यदि उसका विखंडन क्रम हो।{{r|nw|c}} | ||
=== कॉप-विन और डिस्मैंटलेबिलिटी === | === कॉप-विन और डिस्मैंटलेबिलिटी की समानता === | ||
हर परिमित विघटित करने योग्य ग्राफ कॉप-विन है। यह आधार मामले के रूप में एक-शीर्ष ग्राफ (पुलिस द्वारा तुच्छ रूप से जीता गया) के साथ [[गणितीय प्रेरण]] द्वारा सिद्ध किया जा सकता है। एक बड़े ग्राफ के लिए, आइए {{mvar|v}} कोई भी वर्चस्व वाला शीर्ष हो। इंडक्शन परिकल्पना के अनुसार, पुलिस वाले को हटाकर बनाए गए ग्राफ पर जीतने की रणनीति है {{mvar|v}}, और मूल ग्राफ पर उसी रणनीति का पालन कर सकते हैं, यह दिखाते हुए कि डाकू उस शीर्ष पर है जो हावी है {{mvar|v}} जब भी डाकू वास्तव में चालू होता है {{mvar|v}}. इस रणनीति का पालन करने से या तो खेल की वास्तविक जीत होगी, या ऐसी स्थिति में जहां डाकू है {{mvar|v}} और पुलिस वाला हावी शीर्ष पर है, जिससे पुलिस वाला एक और चाल में जीत सकता है।{{r|nw}}{{sfnp|Bonato|Nowakowski|2011|loc=Theorem 2.3, page 32}} एक ग्राफ पर इस आगमनात्मक रणनीति का पालन करने वाला एक पुलिस वाला {{mvar|n}} शीर्ष अधिकतम लेता है {{mvar|n}} | हर परिमित विघटित करने योग्य ग्राफ कॉप-विन है। यह आधार मामले के रूप में एक-शीर्ष ग्राफ (पुलिस द्वारा तुच्छ रूप से जीता गया) के साथ [[गणितीय प्रेरण]] द्वारा सिद्ध किया जा सकता है। एक बड़े ग्राफ के लिए, आइए {{mvar|v}} कोई भी वर्चस्व वाला शीर्ष हो। इंडक्शन परिकल्पना के अनुसार, पुलिस वाले को हटाकर बनाए गए ग्राफ पर जीतने की रणनीति है {{mvar|v}}, और मूल ग्राफ पर उसी रणनीति का पालन कर सकते हैं, यह दिखाते हुए कि डाकू उस शीर्ष पर है जो हावी है {{mvar|v}} जब भी डाकू वास्तव में चालू होता है {{mvar|v}}. इस रणनीति का पालन करने से या तो खेल की वास्तविक जीत होगी, या ऐसी स्थिति में जहां डाकू है {{mvar|v}} और पुलिस वाला हावी शीर्ष पर है, जिससे पुलिस वाला एक और चाल में जीत सकता है।{{r|nw}}{{sfnp|Bonato|Nowakowski|2011|loc=Theorem 2.3, page 32}} एक ग्राफ पर इस आगमनात्मक रणनीति का पालन करने वाला एक पुलिस वाला {{mvar|n}} शीर्ष अधिकतम लेता है {{mvar|n}} प्रारम्भ करने की स्थिति पर ध्यान दिए बिना जीतने के लिए आगे बढ़ता है। पुलिस वाले की प्रारंभिक स्थिति को ध्यान से चुनकर, एक ही विचार का उपयोग यह साबित करने के लिए किया जा सकता है कि, एक में {{mvar|n}}-वर्टेक्स ग्राफ, पुलिस वाला अधिक से अधिक जीत दर्ज कर सकता है {{math|''n'' − 4}} चलता है।{{r|bgh|g}}{{sfnp|Bonato|Nowakowski|2011|p=36}} | ||
इसके विपरीत, हर कॉप-विन ग्राफ में एक वर्चस्व वाला शीर्ष होता है। क्योंकि, बिना वर्चस्व वाले शीर्षों वाले ग्राफ में, यदि लुटेरा पहले से ही हार नहीं गया है, तो पुलिस वाले के आस-पास की स्थिति के लिए एक सुरक्षित चाल है, और लुटेरा इन सुरक्षित चालों में से प्रत्येक पर खेलकर अनिश्चित काल तक खेल जारी रख सकता है। मोड़।{{r|nw}}{{sfnp|Bonato|Nowakowski|2011|loc=Lemma 2.1, page 31}} इसके अतिरिक्त, यदि {{mvar|v}} कॉप-विन ग्राफ़ में एक वर्चस्व वाला शीर्ष है, फिर हटा रहा है {{mvar|v}} को एक और कॉप-विन ग्राफ तैयार करना चाहिए, अन्यथा लुटेरा उस सबग्राफ के भीतर खेल सकता है, यह दिखाते हुए कि पुलिस वाले उस शीर्ष पर हैं जो हावी है {{mvar|v}} जब भी पुलिस वाला वास्तव में चालू होता है {{mvar|v}}, और कभी भी पकड़े न जाएँ। यह इन दो सिद्धांतों से प्रेरण द्वारा अनुसरण करता है कि प्रत्येक परिमित कॉप-विन ग्राफ विघटित करने योग्य है।{{r|nw}}{{sfnp|Bonato|Nowakowski|2011|loc=Theorem 2.2, page 32}} | इसके विपरीत, हर कॉप-विन ग्राफ में एक वर्चस्व वाला शीर्ष होता है। क्योंकि, बिना वर्चस्व वाले शीर्षों वाले ग्राफ में, यदि लुटेरा पहले से ही हार नहीं गया है, तो पुलिस वाले के आस-पास की स्थिति के लिए एक सुरक्षित चाल है, और लुटेरा इन सुरक्षित चालों में से प्रत्येक पर खेलकर अनिश्चित काल तक खेल जारी रख सकता है। मोड़।{{r|nw}}{{sfnp|Bonato|Nowakowski|2011|loc=Lemma 2.1, page 31}} इसके अतिरिक्त, यदि {{mvar|v}} कॉप-विन ग्राफ़ में एक वर्चस्व वाला शीर्ष है, फिर हटा रहा है {{mvar|v}} को एक और कॉप-विन ग्राफ तैयार करना चाहिए, अन्यथा लुटेरा उस सबग्राफ के भीतर खेल सकता है, यह दिखाते हुए कि पुलिस वाले उस शीर्ष पर हैं जो हावी है {{mvar|v}} जब भी पुलिस वाला वास्तव में चालू होता है {{mvar|v}}, और कभी भी पकड़े न जाएँ। यह इन दो सिद्धांतों से प्रेरण द्वारा अनुसरण करता है कि प्रत्येक परिमित कॉप-विन ग्राफ विघटित करने योग्य है।{{r|nw}}{{sfnp|Bonato|Nowakowski|2011|loc=Theorem 2.2, page 32}} | ||
| Line 38: | Line 38: | ||
== मान्यता एल्गोरिदम == | == मान्यता एल्गोरिदम == | ||
कई अलग-अलग रणनीतियों को यह जांचने के लिए जाना जाता है कि क्या कोई ग्राफ कॉप-विन है, और यदि ऐसा है तो पुलिस को ग्राफ़ में जीतने की अनुमति देने वाले एक विखंडन क्रम को खोजना। इनमें | कई अलग-अलग रणनीतियों को यह जांचने के लिए जाना जाता है कि क्या कोई ग्राफ कॉप-विन है, और यदि ऐसा है तो पुलिस को ग्राफ़ में जीतने की अनुमति देने वाले एक विखंडन क्रम को खोजना। इनमें ग्रीडी एल्गोरिदम सम्मिलित हैं, और कोने के साझा पड़ोसियों की गणना के आधार पर एक अधिक जटिल एल्गोरिदम सम्मिलित है। | ||
=== | === ग्रीडी एल्गोरिथ्म === | ||
एक साधारण | एक साधारण ग्रीडी एल्गोरिथ्म द्वारा एक विखंडन क्रम पाया जा सकता है जो किसी भी वर्चस्व वाले शीर्ष को बार-बार ढूंढता और हटाता है। यह प्रक्रिया सफल होती है, ग्राफ को एक शीर्ष तक कम करके, अगर और केवल अगर ग्राफ कॉप-विन है। इसलिए, विखंडन आदेश खोजने के लिए एक एल्गोरिथ्म प्रदान करने के साथ-साथ, यह विधि परीक्षण के लिए एक एल्गोरिथ्म प्रदान करती है कि क्या दिया गया ग्राफ कॉप-विन है। इस एल्गोरिथम के लिए एक तरीका यह है कि इसे हटाए जाने वाले वर्चस्व वाले शीर्षों को खोजने के लिए निम्न चरणों का पालन करना है: | ||
*ग्राफ़ में सभी त्रिभुज खोजें, और उन त्रिभुजों की संख्या गिनें जिनमें प्रत्येक किनारा भाग लेता है। | *ग्राफ़ में सभी त्रिभुज खोजें, और उन त्रिभुजों की संख्या गिनें जिनमें प्रत्येक किनारा भाग लेता है। | ||
* बार-बार एक शीर्ष खोजें {{mvar|v}} कि [[डिग्री (ग्राफ सिद्धांत)]] के बराबर कई त्रिभुजों में भाग लेने वाले किनारे का अंत बिंदु है {{mvar|v}} माइनस एक, हटाएं {{mvar|v}}, और त्रिकोण बनाने वाले प्रत्येक शेष किनारे के प्रति किनारे त्रिकोण को कम करें {{mvar|v}}. | * बार-बार एक शीर्ष खोजें {{mvar|v}} कि [[डिग्री (ग्राफ सिद्धांत)]] के बराबर कई त्रिभुजों में भाग लेने वाले किनारे का अंत बिंदु है {{mvar|v}} माइनस एक, हटाएं {{mvar|v}}, और त्रिकोण बनाने वाले प्रत्येक शेष किनारे के प्रति किनारे त्रिकोण को कम करें {{mvar|v}}. | ||
| Line 48: | Line 48: | ||
=== पड़ोसियों की गिनती === | === पड़ोसियों की गिनती === | ||
द्वारा एक वैकल्पिक और अधिक जटिल एल्गोरिथम {{harvtxt|Spinrad|2004}} में एक संख्या को बनाए रखना | द्वारा एक वैकल्पिक और अधिक जटिल एल्गोरिथम {{harvtxt|Spinrad|2004}} में एक संख्या को बनाए रखना सम्मिलित है जिसे प्रत्येक निकटवर्ती जोड़े के लिए घाटा कहा जाता है {{math|(''x'', ''y'')}}, जो के पड़ोसियों की संख्या की गणना करता है {{mvar|x}} के पड़ोसी नहीं हैं {{mvar|y}}. यदि अन्य शीर्षों को हटा देने के बाद यह संख्या शून्य हो जाती है, तब {{mvar|x}} का प्रभुत्व है {{mvar|y}} और हटाया भी जा सकता है। यह वास्तविक घाटे के सेट का निर्माण और रखरखाव करता है (पड़ोसी {{mvar|x}} के पड़ोसी नहीं हैं {{mvar|y}}) केवल जोड़े के लिए {{math|(''x'', ''y'')}} जिसके लिए घाटा छोटा है।{{r|s}} | ||
अपनी संगणनाओं को गति देने के लिए, स्पिनराड का एल्गोरिथ्म छोटे ब्लॉकों के बीच पड़ोसियों की गिनती के लिए एक सबरूटीन का उपयोग करता है {{math|log<sub>2</sub> ''n''}} शिखर। अगर {{mvar|B}} वर्टिकल का एक सेट है जिसे एल्गोरिथम ने एक ब्लॉक के रूप में चुना है, फिर किसी अन्य वर्टेक्स के लिए, उस वर्टेक्स के पड़ोसियों का सेट {{mvar|B}} को [[बाइनरी संख्या]] के रूप में दर्शाया जा सकता है {{math|log<sub>2</sub> ''n''}} बिट्स। ये संख्याएँ एल्गोरिथम को किसी भी दो शीर्षों के लिए गिनने की अनुमति देती हैं {{mvar|x}} और {{mvar|y}}, कितना {{mvar|B}} की कमी में योगदान देता है {{mvar|x}} और {{mvar|y}}, निरंतर समय में, [[बिटवाइज़ ऑपरेशन]] और टेबल लुकअप के संयोजन से। इस सबरूटीन का उपयोग करते हुए, एल्गोरिथम निम्नलिखित चरणों का पालन करता है: | अपनी संगणनाओं को गति देने के लिए, स्पिनराड का एल्गोरिथ्म छोटे ब्लॉकों के बीच पड़ोसियों की गिनती के लिए एक सबरूटीन का उपयोग करता है {{math|log<sub>2</sub> ''n''}} शिखर। अगर {{mvar|B}} वर्टिकल का एक सेट है जिसे एल्गोरिथम ने एक ब्लॉक के रूप में चुना है, फिर किसी अन्य वर्टेक्स के लिए, उस वर्टेक्स के पड़ोसियों का सेट {{mvar|B}} को [[बाइनरी संख्या]] के रूप में दर्शाया जा सकता है {{math|log<sub>2</sub> ''n''}} बिट्स। ये संख्याएँ एल्गोरिथम को किसी भी दो शीर्षों के लिए गिनने की अनुमति देती हैं {{mvar|x}} और {{mvar|y}}, कितना {{mvar|B}} की कमी में योगदान देता है {{mvar|x}} और {{mvar|y}}, निरंतर समय में, [[बिटवाइज़ ऑपरेशन]] और टेबल लुकअप के संयोजन से। इस सबरूटीन का उपयोग करते हुए, एल्गोरिथम निम्नलिखित चरणों का पालन करता है: | ||
| Line 56: | Line 56: | ||
** उन सभी सन्निकट जोड़ियों के लिए घाटा निर्धारित करें जिनमें सबसे अधिक घाटा हो {{math|log ''n''}} और जिनके पास पहले से ही इस सेट का निर्माण नहीं हुआ है। इस निर्माण को गति देने के लिए ब्लॉकों की प्रारंभिक प्रणाली का उपयोग किया जा सकता है। | ** उन सभी सन्निकट जोड़ियों के लिए घाटा निर्धारित करें जिनमें सबसे अधिक घाटा हो {{math|log ''n''}} और जिनके पास पहले से ही इस सेट का निर्माण नहीं हुआ है। इस निर्माण को गति देने के लिए ब्लॉकों की प्रारंभिक प्रणाली का उपयोग किया जा सकता है। | ||
**निम्न चरणों को दोहराएं {{math|log ''n''}} बार: | **निम्न चरणों को दोहराएं {{math|log ''n''}} बार: | ||
*** एक जोड़ी खोजें {{math|(''x'', ''y'')}} निर्मित लेकिन खाली घाटा सेट के साथ। यदि ऐसी कोई जोड़ी | *** एक जोड़ी खोजें {{math|(''x'', ''y'')}} निर्मित लेकिन खाली घाटा सेट के साथ। यदि ऐसी कोई जोड़ी उपस्थित नहीं है, तो ग्राफ कॉप-विन नहीं है; इस स्थिति में, एल्गोरिथम को निरस्त करें। | ||
*** वर्टेक्स हटाएं {{mvar|x}} | *** वर्टेक्स हटाएं {{mvar|x}} | ||
***निकालना {{mvar|x}} सभी निर्मित घाटा सेटों से जो इसका है। | ***निकालना {{mvar|x}} सभी निर्मित घाटा सेटों से जो इसका है। | ||
| Line 63: | Line 63: | ||
स्पिनराड इस एल्गोरिथम के लिए कुल समय बताता है {{math|''O''(''n''<sup>3</sup>/log ''n'')}}.{{r|s}} | स्पिनराड इस एल्गोरिथम के लिए कुल समय बताता है {{math|''O''(''n''<sup>3</sup>/log ''n'')}}.{{r|s}} | ||
=== अनंत | === अनंत ग्राफ में === | ||
[[अनंत ग्राफ]] के लिए कॉप-विन ग्राफ से जुड़े एल्गोरिथम समस्याओं की संगणना का भी अध्ययन किया गया है। अनंत रेखांकन के मामले में, संगणनीय अनगिनत अनंत रेखांकन का निर्माण संभव है, जिस पर एक सर्वज्ञ डाकू हमेशा किसी पुलिस वाले से बच सकता है, लेकिन जिसके लिए कोई एल्गोरिदम इस रणनीति का पालन नहीं कर सकता है। ये रेखांकन अनंत वृक्ष भी हो सकते हैं, जिनमें प्रति शीर्ष किनारों की एक सीमित संख्या होती है। कोनिग के लेम्मा के अनुसार, इस तरह के पेड़ के पास एक अनंत पथ होना चाहिए, और एक सर्वज्ञानी लुटेरा इस रास्ते पर पुलिस वाले से दूर चलकर जीत सकता है, लेकिन एक एल्गोरिद्म द्वारा रास्ता नहीं खोजा जा सकता है। इसके बजाय, डाकू के लिए चालें चुनने के लिए प्रत्येक एल्गोरिदम को एक पुलिस वाले द्वारा पीटा जा सकता है जो केवल लुटेरे की ओर अद्वितीय पथ के साथ पेड़ में चलता है। अनुरूप रूप से, संगणनीय अनंत कॉप-विन ग्राफ़ का निर्माण करना संभव है, जिस पर एक सर्वज्ञ पुलिस वाले के पास जीतने की रणनीति होती है जो हमेशा चालों की एक सीमित संख्या में समाप्त होती है, लेकिन जिसके लिए कोई एल्गोरिदम इस रणनीति का पालन नहीं कर सकता है। इस तरह के ग्राफ़ पर, पुलिस वाले के लिए चालें चुनने के लिए प्रत्येक एल्गोरिदम को लुटेरे द्वारा अनिश्चित काल के लिए टाला जा सकता है।{{r|stahl}} | [[अनंत ग्राफ]] के लिए कॉप-विन ग्राफ से जुड़े एल्गोरिथम समस्याओं की संगणना का भी अध्ययन किया गया है। अनंत रेखांकन के मामले में, संगणनीय अनगिनत अनंत रेखांकन का निर्माण संभव है, जिस पर एक सर्वज्ञ डाकू हमेशा किसी पुलिस वाले से बच सकता है, लेकिन जिसके लिए कोई एल्गोरिदम इस रणनीति का पालन नहीं कर सकता है। ये रेखांकन अनंत वृक्ष भी हो सकते हैं, जिनमें प्रति शीर्ष किनारों की एक सीमित संख्या होती है। कोनिग के लेम्मा के अनुसार, इस तरह के पेड़ के पास एक अनंत पथ होना चाहिए, और एक सर्वज्ञानी लुटेरा इस रास्ते पर पुलिस वाले से दूर चलकर जीत सकता है, लेकिन एक एल्गोरिद्म द्वारा रास्ता नहीं खोजा जा सकता है। इसके बजाय, डाकू के लिए चालें चुनने के लिए प्रत्येक एल्गोरिदम को एक पुलिस वाले द्वारा पीटा जा सकता है जो केवल लुटेरे की ओर अद्वितीय पथ के साथ पेड़ में चलता है। अनुरूप रूप से, संगणनीय अनंत कॉप-विन ग्राफ़ का निर्माण करना संभव है, जिस पर एक सर्वज्ञ पुलिस वाले के पास जीतने की रणनीति होती है जो हमेशा चालों की एक सीमित संख्या में समाप्त होती है, लेकिन जिसके लिए कोई एल्गोरिदम इस रणनीति का पालन नहीं कर सकता है। इस तरह के ग्राफ़ पर, पुलिस वाले के लिए चालें चुनने के लिए प्रत्येक एल्गोरिदम को लुटेरे द्वारा अनिश्चित काल के लिए टाला जा सकता है।{{r|stahl}} | ||
== | == ग्राफ के संबंधित परिवार == | ||
[[File:Universal vertex.svg|thumb|upright|इस ग्राफ में, {{mvar|u}} एक सार्वभौमिक शीर्ष है: यह अन्य सभी शीर्षों के निकट है]]प्रत्येक परिमित कॉर्डल ग्राफ एक विघटित करने योग्य ग्राफ है, और कॉर्डल ग्राफ का प्रत्येक उन्मूलन क्रम (शीर्षों का एक क्रम जिसमें प्रत्येक शीर्ष के बाद के पड़ोसी एक [[क्लिक (ग्राफ सिद्धांत)]] बनाते हैं) एक वैध विखंडन क्रम है। हालाँकि, अनंत कॉर्डल ग्राफ़ | [[File:Universal vertex.svg|thumb|upright|इस ग्राफ में, {{mvar|u}} एक सार्वभौमिक शीर्ष है: यह अन्य सभी शीर्षों के निकट है]]प्रत्येक परिमित कॉर्डल ग्राफ एक विघटित करने योग्य ग्राफ है, और कॉर्डल ग्राफ का प्रत्येक उन्मूलन क्रम (शीर्षों का एक क्रम जिसमें प्रत्येक शीर्ष के बाद के पड़ोसी एक [[क्लिक (ग्राफ सिद्धांत)]] बनाते हैं) एक वैध विखंडन क्रम है। हालाँकि, अनंत कॉर्डल ग्राफ़ उपस्थित हैं, और व्यास (ग्राफ़ सिद्धांत) दो के अनंत कॉर्डल ग्राफ़ भी हैं, जो कॉप-विन नहीं हैं।{{r|hlsw}}{{sfnp|Bonato|Nowakowski|2011|loc=Section 7.4, Infinite chordal graphs, pp. 178–182}} अन्य प्रकार के ग्राफ़ के लिए, उस प्रकार के अनंत कॉप-विन ग्राफ़ उपस्थित हो सकते हैं, भले ही कोई परिमित न हो; उदाहरण के लिए, यह [[शीर्ष-सकर्मक ग्राफ]] के लिए सही है जो पूर्ण ग्राफ़ नहीं हैं।{{sfnp|Bonato|Nowakowski|2011|loc=Section 7.5, Vertex-transitive cop-win graphs, pp. 182–187}} | ||
ग्राफ़ में सार्वभौमिक शीर्ष एक शीर्ष है {{mvar|u}} जो अन्य सभी शीर्षों के निकट है। जब भी किसी ग्राफ़ में एक सार्वभौमिक शीर्ष होता है, तो यह विघटित होता है, क्योंकि हर दूसरे शीर्ष पर सार्वभौमिक शीर्ष का प्रभुत्व होता है, और कोई भी शीर्ष आदेश जो सार्वभौमिक शीर्ष को अंतिम स्थान देता है, एक वैध विखंडन क्रम है। इसके विपरीत, [[लगभग सभी]] विघटित ग्राफ़ में एक सार्वभौमिक शीर्ष होता है, इस अर्थ में कि, सभी के बीच {{mvar|n}}-वर्टेक्स विघटित करने योग्य ग्राफ़, इन ग्राफ़ों का अंश जिसमें एक सार्वभौमिक शीर्ष होता है, सीमा में एक के रूप में जाता है {{mvar|n}} अनंत तक जाता है।{{r|bkp}} | |||
जब भी किसी ग्राफ़ में एक सार्वभौमिक शीर्ष होता है, तो यह विघटित होता है, क्योंकि हर दूसरे शीर्ष पर सार्वभौमिक शीर्ष का प्रभुत्व होता है, और कोई भी शीर्ष आदेश जो सार्वभौमिक शीर्ष को अंतिम स्थान देता है, एक वैध विखंडन क्रम है। इसके विपरीत, [[लगभग सभी]] विघटित ग्राफ़ में एक सार्वभौमिक शीर्ष होता है, इस अर्थ में कि, सभी के बीच {{mvar|n}}-वर्टेक्स विघटित करने योग्य ग्राफ़, इन ग्राफ़ों का अंश जिसमें एक सार्वभौमिक शीर्ष होता है, सीमा में एक के रूप में जाता है {{mvar|n}} अनंत तक जाता है।{{r|bkp}} | |||
[[साधारण बहुभुज]]ों के [[दृश्यता ग्राफ]] हमेशा पुलिस-जीत होते हैं। ये एक बहुभुज के कोने से परिभाषित ग्राफ हैं, एक किनारे के साथ जब भी दो कोने एक रेखा खंड से जुड़े हो सकते हैं जो बहुभुज के बाहर नहीं गुजरता है। (विशेष रूप से, पॉलीगॉन में आसन्न कोने भी ग्राफ़ में आसन्न होते हैं।) यहां तक कि जब पुलिस और डाकू को पॉलीगॉन के भीतर सीधी रेखा खंडों पर जाने की अनुमति दी जाती है, वर्टेक्स-टू-वर्टेक्स के बजाय, पुलिस वाला जीत सकता है हमेशा लुटेरे के सबसे छोटे रास्ते के पहले कदम पर चलते हैं। | [[साधारण बहुभुज]]ों के [[दृश्यता ग्राफ]] हमेशा पुलिस-जीत होते हैं। ये एक बहुभुज के कोने से परिभाषित ग्राफ हैं, एक किनारे के साथ जब भी दो कोने एक रेखा खंड से जुड़े हो सकते हैं जो बहुभुज के बाहर नहीं गुजरता है। (विशेष रूप से, पॉलीगॉन में आसन्न कोने भी ग्राफ़ में आसन्न होते हैं।) यहां तक कि जब पुलिस और डाकू को पॉलीगॉन के भीतर सीधी रेखा खंडों पर जाने की अनुमति दी जाती है, वर्टेक्स-टू-वर्टेक्स के बजाय, पुलिस वाला जीत सकता है हमेशा लुटेरे के सबसे छोटे रास्ते के पहले कदम पर चलते हैं। | ||
इस तरह की चाल बहुभुज के उस हिस्से को काट देती है जिस तक पहुँचने के लिए डाकू कभी भी दोगुना नहीं हो सकता। जब कॉप एक शीर्ष पर | इस तरह की चाल बहुभुज के उस हिस्से को काट देती है जिस तक पहुँचने के लिए डाकू कभी भी दोगुना नहीं हो सकता। जब कॉप एक शीर्ष पर प्रारम्भ होता है और लुटेरा शीर्षों के बीच चलने के लिए प्रतिबंधित होता है, तो यह रणनीति पुलिस को शीर्षों तक सीमित कर देती है, इसलिए यह दृश्यता ग्राफ के लिए एक मान्य जीत रणनीति है।{{r|lsv}} | ||
[[File:4-cube t3 B2.svg|thumb|upright=0.7|फाइव-वर्टेक्स [[ पहिया ग्राफ ]] कॉप-विन है लेकिन वंशानुगत रूप से कॉप-विन नहीं है।]]वंशानुगत रूप से कॉप-विन ग्राफ़ वे ग्राफ़ हैं जिनमें प्रत्येक [[आइसोमेट्री]] सबग्राफ कॉप-विन है। यह सभी कॉप-विन ग्राफ़ के लिए सत्य नहीं है; उदाहरण के लिए, फाइव-वर्टेक्स व्हील ग्राफ कॉप-विन है, लेकिन इसमें एक आइसोमेट्रिक 4-साइकिल है, जो कॉप-विन नहीं है, इसलिए यह व्हील ग्राफ वंशानुगत रूप से कॉप-विन नहीं है। वंशानुगत रूप से कॉप-विन ग्राफ़ ब्रिज किए गए ग्राफ़ के समान होते हैं, ग्राफ़ जिसमें लंबाई चार या उससे अधिक के प्रत्येक चक्र में एक शॉर्टकट होता है, चक्र की तुलना में ग्राफ़ में वर्टिकल की एक जोड़ी करीब होती है।{{r|af2}} एक कॉप-विन ग्राफ वंशानुगत रूप से कॉप-विन होता है यदि और केवल अगर इसमें न तो 4-चक्र और न ही 5-चक्र [[प्रेरित चक्र]] के रूप में होते हैं। वंशानुगत रूप से कॉप-विन ग्राफ़ के लिए, किसी भी चौड़ाई-प्रथम खोज का उत्क्रमण | चौड़ाई-प्रथम ट्रैवर्सल एक मान्य विखंडन क्रम है, जिससे यह अनुसरण करता है कि किसी भी शीर्ष को विखंडन क्रम के अंतिम शीर्ष के रूप में चुना जा सकता है।{{r|c2}} | [[File:4-cube t3 B2.svg|thumb|upright=0.7|फाइव-वर्टेक्स [[ पहिया ग्राफ ]] कॉप-विन है लेकिन वंशानुगत रूप से कॉप-विन नहीं है।]]वंशानुगत रूप से कॉप-विन ग्राफ़ वे ग्राफ़ हैं जिनमें प्रत्येक [[आइसोमेट्री]] सबग्राफ कॉप-विन है। यह सभी कॉप-विन ग्राफ़ के लिए सत्य नहीं है; उदाहरण के लिए, फाइव-वर्टेक्स व्हील ग्राफ कॉप-विन है, लेकिन इसमें एक आइसोमेट्रिक 4-साइकिल है, जो कॉप-विन नहीं है, इसलिए यह व्हील ग्राफ वंशानुगत रूप से कॉप-विन नहीं है। वंशानुगत रूप से कॉप-विन ग्राफ़ ब्रिज किए गए ग्राफ़ के समान होते हैं, ग्राफ़ जिसमें लंबाई चार या उससे अधिक के प्रत्येक चक्र में एक शॉर्टकट होता है, चक्र की तुलना में ग्राफ़ में वर्टिकल की एक जोड़ी करीब होती है।{{r|af2}} एक कॉप-विन ग्राफ वंशानुगत रूप से कॉप-विन होता है यदि और केवल अगर इसमें न तो 4-चक्र और न ही 5-चक्र [[प्रेरित चक्र]] के रूप में होते हैं। वंशानुगत रूप से कॉप-विन ग्राफ़ के लिए, किसी भी चौड़ाई-प्रथम खोज का उत्क्रमण | चौड़ाई-प्रथम ट्रैवर्सल एक मान्य विखंडन क्रम है, जिससे यह अनुसरण करता है कि किसी भी शीर्ष को विखंडन क्रम के अंतिम शीर्ष के रूप में चुना जा सकता है।{{r|c2}} | ||
| Line 302: | Line 301: | ||
}} | }} | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
Revision as of 21:29, 23 March 2023
ग्राफ सिद्धांत में, कॉप-विन ग्राफ़ एक अप्रत्यक्ष ग्राफ़ होता है, जिस पर पीछा करने वाला (पुलिस) हमेशा एक लुटेरे के खिलाफ पीछा-चोरी का खेल जीत सकता है, जिसमें खिलाड़ी बारी-बारी से मोड़ लेते हैं, जिसमें वे एक किनारे के साथ चलना चुन सकते हैं। ग्राफ या डटे रहो, जब तक कि पुलिस वाला लुटेरे के शीर्ष पर न आ जाए।[1] परिमित कॉप-विन ग्राफ़ को विघटित करने योग्य ग्राफ़ या निर्माण योग्य ग्राफ़ भी कहा जाता है, क्योंकि वे बार-बार एक वर्चस्व वाले शीर्ष को हटाकर नष्ट किए जा सकते हैं (जिसका पड़ोस (ग्राफ़ सिद्धांत) किसी अन्य शीर्ष के पड़ोस का एक सबसेट है) या इस तरह के शीर्ष को बार-बार जोड़कर बनाया गया . कॉप-विन ग्राफ़ को बहुपद समय में एक ग्रीडी एल्गोरिथ्म द्वारा पहचाना जा सकता है जो एक विखंडन क्रम का निर्माण करता है। इनमें कॉर्डल ग्राफ़ और वे ग्राफ़ सम्मिलित हैं जिनमें एक सार्वभौमिक शीर्ष होता है।
परिभाषाएँ
पीछा-चोरी
कॉप-विन ग्राफ़ को पीछा-चोरी के खेल द्वारा परिभाषित किया जा सकता है जिसमें दो खिलाड़ी, एक सिपाही और एक डाकू, एक दिए गए अप्रत्यक्ष ग्राफ़ के अलग-अलग प्रारंभिक शिखर पर स्थित होते हैं। पुलिस वाला पहले एक प्रारंभिक शीर्ष चुनता है, और फिर लुटेरा चुनता है। इसके बाद, वे बारी-बारी से खेलते हैं, फिर से पहले पुलिस वाले के साथ। प्रत्येक खिलाड़ी की बारी पर, खिलाड़ी या तो आसन्न शीर्ष पर जा सकता है या रुका रह सकता है। खेल समाप्त हो जाता है, और पुलिस वाला जीत जाता है, यदि पुलिस डाकू के समान शीर्ष पर एक मोड़ को समाप्त कर सकता है। पुलिस वाले को अनिश्चित काल के लिए चकमा देकर लुटेरा जीत जाता है। एक कॉप-विन ग्राफ संपत्ति के साथ एक ग्राफ है, जब खिलाड़ी प्रारंभिक स्थिति चुनते हैं और फिर इस तरह से आगे बढ़ते हैं, पुलिस हमेशा जीत को मजबूर कर सकती है। यदि एक अप्रत्यक्ष ग्राफ कॉप-विन ग्राफ नहीं है, तो इसे डाकू-जीत ग्राफ कहा जाता है।[2]
निराकरण
पड़ोस (ग्राफ सिद्धांत) N[v] एक शीर्ष का v किसी दिए गए ग्राफ़ में शीर्षों का समूह है जिसमें सम्मिलित हैं v खुद और इसके आस-पास के सभी कोने v. शिखर {{mvar|v} कहा जाता है कि } किसी अन्य शीर्ष का प्रभुत्व है w कब N[v] ⊂ N[w]. वह है, v और w आसन्न हैं, और के हर दूसरे पड़ोसी हैं v का भी पड़ोसी है w.[3] Nowakowski & Winkler (1983) किसी ऐसे शीर्ष को कहते हैं जिस पर किसी अन्य शीर्ष का प्रभुत्व है, उसे इरेड्यूसिबल शीर्ष कहते हैं।[2]
किसी दिए गए ग्राफ़ का डिसमेंटलिंग ऑर्डर या डोमिनेशन एलिमिनेशन ऑर्डर वर्टिकल का ऐसा क्रम है कि, यदि इस क्रम में वर्टिकल को एक-एक करके हटा दिया जाता है, तो प्रत्येक वर्टेक्स (अंतिम को छोड़कर) को हटाते समय हावी हो जाता है। एक ग्राफ़ को विघटित किया जा सकता है यदि और केवल यदि उसका विखंडन क्रम हो।[2][3]
कॉप-विन और डिस्मैंटलेबिलिटी की समानता
हर परिमित विघटित करने योग्य ग्राफ कॉप-विन है। यह आधार मामले के रूप में एक-शीर्ष ग्राफ (पुलिस द्वारा तुच्छ रूप से जीता गया) के साथ गणितीय प्रेरण द्वारा सिद्ध किया जा सकता है। एक बड़े ग्राफ के लिए, आइए v कोई भी वर्चस्व वाला शीर्ष हो। इंडक्शन परिकल्पना के अनुसार, पुलिस वाले को हटाकर बनाए गए ग्राफ पर जीतने की रणनीति है v, और मूल ग्राफ पर उसी रणनीति का पालन कर सकते हैं, यह दिखाते हुए कि डाकू उस शीर्ष पर है जो हावी है v जब भी डाकू वास्तव में चालू होता है v. इस रणनीति का पालन करने से या तो खेल की वास्तविक जीत होगी, या ऐसी स्थिति में जहां डाकू है v और पुलिस वाला हावी शीर्ष पर है, जिससे पुलिस वाला एक और चाल में जीत सकता है।[2][4] एक ग्राफ पर इस आगमनात्मक रणनीति का पालन करने वाला एक पुलिस वाला n शीर्ष अधिकतम लेता है n प्रारम्भ करने की स्थिति पर ध्यान दिए बिना जीतने के लिए आगे बढ़ता है। पुलिस वाले की प्रारंभिक स्थिति को ध्यान से चुनकर, एक ही विचार का उपयोग यह साबित करने के लिए किया जा सकता है कि, एक में n-वर्टेक्स ग्राफ, पुलिस वाला अधिक से अधिक जीत दर्ज कर सकता है n − 4 चलता है।[5][6][7]
इसके विपरीत, हर कॉप-विन ग्राफ में एक वर्चस्व वाला शीर्ष होता है। क्योंकि, बिना वर्चस्व वाले शीर्षों वाले ग्राफ में, यदि लुटेरा पहले से ही हार नहीं गया है, तो पुलिस वाले के आस-पास की स्थिति के लिए एक सुरक्षित चाल है, और लुटेरा इन सुरक्षित चालों में से प्रत्येक पर खेलकर अनिश्चित काल तक खेल जारी रख सकता है। मोड़।[2][8] इसके अतिरिक्त, यदि v कॉप-विन ग्राफ़ में एक वर्चस्व वाला शीर्ष है, फिर हटा रहा है v को एक और कॉप-विन ग्राफ तैयार करना चाहिए, अन्यथा लुटेरा उस सबग्राफ के भीतर खेल सकता है, यह दिखाते हुए कि पुलिस वाले उस शीर्ष पर हैं जो हावी है v जब भी पुलिस वाला वास्तव में चालू होता है v, और कभी भी पकड़े न जाएँ। यह इन दो सिद्धांतों से प्रेरण द्वारा अनुसरण करता है कि प्रत्येक परिमित कॉप-विन ग्राफ विघटित करने योग्य है।[2][9]
क्लोजर प्रॉपर्टीज
| a | b | c | d | e | f | g | h | ||
| 8 |    | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
गणितीय वस्तुओं के एक परिवार को ऑपरेशन के एक सेट के तहत क्लोजर (गणित) कहा जाता है यदि परिवार के सदस्यों को मिलाकर हमेशा उस परिवार के किसी अन्य सदस्य का उत्पादन होता है। उस अर्थ में, कॉप-विन ग्राफ़ का परिवार ग्राफ़ के मजबूत उत्पाद के अंतर्गत बंद है। मजबूत उत्पाद में प्रत्येक शीर्ष दो कारक ग्राफों में से प्रत्येक में शिखर की एक जोड़ी से मेल खाती है। पुलिस वाले दो पुलिस-जीत ग्राफों के एक मजबूत उत्पाद में जीत सकते हैं, सबसे पहले, इन दो कारक ग्राफों में से एक में जीतने के लिए खेलते हुए, एक जोड़ी तक पहुंचें जिसका पहला घटक डाकू के समान है। फिर, जोड़े में रहते हुए जिसका पहला घटक डाकू के समान है, पुलिस वाले दो कारकों में से दूसरे में जीतने के लिए खेल सकते हैं।[2][10] उदाहरण के लिए, राजा का ग्राफ, दो पथ ग्राफों का एक मजबूत उत्पाद, कॉप-विन है। इस ग्राफ पर, कोने एक शतरंज की बिसात के वर्गों के अनुरूप हैं, और पुलिस और डाकू दोनों शतरंज के खेल में एक राजा की तरह चलते हैं, एक वर्ग के लिए जो क्षैतिज, लंबवत या तिरछे आसन्न है। पुलिस वाले के लिए उत्पाद-आधारित रणनीति पहले लुटेरे के समान पंक्ति में जाने की होगी, और फिर लुटेरे के कॉलम की ओर बढ़ना होगा, जबकि प्रत्येक चरण में लुटेरे के समान पंक्ति में रहना होगा।[11]
यह सच नहीं है कि कॉप-विन ग्राफ का हर प्रेरित सबग्राफ कॉप-विन है। हालाँकि, कुछ विशेष प्रेरित सबग्राफ कॉप-विन बने रहते हैं। Nowakowski & Winkler (1983) ग्राफ के प्रत्यावर्तन को परिभाषित करें G इसके प्रेरित सबग्राफ में से एक पर H के शीर्ष से मानचित्रण होना G के शिखर तक H जो प्रत्येक शीर्ष को मैप करता है H खुद के लिए, और वह आसन्न कोने के प्रत्येक जोड़े को मैप करता है G या तो एक ही शीर्ष पर एक दूसरे के रूप में या आसन्न शीर्षों की एक जोड़ी में H. फिर कॉप-विन ग्राफ का परिवार रिट्रेक्शन के तहत बंद हो जाता है। ऐसा इसलिए है क्योंकि एक पुलिस वाला जीत सकता है H एक खेल का अनुकरण करके G. जब भी जीतने की रणनीति में G पुलिस वाले को बने रहने के लिए कहेगा, या एक किनारे का अनुसरण करने के लिए कहेगा जिसके अंतिम बिंदुओं को एक ही शीर्ष पर मैप किया गया है H, सिपाही अंदर रहता है H. और अन्य सभी मामलों में, पुलिस किनारे का अनुसरण करती है H जो एक विजयी बढ़त के पीछे हटने के तहत छवि है G.[2]
मान्यता एल्गोरिदम
कई अलग-अलग रणनीतियों को यह जांचने के लिए जाना जाता है कि क्या कोई ग्राफ कॉप-विन है, और यदि ऐसा है तो पुलिस को ग्राफ़ में जीतने की अनुमति देने वाले एक विखंडन क्रम को खोजना। इनमें ग्रीडी एल्गोरिदम सम्मिलित हैं, और कोने के साझा पड़ोसियों की गणना के आधार पर एक अधिक जटिल एल्गोरिदम सम्मिलित है।
ग्रीडी एल्गोरिथ्म
एक साधारण ग्रीडी एल्गोरिथ्म द्वारा एक विखंडन क्रम पाया जा सकता है जो किसी भी वर्चस्व वाले शीर्ष को बार-बार ढूंढता और हटाता है। यह प्रक्रिया सफल होती है, ग्राफ को एक शीर्ष तक कम करके, अगर और केवल अगर ग्राफ कॉप-विन है। इसलिए, विखंडन आदेश खोजने के लिए एक एल्गोरिथ्म प्रदान करने के साथ-साथ, यह विधि परीक्षण के लिए एक एल्गोरिथ्म प्रदान करती है कि क्या दिया गया ग्राफ कॉप-विन है। इस एल्गोरिथम के लिए एक तरीका यह है कि इसे हटाए जाने वाले वर्चस्व वाले शीर्षों को खोजने के लिए निम्न चरणों का पालन करना है:
- ग्राफ़ में सभी त्रिभुज खोजें, और उन त्रिभुजों की संख्या गिनें जिनमें प्रत्येक किनारा भाग लेता है।
- बार-बार एक शीर्ष खोजें v कि डिग्री (ग्राफ सिद्धांत) के बराबर कई त्रिभुजों में भाग लेने वाले किनारे का अंत बिंदु है v माइनस एक, हटाएं v, और त्रिकोण बनाने वाले प्रत्येक शेष किनारे के प्रति किनारे त्रिकोण को कम करें v.
के साथ एक ग्राफ में n कोने, m किनारों, और अध: पतन (ग्राफ सिद्धांत) d, इस प्रक्रिया को समय पर पूरा किया जा सकता है O(dm).[12]
पड़ोसियों की गिनती
द्वारा एक वैकल्पिक और अधिक जटिल एल्गोरिथम Spinrad (2004) में एक संख्या को बनाए रखना सम्मिलित है जिसे प्रत्येक निकटवर्ती जोड़े के लिए घाटा कहा जाता है (x, y), जो के पड़ोसियों की संख्या की गणना करता है x के पड़ोसी नहीं हैं y. यदि अन्य शीर्षों को हटा देने के बाद यह संख्या शून्य हो जाती है, तब x का प्रभुत्व है y और हटाया भी जा सकता है। यह वास्तविक घाटे के सेट का निर्माण और रखरखाव करता है (पड़ोसी x के पड़ोसी नहीं हैं y) केवल जोड़े के लिए (x, y) जिसके लिए घाटा छोटा है।[13]
अपनी संगणनाओं को गति देने के लिए, स्पिनराड का एल्गोरिथ्म छोटे ब्लॉकों के बीच पड़ोसियों की गिनती के लिए एक सबरूटीन का उपयोग करता है log2 n शिखर। अगर B वर्टिकल का एक सेट है जिसे एल्गोरिथम ने एक ब्लॉक के रूप में चुना है, फिर किसी अन्य वर्टेक्स के लिए, उस वर्टेक्स के पड़ोसियों का सेट B को बाइनरी संख्या के रूप में दर्शाया जा सकता है log2 n बिट्स। ये संख्याएँ एल्गोरिथम को किसी भी दो शीर्षों के लिए गिनने की अनुमति देती हैं x और y, कितना B की कमी में योगदान देता है x और y, निरंतर समय में, बिटवाइज़ ऑपरेशन और टेबल लुकअप के संयोजन से। इस सबरूटीन का उपयोग करते हुए, एल्गोरिथम निम्नलिखित चरणों का पालन करता है:
- शीर्षों के मनमाना विभाजन से ब्लॉक बनाएं, और प्रत्येक ब्लॉक में प्रत्येक शीर्ष के पड़ोसियों का प्रतिनिधित्व करने वाली संख्याएं खोजें।
- कोने के सभी आसन्न जोड़े के लिए घाटे की गणना करने के लिए ब्लॉक-काउंटिंग सबरूटीन का उपयोग करें।
- निम्न चरणों को तब तक दोहराएं जब तक कि सभी शीर्ष हटा न दिए जाएं:
- उन सभी सन्निकट जोड़ियों के लिए घाटा निर्धारित करें जिनमें सबसे अधिक घाटा हो log n और जिनके पास पहले से ही इस सेट का निर्माण नहीं हुआ है। इस निर्माण को गति देने के लिए ब्लॉकों की प्रारंभिक प्रणाली का उपयोग किया जा सकता है।
- निम्न चरणों को दोहराएं log n बार:
- एक जोड़ी खोजें (x, y) निर्मित लेकिन खाली घाटा सेट के साथ। यदि ऐसी कोई जोड़ी उपस्थित नहीं है, तो ग्राफ कॉप-विन नहीं है; इस स्थिति में, एल्गोरिथम को निरस्त करें।
- वर्टेक्स हटाएं x
- निकालना x सभी निर्मित घाटा सेटों से जो इसका है।
- के एक ब्लॉक का निर्माण log n इस ब्लॉक के भीतर अन्य सभी शीर्षों के आसन्न बिंदुओं का प्रतिनिधित्व करने वाले शीर्षों और संख्याओं को हटा दिया।
- सभी किनारों के लिए घाटे को अद्यतन करने के लिए, इस एक ब्लॉक पर ब्लॉक-काउंटिंग सबरूटीन का उपयोग करें।
स्पिनराड इस एल्गोरिथम के लिए कुल समय बताता है O(n3/log n).[13]
अनंत ग्राफ में
अनंत ग्राफ के लिए कॉप-विन ग्राफ से जुड़े एल्गोरिथम समस्याओं की संगणना का भी अध्ययन किया गया है। अनंत रेखांकन के मामले में, संगणनीय अनगिनत अनंत रेखांकन का निर्माण संभव है, जिस पर एक सर्वज्ञ डाकू हमेशा किसी पुलिस वाले से बच सकता है, लेकिन जिसके लिए कोई एल्गोरिदम इस रणनीति का पालन नहीं कर सकता है। ये रेखांकन अनंत वृक्ष भी हो सकते हैं, जिनमें प्रति शीर्ष किनारों की एक सीमित संख्या होती है। कोनिग के लेम्मा के अनुसार, इस तरह के पेड़ के पास एक अनंत पथ होना चाहिए, और एक सर्वज्ञानी लुटेरा इस रास्ते पर पुलिस वाले से दूर चलकर जीत सकता है, लेकिन एक एल्गोरिद्म द्वारा रास्ता नहीं खोजा जा सकता है। इसके बजाय, डाकू के लिए चालें चुनने के लिए प्रत्येक एल्गोरिदम को एक पुलिस वाले द्वारा पीटा जा सकता है जो केवल लुटेरे की ओर अद्वितीय पथ के साथ पेड़ में चलता है। अनुरूप रूप से, संगणनीय अनंत कॉप-विन ग्राफ़ का निर्माण करना संभव है, जिस पर एक सर्वज्ञ पुलिस वाले के पास जीतने की रणनीति होती है जो हमेशा चालों की एक सीमित संख्या में समाप्त होती है, लेकिन जिसके लिए कोई एल्गोरिदम इस रणनीति का पालन नहीं कर सकता है। इस तरह के ग्राफ़ पर, पुलिस वाले के लिए चालें चुनने के लिए प्रत्येक एल्गोरिदम को लुटेरे द्वारा अनिश्चित काल के लिए टाला जा सकता है।[14]
ग्राफ के संबंधित परिवार
प्रत्येक परिमित कॉर्डल ग्राफ एक विघटित करने योग्य ग्राफ है, और कॉर्डल ग्राफ का प्रत्येक उन्मूलन क्रम (शीर्षों का एक क्रम जिसमें प्रत्येक शीर्ष के बाद के पड़ोसी एक क्लिक (ग्राफ सिद्धांत) बनाते हैं) एक वैध विखंडन क्रम है। हालाँकि, अनंत कॉर्डल ग्राफ़ उपस्थित हैं, और व्यास (ग्राफ़ सिद्धांत) दो के अनंत कॉर्डल ग्राफ़ भी हैं, जो कॉप-विन नहीं हैं।[15][16] अन्य प्रकार के ग्राफ़ के लिए, उस प्रकार के अनंत कॉप-विन ग्राफ़ उपस्थित हो सकते हैं, भले ही कोई परिमित न हो; उदाहरण के लिए, यह शीर्ष-सकर्मक ग्राफ के लिए सही है जो पूर्ण ग्राफ़ नहीं हैं।[17]
ग्राफ़ में सार्वभौमिक शीर्ष एक शीर्ष है u जो अन्य सभी शीर्षों के निकट है। जब भी किसी ग्राफ़ में एक सार्वभौमिक शीर्ष होता है, तो यह विघटित होता है, क्योंकि हर दूसरे शीर्ष पर सार्वभौमिक शीर्ष का प्रभुत्व होता है, और कोई भी शीर्ष आदेश जो सार्वभौमिक शीर्ष को अंतिम स्थान देता है, एक वैध विखंडन क्रम है। इसके विपरीत, लगभग सभी विघटित ग्राफ़ में एक सार्वभौमिक शीर्ष होता है, इस अर्थ में कि, सभी के बीच n-वर्टेक्स विघटित करने योग्य ग्राफ़, इन ग्राफ़ों का अंश जिसमें एक सार्वभौमिक शीर्ष होता है, सीमा में एक के रूप में जाता है n अनंत तक जाता है।[18]
साधारण बहुभुजों के दृश्यता ग्राफ हमेशा पुलिस-जीत होते हैं। ये एक बहुभुज के कोने से परिभाषित ग्राफ हैं, एक किनारे के साथ जब भी दो कोने एक रेखा खंड से जुड़े हो सकते हैं जो बहुभुज के बाहर नहीं गुजरता है। (विशेष रूप से, पॉलीगॉन में आसन्न कोने भी ग्राफ़ में आसन्न होते हैं।) यहां तक कि जब पुलिस और डाकू को पॉलीगॉन के भीतर सीधी रेखा खंडों पर जाने की अनुमति दी जाती है, वर्टेक्स-टू-वर्टेक्स के बजाय, पुलिस वाला जीत सकता है हमेशा लुटेरे के सबसे छोटे रास्ते के पहले कदम पर चलते हैं। इस तरह की चाल बहुभुज के उस हिस्से को काट देती है जिस तक पहुँचने के लिए डाकू कभी भी दोगुना नहीं हो सकता। जब कॉप एक शीर्ष पर प्रारम्भ होता है और लुटेरा शीर्षों के बीच चलने के लिए प्रतिबंधित होता है, तो यह रणनीति पुलिस को शीर्षों तक सीमित कर देती है, इसलिए यह दृश्यता ग्राफ के लिए एक मान्य जीत रणनीति है।[19]
वंशानुगत रूप से कॉप-विन ग्राफ़ वे ग्राफ़ हैं जिनमें प्रत्येक आइसोमेट्री सबग्राफ कॉप-विन है। यह सभी कॉप-विन ग्राफ़ के लिए सत्य नहीं है; उदाहरण के लिए, फाइव-वर्टेक्स व्हील ग्राफ कॉप-विन है, लेकिन इसमें एक आइसोमेट्रिक 4-साइकिल है, जो कॉप-विन नहीं है, इसलिए यह व्हील ग्राफ वंशानुगत रूप से कॉप-विन नहीं है। वंशानुगत रूप से कॉप-विन ग्राफ़ ब्रिज किए गए ग्राफ़ के समान होते हैं, ग्राफ़ जिसमें लंबाई चार या उससे अधिक के प्रत्येक चक्र में एक शॉर्टकट होता है, चक्र की तुलना में ग्राफ़ में वर्टिकल की एक जोड़ी करीब होती है।[20] एक कॉप-विन ग्राफ वंशानुगत रूप से कॉप-विन होता है यदि और केवल अगर इसमें न तो 4-चक्र और न ही 5-चक्र प्रेरित चक्र के रूप में होते हैं। वंशानुगत रूप से कॉप-विन ग्राफ़ के लिए, किसी भी चौड़ाई-प्रथम खोज का उत्क्रमण | चौड़ाई-प्रथम ट्रैवर्सल एक मान्य विखंडन क्रम है, जिससे यह अनुसरण करता है कि किसी भी शीर्ष को विखंडन क्रम के अंतिम शीर्ष के रूप में चुना जा सकता है।[21]
बड़ी संख्या में पुलिस वाले एक समान गेम का उपयोग ग्राफ की पुलिस संख्या को परिभाषित करने के लिए किया जा सकता है, गेम जीतने के लिए आवश्यक पुलिस की सबसे छोटी संख्या। कॉप-विन ग्राफ़ बिल्कुल एक के बराबर कॉप संख्या के ग्राफ़ हैं।[22] बोनाटो और नोवाकोव्स्की ने इस खेल का वर्णन सहज रूप से भूतों की संख्या के रूप में किया है, जिसकी आवश्यकता पीएसी-मैन खिलाड़ी को खेलने के क्षेत्र के रूप में दिए गए ग्राफ का उपयोग करके हारने के लिए मजबूर करने के लिए होगी।[23] कॉप नंबर को परिभाषित करने के लिए उपयोग किए जाने वाले गेम को पेड़ की चौड़ाई की एक परिभाषा में उपयोग किए जाने वाले एक अलग पुलिस-और-लुटेरे गेम से अलग किया जाना चाहिए, जो पुलिस को ग्राफ़ किनारों के साथ यात्रा करने की आवश्यकता के बजाय मनमाने ढंग से शीर्ष पर जाने की अनुमति देता है।[24]
इतिहास
सिंगल कॉप वाला गेम और इससे परिभाषित कॉप-विन ग्राफ किसके द्वारा पेश किए गए थे? Quilliot (1978).[25][26] एक अन्य प्रारंभिक संदर्भ का कार्य है Nowakowski & Winkler (1983), जिन्हें जी. गाबोर द्वारा खेल से परिचित कराया गया था।[2][26] एकाधिक पुलिस वाले खेल, और इससे परिभाषित पुलिस संख्या का अध्ययन सबसे पहले किसके द्वारा किया गया था? Aigner & Fromme (1984).[22][26]
संदर्भ
- ↑ Bonato, Anthony; Nowakowski, Richard J. (2011), The Game of Cops and Robbers on Graphs, Student Mathematical Library, vol. 61, Providence, RI: American Mathematical Society, doi:10.1090/stml/061, ISBN 978-0-8218-5347-4, MR 2830217
- ↑ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 Nowakowski, Richard; Winkler, Peter (1983), "Vertex-to-vertex pursuit in a graph", Discrete Mathematics, 43 (2–3): 235–239, doi:10.1016/0012-365X(83)90160-7, MR 0685631
- ↑ 3.0 3.1 Chepoi, Victor (1998), "On distance-preserving and domination elimination orderings", SIAM Journal on Discrete Mathematics, 11 (3): 414–436, doi:10.1137/S0895480195291230, MR 1628110
- ↑ Bonato & Nowakowski (2011), Theorem 2.3, page 32.
- ↑ Bonato, A.; Golovach, P.; Hahn, G.; Kratochvíl, J. (2009), "The capture time of a graph", Discrete Mathematics, 309 (18): 5588–5595, doi:10.1016/j.disc.2008.04.004, MR 2567962
- ↑ Gavenčiak, Tomáš (2010), "Cop-win graphs with maximum capture-time", Discrete Mathematics, 310 (10–11): 1557–1563, doi:10.1016/j.disc.2010.01.015, MR 2601265
- ↑ Bonato & Nowakowski (2011), p. 36.
- ↑ Bonato & Nowakowski (2011), Lemma 2.1, page 31.
- ↑ Bonato & Nowakowski (2011), Theorem 2.2, page 32.
- ↑ Bonato & Nowakowski (2011), Theorem 2.8, page 43.
- ↑ For the fact that a strong product of paths is cop-win, see Nowakowski & Winkler (1983). For the fact that the king's graph is a strong product of paths, see Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), "Two-anticoloring of planar and related graphs" (PDF), 2005 International Conference on Analysis of Algorithms, Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, pp. 335–341, MR 2193130
- ↑ Lin, Min Chih; Soulignac, Francisco J.; Szwarcfiter, Jayme L. (2012), "Arboricity, h-index, and dynamic algorithms", Theoretical Computer Science, 426–427: 75–90, arXiv:1005.2211, doi:10.1016/j.tcs.2011.12.006, MR 2891574, S2CID 15827218
- ↑ 13.0 13.1 Spinrad, Jeremy P. (2004), "Recognizing quasi-triangulated graphs", Discrete Applied Mathematics, 138 (1–2): 203–213, doi:10.1016/S0166-218X(03)00295-6, MR 2057611
- ↑ Stahl, Rachel D. (September 2021), "Computability and the game of cops and robbers on graphs", Archive for Mathematical Logic, 61 (3–4): 373–397, doi:10.1007/s00153-021-00794-3, S2CID 244214571
- ↑ Hahn, Geňa; Laviolette, François; Sauer, Norbert; Woodrow, Robert E. (2002), "On cop-win graphs", Discrete Mathematics, 258 (1–3): 27–41, doi:10.1016/S0012-365X(02)00260-1, MR 2002070
- ↑ Bonato & Nowakowski (2011), Section 7.4, Infinite chordal graphs, pp. 178–182.
- ↑ Bonato & Nowakowski (2011), Section 7.5, Vertex-transitive cop-win graphs, pp. 182–187.
- ↑ Bonato, Anthony; Kemkes, Graeme; Prałat, Paweł (2012), "Almost all cop-win graphs contain a universal vertex", Discrete Mathematics, 312 (10): 1652–1657, doi:10.1016/j.disc.2012.02.018, MR 2901161
- ↑ Lubiw, Anna; Snoeyink, Jack; Vosoughpour, Hamideh (2017), "Visibility graphs, dismantlability, and the cops and robbers game", Computational Geometry, 66: 14–27, arXiv:1601.01298, doi:10.1016/j.comgeo.2017.07.001, MR 3693353
- ↑ Anstee, R. P.; Farber, M. (1988), "On bridged graphs and cop-win graphs", Journal of Combinatorial Theory, Series B, 44 (1): 22–28, doi:10.1016/0095-8956(88)90093-7, MR 0923263
- ↑ Chepoi, Victor (1997), "Bridged graphs are cop-win graphs: an algorithmic proof", Journal of Combinatorial Theory, Series B, 69 (1): 97–100, doi:10.1006/jctb.1996.1726, MR 1426753
- ↑ 22.0 22.1 Aigner, M.; Fromme, M. (1984), "A game of cops and robbers", Discrete Applied Mathematics, 8 (1): 1–11, doi:10.1016/0166-218X(84)90073-8, MR 0739593
- ↑ Bonato & Nowakowski (2011), pp. 1–3.
- ↑ Seymour, Paul D.; Thomas, Robin (1993), "Graph searching and a min-max theorem for tree-width", Journal of Combinatorial Theory, Series B, 58 (1): 22–33, doi:10.1006/jctb.1993.1027
- ↑ Quilliot, Alain (1978), Jeux et pointes fixes sur les graphes [Games and fixed points on graphs], Thèse de 3ème cycle (in français), Pierre and Marie Curie University, pp. 131–145, as cited by Bonato & Nowakowski (2011)
- ↑ 26.0 26.1 26.2 Bonato & Nowakowski (2011), p. 4.
बाहरी संबंध
- Dismantlable graphs, Information System on Graph Classes and their Inclusions
