| http://dbpedia.org/ontology/abstract
|
In graph theory, a perfectly orderable gra … In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.aph is perfectly orderable is NP-complete.
, В теории графов вполне упорядочиваемый гра … В теории графов вполне упорядочиваемый граф — это граф, вершины которого можно упорядочить так, что алгоритм жадной раскраски с этим упорядочением оптимально раскрашивает любой порождённый подграф заданного графа. Соответствующее упорядочение называется совершенным. Вполне упорядочиваемые графы образуют подкласс совершенных графов и в это подкласс входят хордальные графы, графы сравнимости и дистанционно-наследуемые графы. Однако проверка, является ли граф вполне упорядочиваемым, есть NP-полная задача.не упорядочиваемым, есть NP-полная задача.
, У теорії графів цілком упорядковуваний гра … У теорії графів цілком упорядковуваний граф — це граф, вершини якого можна впорядкувати так, що алгоритм жадібного розфарбовування з цим упорядкуванням оптимально розфарбовує будь-який породжений підграф даного графу. Відповідне впорядкування називається досконалим. Цілком упорядковувані графи утворюють підклас досконалих графів і в цей підклас входять хордальні графи, графи порівнянності і дистанційно-успадковувані графи. Однак перевірка, чи є граф цілком упорядковуваним, є NP-повною задачею.лком упорядковуваним, є NP-повною задачею.
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
https://refubium.fu-berlin.de/handle/fub188/18407 +
, https://archive.org/details/graphclassessurv0000bran +
, https://digitalcommons.odu.edu/computerscience_fac_pubs/132 +
|
| http://dbpedia.org/ontology/wikiPageID
|
21051205
|
| http://dbpedia.org/ontology/wikiPageLength
|
10268
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1032107611
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Transitive_orientation +
, http://dbpedia.org/resource/Category:Graph_coloring +
, http://dbpedia.org/resource/Distance-hereditary_graph +
, http://dbpedia.org/resource/Induced_path +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/Journal_of_Combinatorial_Theory +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/Chordal_graph +
, http://dbpedia.org/resource/Discrete_Mathematics_%28journal%29 +
, http://dbpedia.org/resource/Perfect_graph +
, http://dbpedia.org/resource/Neighborhood_%28graph_theory%29 +
, http://dbpedia.org/resource/Comparability_graph +
, http://dbpedia.org/resource/Order_%28journal%29 +
, http://dbpedia.org/resource/Dilworth%27s_theorem +
, http://dbpedia.org/resource/Category:Perfect_graphs +
, http://dbpedia.org/resource/Topological_ordering +
, http://dbpedia.org/resource/Tolerance_graph +
, http://dbpedia.org/resource/Cograph +
, http://dbpedia.org/resource/Lexicographic_breadth-first_search +
, http://dbpedia.org/resource/Mex_%28mathematics%29 +
, http://dbpedia.org/resource/Partially_ordered_set +
, http://dbpedia.org/resource/Complement_graph +
, http://dbpedia.org/resource/Greedy_coloring +
, http://dbpedia.org/resource/Induced_subgraph +
, http://dbpedia.org/resource/Cycle_graph +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Short_description +
, http://dbpedia.org/resource/Template:Citation +
, http://dbpedia.org/resource/Template:Sfnp +
, http://dbpedia.org/resource/Template:Harvtxt +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Graph_coloring +
, http://dbpedia.org/resource/Category:Perfect_graphs +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Graph +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Perfectly_orderable_graph?oldid=1032107611&ns=0 +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Perfectly_orderable_graph +
|
| owl:sameAs |
http://ru.dbpedia.org/resource/%D0%92%D0%BF%D0%BE%D0%BB%D0%BD%D0%B5_%D1%83%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B8%D0%B2%D0%B0%D0%B5%D0%BC%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 +
, http://rdf.freebase.com/ns/m.0kvhwf3 +
, http://yago-knowledge.org/resource/Perfectly_orderable_graph +
, http://uk.dbpedia.org/resource/%D0%A6%D1%96%D0%BB%D0%BA%D0%BE%D0%BC_%D1%83%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%BE%D0%B2%D1%83%D0%B2%D0%B0%D0%BD%D0%B8%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 +
, http://dbpedia.org/resource/Perfectly_orderable_graph +
, http://www.wikidata.org/entity/Q17148818 +
, https://global.dbpedia.org/id/gqAp +
|
| rdf:type |
http://dbpedia.org/class/yago/Abstraction100002137 +
, http://dbpedia.org/ontology/Software +
, http://dbpedia.org/class/yago/VisualCommunication106873252 +
, http://dbpedia.org/class/yago/Communication100033020 +
, http://dbpedia.org/class/yago/WikicatPerfectGraphs +
, http://dbpedia.org/class/yago/Graph107000195 +
|
| rdfs:comment |
У теорії графів цілком упорядковуваний гра … У теорії графів цілком упорядковуваний граф — це граф, вершини якого можна впорядкувати так, що алгоритм жадібного розфарбовування з цим упорядкуванням оптимально розфарбовує будь-який породжений підграф даного графу. Відповідне впорядкування називається досконалим. Цілком упорядковувані графи утворюють підклас досконалих графів і в цей підклас входять хордальні графи, графи порівнянності і дистанційно-успадковувані графи. Однак перевірка, чи є граф цілком упорядковуваним, є NP-повною задачею.лком упорядковуваним, є NP-повною задачею.
, In graph theory, a perfectly orderable gra … In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.aph is perfectly orderable is NP-complete.
, В теории графов вполне упорядочиваемый гра … В теории графов вполне упорядочиваемый граф — это граф, вершины которого можно упорядочить так, что алгоритм жадной раскраски с этим упорядочением оптимально раскрашивает любой порождённый подграф заданного графа. Соответствующее упорядочение называется совершенным. Вполне упорядочиваемые графы образуют подкласс совершенных графов и в это подкласс входят хордальные графы, графы сравнимости и дистанционно-наследуемые графы. Однако проверка, является ли граф вполне упорядочиваемым, есть NP-полная задача.не упорядочиваемым, есть NP-полная задача.
|
| rdfs:label |
Perfectly orderable graph
, Вполне упорядочиваемый граф
, Цілком упорядковуваний граф
|
