Prüfer sequence
संयोजी गणित में, एक लेबल वाले पेड़ का प्रूफर अनुक्रम (प्रूफर कोड या प्रूफर संख्या भी) पेड़ से जुड़ा एक अनूठा अनुक्रम है। n शीर्षों पर एक वृक्ष के लिए अनुक्रम की लंबाई n-2 है, और इसे एक सरल पुनरावृत्ति एल्गोरिथ्म द्वारा उत्पन्न किया जा सकता है। प्रूफर अनुक्रमों का उपयोग पहली बार 1918 में केली के सूत्र को साबित करने के लिए हेंज प्रूफर द्वारा किया गया था। एक वृक्ष को प्रूफर अनुक्रम में बदलने के लिए एल्गोरिदम जब तक केवल दो शीर्ष नहीं रह जाते, तब तक वृक्ष से शीर्षों को बार-बार हटाकर एक लेबल वाले वृक्ष का प्रूफर अनुक्रम उत्पन्न किया जा सकता है। विशेष रूप से, शीर्ष {1,2,., n} के साथ एक लेबल वाले ट्री T पर विचार करें। चरण I में, सबसे छोटे लेबल वाले पत्ते को हटा दें और प्रूफर अनुक्रम के ith तत्व को इस पत्ते के पड़ोसी के लेबल के रूप में सेट करें। एक लेबल वाले पेड़ का प्रूफर अनुक्रम अद्वितीय है और इसकी लंबाई n-2 है। कोडिंग और डिकोडिंग दोनों को पूर्णांक रेडिक्स छँटाई और समानांतर में कम किया जा सकता है। उदाहरण ऊपर दिए गए एल्गोरिदम पर विचार करें जो दाईं ओर दिखाए गए ट्री पर चलता है। प्रारंभ में, शीर्ष 1 सबसे छोटे लेबल वाला पत्ता होता है, इसलिए इसे पहले हटा दिया जाता है और 4 को प्रूफर अनुक्रम में रखा जाता है। इसके बाद वर्टीस 2 और 3 को हटा दिया जाता है, इसलिए 4 को दो बार जोड़ा जाता है। वर्टेक्स 4 अब एक पत्ता है और इसमें सबसे छोटा लेबल है, इसलिए इसे हटा दिया जाता है और हम अनुक्रम में 5 जोड़ते हैं। हमारे पास केवल दो शीर्ष बचे हैं, इसलिए हम रुकते हैं। वृक्ष का अनुक्रम {4,4,4,5} है। प्रूफर अनुक्रम को वृक्ष में बदलने के लिए एल्गोरिदम मान लीजिए कि {a [1], a [2],., a [n]} एक प्रूफर अनुक्रम हैः वृक्ष में n + 2 नोड्स होंगे, जिनकी संख्या 1 से n + 2 तक होगी। प्रत्येक नोड के लिए अपनी डिग्री सेट करें कि यह अनुक्रम प्लस 1 में कितनी बार दिखाई देता है। उदाहरण के लिए, छद्म-कोड मेंः कनवर्ट-प्रूफर-टू-ट्री (ए) 1 एन-लंबाई [ए] 2 टी-एक ग्राफ जिसमें एन + 2 अलग-अलग नोड्स हैं, जिनकी संख्या 1 से एन + 2,3 डिग्री है-पूर्णांकों की एक सरणी 4 प्रत्येक नोड के लिए आई इन टी में 5 डिग्री करें [i] प्रत्येक मान के लिए आई में 7 डिग्री करें [i] <डिग्री [i] + 1 अगला, अनुक्रम में प्रत्येक संख्या के लिए ए [i], पहला (सबसे कम संख्या वाला) नोड खोजें, जे, 1 के बराबर डिग्री के साथ, ट्री में किनारे (जे, ए [i]) जोड़ें, और जे और एक [i] की डिग्री कम करें। स्यूडो-कोड मेंः 8 प्रत्येक मान के लिए i में प्रत्येक नोड के लिए 9 करें t में प्रत्येक नोड के लिए 10 करें यदि डिग्री [j] = 1 तो 11 T 12 डिग्री में किनारा [i, j] डालें [i]-13 डिग्री [j]-डिग्री [j]-1 14 ब्रेक इस लूप के अंत में डिग्री 1 के साथ दो नोड बने रहेंगे (उन्हें u, v कहें)। अंत में, पेड़ के किनारे (यू, वी) को जोड़ें। 15 टी 17 में प्रत्येक नोड आई के लिए, अगर डिग्री [i] = 1 है, तो 18 अगर यू = 0 है, तो 19 यू, आई 20 और 21 वी, आई 22 तोड़ते हैं 23 टी 24 डिग्री [यू] में किनारा [यू, वी] डालें [यू], डिग्री [यू]-1 25 डिग्री [वी], डिग्री [वी]-1 26 रिटर्न टी केले का सूत्र एन शीर्षों पर एक लेबल वाले पेड़ का प्रूफर अनुक्रम 1 से एन पर लंबाई एन-2 का एक अनूठा अनुक्रम है। 1 से एन लेबल पर लंबाई एन-2 के दिए गए अनुक्रम एस के लिए, एक अद्वितीय लेबल वाला पेड़ है जिसका प्रूफर अनुक्रम एस है। तत्काल परिणाम यह है कि प्रू कि n शीर्षों पर nn-2 लेबल वाले पेड़ हैं। अन्य अनुप्रयोगों केले के सूत्र को निम्नलिखित दावे को साबित करने के लिए मजबूत किया जा सकता हैः प्रत्येक शीर्ष के लिए निर्दिष्ट डिग्री के साथ एक पूर्ण ग्राफ में फैले हुए पेड़ों की संख्या बहुपद गुणांक के बराबर होती है। केले के सूत्र को सामान्यीकृत किया जा सकता हैः एक लेबल वाला पेड़ वास्तव में लेबल वाले पूर्ण ग्राफ का एक फैला हुआ पेड़ है। गणना किए गए प्रूफर अनुक्रमों पर प्रतिबंध लगाकर, इसी तरह के तरीके एक पूर्ण द्विदलीय ग्राफ के फैले हुए पेड़ों की संख्या दे सकते हैं। यदि G एक विभाजन में शीर्ष 1 से n1 और दूसरे विभाजन में शीर्ष n1 + 1 से n के साथ पूर्ण द्विदलीय ग्राफ है, तो G के लेबल किए गए फैले हुए पेड़ों की संख्या है, जहाँ n2 = n − n1 है। समान रूप से वितरित यादृच्छिक प्रूफर अनुक्रमों को उत्पन्न करना और उन्हें संबंधित पेड़ों में परिवर्तित करना समान रूप से वितरित यादृच्छिक लेबल वाले पेड़ों को उत्पन्न करने का एक सीधा तरीका है। संदर्भ बाहरी लिंक प्रूफर कोड-मैथवर्ल्ड एन्यूमरेटिव कॉम्बिनेटोरिक्स ट्रीज़ (ग्राफ थ्योरी) से