Többrészes gráf
A matematika, azon belül a gráfelmélet területén egy többrészes gráf, specifikusan, egy k-részes gráf (k-partite graph) olyan gráf, melynek csúcsai k darab különböző független halmazba particionálhatók. Ezzel ekvivalens kijelentés, hogy ha egy gráf akkor k-részes, ha kiszínezhető k színnel úgy, hogy egy él két végpontja mindig eltérő színű legyen.. A k = 2 esetet páros gráfoknak vagy kétrészes gráfoknak nevezzük, néha megkülönböztetik még a k = 3, háromrészes gráf (tripartite graph) esetet.
Míg a páros gráfok polinom idő alatt felismerhetők, bármely k > 2-re adott színezetlen gráf k-részességének felismerése NP-teljes probléma.[1] A gráfelmélet egyes alkalmazásaiban azonban egy k-részes gráf a már meghatározott színezésével együtt jelenti a bemenetet; ez jellemzően akkor történik, ha a gráf különböző partícióba tartozó csúcsai különböző típusú objektumokat jelképeznek. Például a közösségi klasszifikációs rendszerek (folksonomy) matematikailag olyan háromrészes gráfokkal modellezhetők, melyekben a gráf egyik partíciójának csúcsai a rendszer felhasználóit jelképezik, másik az erőforrásokat, amiket a felhasználók osztályoznak, a harmadik pedig a felhasználók által az erőforrásokhoz rendelt osztályokat.[2]
| K2,2,2 | K3,3,3 | K2,2,2,2 |
|---|---|---|
 Oktaéder gráfja |
 Komplex általánosított oktaéder gráfja |
 16-cella gráfja |
Egy teljes k-részes gráf olyan k-részes gráf, melynek bármely, különböző független halmazba tartozó csúcspárja között él húzódik. Jelölésük nagy K, majd alsó indexben vesszővel elválasztva az egyes partíciók méretei. Például a K2,2,2 a szabályos oktaéder teljes háromrészes gráfja, ami három, egyenként két, szemközti helyzetű csúcsba particionálható. Egy teljes többrészes gráf olyan gráf, ami teljes k-részes gráf valamely k-ra.[3] A k = 2 eset a teljes páros gráfokat adja.
A Turán-gráfok a teljes többrészes gráfok speciális esetei, melyben két független csúcshalmaz mérete legfeljebb egy-egy csúccsal tér el. A teljes többrészes gráfok és komplementereik, a klasztergráfok is a kográfok speciális esetei, még akkor is polinom időben felismerhetők, ha a partíciókat nem adják meg bemenetként.
Jegyzetek
[szerkesztés]- ↑ Garey, M. R. & Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, GT4, ISBN 0-7167-1045-5.
- ↑ Hotho, Andreas; Jäschke, Robert & Schmitz, Christoph et al. (2006), "FolkRank : A Ranking Algorithm for Folksonomies", LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, October 9th-11th 2006, pp. 111–114, <http://opus.bsz-bw.de/ubhi/volltexte/2011/39/>.
- ↑ Chartrand, Gary & Zhang, Ping (2008), Chromatic Graph Theory, CRC Press, p. 41, ISBN 9781584888017, <https://books.google.com/books?id=_l4CJq46MXwC&pg=PA41>.
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Multipartite graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.