| http://dbpedia.org/ontology/abstract
|
In graph theory, a well-covered graph is a … In graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Equivalently, these are the graphs in which all maximal independent sets have equal size. Well-covered graphs were defined and first studied by Michael D. Plummer in 1970. The well-covered graphs include all complete graphs, balanced complete bipartite graphs, and the rook's graphs whose vertices represent squares of a chessboard and edges represent moves of a chess rook. Known characterizations of the well-covered cubic graphs, well-covered claw-free graphs, and well-covered graphs of high girth allow these graphs to be recognized in polynomial time, but testing whether other kinds of graph are well-covered is a coNP-complete problem.e well-covered is a coNP-complete problem.
, В теории графов хорошо покрытый граф (иногда встречается название хорошо укрытый граф) — это неориентированный граф, в котором все минимальные по включению вершинные покрытия имеют один и тот же размер. Хорошо покрытые графы определил и изучал Пламмер.
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/Well-covered_graph.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
https://web.archive.org/web/20120527164352/http:/handle.dtic.mil/100.2/ADA247861 +
, http://handle.dtic.mil/100.2/ADA247861 +
, http://www.combinatorics.org/Volume_16/Abstracts/v16i2r2.html +
|
| http://dbpedia.org/ontology/wikiPageID
|
32696387
|
| http://dbpedia.org/ontology/wikiPageLength
|
25893
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1110999438
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Euler_characteristic +
, http://dbpedia.org/resource/Clique_complex +
, http://dbpedia.org/resource/Open_interval +
, http://dbpedia.org/resource/Journal_of_Combinatorial_Theory +
, http://dbpedia.org/resource/Discrete_Mathematics_%28journal%29 +
, http://dbpedia.org/resource/File:3r3c_well-covered.svg +
, http://dbpedia.org/resource/Simplicial_complex +
, http://dbpedia.org/resource/File:Well-covered_graph.svg +
, http://dbpedia.org/resource/Complete_bipartite_graph +
, http://dbpedia.org/resource/File:3r1c_well-covered.svg +
, http://dbpedia.org/resource/Polynomial_time +
, http://dbpedia.org/resource/Maximal_matching +
, http://dbpedia.org/resource/Intersection_graph +
, http://dbpedia.org/resource/Ars_Combinatoria_%28journal%29 +
, http://dbpedia.org/resource/Critical_graph +
, http://dbpedia.org/resource/Generalized_Petersen_graph +
, http://dbpedia.org/resource/Category:Graph_families +
, http://dbpedia.org/resource/File:Snub_disphenoid.png +
, http://dbpedia.org/resource/Discrete_Applied_Mathematics +
, http://dbpedia.org/resource/Snub_disphenoid +
, http://dbpedia.org/resource/Convex_polyhedron +
, http://dbpedia.org/resource/Triangulation_%28geometry%29 +
, http://dbpedia.org/resource/Deltahedron +
, http://dbpedia.org/resource/Pentagonal_prism +
, http://dbpedia.org/resource/K-vertex-connected_graph +
, http://dbpedia.org/resource/Perfect_matching +
, http://dbpedia.org/resource/Cycle_graph +
, http://dbpedia.org/resource/Rook_%28chess%29 +
, http://dbpedia.org/resource/Hamiltonian_cycle +
, http://dbpedia.org/resource/Complete_graph +
, http://dbpedia.org/resource/Simplicial_polytope +
, http://dbpedia.org/resource/Complement_%28set_theory%29 +
, http://dbpedia.org/resource/Undirected_graph +
, http://dbpedia.org/resource/Connectivity_%28graph_theory%29 +
, http://dbpedia.org/resource/Clique_cover +
, http://dbpedia.org/resource/Bridge_%28graph_theory%29 +
, http://dbpedia.org/resource/Triangular_prism +
, http://dbpedia.org/resource/Degree_%28graph_theory%29 +
, http://dbpedia.org/resource/Cubic_graph +
, http://dbpedia.org/resource/Transactions_of_the_American_Mathematical_Society +
, http://dbpedia.org/resource/Planar_graph +
, http://dbpedia.org/resource/Pentagonal_dipyramid +
, http://dbpedia.org/resource/Regular_graph +
, http://dbpedia.org/resource/Michael_D._Plummer +
, http://dbpedia.org/resource/CoNP-complete +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/Girth_%28graph_theory%29 +
, http://dbpedia.org/resource/D%C3%BCrer_graph +
, http://dbpedia.org/resource/Rook%27s_graph +
, http://dbpedia.org/resource/Electronic_Journal_of_Combinatorics +
, http://dbpedia.org/resource/Claw-free_graph +
, http://dbpedia.org/resource/Simple_polytope +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/Line_graph +
, http://dbpedia.org/resource/Cluster_graph +
, http://dbpedia.org/resource/Utility_graph +
, http://dbpedia.org/resource/Chessboard +
, http://dbpedia.org/resource/Independent_set_%28graph_theory%29 +
, http://dbpedia.org/resource/Y-%CE%94_transform +
, http://dbpedia.org/resource/Rooted_product_of_graphs +
, http://dbpedia.org/resource/Induced_subgraph +
, http://dbpedia.org/resource/Regular_octahedron +
, http://dbpedia.org/resource/Polyhedral_graph +
, http://dbpedia.org/resource/Vertex_cover +
, http://dbpedia.org/resource/Minimal_element +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Chess_diagram +
, http://dbpedia.org/resource/Template:Math +
, http://dbpedia.org/resource/Template:Short_description +
, http://dbpedia.org/resource/Template:Sfnp +
, http://dbpedia.org/resource/Template:Citation +
, http://dbpedia.org/resource/Template:Mvar +
, http://dbpedia.org/resource/Template:Refbegin +
, http://dbpedia.org/resource/Template:Refend +
, http://dbpedia.org/resource/Template:Harvtxt +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Graph_families +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Graph +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Well-covered_graph?oldid=1110999438&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/Snub_disphenoid.png +
, http://commons.wikimedia.org/wiki/Special:FilePath/3r1c_well-covered.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/3r3c_well-covered.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Well-covered_graph.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Well-covered_graph +
|
| owl:sameAs |
http://dbpedia.org/resource/Well-covered_graph +
, https://global.dbpedia.org/id/4xoLr +
, http://ru.dbpedia.org/resource/%D0%A5%D0%BE%D1%80%D0%BE%D1%88%D0%BE_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 +
, http://rdf.freebase.com/ns/m.0h3rq4f +
, http://yago-knowledge.org/resource/Well-covered_graph +
, http://www.wikidata.org/entity/Q7981049 +
|
| rdf:type |
http://dbpedia.org/class/yago/SocialGroup107950920 +
, http://dbpedia.org/class/yago/Unit108189659 +
, http://dbpedia.org/class/yago/YagoLegalActorGeo +
, http://dbpedia.org/class/yago/YagoLegalActor +
, http://dbpedia.org/class/yago/Family108078020 +
, http://dbpedia.org/class/yago/YagoPermanentlyLocatedEntity +
, http://dbpedia.org/class/yago/Abstraction100002137 +
, http://dbpedia.org/class/yago/Group100031264 +
, http://dbpedia.org/class/yago/Organization108008335 +
, http://dbpedia.org/class/yago/WikicatGraphFamilies +
, http://dbpedia.org/ontology/Software +
|
| rdfs:comment |
В теории графов хорошо покрытый граф (иногда встречается название хорошо укрытый граф) — это неориентированный граф, в котором все минимальные по включению вершинные покрытия имеют один и тот же размер. Хорошо покрытые графы определил и изучал Пламмер.
, In graph theory, a well-covered graph is a … In graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Equivalently, these are the graphs in which all maximal independent sets have equal size. Well-covered graphs were defined and first studied by Michael D. Plummer in 1970.rst studied by Michael D. Plummer in 1970.
|
| rdfs:label |
Хорошо покрытый граф
, Well-covered graph
|
