நிரப்பு கோட்டுரு
கோட்டுருவியலில் ஒரு கோட்டுருவின் (G) நிரப்பு கோட்டுரு (complement) அல்லது நேர்மாறு (inverse) (H) கோட்டுரு பின்வரும் பண்புகளைக் கொண்ட கோட்டுருவாக இருக்கும்:
- G இன் முனைகளே H இன் முனைகளாக இருக்கும்.
- இரு வெவ்வேறான இரு முனைகள் G இல் அடுத்துள்ளவைகளாக இல்லாமல் "இருந்தால், இருந்தால் மட்டுமே" அவை H இல் அடுத்துள்ள முனைகளாக இருக்கும்.
G ஒரு முழுக்கோட்டுருவாகும்படி அதன் இணைக்கப்படாத முனைகளை இணைத்து இல்லாத விளிம்புகளை நிரப்பிய பின்னர் ஏற்கனவே உள்ள விளிம்புகளை நீக்கினால் G இன் நிரப்பு கோட்டுருவான H கிடைக்கும். [1] நிரப்பு கோட்டுருவானது மூலக் கோட்டுருவின் கண நிரப்பி அல்ல; விளிம்புகள் மட்டுமே நிரப்பப்படுகின்றன.
வரையறை
தொகுதிசையற்ற கோட்டுரு
தொகுG = (V, E) ஒரு திசையற்ற கோட்டுரு; K என்பது V இன் ஈருறுப்பு உட்கணங்களைக் கொண்டது எனில், H = (V, K \ E) ஆனது G இன் நிரப்பி ஆகும்.[2]
இதில் K \ E என்பது K இல் E இன் நிரப்பு கணமாகும்.
திசை கோட்டுரு
தொகுதிசையற்ற கோட்டுரு போலவே திசை கோட்டுருவின் நிரப்பியையும் வரையறுக்கலாம்: ஒரு திசை கோட்டுருவின் நிரப்பு கோட்டுருவும் அதே முனைகளைக் கொண்டதொரு திசைக் கோட்டுருவாக இருக்கும். V இன் வரிசைச்சோடிகளாலான உட்கணங்களைக் கொண்டதாக K அமையும்.
- G = (V, E) ஒரு திசை கோட்டுரு; K என்பது V இன் வரிசைச் சோடிகளின் உட்கணங்களைக் கொண்டது எனில், H = (V, K \ E) ஆனது G இன் நிரப்பி ஆகும்.
பயன்பாடுகளும் எடுத்துக்காட்டுகளும்
தொகுபல கோட்டுருவியல் கருத்துகள் நிரப்பு கோட்டுரு வழியாக தொடர்பு கொண்டுள்ளன:
- வெற்று கோட்டுருவின் நிரப்பு கோட்டுரு ஒரு முழுக்கோட்டுருவாக இருக்கும். இதன் மறுதலையும் உண்மையாகும்.
- G கோட்டுருவின் நிரப்பு கோட்டுருவின் தூண்டப்பட்ட உட்கோட்டுருவானது G இல் ஒத்த தூண்டப்பட்ட உட்கோட்டுருவின் நிரப்பு கோட்டுருவாக இருக்கும்.
- ஒரு கோட்டுருவின் சாரா கணமானது, அக்கோட்டுருவின் நிரப்பு கோட்டுருவில் ஒரு குறுகும்பாக இருக்கும். இதன் மறுதலையும் உண்மையாகும். ஒரு கோட்டுருவின் சாரா கணமானது விளிம்பற்ற தூண்டப்பட்ட உட்கோட்டுருவாகவும் ஒரு குறுகும்பு முழுமையான தூண்டப்பட்ட கோட்டுருவாகவும் இருக்கும் என்பதால் இக்கூற்று முதல் இரு கூற்றுகளின் சிறப்புவகையாக அமையும்.
- ஒரு கோட்டுருவின் தன்னுருவாக்கக் குலமானது நிரப்பிக் கோட்டுருவின் தன்னுருவாக்கக் குலமாக இருக்கும்.
- ஒவ்வொரு முக்கோணமற்ற கோட்டுருவின் நிரப்பியும் வளைநகமற்ற கோட்டுருவாகும்.[3] இதன் மறுதலை உண்மையில்லை.
மேற்கோள்கள்
தொகு- ↑ Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, p. 6, பன்னாட்டுத் தரப்புத்தக எண் 0-444-19451-7.
- ↑ Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, பன்னாட்டுத் தரப்புத்தக எண் 3-540-26182-6. Electronic edition, page 4.
- ↑ Chudnovsky, Maria; Seymour, Paul (2005), "The structure of claw-free graphs" (PDF), Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge: Cambridge Univ. Press, pp. 153–171, MR 2187738..