மீகோட்டுரு

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

படிமம்:Hypergraph-wikipedia.svg

மீகோட்டுருவிற்கு ஒரு எடுத்துக்காட்டு. $X=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}$ $E=\{e_1,e_2,e_3,e_4\}=$ $\{\{v_1,v_2,v_3\},$ $\{v_2,v_3\},$ $\{v_3,v_5,v_6\},$ $\{v_4\}\}$. இதன் வரிசை 7; அளவு 4. நிறமிட்டுக் காட்டப்பட்டுள்ள மீவிளிம்புகள் இரு முனைகளை மட்டும் இணைக்காமல் பல முனைகளை இணைப்பதைக் காணலாம்..

சிறு முன்தோற்றத்தை உருவாக்கப்படுவதில் தவறு:

மேலுள்ள பட மீகோட்டுருவின் மாற்று உருவகிப்பு (PAOH) முனைகளை இணைக்கும் குத்துக்கோடுகளாக விளிம்புகள் காட்டப்பட்டுள்ளன. முனைகள் இடப்புறம் வரிசைப்படுத்தப்பட்டுள்ளன. வலப்புறம் விளிம்புகளின் பெயர்கள் குறிப்பிடப்பட்டுள்ளன

மீகோட்டுரு $H$ என்பது $H=(X,E)$ என்ற சோடியைக் குறிக்கும். இதில்

• $X$ - முனைகளின் கணம்.
• $E$ - $X$ இன் வெற்றுக்கணமற்ற உட்கணங்களின் கணம். இந்த உட்கணங்கள் மீவிளிம்புகள் (hyperedges) அல்லது விளிம்புகள் என அழைக்கப்படும்.

$E$ என்பது ${𝒫}(X)\setminus \{\mathrm{\varnothing }\}$ இன் உட்கணமாக அமைகிறது. ${𝒫}(X)$ - $X$ இன் அடுக்கு கணம்.

$|X|$ - முனைகளின் கணத்தின் அளவு "மீகோட்டுருவின் வரிசை" எனவும் $|E|$ மீவிளிம்பு கணத்தின் அளவு "மீகோட்டுருவின் அளவு" எனவும் அழைக்கப்படும்.

பண்புகள்

மீகோட்டுருக்கள் பின்வருமாறு அமையலாம்.

• வெற்று கோட்டுரு - விளிம்புகள் இல்லாத கோட்டுரு
• பல்கோட்டுரு - கண்ணிகள் கொண்ட அல்லது பல்விளிம்புகள் கொண்டதாக இருக்கலாம் (ஒரே முனைகளைக் கொண்ட விளிம்புகள்).
• எளிய கோட்டுரு - கண்ணிகளோ அல்லது பல்விளிம்புகளோ அற்றது.
• $k$-சீரானது - ஒவ்வொரு மீவிளிம்பும் $k$ முனைகளை இணைக்கும்.
• $d$-ஒழுங்கு - ஒவ்வொரு முனையும் $d$ படிகொண்டதாக இருக்கும்.
• சுழற்சியற்ற கோட்டுரு.
• இருகூறு கோட்டுரு - கோட்டுருவை U , V என்ற இரு தொகுப்பாகப் பிரிக்கலாம்: குறைந்தபட்சம் 2 அளவுகொண்ட மீவிளிம்புகள் ஒவ்வொன்றும், ஒவ்வொரு தொகுதியிலிருந்தும் குறைந்தது ஒரு முனையைக் கொண்டிருக்கும்.

படுகை அணி

• $V=\{v_1,v_2,\dots ,v_n\}$
• $E=\{e_1,e_2,\dots e_m\}$.

ஒவ்வொரு மீகோட்டுருவுக்கும் Every hypergraph has an $n\times m$ படுகை அணி $A=(a_{ij})$ உண்டு. இதில்:

$a_{ij}=\{\begin{array}{cc}1& \mathrm{i}\mathrm{f}{v}_i\in e_j\\ 0& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}$

படுகை அணியின் இடமாற்று அணி $A^t$, $H^{*}=(V^{*},E^{*})$ என்ற மீகோட்டுருவை வரையறுக்கிறது.

• $H^{*}=(V^{*},E^{*})$ ஆனது $H$ இன் "இரட்டை" எனப்படும்.
• $V^{*}$ இன் உறுப்புகளின் எண்ணிக்கை m
• $E^{*}$ இன் உறுப்புகளின் எண்ணிக்கை n; மேலும் அவ்வுறுப்புகள்
• $V^{*}$ இன் உட்கணங்களாக இருக்கும். $a_{ij}=1$ என இருந்தால், இருந்தால் மட்டுமே, $v_j^{*}\in V^{*}$ மற்றும் $e_i^{*}\in E^{*}$ எனில், $v_j^{*}\in e_i^{*}$ ஆக இருக்கும்.

மேற்கோள்கள்

• Claude Berge, "Hypergraphs: Combinatorics of finite sets". North-Holland, 1989.
• Claude Berge, Dijen Ray-Chaudhuri, "Hypergraph Seminar, Ohio State University 1972", Lecture Notes in Mathematics 411 Springer-Verlag
• Hazewinkel, Michiel, ed. (2001), "Hypergraph", Encyclopedia of Mathematics, Springer, ISBN 978-1556080104
• Alain Bretto, "Hypergraph Theory: an Introduction", Springer, 2013.
• Vitaly I. Voloshin. "Coloring Mixed Hypergraphs: Theory, Algorithms and Applications". Fields Institute Monographs, American Mathematical Society, 2002.
• Vitaly I. Voloshin. "Introduction to Graph and Hypergraph Theory". Nova Science Publishers, Inc., 2009.
• This article incorporates material from hypergraph on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

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

தமிழர்விக்கி பொதுவகத்தில் விரைவில் வருவதற்கு உதவி செய்யுங்கள்.

• PAOHVis: open-source PAOHVis system for visualizing dynamic hypergraphs.