This HTML5 document contains 36 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/
n15http://www.hananayad.com/teaching/syde423/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
n16http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n12https://web.archive.org/web/20131111184129/http:/networkx.lanl.gov/reference/generated/
n13http://weitz.de/indset/
n7https://web.archive.org/web/20131003042250/http:/openopt.org/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n9http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n17http://igraph.sourceforge.net/doc/html/
n11http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Független_csúcshalmaz
rdfs:label
Független csúcshalmaz
dct:subject
n11:Gráfelmélet n11:Gráfelméleti_objektumok n11:Számítási_problémák_a_gráfelméletben
dbo:wikiPageID
1414651
dbo:wikiPageRevisionID
21428200
dbo:wikiPageExternalLink
n7:STAB n12:networkx.algorithms.approximation.independent_set.maximum_independent_set.html n13: n15:IndependentSet.pdf n16:graph-benchmarks.htm n17:ch15s02.html
prop-hu:wikiPageUsesTemplate
n9:Fő n9:Refbegin n9:Refend n9:Citation n9:Reflist n9:Jegyzetek n9:Wd n9:Fordítás n9:MathWorld n9:Harvtxt
prop-hu:title
Maximal Independent Vertex Set
prop-hu:urlname
MaximalIndependentVertexSet
dbo:abstract
A matematika, azon belül a gráfelmélet területén egy független csúcshalmaz, független ponthalmaz, független halmaz (independent set) vagy stabil halmaz (stable set) egy gráf olyan csúcsainak halmaza, melyek közül semelyik kettő sem szomszédos egymással. Tehát a csúcsok olyan S halmaza, hogy bármelyik két S-beli csúcsot tekintve állítható, hogy nincs közöttük él. Ezzel ekvivalens állítás, hogy a gráf minden élének pontosan egy végpontja található S-ben. A független halmaz méretén az azt alkotó csúcsok számát értjük. A független halmazokat nevezik belsőleg stabil halmazoknak (internally stable sets) is. Egy maximális független halmaz (maximal independent set) olyan halmaz, melyhez vagy bármely csúcsot hozzáadva biztosan tartalmazni fog egy élet is, vagy az üres gráf összes csúcsát tartalmazza. Egy adott G gráfhoz tartozó maximális független halmazok nevükkel ellentétben nagyon különböző méretűek lehetnek. A maximális független halmazok közül a maximális elemszámú független halmaz az adott G gráfhoz tartozó legnagyobb lehetséges méretű halmaz. Ezt a méretet nevezik G függetlenségi számának (independence number), jelölése α(G). Az ilyen halmaz előállításának a problémája, a maximális elemszámú független csúcshalmaz-probléma (maximum independent set problem) optimalizálási feladat. Így hát valószínűtlen, hogy létezik hatékony algoritmus egy gráf maximális elemszámú független csúcshalmazának meghatározására. A maximális elemszámú független csúcshalmazok (maximum independent set) minden esetben maximális független csúcshalmazok is (maximal independent set), az állítás megfordítása azonban nem áll fenn.
prov:wasDerivedFrom
wikipedia-hu:Független_csúcshalmaz?oldid=21428200&ns=0
dbo:wikiPageLength
23036
foaf:isPrimaryTopicOf
wikipedia-hu:Független_csúcshalmaz
Subject Item
dbpedia-hu:Belsőleg_stabil_halmaz
dbo:wikiPageRedirects
dbpedia-hu:Független_csúcshalmaz
Subject Item
dbpedia-hu:Független_halmaz
dbo:wikiPageRedirects
dbpedia-hu:Független_csúcshalmaz
Subject Item
dbpedia-hu:Független_ponthalmaz
dbo:wikiPageRedirects
dbpedia-hu:Független_csúcshalmaz
Subject Item
dbpedia-hu:Függetlenségi_szám
dbo:wikiPageRedirects
dbpedia-hu:Független_csúcshalmaz
Subject Item
dbpedia-hu:Stabil_halmaz
dbo:wikiPageRedirects
dbpedia-hu:Független_csúcshalmaz
Subject Item
wikipedia-hu:Független_csúcshalmaz
foaf:primaryTopic
dbpedia-hu:Független_csúcshalmaz
Subject Item
dbpedia-hu:Maximális_elemszámú_független_csúcshalmaz
dbo:wikiPageRedirects
dbpedia-hu:Független_csúcshalmaz
Subject Item
dbpedia-hu:Maximális_elemszámú_független_halmaz
dbo:wikiPageRedirects
dbpedia-hu:Független_csúcshalmaz