தூண்டப்பட்ட உட்கோட்டுரு

தூண்டப்பட்ட உட்கோட்டுரு (induced subgraph) என்பது ஒரு கோட்டுவின் உட்கோட்டுரு ஆகும். மூலக் கோட்டுருவின் கணுக்களின் உட்கணம் ஒன்றிலுள்ள கணுக்களாலும் அவற்றின் இருமங்களை இணைக்கும் விளிம்புகளாலுமான உட்கோட்டுருவாக இது அமையும்.

வரையறை தொகு

G = (V, E) என்பது ஒரு கோட்டுரு; இதன் கணுக்களின் உட்கணம் S, SV எனில்:

தூண்டப்பட்ட உட்கோட்டுரு G[S] வின் கணுக்களும் விளிம்புகளும் பின்வருவனவாக இருக்கும்:

  • கணுக்கள்: S
  • விளிம்புகள்: கோட்டுரு G இன் விளிம்புகணமான (E) இல் உள்ள விளிம்புகளில், முனைகளை S இல் கொண்ட விளிம்புகள்[1]

திசையிலாக் கோட்டுருக்களுக்கும் திசை கோட்டுருக்களுக்கும், பல்கோட்டுருகளுக்கும் இந்த வரையறை பொருந்தும்.

மேற்கோள்கள் தொகு

  1. Diestel, Reinhard (2006), Graph Theory, Graduate texts in mathematics, vol. 173, Springer-Verlag, pp. 3–4, ISBN 9783540261834.