This HTML5 document contains 12 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n6http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n11http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Többrészes_gráf
rdfs:label
Többrészes gráf
dct:subject
n11:Gráfcsaládok
dbo:wikiPageID
1466620
dbo:wikiPageRevisionID
18719264
prop-hu:wikiPageUsesTemplate
n6:Reflist n6:Fordítás
dbo:abstract
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 probléma.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 (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. 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 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. 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.
prov:wasDerivedFrom
wikipedia-hu:Többrészes_gráf?oldid=18719264&ns=0
dbo:wikiPageLength
3917
foaf:isPrimaryTopicOf
wikipedia-hu:Többrészes_gráf
Subject Item
dbpedia-hu:Teljes_többrészes_gráf
dbo:wikiPageRedirects
dbpedia-hu:Többrészes_gráf
Subject Item
wikipedia-hu:Többrészes_gráf
foaf:primaryTopic
dbpedia-hu:Többrészes_gráf