This HTML5 document contains 46 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/
n14http://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/
n12http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n17https://web.archive.org/web/20131111184129/http:/networkx.lanl.gov/reference/generated/
n16http://weitz.de/indset/
n13https://web.archive.org/web/20131003042250/http:/openopt.org/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n4http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n9http://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
rdfs:comment
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.
dct:subject
n11:Gráfelméleti_objektumok n11:Számítási_problémák_a_gráfelméletben n11:Gráfelmélet
dbo:wikiPageID
1414651
dbo:wikiPageRevisionID
25439897 21428200
dbo:wikiPageExternalLink
n9:ch15s02.html n12:graph-benchmarks.htm n13:STAB n14:IndependentSet.pdf n16: n17:networkx.algorithms.approximation.independent_set.maximum_independent_set.html
prop-hu:wikiPageUsesTemplate
n4:Fő n4:Refend n4:MathWorld n4:Reflist n4:Refbegin n4:Harvtxt n4:Fordítás n4:Jegyzetek n4:Wd n4:Wayback n4:Citation
prop-hu:date
20140214093238 20130529163947
prop-hu:title
Maximal Independent Vertex Set
prop-hu:url
n12:graph-benchmarks.htm n9:ch15s02.html
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 legfeljebb 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. 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 wikipedia-hu:Független_csúcshalmaz?oldid=25439897&ns=0
dbo:wikiPageLength
23036 23233
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