V matematické disciplíně teorie grafů je vrcholové pokrytí grafu taková podmnožina vrcholů, že každá hrana grafu je incidentní aspoň s jedním vrcholem z této množiny.Minimální vrcholové pokrytí je klasický problém teoretické informatiky a je příkladem NP-úplnosti. Lze ho formulovat jako napůl celočíselný lineární program jehož duálním lin. programem je maximální párování grafu.

PropertyValue
dbpedia-owl:abstract
  • V matematické disciplíně teorie grafů je vrcholové pokrytí grafu taková podmnožina vrcholů, že každá hrana grafu je incidentní aspoň s jedním vrcholem z této množiny.Minimální vrcholové pokrytí je klasický problém teoretické informatiky a je příkladem NP-úplnosti. Lze ho formulovat jako napůl celočíselný lineární program jehož duálním lin. programem je maximální párování grafu.
dbpedia-owl:wikiPageID
  • 835321 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 1386 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 14 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 12621720 (xsd:integer)
dbpedia-owl:wikiPageWikiLink
dbpedia-owl:wikiPageWikiLinkText
  • vrcholové pokrytí
  • vrcholového pokrytí
  • vrcholovému pokrytí
dcterms:subject
rdfs:comment
  • V matematické disciplíně teorie grafů je vrcholové pokrytí grafu taková podmnožina vrcholů, že každá hrana grafu je incidentní aspoň s jedním vrcholem z této množiny.Minimální vrcholové pokrytí je klasický problém teoretické informatiky a je příkladem NP-úplnosti. Lze ho formulovat jako napůl celočíselný lineární program jehož duálním lin. programem je maximální párování grafu.
rdfs:label
  • Vrcholové pokrytí
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbpedia-owl:wikiPageWikiLink of
is foaf:primaryTopic of