பன்மரம்

கோட்டுருவியலில் பன்மரம் (polytree)^[1] என்பது ஒரு திசையுள்ள சுழற்சியற்றக் கோட்டுருவாகும். பன்மரத்தில் அமைந்துள்ள திசையற்ற கோட்டுரு ஒரு மரமாக இருக்கும். பன்மரத்தின் திசையுள்ள விளிம்புகளைத் திசையில்லா விளிம்புகளாக மாற்றக் கிடைக்கும் கோட்டுருவானது இணைப்புள்ள சுழற்சியற்றக் கோட்டுருவாக, அதாவது மரமாக இருக்கும்.

பன்மரம்.

பன்மரமானது "திசை மரம்"^[2] என்றும் "திசைபோக்கு மரம்"^[3][4] என்றும் "ஒற்றை இணைப்பு வலையமைப்பு"^[5] என்றும் அழைக்கப்படுகிறது. திசைபோக்கு கோட்டுருவிற்கு பன்மரம் ஒரு எடுத்துக்காட்டாகும்.

பன்மரம் என்பதற்கு இணையான ஆங்கிலச் சொல்லான polytree, 1987 இல் ரெபனே மற்றும் ஜுடியா பேர்ல் ஆகியோரால் உருவாக்கப்பட்டது.^[6]

காட்டினைத் தன் அடிப்படைத் திசையற்ற கோட்டுருவாகக் கொண்ட திசையுள்ள சுழற்சியற்றக் கோட்டுருவானது "பல்காடு" என அழைக்கப்படும். பல்காட்டின் திசையுள்ள விளிம்புகளைத் திசையற்ற விளிம்புகளாக மாற்றினால் திசையற்ற சுழற்சியற்றக் கோட்டுருவான காடு கிடைக்கும்.

பல்காடானது "திசையுறு காடு" அல்லது "திசைப்போக்கு காடு" எனவும் அழைக்கப்படுகிறது.

கணக்கிடுதல்

n - பெயரிடப்படாத கணுக்களின் எண்ணிக்கை. n = 1, 2, 3, ..., ஆகிய மதிப்புகளுக்குக் கிடைக்கக்கூடிய வெவ்வேறான பன்மரங்களின் எண்ணிக்கை:

1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... (OEIS-இல் வரிசை A000238)

.

குறிப்புகள்

1. (Dasgupta 1999).
2. Deo 1974, ப. 206.
3. Harary & Sumner (1980).
4. (Simion 1991).
5. (Kim & Pearl 1983).
6. (Rebane & Pearl 1987).

மேற்கோள்கள்

• Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000), "Computing contour trees in all dimensions", in Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 918–926
• Dasgupta, Sanjoy (1999), "Learning polytrees", in Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July-August 1999 (PDF), pp. 134–141.
• Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF), Englewood, New Jersey: Prentice-Hall, பன்னாட்டுத் தரப்புத்தக எண் 0-13-363473-6.
• Harary, Frank; Sumner, David (1980), "The dichromatic number of an oriented tree", Journal of Combinatorics, Information & System Sciences, 5 (3): 184–187, MR 0603363.
• Kim, Jin H.; Pearl, Judea (1983), "A computational model for causal and diagnostic reasoning in inference engines", in Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983 (PDF), pp. 190–193.
• Kühn, Daniela; Mycroft, Richard; Osthus, Deryk (2011), "A proof of Sumner's universal tournament conjecture for large tournaments", Proceedings of the London Mathematical Society, Third Series, 102 (4): 731–766, arXiv:1010.4430, எண்ணிம ஆவணச் சுட்டி:10.1112/plms/pdq035, MR 2793448.
• Rebane, George; Pearl, Judea (1987), "The recovery of causal poly-trees from statistical data", in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987 (PDF), pp. 222–228 ^{[தொடர்பிழந்த இணைப்பு]}.
• Simion, Rodica (1991), "Trees with 1-factors and oriented trees", Discrete Mathematics (journal), 88 (1): 93–104, எண்ணிம ஆவணச் சுட்டி:10.1016/0012-365X(91)90061-6, MR 1099270.
• Trotter, William T., Jr.; Moore, John I., Jr. (1977), "The dimension of planar posets", Journal of Combinatorial Theory, Series B, 22 (1): 54–67, எண்ணிம ஆவணச் சுட்டி:10.1016/0095-8956(77)90048-X{{citation}}: CS1 maint: multiple names: authors list (link).