பல்கோட்டுரு
கணிதத்திலும் கோட்டுருவியலிலும் பல்கோட்டுரு (multigraph) என்பது பல்விளிம்புகள் (இணை விளிம்புகள்) கொண்டிருப்பதற்கு அனுமதிக்கப்பட்ட கோட்டுருவாகும்.[1]) அதாவது, பல்கோட்டுருவில் ஒரே இரு முனைகளை ஒன்றுக்கு மேற்பட்ட விளிம்புகள் இணைத்திருக்கும்.
ஒரு விளிம்பின் தன்னடையாளம் என்பது அது இணைக்கும் முனைகளைக் கொண்டு வரையறுக்கப்படுகிறது. இருவிதமான பல்விளிம்புகள்:
- தன்னடையாளமற்ற பல்விளிம்புகள் (Edges without own identity):
- தன்னடையாளமற்ற பல்விளிம்புகள் என்பது, ஒரே சோடி முனைகளுக்கிடையே ஒரு விளிம்பு பலதடவைகள் அமையும் ஒரே விளிம்பைக் குறிக்கிறது.
- தன்னடையாளமுள்ள பல்விளிம்புகள் (Edges with own identity):
- வெவ்வேறு விளிம்புகள், ஒரே சோடி முனைகளை இணைக்குமானால் அந்தப் பல்விளிம்புகள் தன்னடையாளமுள்ள பல்விளிம்புகள் ஆகும்.
ஒரு விளிம்பு இரு முனைகளை மட்டுமல்லாது, எத்தனை முனைகளையும் இணைக்கக்கூடிய பண்புடைய மீகோட்டுருவிலிருந்து பல்கோட்டுருவானது வேறுபட்டது. சில அறிஞர்கள் பல்கோட்டுருவையும் "போலி கோட்டுரு"வையும் ஒன்றாகக் கருதுகிறார்கள்; வேறு சிலர் போலி கோட்டுருவைக் கண்ணிகள் அனுமதிக்கப்பட்ட பல்கோட்டுருவாகக் கருதுகிறார்கள்
திசையற்ற பல்கோட்டுரு தொகு
- தன்னடையாளமற்ற விளிம்புகள் கொண்ட பல்கோட்டுரு
இவ்வகையான கோட்டுரு G என்பது G:=(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 - விளிம்புகளின் கணம்
- , ஒவ்வொரு விளிம்புக்கும் அதன் மூல முனையை இணைக்கிறது.
- , ஒவ்வொரு விளிம்புக்கும் அதன் இலக்கு முனையை இணைக்கிறது
குறிப்புகள் தொகு
மேற்கோள்கள் தொகு
- Balakrishnan, V. K. (1997). Graph Theory. McGraw-Hill. பன்னாட்டுத் தரப்புத்தக எண்:0-07-005489-4.
- Béla Bollobás (2002). Modern Graph Theory. Graduate Texts in Mathematics. 184. Springer. பன்னாட்டுத் தரப்புத்தக எண்:0-387-98488-7.
- Gary Chartrand; Ping Zhang (graph theorist) (2012). A First Course in Graph Theory. Dover. பன்னாட்டுத் தரப்புத்தக எண்:978-0-486-48368-9. https://archive.org/details/firstcourseingra0000char.
- Diestel, Reinhard (2010). Graph Theory. Graduate Texts in Mathematics. 173 (4th ). 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, தொகுப்பாசிரியர்கள் (2003). Handbook of Graph Theory. CRC. பன்னாட்டுத் தரப்புத்தக எண்:1-58488-090-2.
- Frank Harary (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. https://books.google.com/?id=iq0sSnIxJioC&pg=PA6&dq=pseudograph.
- Zwillinger, Daniel (2002). CRC Standard Mathematical Tables and Formulae (31st ). Chapman & Hall/CRC. பன்னாட்டுத் தரப்புத்தக எண்:1-58488-291-3.
வெளியிணைப்புகள் தொகு
- Black, Paul E. "Multigraph". Dictionary of Algorithms and Data Structures. NIST.