அமில்தோன் பாதை

கோட்டுருவியலில் அமில்தோன் பாதை (Hamiltonian path) அல்லது கடக்கக்கூடிய பாதை (traceable path) என்பது ஒரு திசையற்ற கோட்டுரு அல்லது திசை கோட்டுருவில் அதன் ஒவ்வொரு முனையையும் ஒரேயொரு முறை மட்டுமே கடக்கும் ஒரு பாதையைக் குறிக்கும்.

ஒரு சுழற்சியாக அமையும் அமில்தோன் பாதையானது அமில்தோன் சுழற்சி (Hamiltonian cycle) அல்லது அமில்தோன் சுற்று (Hamiltonian circuit) என அழைக்கப்படும்.

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

அமில்தோன் பாதைகளும் சுழற்சிகளும் அயர்லாந்து கணிதவியலாளர் வில்லியம் ரோவன் அமில்தோன் பெயரால் அழைக்கப்படுகின்றன. இவர் பன்னிரண்டுமுக ஐங்கோணகத்தின் விளிம்புக் கோட்டுருவில் இருக்கக்கூடிய அமில்தோன் சுழற்சிகளைக் கண்டறியும் புதிரைக் கண்டுபிடித்தவர். இப்புதிர் "அமில்தோன் புதிர்" ("அய்கோசிய விளையாட்டு") என அறியப்படுகிறது. ஒன்றின் படிமூலங்களை அடிப்படையாகக் கொண்ட இயற்கணித அமைப்பான அய்கோசிய நுண்கணிதம் மூலம் இப்புதிருக்கான விடையைக் கண்டுபிடித்துள்ளார்.

அமில்தோன் பெயரால் இவை அழைக்கப்பட்டாலும் ஓராண்டு காலத்துக்கு முன்னரே பன்முகிகளில் இருக்கக்கூடிய அமில்தோன் சுழற்சிகளைக் குறித்து பிரித்தானிய கணிதவியலாளரான தாமசு கிர்க்மன் (Thomas Kirkman) ஆய்வு செய்து அமில்தோன் சுழற்சிகளற்ற பன்முகி ஒன்றையும் எடுத்துக்காட்டாக அளித்தார்.^[1] இதற்கும் முன்பாகவே ஒன்பதாம் நூற்றாண்டில் இந்தியக் கணிதவியலாளர் ருத்தரத்தர் சதுரங்கப்பலகையின் வீரனின் கோட்டுருவிலுள்ள அமில்தோன் பாதை மற்றும் சுழற்சிகள் குறித்து ஆய்வு மேற்கொண்டுள்ளார். அதே சமயத்தில் அல்-அட்லி அர்-ருமியின் இசுலாமியக் கணிதத்திலும் இது குறித்த ஆய்வுகள் நடத்தப்பட்டுள்ளன. 18 ஆம் நூற்றாண்டில் ஐரோப்பாவில் கணிதவியலாளர்கள் டிமாவர் மற்றும் ஆய்லர் ஆகிய இரு கணிதவியலாளர்களும் "வீரனின் உலா"க்களை வெளியிட்டனர்.^[2]

வரையறைகள்

"அமில்தோன் பாதை" அல்லது "கடக்கக்கூடிய பாதை" என்பது ஒரு கோட்டுருவின் ஒவ்வொரு முனையையும் ஒரேயொரு முறை மட்டுமே கடக்கும் பாதை ஆகும். அமில்தோன் பாதையுள்ள கோட்டுருவானது "கடக்கக்கூடிய கோட்டுரு" எனப்படும். ஒரு கோட்டுருவின் முனைகளின் ஒவ்வொரு இருமத்திற்கு இடையே ஒரு அமில்தோன் பாதை இருக்குமானால் அக்கோட்டுரு "அமில்தோன்-இணைப்பு"ள்ளதாகும்.

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

இதேபோல் திசை கோட்டுருக்களுக்கும் அமில்தோன் பாதை மற்றும் சுழற்சி இரண்டையும் வரையறுக்கலாம். ஆனால் பாதை அல்லது சுழற்சிகளிலுள்ள விளிம்புகளை ஒரே திசையில்தான் கடக்க முடியும்.

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

எடுத்துக்காட்டுகள்

இரண்டுக்கு மேற்பட்ட முனைகள் கொண்ட ஒரு முழுக்கோட்டுரு, அமில்தோன் கோட்டுருவாக இருக்கும்.
ஒவ்வொரு சுழற்சி கோட்டுருவும் அமில்தோன் கோட்டுரு.
ஒவ்வொரு பிளேட்டோவின் சீர்திண்மமும் கோட்டுருவாக எடுத்துக்கொள்ளப்படும்போது அமில்தோன் கோட்டுருவாக இருக்கும்^[5]
முடிவுறு கோசிட்டர் குலத்தின் கெய்லி கோட்டுரு ஒரு அமில்தோன் கோட்டுரு ஆகும்.

பண்புகள்

அமில்தோன் சுழற்சியில்லாத மிகச்சிறிய பன்முகக் கோட்டுருவான ஏர்ச்செல்கோட்டுரு. அதிலுள்ள அமில்தோன் பாதை காட்டப்பட்டுள்ளது.

ஒரு கோட்டுருவின் அமில்தோன் சுழற்சியிலுள்ள ஏதேனுமொரு விளிம்பை நீக்குவதன் மூலம் அதனை அமில்தோன் பாதை ஆக்கலாம். ஆனால் ஒரு அமில்தோன் பாதையின் இறுதிமுனைகள் அடுத்துள்ளவையாக இருந்தால் மட்டுமே அதனை அமில்தோன் சுழற்சியாக நீட்டிக்க முடியும்.
அனைத்து அமில்தோன் கோட்டுருக்களும் ஈரிணைப்புக் கோட்டுருக்கள்; ஆனால் ஒரு ஈரிணைப்புக் கோட்டுருவானது அமில்தோன் கோட்டுருவாக இருக்கவேண்டியதில்லை.^[6]
G ஒரு ஆய்லர் கோட்டுரு (G ஒரு இணைப்புள்ள கோட்டுருவாகவும் அதன் முனைகள் அனைத்தும் இரட்டையெண் படிகொண்டும் இருக்கும்) எனில் அதில் அவசியமொரு ஆய்லர் சுற்று இருக்கும். இச்சுற்று G இன் ஒவ்வொரு விளிம்பின் வழியாகவும் ஒரேயொரு முறை மட்டுமே செல்லும். இது G இன் வரிக் கோட்டுரு L(G) இலுள்ள ஒரு அமில்தோன் சுழற்சிக்கு ஒத்ததாக இருக்கும். கோடு கோட்டுருக்களில் ஆய்லர் சுற்றுக்களுக்கு ஒத்தற்ற வேறு அமில்தோன் சுழற்சிகளும் இருக்கலாம். குறிப்பாக G ஒரு (G ஆய்லர் கோட்டுருவாக இருந்தாலும் இல்லாவிட்டாலும்) அமில்தோன் கோட்டுரு எனில், அதன் வரிக் கோட்டுரு L(G) உம் அமில்தோன் கோட்டுருவாக இருக்கும்.^[7]
n முனைகள் கொண்ட திசையற்ற முழுக்கோட்டுருவிலுள்ள வேறுபட்ட அமில்தோன் சுழற்சிகளின் எண்ணிக்கை (n − 1)! ஆகும். இந்த எண்ணிக்கையில் துவக்க முனையை மட்டும் வெவ்வேறாகக் கொண்ட ஒரேமாதிரியான சுழற்சிகள் தனித்தனியாக எண்ணப்படவில்லை.

குறிப்புகள்

↑ Biggs, N. L. (1981), "T. P. Kirkman, mathematician", The Bulletin of the London Mathematical Society, 13 (2): 97–120, எண்ணிம ஆவணச் சுட்டி:10.1112/blms/13.2.97, MR 0608093.
↑ Watkins, John J. (2004), "Chapter 2: Knight's Tours", Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, pp. 25–38, பன்னாட்டுத் தரப்புத்தக எண் 978-0-691-15498-5.
↑ de Ruiter, Johan (2017). Hamilton Mazes - The Beginner's Guide.
↑ Friedman, Erich (2009). "Hamiltonian Mazes". Erich's Puzzle Palace. Archived from the original on 16 April 2016. பார்க்கப்பட்ட நாள் 27 May 2017.
↑ Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150–156, May 1957
↑ Eric Weinstein. "Biconnected Graph". Wolfram MathWorld.
↑ Balakrishnan, R.; Ranganathan, K. (2012), "Corollary 6.5.5", A Textbook of GraphTheory, Springer, p. 134, பன்னாட்டுத் தரப்புத்தக எண் 9781461445296.

மேற்கோள்கள்

Berge, Claude; Ghouila-Houiri, A. (1962), Programming, games and transportation networks, New York: Sons, Inc.
DeLeon, Melissa (2000), "A study of sufficient conditions for Hamiltonian cycles" (PDF), Rose-Hulman Undergraduate Math Journal, 1 (1), archived from the original (PDF) on 2012-12-22, பார்க்கப்பட்ட நாள் 2005-11-28.
Dirac, G. A. (1952), "Some theorems on abstract graphs", Proceedings of the London Mathematical Society, 3rd Ser., 2: 69–81, எண்ணிம ஆவணச் சுட்டி:10.1112/plms/s3-2.1.69, MR 0047308.
Hamilton, William Rowan (1856), "Memorandum respecting a new system of roots of unity", Philosophical Magazine, 12: 446.
Hamilton, William Rowan (1858), "Account of the Icosian Calculus", Proceedings of the Royal Irish Academy, 6: 415–416.
Meyniel, M. (1973), "Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté", Journal of Combinatorial Theory, Series B, 14 (2): 137–147, எண்ணிம ஆவணச் சுட்டி:10.1016/0095-8956(73)90057-9, MR 0317997.
Ore, Øystein (1960), "Note on Hamilton circuits", The American Mathematical Monthly, 67 (1): 55, எண்ணிம ஆவணச் சுட்டி:10.2307/2308928, JSTOR 2308928, MR 0118683.
Pósa, L. (1962), "A theorem concerning Hamilton lines", Magyar Tud. Akad. Mat. Kutató Int. Közl., 7: 225–226, MR 0184876.
Whitney, Hassler (1931), "A theorem on graphs", Annals of Mathematics, Second Series, 32 (2): 378–390, எண்ணிம ஆவணச் சுட்டி:10.2307/1968197, JSTOR 1968197, MR 1503003.
Tutte, W. T. (1956), "A theorem on planar graphs", Trans. Amer. Math. Soc., 82: 99–116, எண்ணிம ஆவணச் சுட்டி:10.1090/s0002-9947-1956-0081471-8.
Kogan, Grigoriy (1996), "Computing permanents over fields of characteristic 3: where and why it becomes difficult", 37th Annual Symposium on Foundations of Computer Science (FOCS '96): 108–114, எண்ணிம ஆவணச் சுட்டி:10.1109/SFCS.1996.548469, பன்னாட்டுத் தரப்புத்தக எண் 0-8186-7594-2

வெளியிணைப்புகள்

Weisstein, Eric W., "Hamiltonian Cycle", MathWorld.
Euler tour and Hamilton cycles

[1] Biggs, N. L. (1981), "T. P. Kirkman, mathematician", The Bulletin of the London Mathematical Society, 13 (2): 97–120, எண்ணிம ஆவணச் சுட்டி:10.1112/blms/13.2.97, MR 0608093.

[2] Watkins, John J. (2004), "Chapter 2: Knight's Tours", Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, pp. 25–38, பன்னாட்டுத் தரப்புத்தக எண் 978-0-691-15498-5.

[3] Ruiter, Johan (2017). Hamilton Mazes - The Beginner's Guide.

[4] Friedman, Erich (2009). "Hamiltonian Mazes". Erich's Puzzle Palace. Archived from the original on 16 April 2016. பார்க்கப்பட்ட நாள் 27 May 2017.

[5] Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150–156, May 1957

[6] Eric Weinstein. "Biconnected Graph". Wolfram MathWorld.

[7] Balakrishnan, R.; Ranganathan, K. (2012), "Corollary 6.5.5", A Textbook of GraphTheory, Springer, p. 134, பன்னாட்டுத் தரப்புத்தக எண் 9781461445296.

[1]

[2]

[3]

[4]

[5]

[6]

[7]