மீகோட்டுரு

படிமம்: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) முனைகளை இணைக்கும் குத்துக்கோடுகளாக விளிம்புகள் காட்டப்பட்டுள்ளன. முனைகள் இடப்புறம் வரிசைப்படுத்தப்பட்டுள்ளன. வலப்புறம் விளிம்புகளின் பெயர்கள் குறிப்பிடப்பட்டுள்ளன

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

மீகோட்டுரு $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.