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

ஒரு திசையற்ற கோட்டுருவின் கூறு அல்லது இணைப்புக் கூறு (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

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

• MATLAB code to find components in undirected graphs, MATLAB File Exchange.
• Connected components, Steven Skiena, The Stony Brook Algorithm Repository