கோட்டுருவியல்: திருத்தங்களுக்கு இடையிலான வேறுபாடு

உள்ளடக்கம் நீக்கப்பட்டது உள்ளடக்கம் சேர்க்கப்பட்டது

வரியுள்

15:09, 28 சூன் 2020 இல் நிலவும் திருத்தம்

கணிதத்தில், கோட்டுருவியல் (graph theory) என்பது கோட்டுருக்களைப் பற்றிய ஆய்வு ஆகும். கோட்டுருக்கள், பொருள்களுக்கு இடையிலான சோடிவரிசை உறவுகளை மாதிரிப்படுத்த உதவும் கணிதக் கட்டமைப்புகள் ஆகும். கோட்டுருக்கள் முனைகள் என அழைக்கப்படும் புள்ளிகளாலும், விளிம்புகள் என அழைக்கப்பயும் இரு முனைகளை இணைக்கும் விளிம்புகளாலும் ஆனது. முனைகள் "கணு"க்கள் என்றும் விளிம்புகள் "இணைப்பு"கள் அல்லது "கோடு"கள் எனவும் அழைக்கப்படுவதும் உண்டு. அடிப்படையில் திசையற்ற கோட்டுருக்கள் மற்றும் திசையுள்ள கோட்டுருக்களென இருவகைப்படுத்தப்படுகின்றன. திசையற்ற கோட்டுருக்களில் இரண்டு முனைகள் விளிம்புகளால் சமச்சீராக இணைக்கப்படுகின்றன. திசை கோட்டுருக்களில் இருமுனைகளை விளிம்புகள் அசமச்சீராக இணைக்கின்றன.

வரையறைகள்

கோட்டுருவியலின் வரையறைகள் வேறுபடுகின்றன. பின்வருபவை கோட்டுருக்கள் மற்றும் தொடர்புடைய கணித கட்டமைப்புகளை வரையறுக்கும் சில அடிப்படை வழிகளாகும்.

கோட்டுரு

வழக்கமாகக் "கோட்டுரு" என்ற சொல் G = (V, E) என்ற வரிசைச் சோடிகளைக் குறிக்கும்^[1]^[2]:

V - "முனை"களின் கணம்
E - விளிம்புகளின் கணம்

E ⊆ {{x, y} | (x, y) ∈ V² ∧ x ≠ y} என்பது முனைகளின் வரிசையற்ற இரு வெவ்வேறு முனைகளாலான "விளிம்பு"களின் கணம்.

இக்கோட்டுருக்கள் "திசையற்ற எளிய கோட்டுருக்கள்" என அழைக்கப்படுகின்றன.

{x, y} என்ற விளிம்பில், x , y இரண்டும் விளிம்பின் இறுதிப்புள்ளிகள் எனப்படும். மேலும் இந்த விளிம்பானது x , y முனைகளை இணைக்கிறது அல்லது அம்முனைகளில் "படு"கிறது எனவும் x , y முனைகளின் "படுகை விளிம்பு" எனவும் அழைக்கப்படும்.

பல்விளிம்புகள்

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

பல்கோட்டுருக்கள்

பல்விளிம்புகளை கணக்கில் கொள்வதற்காகக் கோட்டுருவானது ஒரு வரிசை மும்மையாக G = (V, E, ϕ) வரையறுக்கப்படுகிறது:^[3]^[4]

V - முனைகளின் கணம்;
E - விளிம்புகளின் கணம்;

ϕ: E → {{x, y} | (x, y) ∈ V² ∧ x ≠ y} என்பது ஒவ்வொரு விளிம்பையும் ஒரு வரிசையற்ற சோடி முனைகளுடன் (வெவ்வேறான இரு முனைகள்)கோர்க்கும் "படுகைச் சார்பு" (incidence function) ஆகும்.

குழப்பம் தவிர்க்க முதல் வகையான கோட்டுருக்கள் "திசையற்ற எளிய கோட்டுரு"க்கள் எனவும் பல்விளிம்புகளுடைய கோட்டுருக்கள் "திசையற்ற பல்கோட்டுருக்கள்" எனவும் அழைக்கப்படுகிறன.

கண்ணி

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

திசையற்ற எளிய கோட்டுருக்களின் வரயறையிலுள்ள E ⊆ {{x, y} | (x, y) ∈ V² ∧ x ≠ y} என்பது E ⊆ {{x, y} | (x, y) ∈ V²} என நீட்டிக்கப்பட வேண்டும். இக்கோட்டுருக்கள் "கண்ணிகளை அனுமதிக்கும் திசையற்ற எளிய கோட்டுருக்கள்" எனக் குறிப்பிடப்படுகின்றன.

திசையற்ற பல்கோட்டுருக்கள் வரையறையிலுள்ள ϕ: E → {{x, y} | (x, y) ∈ V² ∧ x ≠ y} என்பது ϕ: E → {{x, y} | (x, y) ∈ V²} என நீட்டிக்கப்பட வேண்டும். இக்கோட்டுருக்கள் "கண்ணிகளை அனுமதிக்கும் திசையற்ற பல்கோட்டுருக்கள்" எனக் குறிப்பிடப்படுகின்றன.

வரிசை, அளவு, படி

பொதுவாக V மற்றும் E ஆகிய இரண்டும் முடிவுற்ற கணங்களாகவே கொள்ளப்படுகின்றன. முடிவுறா கோட்டுருக்களுக்கு பல முடிவுகள் பொருத்தமற்றவையாகவும் வேறானவையாகவும் அமையும். கோட்டுருக்களில் பெரும்பாலும் முனைகளின் கணமான V வெற்றற்ற கணமாகக் கொள்ளப்படுகிறது. ஆனால் விளிம்புகளின் கணமான E வெற்றுக் கணமாக இருக்கலாம்.

|V| ஆனது கோட்டுருவின் "வரிசை" எனவும் |E| ஆனது கோட்டுருவின் "அளவு" எனவும் அழைக்கப்படுகிறது.
ஒரு முனையின் படுகை விளிம்புகளின் எண்ணிக்கை அம்முனையின் "படி" அல்லது "வலு" (degree or valency) எனப்படுகிறது. ஒரு முனையின் படியைக் கணக்கிடும்போது அதிலமையும் கண்ணி இருமுறை கணக்கிடப்படுகிறது.
n வரிசையுடைய திசையற்ற எளிய கோட்டுருவில், ஒவ்வொரு முனையின் பெருமப் படி n − 1 ஆகவும் கோட்டுருவின் பெரும அளவு n(n − 1)/2 ஆகவும் இருக்கும்.

G என்ற கண்ணிகளை அனுமதிக்கும் திசையற்ற எளிய கோட்டுருவின் விளிம்புகள், G இன் முனைகளின் மீது "அடுத்தமையும் உறவை"த் தூண்டுகின்றன. ஒவ்வொரு விளிம்பு {x, y இன் இறுதிப்புள்ளிகள் x , y இரண்டும் அடுத்தடுத்த முனைகளாகும்; இது குறியீட்டில் x ~ y என எழுதப்படுகிறது.

திசை கோட்டுரு

ஒவ்வொரு விளிம்பும் திசையுடையதாகக் உள்ள கோட்டுரு "திசை கோட்டுரு" எனப்படும்.

திசை கோட்டுரு என்பது G = (V, E) என்ற வரிசைச் சோடிகளைக் குறிக்கும்:

V - முனைகளின் கணம்;

E ⊆ {(x, y) | (x, y) ∈ V² ∧ x ≠ y} - விளிம்புகளின் கணம். இவ்விளிம்புகள் திசை விளிம்புகள், திசை இணைப்புகள், அம்புகள் அல்லது விற்கள் எனவும் அழைக்கப்படுகின்றன. விளிம்புகளின் இறுதிமுனைகள் வெவ்வேறானவை.

இக்கோட்டுருக்கள் "திசையுள்ள எளிய கோட்டுருக்கள்" எனப்படுகின்றன.

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

மேற்கோள்கள்

↑ 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.

[FOOTNOTEBenderWilliamson2010148-1] Bender & Williamson 2010, ப. 148.

[2] See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.

[FOOTNOTEBenderWilliamson2010149-3] Bender & Williamson 2010, ப. 149.

[4] See, for instance, Graham et al., p. 5.

[1]

[2]

[3]

[4]

@@ வரிசை 19: / வரிசை 19: @@
 ஒரே வரிசைச் சோடி முனைகளை இணைக்கும் பல விளிம்புகள் பல இருக்குமானால் அவை "[[பல்விளிம்புகள்]]" எனப்படுகின்றன.
+;பல்கோட்டுருக்கள்
 பல்விளிம்புகளை கணக்கில் கொள்வதற்காகக் கோட்டுருவானது ஒரு வரிசை மும்மையாக {{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}} வரையறுக்கப்படுகிறது:{{sfn|Bender|Williamson|2010|p=149}}<ref>See, for instance, Graham et al., p. 5.</ref>
 * ''V'' - முனைகளின் [[கணம் (கணிதம்)|கணம்]];