கூறு (கோட்டுருவியல்)

ஒரு திசையற்ற கோட்டுருவின் கூறு அல்லது இணைப்புக் கூறு (component, connected component) என்பது அக்கோட்டுருவின் ஒரு உட்கோட்டுருவாகும்.

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

சமான உறவுதொகு

கோட்டுருவின் முனைகளின் மீது வரையறுக்கப்பட்ட ஒரு சமான உறவின் சமானப் பகுதிகளைக் கொண்டும் கூறுகளை மாற்றுமுறையில் வரையறுக்கலாம்.

ஒரு திசையற்ற கோட்டுருவில் ஒரு முனை u இலிருந்து மற்றொரு முனை v விற்கு ஒரு பாதை இருந்தால், u இலிருந்து "சென்றடையக்கூடியது" v என்ற உறவு வரையறுக்கப்படுகிறது. இந்த வரையறையில் ஒற்றை முனைகள் "0" நீளமுள்ள பாதைகளாகவும், ஒரு பாதையில் ஒரு முனை மீண்டும் வரலாம் எனவும் கொள்ளப்படுகிறது.

இந்த "சென்றடையக்கூடியது" என்ற உறவு ஒரு சமான உறவாக அமைகிறது. ஏனெனில்:

ஒரு முனையிலிருந்து அதற்கே "0" நீளமுள்ள பாதை உள்ளதால் உட்கோட்டுருவின் ஒரு முனை u இலிருந்து u ஐச் சென்றடையலாம்
u இலிருந்து v ஒரு பாதை இருக்குமானால், அப்பாதையிலுள்ள அதே விளிம்புகள் v இலிருந்து u ஒரு பாதையை அமைக்கும்.
u இலிருந்து v மற்றும் v இலிருந்து w பாதைகள் இருக்குமானால் அப்பாதைகளை ஒன்றிணைத்து u இலிருந்து w பாதையாக்கலாம்.

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

மேற்கோள்கள்தொகு

  • Hopcroft, J.; Tarjan, R. (1973), "Algorithm 447: efficient algorithms for graph manipulation", Communications of the ACM, 16 (6): 372–378, doi:10.1145/362248.362272
  • Lewis, Harry R.; Papadimitriou, Christos H. (1982), "Symmetric space-bounded computation", Theoretical Computer Science, 19 (2): 161–187, doi:10.1016/0304-3975(82)90058-5
  • Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM, 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291
  • Shiloach, Yossi; Even, Shimon (1981), "An on-line edge-deletion problem", Journal of the ACM, 28 (1): 1–4, doi:10.1145/322234.322235

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

"https://ta.wikipedia.org/w/index.php?title=கூறு_(கோட்டுருவியல்)&oldid=2979388" இருந்து மீள்விக்கப்பட்டது