மீகோட்டுரு

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

மீகோட்டுருவிற்கு ஒரு எடுத்துக்காட்டு. ${\displaystyle X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}}$ ${\displaystyle E=\{e_{1},e_{2},e_{3},e_{4}\}=}$ ${\displaystyle \{\{v_{1},v_{2},v_{3}\},}$ ${\displaystyle \{v_{2},v_{3}\},}$ ${\displaystyle \{v_{3},v_{5},v_{6}\},}$ ${\displaystyle \{v_{4}\}\}}$. இதன் வரிசை 7; அளவு 4. நிறமிட்டுக் காட்டப்பட்டுள்ள மீவிளிம்புகள் இரு முனைகளை மட்டும் இணைக்காமல் பல முனைகளை இணைப்பதைக் காணலாம்..

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

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

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

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

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

பண்புகள்

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

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

படுகை அணி

• ${\displaystyle V=\{v_{1},v_{2},~\ldots ,~v_{n}\}}$
• ${\displaystyle E=\{e_{1},e_{2},~\ldots ~e_{m}\}}$.

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

${\displaystyle a_{ij}=\left\{{\begin{matrix}1&\mathrm {if} ~v_{i}\in e_{j}\\0&\mathrm {otherwise} .\end{matrix}}\right.}$

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

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

குறிப்புகள்

1. Valdivia, Paola; Buono, Paolo; Plaisant, Catherine; Dufournaud, Nicole; Fekete, Jean-Daniel (2020). "Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization". IEEE Transactions on Visualization and Computer Graphics (IEEE) 26: 12. doi:10.1109/TVCG.2019.2933196. பன்னாட்டுத் தர தொடர் எண்:1077-2626. பப்மெட்:31398121.

மேற்கோள்கள்

• 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, பன்னாட்டுத் தரப்புத்தக எண் 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.
• வார்ப்புரு:PlanetMath attribution

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

விக்கிமீடியா பொதுவகத்தில்,
Hypergraphs
என்பதில் ஊடகங்கள் உள்ளன.

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