கோட்டுருவியல்: திருத்தங்களுக்கு இடையிலான வேறுபாடு
வரிசை 8: | வரிசை 8: | ||
[[File:Undirected.svg|thumb|100px|மூன்று முனைகளும் மூன்று விளிம்புகளும் கொண்ட கோட்டுரு.]] |
[[File:Undirected.svg|thumb|100px|மூன்று முனைகளும் மூன்று விளிம்புகளும் கொண்ட கோட்டுரு.]] |
||
வழக்கமாகக் "கோட்டுரு" என்ற சொல் {{nowrap|1=''G'' = (''V'', ''E'')}} என்ற [[வரிசைச் சோடி]]களைக் குறிக்கும்{{sfn|Bender|Williamson|2010|p=148}}<ref>See, for instance, Iyanaga and Kawada, ''69 J'', p. 234 or Biggs, p. 4.</ref>: |
வழக்கமாகக் "கோட்டுரு" என்ற சொல் {{nowrap|1=''G'' = (''V'', ''E'')}} என்ற [[வரிசைச் சோடி]]களைக் குறிக்கும்{{sfn|Bender|Williamson|2010|p=148}}<ref>See, for instance, Iyanaga and Kawada, ''69 J'', p. 234 or Biggs, p. 4.</ref>: |
||
* ''V'' - "முனை"களின் [[கணம் (கணிதம்)|கணம்]] |
* ''V'' - "முனை"களின் [[கணம் (கணிதம்)|கணம்]] |
||
* ''E'' - விளிம்புகளின் கணம் |
|||
:{{nowrap begin}}''E'' ⊆ {{''x'', ''y''} | (''x'', ''y'') ∈ ''V''<sup>2</sup> ∧ x ≠ y}{{nowrap end}} என்பது முனைகளின் வரிசையற்ற இரு வெவ்வேறு முனைகளாலான "விளிம்பு"களின் கணம் |
|||
{{nowrap|{''x'', ''y''}}} என்ற விளிம்பில், ''x'' , ''y'' இரண்டும் விளிம்பின் இறுதிப்புள்ளிகள் எனப்படும். மேலும் இந்த விளிம்பானது ''x'' , ''y'' முனைகளை இணைக்கிறது அல்லது அம்முனைகளில் "படு"கிறது எனவும் ''x'' , ''y'' முனைகளின் "படுகை விளிம்பு" எனவும் அழைக்கப்படும். |
{{nowrap|{''x'', ''y''}}} என்ற விளிம்பில், ''x'' , ''y'' இரண்டும் விளிம்பின் இறுதிப்புள்ளிகள் எனப்படும். மேலும் இந்த விளிம்பானது ''x'' , ''y'' முனைகளை இணைக்கிறது அல்லது அம்முனைகளில் "படு"கிறது எனவும் ''x'' , ''y'' முனைகளின் "படுகை விளிம்பு" எனவும் அழைக்கப்படும். |
||
;பல்விளிம்புகள் |
|||
⚫ | |||
ஒரே வரிசைச் சோடி முனைகளை இணைக்கும் பல விளிம்புகள் பல இருக்குமானால் அவை "[[பல்விளிம்புகள்]]" எனப்படுகின்றன. |
|||
⚫ | |||
* ''V'' - முனைகளின் [[கணம் (கணிதம்)|கணம்]]; |
* ''V'' - முனைகளின் [[கணம் (கணிதம்)|கணம்]]; |
||
* ''E'' - விளிம்புகளின் [[கணம் (கணிதம்)|கணம்]]; |
* ''E'' - விளிம்புகளின் [[கணம் (கணிதம்)|கணம்]]; |
||
* {{nowrap begin}}''ϕ'': ''E'' → {{''x'', ''y''} | (''x'', ''y'') ∈ ''V''<sup>2</sup> ∧ x ≠ y}{{nowrap end}} என்பது ஒவ்வொரு விளிம்பையும் ஒரு வரிசையற்ற சோடி முனைகளுடன் (வெவ்வேறான இரு முனைகள்)கோர்க்கும் "படுகைச் சார்பு" (''incidence function'') ஆகும். |
* {{nowrap begin}}''ϕ'': ''E'' → {{''x'', ''y''} | (''x'', ''y'') ∈ ''V''<sup>2</sup> ∧ x ≠ y}{{nowrap end}} என்பது ஒவ்வொரு விளிம்பையும் ஒரு வரிசையற்ற சோடி முனைகளுடன் (வெவ்வேறான இரு முனைகள்)கோர்க்கும் "படுகைச் சார்பு" (''incidence function'') ஆகும். |
||
குழப்பம் தவிர்க்க |
குழப்பம் தவிர்க்க முதல் வகையான கோட்டுருக்கள் "திசையற்ற எளிய கோட்டுரு"க்கள் எனவும் பல்விளிம்புகளுடைய கோட்டுருக்கள் "திசையற்ற [[பல்கோட்டுரு]]க்கள்" எனவும் அழைக்கப்படுகிறன. |
||
;கண்ணி |
|||
ஒரு முனையை அதனுடனேயே இணைக்கும் விளிம்பானது [[கண்ணி (கோட்டுருவியல்)|கண்ணி]] என அழைக்கப்படும். மேலே தரப்பட்ட இரு வரையறைகளில் கண்ணிகள் இருக்க முடியாது. கண்ணிகள் அனுமதிக்கப்படுவதற்கு அவ்வரையறைகள் பின்னுள்ளவாறு நீட்டிக்கப்பட வேண்டும். |
ஒரு முனையை அதனுடனேயே இணைக்கும் விளிம்பானது [[கண்ணி (கோட்டுருவியல்)|கண்ணி]] என அழைக்கப்படும். மேலே தரப்பட்ட இரு வரையறைகளில் கண்ணிகள் இருக்க முடியாது. கண்ணிகள் அனுமதிக்கப்படுவதற்கு அவ்வரையறைகள் பின்னுள்ளவாறு நீட்டிக்கப்பட வேண்டும். |
||
⚫ | திசையற்ற எளிய கோட்டுருக்களின் வரயறையிலுள்ள {{nowrap begin}}''E'' ⊆ {{''x'', ''y''} | (''x'', ''y'') ∈ ''V''<sup>2</sup> ∧ x ≠ y}{{nowrap end}} என்பது {{nowrap begin}}''E'' ⊆ {{''x'', ''y''} | (''x'', ''y'') ∈ ''V''<sup>2</sup>}{{nowrap end}} என நீட்டிக்கப்பட வேண்டும். இக்கோட்டுருக்கள் "கண்ணிகளை அனுமதிக்கும் திசையற்ற எளிய கோட்டுருக்கள்" எனக் குறிப்பிடப்படுகின்றன. |
||
திசையற்ற எளிய கோட்டுருக்களின் வரயறையிலுள்ள |
|||
:{{nowrap begin}}''E'' ⊆ {{''x'', ''y''} | (''x'', ''y'') ∈ ''V''<sup>2</sup> ∧ x ≠ y}{{nowrap end}} என்பது {{nowrap begin}}''E'' ⊆ {{''x'', ''y''} | (''x'', ''y'') ∈ ''V''<sup>2</sup>}{{nowrap end}} |
|||
⚫ | |||
திசையற்ற பல்கோட்டுருக்கள் வரையறையிலுள்ள |
|||
:{{nowrap begin}}''ϕ'': ''E'' → {{''x'', ''y''} | (''x'', ''y'') ∈ ''V''<sup>2</sup> ∧ x ≠ y}{{nowrap end}} என்பது {{nowrap begin}}''ϕ'': ''E'' → {{''x'', ''y''} | (''x'', ''y'') ∈ ''V''<sup>2</sup>}{{nowrap end}} |
|||
என நீட்டிக்கப்பட வேண்டும். இக்கோட்டுருக்கள் "கண்ணிகளை அனுமதிக்கும் திசையற்ற பல்கோட்டுருக்கள்" எனக் குறிப்பிடப்படுகின்றன. |
திசையற்ற பல்கோட்டுருக்கள் வரையறையிலுள்ள {{nowrap begin}}''ϕ'': ''E'' → {{''x'', ''y''} | (''x'', ''y'') ∈ ''V''<sup>2</sup> ∧ x ≠ y}{{nowrap end}} என்பது {{nowrap begin}}''ϕ'': ''E'' → {{''x'', ''y''} | (''x'', ''y'') ∈ ''V''<sup>2</sup>}{{nowrap end}} என நீட்டிக்கப்பட வேண்டும். இக்கோட்டுருக்கள் "கண்ணிகளை அனுமதிக்கும் திசையற்ற பல்கோட்டுருக்கள்" எனக் குறிப்பிடப்படுகின்றன. |
||
== மேற்கோள்கள் == |
== மேற்கோள்கள் == |
13:51, 28 சூன் 2020 இல் நிலவும் திருத்தம்
கணிதத்தில், கோட்டுருவியல் (graph theory) என்பது கோட்டுருக்களைப் பற்றிய ஆய்வு ஆகும். கோட்டுருக்கள், பொருள்களுக்கு இடையிலான சோடிவரிசை உறவுகளை மாதிரிப்படுத்த உதவும் கணிதக் கட்டமைப்புகள் ஆகும். கோட்டுருக்கள் முனைகள் என அழைக்கப்படும் புள்ளிகளாலும், விளிம்புகள் என அழைக்கப்பயும் இரு முனைகளை இணைக்கும் விளிம்புகளாலும் ஆனது. முனைகள் "கணு"க்கள் என்றும் விளிம்புகள் "இணைப்பு"கள் அல்லது "கோடு"கள் எனவும் அழைக்கப்படுவதும் உண்டு. அடிப்படையில் திசையற்ற கோட்டுருக்கள் மற்றும் திசையுள்ள கோட்டுருக்களென இருவகைப்படுத்தப்படுகின்றன. திசையற்ற கோட்டுருக்களில் இரண்டு முனைகள் விளிம்புகளால் சமச்சீராக இணைக்கப்படுகின்றன. திசை கோட்டுருக்களில் இருமுனைகளை விளிம்புகள் அசமச்சீராக இணைக்கின்றன.
வரையறைகள்
கோட்டுருவியலின் வரையறைகள் வேறுபடுகின்றன. பின்வருபவை கோட்டுருக்கள் மற்றும் தொடர்புடைய கணித கட்டமைப்புகளை வரையறுக்கும் சில அடிப்படை வழிகளாகும்.
கோட்டுரு
வழக்கமாகக் "கோட்டுரு" என்ற சொல் G = (V, E) என்ற வரிசைச் சோடிகளைக் குறிக்கும்[1][2]:
- V - "முனை"களின் கணம்
- E - விளிம்புகளின் கணம்
E ⊆ {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} என்பது முனைகளின் வரிசையற்ற இரு வெவ்வேறு முனைகளாலான "விளிம்பு"களின் கணம்
{x, y} என்ற விளிம்பில், x , y இரண்டும் விளிம்பின் இறுதிப்புள்ளிகள் எனப்படும். மேலும் இந்த விளிம்பானது x , y முனைகளை இணைக்கிறது அல்லது அம்முனைகளில் "படு"கிறது எனவும் x , y முனைகளின் "படுகை விளிம்பு" எனவும் அழைக்கப்படும்.
- பல்விளிம்புகள்
ஒரே வரிசைச் சோடி முனைகளை இணைக்கும் பல விளிம்புகள் பல இருக்குமானால் அவை "பல்விளிம்புகள்" எனப்படுகின்றன.
பல்விளிம்புகளை கணக்கில் கொள்வதற்காகக் கோட்டுருவானது ஒரு வரிசை மும்மையாக G = (V, E, ϕ) வரையறுக்கப்படுகிறது:[3][4]
ϕ: E → {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} என்பது ஒவ்வொரு விளிம்பையும் ஒரு வரிசையற்ற சோடி முனைகளுடன் (வெவ்வேறான இரு முனைகள்)கோர்க்கும் "படுகைச் சார்பு" (incidence function) ஆகும்.
குழப்பம் தவிர்க்க முதல் வகையான கோட்டுருக்கள் "திசையற்ற எளிய கோட்டுரு"க்கள் எனவும் பல்விளிம்புகளுடைய கோட்டுருக்கள் "திசையற்ற பல்கோட்டுருக்கள்" எனவும் அழைக்கப்படுகிறன.
- கண்ணி
ஒரு முனையை அதனுடனேயே இணைக்கும் விளிம்பானது கண்ணி என அழைக்கப்படும். மேலே தரப்பட்ட இரு வரையறைகளில் கண்ணிகள் இருக்க முடியாது. கண்ணிகள் அனுமதிக்கப்படுவதற்கு அவ்வரையறைகள் பின்னுள்ளவாறு நீட்டிக்கப்பட வேண்டும்.
திசையற்ற எளிய கோட்டுருக்களின் வரயறையிலுள்ள E ⊆ {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} என்பது E ⊆ {{x, y} | (x, y) ∈ V2} என நீட்டிக்கப்பட வேண்டும். இக்கோட்டுருக்கள் "கண்ணிகளை அனுமதிக்கும் திசையற்ற எளிய கோட்டுருக்கள்" எனக் குறிப்பிடப்படுகின்றன.
திசையற்ற பல்கோட்டுருக்கள் வரையறையிலுள்ள ϕ: E → {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} என்பது ϕ: E → {{x, y} | (x, y) ∈ V2} என நீட்டிக்கப்பட வேண்டும். இக்கோட்டுருக்கள் "கண்ணிகளை அனுமதிக்கும் திசையற்ற பல்கோட்டுருக்கள்" எனக் குறிப்பிடப்படுகின்றன.
மேற்கோள்கள்
- ↑ Bender & Williamson 2010, ப. 148.
- ↑ See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
- ↑ Bender & Williamson 2010, ப. 149.
- ↑ See, for instance, Graham et al., p. 5.