ஆய்லர் பாதை

கோட்டுருவியலில் ஆய்லர் தடம் அல்லது ஆய்லர் பாதை (Eulerian trail, Eulerian path) என்பது ஒரு முடிவுறு கோட்டுருவில் ஒவ்வொரு விளிம்பையும் ஒரேயொருமுறை மட்டுமே கடக்கின்ற ஒரு தடமாகும். இத்தடத்தில் முனைகள் மீண்டும் வருவதற்கு அனுமதியுண்டு.

ஆய்லர் சுற்று (Eulerian circuit) அல்லது ஆய்லர் சுழற்சி (Eulerian cycle) என்பது ஒரு முனையில் துவங்கி அதே முனையில் முடிவடையும் ஆய்லர் தடத்தைக் குறிக்கும். 1736 இல் கோநிக்சுபெர்கின் ஏழு பாலங்கள் என்ற கணக்கிற்குத் தீர்வுகாணும் முயற்சியின்போது இவை முதன்முதலில் ஆய்லரால் விவாதிக்கப்பட்டது.

கோநிக்சுபெர்கின் ஏழு பாலங்கள் கணக்கு:

படத்தில் தரப்பட்டுள்ள கோட்டுருவில் துவங்கிய முனையிலேயே முடிவடையுமாறும், ஒரு விளிம்பை ஒரேயொரு முறை மட்டுமே கடக்குமாறுமுள்ள ஒரு பாதையைக் காண இயலுமா?

ஒரு கோட்டுருவில் ஆய்லர் சுற்று இருப்பதற்குத் தேவையான கட்டுப்பாடாக அக்கோட்டுருவின் ஒவ்வொரு முனையும் இரட்டைப் படியுடையதாக இருக்க வேண்டுமென ஆய்லர் நிறுவினார். மேலும் இரட்டைப் படியுடையதாக அனைத்து முனைகளையும் கொண்ட ஒரு இணைப்புள்ள கோட்டுருவிற்கு ஒரு ஆய்லர் சுற்று இருக்குமென்றும் நிறுவல்கள் ஏதுமில்லாமல் கூறியுள்ளார். இந்த இரண்டாவது கூற்றின் முழுமையான நிறுவல் ஆய்லரின் இறப்பிற்குப் பின்னர் 1873 இல் வெளியிடப்பட்டது.^[1]

இது "ஆய்லரின் தேற்றம்" என அறியப்படுகிறது:

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

"ஆய்லர் கோட்டுரு" என்பது கோட்டுருவியலில் இரு பொருட்படும்:

ஒரு ஆய்லர் சுற்றுடைய கோட்டுரு.
ஒவ்வொரு முனையின் படியும் இரட்டையெண்ணாகக் கொண்ட கோட்டுரு.

இந்த வரையறைகள் இணைப்புள்ள கோட்டுருக்களுக்குப் பொருந்துகின்றன.^[2]

ஒரு கோட்டுருவில் ஆய்லர் சுற்று இருக்கத் தேவையான கட்டுப்பாட்டின்படி அதற்கு ஒற்றைப்படி முனைகளே இருக்கக் கூடாது அல்லது இருந்தால் இரண்டு முனைகள் இருக்க வேண்டும். இக்கட்டுப்பாட்டை நிறைவு செய்யாததால் கோநிக்சுபெர்க்கின் கோட்டுரு ஆய்லர் கோட்டுருவாக அமையவில்லை. ஒரு கோட்டுருவில் ஒற்றைப்படி முனைகளே இல்லாமலோ அல்லது இரண்டு முனைகள் இருந்தால் அக்கோட்டுருவின் அனைத்து ஆய்லர் தடங்களும் ஆய்லர் சுற்றுக்களாக இருக்கும். இரண்டேயிரண்டு ஒற்றைப்படி முனைகள் மட்டுமிருந்தால், அனைத்து ஆய்லர் தடங்களும் ஒரு ஒற்றைப்படி முனையில் துவங்கி மற்றொரு ஒற்றைப்படி முனையில் முடிவடையும்.

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

வரையறை

திசையற்ற கோட்டுரு

ஆய்லர் தடம். ஒவ்வொரு விளிம்பும் ஒரு முறைமட்டுமே கடக்கப்படுகிறது.

ஆய்லர் தடம

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

ஆய்லர் சுற்று

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

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

ஆய்லர் சுற்றுள்ள கோட்டுரு "ஆய்லர் கோட்டுரு" என அழைக்கப்படும்.^[5]

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

திசை கோட்டுரு

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

பண்புகள்

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

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

ஒரு திசை கோட்டுருவில் (வெளிப்படி) − (உட்படி) = 1 என்றவாறு அதிகபட்சம் ஒரு முனையும் (உட்படி) − (வெளிப்படி) = 1 என்றவாறு அதிகபட்சம் ஒரு முனையும் இருந்து ஏனைய முனைகள் சமமான உள் மற்றும் வெளிப்படிகளைக் கொண்டதாகவும், சுழியற்ற படிகொண்ட அதன் முனைகள் அனைத்தும் அத்திசை கோட்டுருவிலமையும் திசையற்ற கோட்டுருவின் ஒரே இணைப்புள்ள கூறில் அமைந்தவையாக இருந்தால், இருந்தால் மட்டுமே, அக்கோட்டுரு ஒரு ஆய்லர் தடத்தைக் கொண்டிருக்கும்.

பயன்பாடுகள்

கையெடுக்காமல் ஒரு வடிவத்தை வரையத்தேவையான இடங்களில் ஆய்லர் தடங்கள் பயன்படுகின்றன.

உயிர் தகவலியலில் டி.என்.ஏ வரன்முறையை அதன் துண்டுகளைக் கொண்டு மறுகட்டமைப்பு செய்வதற்கு ஆய்லர் தடங்கள் பயன்படுத்தப்படுகிறது.^[6] They are also used in துணை உலோக ஆக்சைடு குறைகடத்தி சுற்று வடிவமைப்பில் பயன்படுத்தப்படுகிறது.^[7] மரங்களின் சில செயலாக்கப் படிமுறைத் தீர்வுகள் அம்மரத்தின் ஆய்லர் சுழற்சியை சார்ந்துள்ளன.^[8]^[9]

அருகிலுள்ள படத்திலுள்ள வடிவங்கள் கையெடுக்காமல் தொடர்வரைதலாக வரையப்பட்டுள்ளன:

காஸ் வொம் நிக்கோலசு புதிர் (Haus vom Nikolaus puzzle)- இதில் இரு ஒற்றைமுனைகள் உள்ளதால் பாதை அந்த ஒற்றை முனைகளில் ஒன்றில் துவங்கி மற்றொன்றில் முடிவுறுகிறது.
நான்கு ஒற்றை முனை உள்ளதால் இதற்குத் தீர்வு இல்லை.
ஒற்றை முனைகளே இல்லாததால் பாதை எந்தவொரு முனையிலும் தொடங்கலாம்; மேலும் பாதை மூடிய சுற்றை உருவாக்குகிறது.
இளகுமுனைகள் படி 1 கொண்ட முனைகளாகக் கொள்ளப்படுகின்றன.

குறிப்புகள்

↑ N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory 1736–1936, Clarendon Press, Oxford, 1976, 8–9, பன்னாட்டுத் தரப்புத்தக எண் 0-19-853901-0.
↑ C. L. Mallows, N. J. A. Sloane (1975). "Two-graphs, switching classes and Euler graphs are equal in number". SIAM Journal on Applied Mathematics 28 (4): 876–880. doi:10.1137/0128070. http://neilsloane.com/doc/MallowsSloane.pdf.
↑ ^3.0 ^3.1 சிலர் தன்வெட்டு இல்லாத பாதை/சுழற்சிகளை மட்டுமே குறிக்கும் சொற்களாகப் "பாதை"/"சுழற்சி"யைப் பயன்படுத்துகின்றனர். பொதுவாக, தன்வெட்டுள்ள பாதை "தடம்" என்றும், தன்வெட்டுள்ள சுழற்சி "சுற்று" அல்லது "மூடிய நடை" என்றும் அறியப்படுகிறது. இக்குழப்பத்தைத் தவிர்ப்பதற்காக, தன்வெட்டு அனுமதிக்கப்படும் இடங்களில் ஆய்லர் தடம்/ஆய்லர் சுழற்சி என்ற பெயர்களைப் பயன்படுத்தலாம்.
↑ Jun-ichi Yamaguchi, Introduction of Graph Theory பரணிடப்பட்டது 2017-10-02 at the வந்தவழி இயந்திரம்.
↑ Schaum's outline of theory and problems of graph theory By V. K. Balakrishnan [1].
↑ Pevzner, Pavel A.; Tang, Haixu; Waterman, Michael S. (2001). "An Eulerian trail approach to DNA fragment assembly". Proceedings of the National Academy of Sciences of the United States of America 98 (17): 9748–9753. doi:10.1073/pnas.171285098. பப்மெட்:11504945. Bibcode: 2001PNAS...98.9748P.
↑ Roy, Kuntal (2007). "Optimum Gate Ordering of CMOS Logic Gates Using Euler Path Approach: Some Insights and Explanations". Journal of Computing and Information Technology 15 (1): 85–92. doi:10.2498/cit.1000731.
↑ Tarjan, Robert E.; Vishkin, Uzi (1985). "An efficient parallel biconnectivity algorithm". SIAM Journal on Computing 14 (4): 862–874. doi:10.1137/0214061.
↑ Berkman, Omer; Vishkin, Uzi (Apr 1994). "Finding level-ancestors in trees". J. Comput. Syst. Sci.. 2 48 (2): 214–230. doi:10.1016/S0022-0000(05)80002-9.

மேற்கோள்கள்

Erdõs, Pál; Grünwald, Tibor; Weiszfeld, Endre (1936), "Végtelen gráfok Euler vonalairól" [On Euler lines of infinite graphs] (PDF), Mat. Fix. Lapok (in Hungarian), 43: 129–140{{citation}}: CS1 maint: unrecognized language (link). Translated as Erdős, P.; Grünwald, T.; Vázsonyi, E. (1938), "Über Euler-Linien unendlicher Graphen" [On Eulerian lines in infinite graphs] (PDF), J. Math. Phys. (in German), 17 (1–4): 59–75, எண்ணிம ஆவணச் சுட்டி:10.1002/sapm193817159{{citation}}: CS1 maint: unrecognized language (link).
Euler, L., "Solutio problematis ad geometriam situs pertinentis", Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128–140.
Hierholzer, Carl (1873), "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren", Mathematische Annalen, 6 (1): 30–32, எண்ணிம ஆவணச் சுட்டி:10.1007/BF01442866.
Lucas, E., Récréations Mathématiques IV, Paris, 1921.
Fleury, "Deux problemes de geometrie de situation", Journal de mathematiques elementaires (1883), 257–261.
T. van Aardenne-Ehrenfest and N. G. de Bruijn (1951) "Circuits and trees in oriented linear graphs", Simon Stevin 28: 203–217.
Thorup, Mikkel (2000), "Near-optimal fully-dynamic graph connectivity", Proc. 32nd ACM Symposium on Theory of Computing, pp. 343–350, எண்ணிம ஆவணச் சுட்டி:10.1145/335305.335345
W. T. Tutte and Cedric Smith (statistician) (C. A. B. Smith) (1941) "On Unicursal Paths in a Network of Degree 4", American Mathematical Monthly 48: 233–237.

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

Discussion of early mentions of Fleury's algorithm.
Euler tour at Encyclopedia of Mathematics.

[1] N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory 1736–1936, Clarendon Press, Oxford, 1976, 8–9, பன்னாட்டுத் தரப்புத்தக எண் 0-19-853901-0.

[2] C. L. Mallows, N. J. A. Sloane (1975). "Two-graphs, switching classes and Euler graphs are equal in number". SIAM Journal on Applied Mathematics 28 (4): 876–880. doi:10.1137/0128070. http://neilsloane.com/doc/MallowsSloane.pdf.

[pathcycle-3] 3.0 ^3.1 சிலர் தன்வெட்டு இல்லாத பாதை/சுழற்சிகளை மட்டுமே குறிக்கும் சொற்களாகப் "பாதை"/"சுழற்சி"யைப் பயன்படுத்துகின்றனர். பொதுவாக, தன்வெட்டுள்ள பாதை "தடம்" என்றும், தன்வெட்டுள்ள சுழற்சி "சுற்று" அல்லது "மூடிய நடை" என்றும் அறியப்படுகிறது. இக்குழப்பத்தைத் தவிர்ப்பதற்காக, தன்வெட்டு அனுமதிக்கப்படும் இடங்களில் ஆய்லர் தடம்/ஆய்லர் சுழற்சி என்ற பெயர்களைப் பயன்படுத்தலாம்.

[4] Jun-ichi Yamaguchi, Introduction of Graph Theory பரணிடப்பட்டது 2017-10-02 at the வந்தவழி இயந்திரம்.

[5] Schaum's outline of theory and problems of graph theory By V. K. Balakrishnan [1].

[6] Pevzner, Pavel A.; Tang, Haixu; Waterman, Michael S. (2001). "An Eulerian trail approach to DNA fragment assembly". Proceedings of the National Academy of Sciences of the United States of America 98 (17): 9748–9753. doi:10.1073/pnas.171285098. பப்மெட்:11504945. Bibcode: 2001PNAS...98.9748P.

[7] Roy, Kuntal (2007). "Optimum Gate Ordering of CMOS Logic Gates Using Euler Path Approach: Some Insights and Explanations". Journal of Computing and Information Technology 15 (1): 85–92. doi:10.2498/cit.1000731.

[8] Tarjan, Robert E.; Vishkin, Uzi (1985). "An efficient parallel biconnectivity algorithm". SIAM Journal on Computing 14 (4): 862–874. doi:10.1137/0214061.

[9] Berkman, Omer; Vishkin, Uzi (Apr 1994). "Finding level-ancestors in trees". J. Comput. Syst. Sci.. 2 48 (2): 214–230. doi:10.1016/S0022-0000(05)80002-9.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]