இணைப்பு (கோட்டுருவியல்)

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

படம் 1 இல் இடப்புறமுள்ள சாம்பல்நிறப் பகுதியில் வலதோர முனையை நீக்க இணைப்பிலாக் கோட்டுருவாகி விடும்.
படம் 2 இல் புள்ளியிடப்பட்ட விளிம்பை நீக்கினால் இணைப்பற்ற கோட்டுரு ஆகிவிடும்.

கோட்டுருக்களில் இணைப்பு

இணைப்புள்ள முனைகள்

திசையற்ற கோட்டுரு $G$ இன் முனைகள் $u$ , $v$ இரண்டும் இடையே ஒரு பாதை அக்கோட்டுருவில் இருந்தால் அம்முனைகள் இரண்டும் இணைப்புள்ளவையாகும். அவ்வாறான பாதை இல்லையெனில் அம்முனைகள் இணைப்பற்றவை.

இரு முனைகளை இணைக்கும் பாதை ஒரேயொரு விளிம்பால் ஆனதாக இருக்கும்போது (அதாவது பாதையின் நீளம் $1$ அலகு) அம்முனைகள் "அடுத்துள்ள முனை"கள் எனப்படும்.

இணைப்புள்ள கோட்டுரு

படம் 3. இணைப்புள்ள முழுக்கோட்டுரு.

படம் 4. இணைப்புள்ள கோட்டுரு (முழுக்கோட்டுரு அல்ல).

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

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

படம் 3 இல்

K 5

- முழுக்கோட்டுருவின் ஒவ்வொரு முனைய இருமத்துக்கும் ஒரு பாதை உள்ளதைக் காணலாம்.

படம் 4 இல் உள்ள கோட்டுரு ஒரு முழுக்கோட்டுரு அல்ல. இருப்பினும் அதன் ஒவ்வொரு முனைய இருமத்துக்கும் இடையே ஒரு பாதையுள்ளதால் இணைப்புள்ள கோட்டுருவாக உள்ளது

இணைப்பில்லாக் கோட்டுரு

படம் 4: இணைப்பிலாக் கோட்டுரு

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

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

படம் 4 இல் உள்ள கோட்டுருவின் முனை "0" ஆனது கோட்டுருவின் வேறெந்த முனைகளுடனும் இணைக்கப்படவில்லை. இதனால் இக்கோட்டுரு இணைப்பற்றதாகிறது. முனை "0" ஐ நீக்கினால் இதர பகுதி இணைப்புள்ள கோட்டுருவாக அமைவதைக் காணலாம்.

இணைப்புக் கூறுகள்

படம் 5: மூன்று இணைப்புக் கூறுகள் கொண்ட கோட்டுரு

ஒரு திசையற்ற கோட்டுருவின் உட்கோட்டுருக்களில் பின்வரும் பண்புகளைக் கொண்டவை மூலக் கோட்டுருவின் இணைப்புக் கூறு எனப்படும்:

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

G

இன் உட்கோட்டுருக்களில் இணைப்புள்ள கோட்டுருக்களாக இருப்பவை

G

இன் இணைப்புக் கூறுகள் என அழைக்கப்படுகின்றன. $G$ ஒவ்வொரு முனையும் (விளிம்பும்) ஒரேயொரு இணைப்புக் கூறில் மட்டுமே அமைந்திருக்கும்.

படம் 5 இல் உள்ள கோட்டுருவிற்கு மூன்று இணைப்புக் கூறுகள் உள்ளதைக் காணலாம்.

முனைகள்

முனை வெட்டு

ஓர் இணைப்புள்ள கோட்டுருவின் எந்தெந்த முனைகளை நீக்க அக்கோட்டுரு இணைப்பிலாக் கோட்டுருவாக மாறுமோ, அந்த முனைகளின் கணம் கோட்டுருவின் "வெட்டு" அல்லது "முனை வெட்டு" அல்லது "பிரிக்கும் கணம்" எனப்படும்.

G

ஓர் இணைப்புள்ள கோட்டுருவெனில் அதன் எந்ததெந்த முனைகளை நீக்கும்போது

G

ஓர் இணைப்பிலாக் கோட்டுருவாகிறதோ அந்த முனைகளின் கணம்

G

இன் முனை வெட்டாகும்.

முனை-இணைப்பு

ஓர் இணைப்புள்ள கோட்டுருவின் எந்தெந்த முனைகளை நீக்க அக்கோட்டுரு இணைப்பிலாக் கோட்டுருவாக மாறுமோ, அந்த முனைகளின் எண்ணிக்கைகளின் மிகக் குறைந்த அளவே அக்கோட்டுருவின் "முனை-இணைப்பு" அல்லது "இணைப்பு" ஆகும்.

$G$ (முழுக்கோட்டுரு அல்ல) இன் "முனை-இணைப்பு" என்பது முனை வெட்டுக்களாக அமையும் முனைகளின் கணங்களின் அளவில் சிறும அளவாகும்.

G

இன் முனை-இணைப்பின் குறியீடு:

κ (G)

.

அதாவது

G

ஓர் இணைப்புள்ள கோட்டுரு; அதன் ஒரு முனையை நீக்கினால் அது இணைப்பற்றதாகிவிடும் மற்றும் இரு முனைகளை நீக்கும்போதும் அது இணைப்பற்றதாகி விடுமெனில்,

G

இன் முனை இணைப்பு

κ (G)

=

1

$k$ -இணைப்பு

முனை-இணைப்பின் மதிப்பு $k$ அல்லது அதற்கு அதிகமானதாகக் கொண்ட கோட்டுரு $k$ -இணைப்பு அல்லது $k$ -முனை-இணைப்பு உடையது எனப்படும்.

கோட்டுரு $G$ (முழுக்கோட்டுரு/முழு கோட்டுரு அல்ல) ஓர் $k$ -இணைப்பு உள்ளதாக இருக்க வேண்டுமெனில்:

குறைந்தபட்சம் $k +1$ முனைகள் இருக்க வேண்டும்.
எந்தெந்த முனைகளை நீக்க கோட்டுரு இணைப்பற்றதாகுமோ அந்த முனைகளின் எண்ணிக்கை $k - 1$ ஆகக்கொண்ட கணம் இருக்கக்கூடாது.
கோட்டுரு $k$ -இணைப்பு கொண்டதாக இருக்குமாறுள்ள $k$ இன் மதிப்புகளுள் மிகப்பெரியதாக $κ (G)$ வரையறுக்கப்படும்.

இடஞ்சார் இணைப்பு

ஒரு கோட்டுருவின் $u$ , $v$ ஆகிய "இரு முனைகளின் முனை வெட்டு" என்பது கோட்டுருவின் எந்தெந்த முனைகளின் நீக்கம் $u$ , $v$ இரண்டையும் இணைப்பற்றதாக்குமோ அந்த முனைகளின் கணமாகும்.

இவ்வாறான $u$ , $v$ இன் முனை வெட்டுக்களில் மிகச்சிறிய முனைவெட்டு "இடஞ்சார் இணைப்பு" எனப்படும்.

இடஞ்சார் இணைப்பின் குறியீடு:

κ (u, v)

.

திசையற்ற கோட்டுருக்களில் இடஞ்சார் இணைப்பு சமச்சீரானது:

κ (u, v) = κ (v, u)

.

முழுக்கோட்டுருக்கள் தவிர பிற கோட்டுருக்களுக்கு $κ (G)$ இன் மதிப்பு, $κ (u, v)$ இன் மதிப்புகளின் சிறுமவளவாகும் ( $u, v$ அடுத்தமையாத முனைகள்).

விளிம்புகள்

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

பாலம்

ஒரு கோட்டுருவின் குறிப்பிட்ட எந்த விளிம்பை நீக்க அக்கோட்டுரு இணைப்பற்றதாகுமோ அந்த விளிம்பு பாலம் என அழைக்கப்படும்.

விளிம்பு வெட்டு

எந்தெந்த விளிம்புகளின் நீக்கம் $G$ ஐ இணைப்பற்றதாக்குகின்றதோ அந்த விளிம்புகளின் கணம் "விளிம்பு வெட்டு" ஆகும்.

விளிம்பு-இணைப்பு

"விளிம்பு-இணைப்பு" என்பது "விளிம்பு வெட்டுக்களாக அமையும் கணங்களின் அளவுகளில் சிறும அளவு.

இதன் குறியீடு:

λ (G)

இடஞ்சார் விளிம்பு-இணைப்பு

$u, v$ என்ற இரு முனைகளின் "இடஞ்சார் விளிம்பு-இணைப்பு" என்பது $u$ இலிருந்து $v$ ஐ இணைப்பற்றதாக்கும் "விளிம்பு வெட்டு"க்களில் மிகச்சிறியது.