ஆய்லர் பாதை
[[File:Comparison_7_bridges_of_Konigsberg_5_room_puzzle_graphs.svg|thumb|கோனிக்சுபெர்க்கின் ஏழுபாலங்கள் மற்றும் ஐந்து அறை புதிர்கள் இரண்டின் [[பல்கோட்டுரு]]க்கள். இவற்றுக்கு இரண்டிற்கு மேற்பட்ட ஒற்றைப்படி முனைகள் (ஆரஞ்சு) உள்ளதால் இவை ஆய்லேரியன் கோட்டுருக்கள் அல்ல; இவற்றுக்குத் தீர்வுகளும் இல்லை.]]
 [[கோட்டுருவியல்|கோட்டுருவியலில்]] '''ஆய்லர் தடம்''' அல்லது '''ஆய்லர் பாதை''' (''Eulerian trail'',  ''Eulerian path'') என்பது ஒரு முடிவுறு கோட்டுருவில் ஒவ்வொரு [[விளிம்பு (கோட்டுருவியல்)|விளிம்பையும்]] ஒரேயொருமுறை மட்டுமே கடக்கின்ற ஒரு [[பாதை (கோட்டுருவியல்)#நடை, தடம், பாதை|தடமாகும்]]. இத்தடத்தில் முனைகள் மீண்டும் வருவதற்கு அனுமதியுண்டு. 
 
 '''ஆய்லர் சுற்று''' (''Eulerian circuit'') அல்லது '''ஆய்லர் சுழற்சி''' (''Eulerian cycle'') என்பது ஒரு முனையில் துவங்கி அதே முனையில் முடிவடையும் ஆய்லர் தடத்தைக் குறிக்கும். 1736 இல் [[கோநிக்சுபெர்கின் ஏழு பாலங்கள்]] என்ற கணக்கிற்குத் தீர்வுகாணும் முயற்சியின்போது இவை முதன்முதலில் [[லியோனார்டு ஆய்லர்|ஆய்லரால்]] விவாதிக்கப்பட்டது.
 
 கோநிக்சுபெர்கின் ஏழு பாலங்கள் கணக்கு:
 :படத்தில் தரப்பட்டுள்ள கோட்டுருவில் துவங்கிய முனையிலேயே முடிவடையுமாறும், ஒரு விளிம்பை ஒரேயொரு முறை மட்டுமே கடக்குமாறுமுள்ள ஒரு பாதையைக் காண இயலுமா?
 
 ஒரு கோட்டுருவில் ஆய்லர் சுற்று இருப்பதற்குத் தேவையான கட்டுப்பாடாக அக்கோட்டுருவின் ஒவ்வொரு முனையும் இரட்டைப் படியுடையதாக இருக்க வேண்டுமென ஆய்லர் நிறுவினார். மேலும் இரட்டைப் படியுடையதாக அனைத்து முனைகளையும் கொண்ட ஒரு இணைப்புள்ள கோட்டுருவிற்கு ஒரு ஆய்லர் சுற்று இருக்குமென்றும் நிறுவல்கள் ஏதுமில்லாமல் கூறியுள்ளார். இந்த இரண்டாவது கூற்றின் முழுமையான நிறுவல் ஆய்லரின் இறப்பிற்குப் பின்னர் 1873 இல் வெளியிடப்பட்டது.&lt;ref&gt;N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory 1736–1936, Clarendon Press, Oxford, 1976, 8–9, {{ISBN|0-19-853901-0}}.&lt;/ref&gt; 
 
 இது &quot;ஆய்லரின் தேற்றம்&quot; என அறியப்படுகிறது:
 :&quot;ஒரு இணைப்புள்ள  கோட்டுருவின் ஒவ்வொரு முனையின் படியும் இரட்டை எண்ணாக இருந்தால், இருந்தால் மட்டுமே, அக்கோட்டுருவிற்கு ஒரு ஆய்லர் சுழற்சி இருக்கும்.&quot;
 
 &quot;ஆய்லர் கோட்டுரு&quot; என்பது கோட்டுருவியலில் இரு பொருட்படும்:
 #ஒரு ஆய்லர் சுற்றுடைய கோட்டுரு.
 #ஒவ்வொரு முனையின் படியும் இரட்டையெண்ணாகக் கொண்ட கோட்டுரு.
 
 இந்த வரையறைகள் இணைப்புள்ள கோட்டுருக்களுக்குப் பொருந்துகின்றன.&lt;ref&gt;{{cite journal |doi=10.1137/0128070 |author=C. L. Mallows, N. J. A. Sloane |title=Two-graphs, switching classes and Euler graphs are equal in number |journal=[[SIAM Journal on Applied Mathematics]] |volume=28 |year=1975 |pages=876–880 |jstor=2100368 |issue=4 |ref=harv|url=http://neilsloane.com/doc/MallowsSloane.pdf }}&lt;/ref&gt;
 
 ஒரு கோட்டுருவில் ஆய்லர் சுற்று இருக்கத் தேவையான கட்டுப்பாட்டின்படி அதற்கு ஒற்றைப்படி முனைகளே இருக்கக் கூடாது அல்லது இருந்தால் இரண்டு முனைகள் இருக்க வேண்டும். இக்கட்டுப்பாட்டை நிறைவு செய்யாததால் கோநிக்சுபெர்க்கின் கோட்டுரு ஆய்லர் கோட்டுருவாக அமையவில்லை. ஒரு கோட்டுருவில் ஒற்றைப்படி முனைகளே இல்லாமலோ அல்லது இரண்டு முனைகள் இருந்தால் அக்கோட்டுருவின் அனைத்து ஆய்லர் தடங்களும் ஆய்லர் சுற்றுக்களாக இருக்கும். இரண்டேயிரண்டு ஒற்றைப்படி முனைகள் மட்டுமிருந்தால், அனைத்து ஆய்லர் தடங்களும் ஒரு ஒற்றைப்படி முனையில் துவங்கி மற்றொரு ஒற்றைப்படி முனையில் முடிவடையும். 
 
 ஆய்லர் தடம் கொண்ட ஆனால் ஆய்லர் சுற்றற்ற கோட்டுருவானது &quot;அரை-ஆய்லர் கோட்டுரு&quot; எனப்படும். ஆய்லர் தடங்கள், ஆய்லர் சுழற்சிகள் மற்றும் ஆய்லர் கோட்டுருக்களுக்காக வரையறைகளும் பண்புகளும் [[பல்கோட்டுரு]]க்களுக்கும் பொருந்தும்.
 
 
 == வரையறை ==
 === திசையற்ற கோட்டுரு ===
 [[File:Ciclo euleriano.PNG|right|ஆய்லர் தடம். ஒவ்வொரு விளிம்பும் ஒரு முறைமட்டுமே கடக்கப்படுகிறது.]]
 ==== ஆய்லர் தடம ==== 
 ஒரு திசையற்ற கோட்டுருவில் ஒரு விளிம்பை ஒருமுறை மட்டுமே சந்திக்கும் பாதை &quot;ஆய்லர் தடம்&quot; அல்லது &quot;ஆய்லர் நடை&quot;&lt;ref name=&quot;pathcycle&quot;&gt;சிலர் தன்வெட்டு இல்லாத பாதை/சுழற்சிகளை மட்டுமே குறிக்கும் சொற்களாகப் &quot;பாதை&quot;/&quot;சுழற்சி&quot;யைப் பயன்படுத்துகின்றனர். பொதுவாக, தன்வெட்டுள்ள பாதை &quot;தடம்&quot; என்றும், தன்வெட்டுள்ள  சுழற்சி &quot;சுற்று&quot; அல்லது &quot;மூடிய நடை&quot; என்றும் அறியப்படுகிறது. இக்குழப்பத்தைத் தவிர்ப்பதற்காக, தன்வெட்டு அனுமதிக்கப்படும் இடங்களில் ஆய்லர் தடம்/ஆய்லர் சுழற்சி என்ற பெயர்களைப் பயன்படுத்தலாம்.&lt;/ref&gt;  
 எனப்படும். அவ்வாறான ஒரு தடம் இருக்கக்கூடிய கோட்டுரு &quot;கடக்கக்கூடிய கோட்டுரு&quot; அல்லது &quot;அரை-ஆய்லர் கோட்டுரு&quot; என அழைக்கப்படுகிறது.&lt;ref&gt;Jun-ichi Yamaguchi, [http://jwilson.coe.uga.edu/EMAT6680/Yamaguchi/emat6690/essay1/GT.html Introduction of Graph Theory] {{Webarchive|url=https://web.archive.org/web/20171002131856/http://jwilson.coe.uga.edu/emat6680/yamaguchi/emat6690/essay1/gt.html |date=2017-10-02 }}.&lt;/ref&gt;
 
 ==== ஆய்லர் சுற்று ====
 [[File:Labelled Eulergraph.svg|thumb|இக்கோட்டுருவின் ஒவ்வொரு முனையும் இரட்டைப் [[படி (கோட்டுருவியல்)|படியுடையது]]. எனவே இதொரு ஆய்லர் கோட்டுரு. இதன் விளிம்புகளை ஆங்கில அகரவரிசையில் பின்பற்றிச் சென்றால் ஆய்லர் சுற்று/சுழற்சி கிடைக்கும்.]]
 ஒரு திசையற்ற கோட்டுருவின் சுழற்சியில் ஒரு விளிம்பு ஒரேயொரு முறைமட்டுமே பயன்படுத்தப்பட்டால் அச்சுழற்சி &quot;ஆய்லர் சுழற்சி&quot; அல்லது &quot;ஆய்லர் சுற்று&quot;&lt;ref name=&quot;pathcycle&quot;/&gt; எனப்படும். 
 
 ஆய்லர் சுற்றுள்ள கோட்டுரு &quot;ஆய்லர் கோட்டுரு&quot; என அழைக்கப்படும்.&lt;ref&gt;Schaum's outline of theory and problems of graph theory By V. K. Balakrishnan [https://books.google.com/books?id=1NTPbSehvWsC&amp;lpg=PA60&amp;dq=unicursal&amp;pg=PA60#v=onepage&amp;q=unicursal&amp;f=false].&lt;/ref&gt;
 
 ஆய்லர் கோட்டுரு என்ற பெயர் சில சமயங்களின் இரட்டைப்படி முனைகள் மட்டுமுள்ள கோட்டுருக்களைக் குறிக்கப் பலவீனமாகக் பயன்படுத்தப்படுகிறது. முடிவுறு இணைப்புள்ள கோட்டுருக்களுக்கு மட்டுமே ஆய்லர் கோட்டுரு மற்றும் இரட்டைப்படி முனை கொண்ட கோட்டுரு ஆகிய இரு வரையறைகளும் பொருத்தமாக இருக்கும். இணைப்பில்லா கோட்டுருக்களுக்கு, ஒரு இணைப்பில்லா கோட்டுருவின் ஒவ்வொரு இணைப்புள்ள கூறுகளும் ஒரு ஆய்லர் சுழற்சியைக் கொண்டிருந்தால், இருந்தால் மட்டுமே அது பலவீனமான பொருளில் ஆய்லர் கோட்டுரு என அழைக்கப்பட முடியும்.
 
 === திசை கோட்டுரு ===
 திசையற்ற கோட்டுருக்களின் ஆய்லர் தடம் மற்றும் ஆய்லர் சுழற்சியின் வரையறைகளில் &quot;தடம்&quot; என்பதற்குப் பதிலாக ''[[பாதை (கோட்டுருவியல்)|திசையுறு தடம்]]'' மற்றும் &quot;சுற்று&quot; என்பதற்குப் பதிலாக ''[[சுழற்சி (கோட்டுருவியல்)|திசையுறு சுழற்சி]]'' என்ற சொற்களைக் கொண்டு பதிலிட [[திசை கோட்டுரு]]க்களின் ஆய்லர் தடம் மற்றும் ஆய்லர் சுழற்சியின் வரையறைகளைப் பெறலாம்.
 
 == பண்புகள் ==
 *ஒரு திசையற்ற கோட்டுருவின் அனைத்து முனைகளும் இரட்டையெண் படி கொண்டவையாகவும், சுழியற்ற படிகொண்ட அதன் முனைகள் அனைத்தும் ஒரே [[கூறு (கோட்டுருவியல்)|இணைப்புள்ள கூறில்]] அமைந்தவையாகவும் இருந்தால், இருந்தால் மட்டுமே, அக்கோட்டுரு ஒரு ஆய்லர் சுழற்சியைக் கொண்டிருக்கும்.
 * ஒரு திசையற்ற கோட்டுருவின் அனைத்து முனைகளும் இரட்டையெண் படி கொண்டவையாக இருந்தால், இருந்தால் மட்டுமே அக்கோட்டுருவை விளிம்பு-இணைப்பற்ற [[சுழற்சி (கோட்டுருவியல்)|சுழற்சிகளாகப்]] பிரிக்க இயலும். 
 *மேலுள்ள இரு பண்புகளையும் இணைத்து, ஒரு திசையற்ற கோட்டுருவை விளிம்பு-இணைப்பற்ற [[சுழற்சி (கோட்டுருவியல்)|சுழற்சிகளாகப்]] பிரிக்கமுடிந்து மற்றும் சுழியற்ற படிகொண்ட அதன் முனைகள் அனைத்தும் ஒரே [[கூறு (கோட்டுருவியல்)|இணைப்புள்ள கூறில்]] அமைந்தவையாகவும் இருந்தால், இருந்தால் மட்டுமே, அக்கோட்டுரு ஒரு ஆய்லர் சுழற்சியைக் கொண்டிருக்கும் எனக் கூறலாம்.
 *ஒரு திசையற்ற கோட்டுரு ஒற்றைப்படி கொண்ட முனைகளே இல்லாமல் அல்லது இரு முனைகள் மட்டும் கொண்டிருந்து,  சுழியற்ற படிகொண்ட அதன் முனைகள் அனைத்தும் ஒரே [[கூறு (கோட்டுருவியல்)|இணைப்புள்ள கூறில்]] அமைந்தவையாக இருந்தால், இருந்தால் மட்டுமே, அக்கோட்டுருவில் ஒரு ஆய்லர் தடம் அமைந்திருக்கும்.
 *ஒரு திசை கோட்டுருவில் ஒவ்வொரு முனையும் சமமான [[படி (கோட்டுருவியல்)|உட்படியும்]] [[படி (கோட்டுருவியல்)|வெளிப்படியும்]] கொண்டிருந்து, சுழியற்ற படிகொண்ட அதன் முனைகள் அனைத்தும் ஒரே வலிமையான இணைப்புள்ள கூறில் அமைந்தவையாக இருந்தால், இருந்தால் மட்டுமே, அக்கோட்டுருவில் ஒரு ஆய்லர் சுழற்சி அமைந்திருக்கும்
 
 இதற்குச் சமானமாக, ஒரு திசை கோட்டுருவை விளிம்பு-இணைப்பற்ற [[சுழற்சி (கோட்டுருவியல்)|திசையுள்ள சுழற்சிகளாகப்]] பிரிக்கமுடிந்து, சுழியற்ற படிகொண்ட அதன் முனைகள் அனைத்தும் ஒரே [[கூறு (கோட்டுருவியல்)|இணைப்புள்ள கூறில்]] அமைந்தவையாக இருந்தால், இருந்தால் மட்டுமே, அக்கோட்டுரு ஒரு ஆய்லர் சுழற்சியைக் கொண்டிருக்கும் எனக் கூறலாம்.
 
 *ஒரு திசை கோட்டுருவில் ([[படி (கோட்டுருவியல்)|வெளிப்படி]])&amp;nbsp;&amp;minus;&amp;nbsp;([[படி (கோட்டுருவியல்)|உட்படி]])&amp;nbsp;=&amp;nbsp;1 என்றவாறு அதிகபட்சம் ஒரு முனையும் (உட்படி)&amp;nbsp;&amp;minus;&amp;nbsp;(வெளிப்படி)&amp;nbsp;=&amp;nbsp;1 என்றவாறு அதிகபட்சம் ஒரு முனையும் இருந்து ஏனைய முனைகள் சமமான உள் மற்றும் வெளிப்படிகளைக் கொண்டதாகவும், சுழியற்ற படிகொண்ட அதன் முனைகள் அனைத்தும் அத்திசை கோட்டுருவிலமையும் திசையற்ற கோட்டுருவின் ஒரே [[கூறு (கோட்டுருவியல்)|இணைப்புள்ள கூறில்]] அமைந்தவையாக இருந்தால், இருந்தால் மட்டுமே, அக்கோட்டுரு ஒரு ஆய்லர் தடத்தைக் கொண்டிருக்கும்.
 
 == பயன்பாடுகள் ==
 [[File:Eulerian_path_puzzles.svg|thumb|250px|கையெடுக்காமல் ஒரு வடிவத்தை வரையத்தேவையான இடங்களில் ஆய்லர் தடங்கள் பயன்படுகின்றன.]]
 
 [[உயிர் தகவலியல்|உயிர் தகவலியலில்]] [[டி.என்.ஏ வரன்முறையிடல்|டி.என்.ஏ வரன்முறையை]] அதன் துண்டுகளைக் கொண்டு மறுகட்டமைப்பு செய்வதற்கு ஆய்லர் தடங்கள் பயன்படுத்தப்படுகிறது.&lt;ref&gt;{{cite journal| last1=Pevzner| first1=Pavel A.| last2=Tang| first2=Haixu| last3=Waterman| first3=Michael S.| year=2001 |title=An Eulerian trail approach to DNA fragment assembly |journal=Proceedings of the National Academy of Sciences of the United States of America |volume=98| pmid=11504945 |issue=17 |pages=9748–9753| pmc=55524 |doi=10.1073/pnas.171285098 | bibcode=2001PNAS...98.9748P| ref=harv}}&lt;/ref&gt; They are also used in [[துணை உலோக ஆக்சைடு குறைகடத்தி]] சுற்று வடிவமைப்பில் பயன்படுத்தப்படுகிறது.&lt;ref&gt;{{cite journal| last1=Roy| first1=Kuntal| year=2007 |title=Optimum Gate Ordering of CMOS Logic Gates Using Euler Path Approach: Some Insights and Explanations |journal=Journal of Computing and Information Technology |volume=15 |issue=1 |pages=85–92|doi=10.2498/cit.1000731 | ref=harv|doi-access=free }}&lt;/ref&gt; [[மரம் (கோட்டுருவியல்)|மரங்களின்]] சில செயலாக்கப் [[படிமுறைத் தீர்வு]]கள் அம்மரத்தின் ஆய்லர் சுழற்சியை சார்ந்துள்ளன.&lt;ref&gt;{{cite journal|last=Tarjan|first=Robert E.|last2=Vishkin|first2=Uzi|title=An efficient parallel biconnectivity algorithm|journal=SIAM Journal on Computing|date=1985|volume=14|number=4|pages=862–874|doi=10.1137/0214061|citeseerx=10.1.1.465.8898}}&lt;/ref&gt;&lt;ref&gt;{{cite journal|last=Berkman|first=Omer|last2=Vishkin|first2=Uzi|title=Finding level-ancestors in trees|journal=J. Comput. Syst. Sci.|date=Apr 1994|volume=48|issue=2|series=2|pages=214–230|doi=10.1016/S0022-0000(05)80002-9}}&lt;/ref&gt;
 
 அருகிலுள்ள படத்திலுள்ள வடிவங்கள் கையெடுக்காமல் தொடர்வரைதலாக வரையப்பட்டுள்ளன:
 #காஸ் வொம் நிக்கோலசு புதிர் (Haus vom Nikolaus puzzle)- இதில் இரு ஒற்றைமுனைகள் உள்ளதால் பாதை அந்த ஒற்றை முனைகளில் ஒன்றில் துவங்கி மற்றொன்றில் முடிவுறுகிறது.
 #நான்கு ஒற்றை முனை உள்ளதால் இதற்குத் தீர்வு இல்லை.
 #ஒற்றை முனைகளே இல்லாததால் பாதை எந்தவொரு முனையிலும் தொடங்கலாம்; மேலும் பாதை மூடிய சுற்றை உருவாக்குகிறது.
 #இளகுமுனைகள் படி 1 கொண்ட முனைகளாகக் கொள்ளப்படுகின்றன.
 
 == குறிப்புகள் ==
 {{reflist|2}}
 
 == மேற்கோள்கள் ==
 *{{citation
  | last1 = Erdõs | first1 = Pál | author1-link = Paul Erdõs
  | last2 = Grünwald | first2 = Tibor | author2-link = Tibor Gallai
  | last3 = Weiszfeld | first3 = Endre | author3-link = Andrew Vázsonyi
  | journal = Mat. Fix. Lapok
  | pages = 129–140
  | title = Végtelen gráfok Euler vonalairól
  | trans-title = On Euler lines of infinite graphs
  | language = Hungarian
  | url = https://www.renyi.hu/~p_erdos/1936-11.pdf
  | volume = 43
  | year = 1936}}.  Translated as {{citation
  | last1 = Erdős | first1 = P. | author1-link = Paul Erdős
  | last2 = Grünwald | first2 = T. | author2-link = Tibor Gallai
  | last3 = Vázsonyi | first3 = E.
  | journal = J. Math. Phys.
  | language = German
  | pages = 59–75
  | title = Über Euler-Linien unendlicher Graphen
  |trans-title=On Eulerian lines in infinite graphs
  | url = http://www.renyi.hu/~p_erdos/1938-15.pdf
  | volume = 17
  | issue = 1–4 | year = 1938
  | doi = 10.1002/sapm193817159}}.
 * Euler, L., &quot;[http://www.math.dartmouth.edu/~euler/pages/E053.html Solutio problematis ad geometriam situs pertinentis]&quot;, ''Comment. Academiae Sci. I. Petropolitanae'' '''8''' (1736), 128–140.
 *{{citation
  | last = Hierholzer | first = Carl | author-link = Carl Hierholzer
  | doi = 10.1007/BF01442866
  | issue = 1
  | journal = [[Mathematische Annalen]]
  | pages = 30–32
  | title = Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren
  | volume = 6
  | year = 1873| url = https://zenodo.org/record/1447429
  }}.
 * Lucas, E., ''Récréations Mathématiques IV'', Paris, 1921.
 * Fleury, &quot;Deux problemes de geometrie de situation&quot;, ''Journal de mathematiques elementaires'' (1883), 257–261.
 * [[Tatyana Pavlovna Ehrenfest|T. van Aardenne-Ehrenfest]] and [[Nicolaas Govert de Bruijn|N. G. de Bruijn]] (1951) &quot;Circuits and trees in oriented linear graphs&quot;, [[Simon Stevin (journal)|Simon Stevin]] 28: 203–217.
 *{{Citation|first=Mikkel|last=Thorup|authorlink=Mikkel Thorup|year=2000|pages=343–350|doi=10.1145/335305.335345|contribution=Near-optimal {{Sic|hide=y|fully|-}}dynamic graph connectivity|title=Proc. 32nd ACM Symposium on Theory of Computing|title-link=Symposium on Theory of Computing}}
 * W. T. Tutte and Cedric Smith (statistician) (C. A. B. Smith) (1941) &quot;On Unicursal Paths in a Network of Degree 4&quot;, [[American Mathematical Monthly]] 48: 233–237.
 
 == வெளியிணைப்புகள் ==
 {{Commons category|Eulerian paths}}
 * [http://mathforum.org/kb/message.jspa?messageID=3648262&amp;tstart=135 Discussion of early mentions of Fleury's algorithm].
 * [http://www.encyclopediaofmath.org/index.php/Euler_tour ''Euler tour''] at Encyclopedia of Mathematics.
 
 [[பகுப்பு:கோட்டுருவியல்]]