இருகூறு கோட்டுரு

சுழற்சிகளற்ற ஒரு இருகூறு கோட்டுரு

ஒரு முழு இருகூறு கோட்டுரு $|U|=5$ $|V|=3$

கோட்டுருவியலில் இருகூறு கோட்டுரு (bipartite graph) என்பது கீழ்வருமாறு அமையும் கோட்டுருவாகும்:

ஒரு கோட்டுரு இருகூறு கோட்டுருவெனில்:

• அதன் முனைகள் $U,$ $V$ என்ற இரு சேர்ப்பிலா மற்றும் சாரா கணங்களாகப் பிரிக்கப்பட்டிருக்கும்
• $U$ இன் ஒவ்வொரு முனையும் $V$ இன் ஒரு முனையோடு இணைக்கப்பட்டிருக்கும்.

இருகூறு கோட்டுருவின் முனைகணங்கள் $U,$ $V$ இரண்டும் அக்கோட்டுருவின் "பாகங்கள்" எனப்படும். ஒற்றை-நீள சுழற்சிகளற்ற கோட்டுரு இருகூறு கோட்டுருவாக இருக்கும்.

$U,$ $V$ இரண்டையும் இரு நிறங்களைக் கொண்டு கோட்டுருவை நிறந்தீட்டலுக்குச் சமமாகக் கருதலாம். $U$ இலுள்ள முனைகளெல்லாம் நீலநிறத்திலும் $V$ இலுள்ள முனைகளெல்லாம் பச்சை நிறத்திலும் எடுத்துக்கொள்ளப்பட்டால், கோட்டுருவின் ஒவ்வொரு விளிம்பின் ஒரு முனை நீலநிறத்திலும் மற்றொரு முனை பச்சைநிறத்திலும் அதாவது ஒவ்வொரு விளிம்பின் இருமுனைகள் வெவ்வேறு நிறங்களில் அமைந்திருக்கும். இதுவே கோட்டுருநிறந்தீட்டலின் தேவையுமாகும். மாறாக, இருகூறற்ற கோட்டுருவில் இதுபோன்ற நிறந்தீட்டல் சாத்தியமில்லை. எடுத்துக்காட்டாக முக்கோணத்தில் ஒரு முனை நீலம், இரண்டாவது முனை பச்சை நிறமிடப்பட்டால், மூன்றாவது முனை நீலம் மற்றும் பச்சை நிற முனைகள் இரண்டுடனும் இணைக்கப்பட்டிருக்கும். எனவே மூன்றாவது முனைக்கு நீலம் அல்லது பச்சை நிறம் தீட்ட முடியாது. இரண்டில் ஏதேனும் ஒரு நிறத்தை மூன்றாவது முனைக்குத் தீட்டினால் முக்கோணக் கோட்டுருவின் ஒரு விளிம்பு ஒரே நிறமுனைகளைக் கொண்டிருக்கும். இது கோட்டுரு நிறந்தீட்டலின் கட்டுப்பாட்டிற்கு முரணாக அமையும்.

இருகூறு கோட்டுருவானது $G=(U,V,E)$ எனக் குறிக்கப்படுகிறது. இதில் $U,$ $V$ இரண்டும் கோட்டுருவின் பிரிவினைப் பகுதிகள். $E$ கோட்டுருவின் விளிம்புகள்

ஒரு இருகூறு கோட்டுரு இணைப்புள்ளதாக இருந்தால் அதற்கு ஒன்றுக்கு மேற்பட்ட இருகூறுகள் இருக்கலாம். $|U|=|V|$ எனில் (இரண்டிலும் உள்ள முனைகளின் எண்ணிக்கை சமம்), $G$ கோட்டுருவானது "சமநிலை" இருகூறு கோட்டுரு என அழைக்கப்படும்.

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

• வார்ப்புரு:Springer
• Information System on Graph Classes and their Inclusions: bipartite graph
• வார்ப்புரு:Mathworld
• Bipartite graphs in systems biology and medicine