பல்கோட்டுரு

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

பல்விளிம்புகள் (சிவப்பு) மற்றும் கண்ணிகள் (நீலம்) கொண்ட பல்கோட்டுரு. (சில அறிஞர்கள் பல்கோட்டுருக்களில் கண்ணிகளை அனுமதிப்பதில்லை)

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

• தன்னடையாளமற்ற பல்விளிம்புகள் (Edges without own identity):

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

• தன்னடையாளமுள்ள பல்விளிம்புகள் (Edges with own identity):

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

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

திசையற்ற பல்கோட்டுரு

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

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

• V - முனைகளின் கணம்;
• E - விளிம்புகளென அழைக்கப்படும் வரிசையற்ற முனைச் சோடிகளின் பல்கணம்

தன்னடையாளமுள்ள விளிம்புகள் கொண்ட பல்கோட்டுரு

இவ்வகையான கோட்டுரு G என்பது G:=(V, E, r) என்ற மும்மையாகும். இதில்:

• V - முனைகளின் கணம்;
• E - விளிம்புகளின் கணம்,
• r : E → {{x,y} : x, y ∈ V}, ஒவ்வொரு விளிம்புடனும் ஒரு வரிசையற்ற சோடி முனைகளை கோர்க்கிறது.

சில அறிஞர்கள் ஒரு முனையுடனை அதனுடனேயே இணைக்கும் கண்ணிகளைக் கொண்டிருக்கவும் பல்கோட்டுருக்களை அனுமதிக்கின்றனர்.^[2]வேறுசிலர் கண்ணிகளற்ற ஆனால் பல்விளிம்புகள் கொண்ட கோட்டுருக்களை பல்கோட்டுருக்கள் என்றும், கண்ணிகளும் பல்விளிம்புகளும் கொண்ட கோட்டுருக்களை போலி கோட்டுருக்கள் என்றும் வேறுபடுத்திக் குறிப்பிடுகின்றனர்.^[3]

திசையுள்ள பல்கோட்டுரு

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

இக்கோட்டுரு G என்பது G:=(V,A) என்ற வரிசைச்சோடியாகும். இதில்:

• V - முனைகளின் கணம்;
• A திசையிடப்பட்ட விளிம்புகள் அல்லது விற்கள் அல்லது அம்புகள் என அழைக்கப்படும் முனைகளின் வரிசைச்சோடிகளின் பல்கணம்.

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

இக்கோட்டுரு G := (V, A, s, t) ஆகும். இதில்:

• V - முனைகளின் கணம்
• A - விளிம்புகளின் கணம்
• ${\displaystyle s:A\rightarrow V}$, ஒவ்வொரு விளிம்புக்கும் அதன் மூல முனையை இணைக்கிறது.
• ${\displaystyle t:A\rightarrow V}$, ஒவ்வொரு விளிம்புக்கும் அதன் இலக்கு முனையை இணைக்கிறது

குறிப்புகள்

1. For example, see Balakrishnan 1997, p. 1 or Chartrand and Zhang 2012, p. 26.
2. For example, see Bollobás 2002, p. 7 or Diestel 2010, p. 28.
3. For example, see Wilson 2002, p. 6 or Chartrand and Zhang 2012, pp. 26-27.

மேற்கோள்கள்

• Balakrishnan, V. K. (1997). Graph Theory. McGraw-Hill. பன்னாட்டுத் தரப்புத்தக எண் 0-07-005489-4.
• Bollobás, Béla (2002). Modern Graph Theory. Graduate Texts in Mathematics. Vol. 184. Springer. பன்னாட்டுத் தரப்புத்தக எண் 0-387-98488-7.
• Chartrand, Gary; Zhang, Ping (2012). A First Course in Graph Theory. Dover. பன்னாட்டுத் தரப்புத்தக எண் 978-0-486-48368-9.
• Diestel, Reinhard (2010). Graph Theory. Graduate Texts in Mathematics. Vol. 173 (4th ed.). Springer. பன்னாட்டுத் தரப்புத்தக எண் 978-3-642-14278-9.
• Gross, Jonathan L.; Yellen, Jay (1998). Graph Theory and Its Applications. CRC Press. பன்னாட்டுத் தரப்புத்தக எண் 0-8493-3982-0.
• Gross, Jonathan L.; Yellen, Jay, eds. (2003). Handbook of Graph Theory. CRC. பன்னாட்டுத் தரப்புத்தக எண் 1-58488-090-2.
• Harary, Frank (1995). Graph Theory. Addison Wesley. பன்னாட்டுத் தரப்புத்தக எண் 0-201-41033-8.
• Svante Janson; Donald Knuth; Luczak, Tomasz; Pittel, Boris (1993). "The birth of the giant component". Random Structures and Algorithms 4 (3): 231–358. doi:10.1002/rsa.3240040303. பன்னாட்டுத் தர தொடர் எண்:1042-9832. Bibcode: 1993math.....10236J.
• Wilson, Robert A. (2002). Graphs, Colourings and the Four-Colour Theorem. Oxford Science Publ. பன்னாட்டுத் தரப்புத்தக எண் 0-19-851062-4.
• Zwillinger, Daniel (2002). CRC Standard Mathematical Tables and Formulae (31st ed.). Chapman & Hall/CRC. பன்னாட்டுத் தரப்புத்தக எண் 1-58488-291-3.

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

• Black, Paul E. "Multigraph". Dictionary of Algorithms and Data Structures. NIST.