பாதை (கோட்டுருவியல்)

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

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

வரையறைகள்

நடை, தடம், பாதை

முடிவுறு/முடிவுறா நடைகள்

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

G = (V, E, ϕ) ஒரு கோட்டுரு. இதில் (v₁, v₂, …, v_n) என்பவை கணுக்கள் என்க.

ϕ(e_i) = {v_i, v_{i + 1}} என்றவாறு இணைக்கும் (e₁, e₂, …, e_{n − 1}) விளிம்புகள் முடிவுறு நடையாகும்.

முடிவுறு நடையைப் போன்றே முடிவுறா நடையும் வரையறுக்கப்படுகிறது. ஆனால் முடிவுறா நடையில் முதல் மற்றும் இறுதிக் கணுக்கள் என இருக்காது. அரை-முடிவுறா நடையில் (கதிர்) முதல் கணு இருக்கும்; ஆனால் இறுதிக் கணு இருக்காது.

தடம்

கணுக்களை இணைக்கும் விளிம்புகள் எல்லாம் வெவ்வேறானவையாக இருக்குமானால் அந்த நடையானது "தடம்" (trail) எனப்படும்.

பாதை

வெவ்வேறான கணுக்களை (இதனால் விளிம்புகளும் வெவ்வேறானவையாக இருக்கும்) உடைய தடமானது "பாதை" (path) எனப்படும்.

(v₁, v₂, …, v_n) என்ற கணுக்களின் தொடர்வரிசையின் முடிவுறு நடை w = (e₁, e₂, …, e_{n − 1}) எனில் v₁ இலிருந்து v_n க்கான நடை w ஆகும்.. இக்கூற்று தடம் மற்றும் பாதைக்கும் பொருந்தும். இரு வெவ்வேறான கணுக்களுக்கிடையே ஒரு முடிவுறு நடை இருக்குமானால், அவற்றுக்கிடையே முடிவுறு தடம் மற்றும் முடிவுறு பாதையும் இருக்கும்.

திசையுறு நடை, தடம், பாதை

திசையுறு (முடிவுறு/முடிவுறா) நடைகள்

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

G = (V, E, ϕ) ஒரு திசையுறு கோட்டுரு. இதில் (v₁, v₂, …, v_n) கணுக்கள் என்க.

ϕ(e_i) = {v_i, v_{i + 1}} என்றவாறு இணைக்கும் (e₁, e₂, …, e_{n − 1}) ஒரே திசையுள்ள விளிம்புகள் தொடர்வரிசை திசையுறு (முடிவுறு) நடையாகும்

முடிவுறு திசையுள்ள நடையைப் போன்றே முடிவுறா திசையுள்ள நடையும் வரையறுக்கப்படுகிறது. ஆனால் முடிவுறா திசையுறு நடையில் முதல் மற்றும் இறுதிக் கணுக்கள் என இருக்காது. அரை-முடிவுறா திசையுறு நடையில் (கதிர்) முதல் கணு இருக்கும்; ஆனால் இறுதிக் கணு இருக்காது.

தடம்

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

பாதை

வெவ்வேறான கணுக்களை (இதனால் விளிம்புகளும் வெவ்வேறானவையாக இருக்கும்) உடைய திசையுறு தடமானது "திசையுறு பாதை" எனப்படும்.

(v₁, v₂, …, v_n) என்ற கணுக்களின் தொடர்வரிசையின் திசையுறு நடை w = (e₁, e₂, …, e_{n − 1}) எனில் v₁ இலிருந்து v_n க்கான திசையுறு நடை w ஆகும்.. இக்கூற்று திசையுறு தடம் மற்றும் திசையுறு பாதைக்கும் பொருந்தும். இரு வெவ்வேறான கணுக்களுக்கிடையே ஒரு திசையுறு (முடிவுறு) நடை இருக்குமானால், அவற்றுக்கிடையே திசையுறு (முடிவுறு) தடம் மற்றும் திசையுறு (முடிவுறு) பாதையும் இருக்கும்.

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

மேற்கோள்கள்

• Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability.
• Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. North Holland. p. 12-21. பன்னாட்டுத் தரப்புத்தக எண் 0-444-19451-7.
• Diestel, Reinhard (2005). Graph Theory. Springer-Verlag. p. 6-9. பன்னாட்டுத் தரப்புத்தக எண் 3-540-26182-6.
• Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press. p. 5-6. பன்னாட்டுத் தரப்புத்தக எண் 0-521-28881-9.
• Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (1990). Paths, Flows, and VLSI-Layout. Springer-Verlag. பன்னாட்டுத் தரப்புத்தக எண் 0-387-52685-4.