| http://dbpedia.org/ontology/abstract
|
В теории графов древесная ширина неориенти … В теории графов древесная ширина неориентированного графа — это число, ассоциированное с графом. Древесную ширину можно определить несколькими эквивалентными путями: как размер наибольшего множества вершин в древесном разложении, как размер наибольшей клики в хордальном дополнении графа, как максимальный порядок убежища при описании стратегии игры преследования на графе или как максимальный порядок ежевики, набора связных подграфов, которые касаются друг друга.Древесная ширина часто используется в качестве параметра в анализе алгоритмов на графах. Графы с шириной дерева, не превосходящей k, называются частичными k-деревьями. Многие другие хорошо изученные семейства графов также имеют ограниченную ширину дерева. Понятие ширины дерева ввёл Халин основываясь на другом параметре, числе Хадвигера, с которым древесная ширина имеет ряд общих свойств. Позже древесную ширину переоткрыли Робертсон и Сеймур, и с тех пор она изучалась многими авторами. с тех пор она изучалась многими авторами.
, In graph theory, the treewidth of an undir … In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth. Treewidth may be formally defined in several equivalent ways: in terms of the size of the largest vertex set in a tree decomposition of the graph, in terms of the size of the largest clique in a chordal completion of the graph, in terms of the maximum order of a haven describing a strategy for a pursuit–evasion game on the graph, or in terms of the maximum order of a bramble, a collection of connected subgraphs that all touch each other. Treewidth is commonly used as a parameter in the parameterized complexity analysis of graph algorithms. Many algorithms that are NP-hard for general graphs, become easier when the treewidth is bounded by a constant. The concept of treewidth was originally introduced by Umberto Bertelè and Francesco Brioschi under the name of dimension. It was later rediscovered by Rudolf Halin, based on properties that it shares with a different graph parameter, the Hadwiger number. Later it was again rediscovered by Neil Robertson and Paul Seymour and has since been studied by many other authors. since been studied by many other authors.
, En théorie des graphes et en informatique … En théorie des graphes et en informatique théorique, la largeur arborescente ou largeur d'arbre d'un graphe (treewidth en anglais) est un nombre qui, intuitivement, mesure s'il est proche d'un arbre. Elle peut être définie de plusieurs manières[Lesquelles ?], notamment en utilisant la décomposition arborescente. Souvent, un problème algorithmique facile sur les arbres est en fait facile pour les graphes qui ressemblent à des arbres. Ainsi, ce paramètre est souvent utilisé en algorithmique de graphes, notamment pour les schémas d'approximation polynomiaux et complexité paramétrée. Dans beaucoup d'applications, les graphes ont des largeurs arborescentes petites[réf. nécessaire], comme par exemple les réseaux sociaux.e], comme par exemple les réseaux sociaux.
, В теорії графів деревна ширина неорієнтова … В теорії графів деревна ширина неорієнтованого графу — це число, асоційоване з графом. Деревну ширину можна визначити декількома еквівалентними способами: як розмір найбільшої множини вершин у деревному розкладі, як розмір найбільшої кліки в хордальному доповненні графу, як найбільший порядок укриття під час опису стратегії гри переслідування на графі або як найбільший порядок ожини, набору зв'язних підграфів, які дотикаються один з одним. Деревна ширина часто використовується як параметр в аналізі алгоритмів на графах. Графи з шириною дерева, що не перевищує k, називаються частковими k-деревами. Багато інших добре вивчених сімейств графів також мають обмежену ширину дерева. Поняття ширини дерева ввів Халін ґрунтуючись на іншому параметрі, , з яким деревна ширина має низку спільних властивостей. Пізніше деревну ширину перевідкрили Робертсон і Сеймур, і відтоді її вивчали багато авторів.ймур, і відтоді її вивчали багато авторів.
, Die Baumweite ist ein Begriff aus der Grap … Die Baumweite ist ein Begriff aus der Graphentheorie. Sie sagt aus, wie "baum-ähnlich" ein Graph ist. Da viele Algorithmen auf Bäumen (oder Baumzerlegungen) effizient laufen, die dies auf allgemeinenGraphen nicht tun, ist es interessant, die Baumweite zu kennen. Ein verwandter Begriff ist die Pfadweite. Der Begriff wurde 1972 von Umberto Bertelè und Francesco Brioschi eingeführt, unabhängig von Rudolf Halin 1976 und erneut unabhängig von Neil Robertson und Paul Seymour 1984. von Neil Robertson und Paul Seymour 1984.
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/Tree_decomposition.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ +
, https://books.google.com/books%3Fid=baw3LMwm-y8C&pg=PA37 +
, http://erikdemaine.org/papers/GridMinors_Combinatorica/paper.pdf +
, https://books.google.com/books%3Fid=i3S9_GnHZwYC&pg=PA969%7Cquote=Another +
, https://www.aaai.org/Library/AAAI/1997/aaai97-029.php +
|
| http://dbpedia.org/ontology/wikiPageID
|
3987086
|
| http://dbpedia.org/ontology/wikiPageLength
|
42012
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1124268108
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Control-flow_graph +
, http://dbpedia.org/resource/Pathwidth +
, http://dbpedia.org/resource/Journal_of_Combinatorial_Theory +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/Parameterized_complexity +
, http://dbpedia.org/resource/Journal_of_the_ACM +
, http://dbpedia.org/resource/Complete_graph +
, http://dbpedia.org/resource/Category:Graph_invariants +
, http://dbpedia.org/resource/Wagner_graph +
, http://dbpedia.org/resource/Bramble_%28graph_theory%29 +
, http://dbpedia.org/resource/Planar_graph +
, http://dbpedia.org/resource/Best-first_search +
, http://dbpedia.org/resource/Proper_interval_graph +
, http://dbpedia.org/resource/Chordal_completion +
, http://dbpedia.org/resource/NP-hard +
, http://dbpedia.org/resource/Octahedron +
, http://dbpedia.org/resource/Chordal_graph +
, http://dbpedia.org/resource/SIAM_Journal_on_Matrix_Analysis_and_Applications +
, http://dbpedia.org/resource/Algorithm +
, http://dbpedia.org/resource/Undirected_graph +
, http://dbpedia.org/resource/Discrete_Mathematics_%28journal%29 +
, http://dbpedia.org/resource/Polyhedral_graph +
, http://dbpedia.org/resource/SIAM_Journal_on_Computing +
, http://dbpedia.org/resource/Bidimensionality +
, http://dbpedia.org/resource/Apollonian_network +
, http://dbpedia.org/resource/Paul_Seymour_%28mathematician%29 +
, http://dbpedia.org/resource/Partial_k-tree +
, http://dbpedia.org/resource/Springer_Science%2BBusiness_Media +
, http://dbpedia.org/resource/Big_O_notation +
, http://dbpedia.org/resource/Forbidden_graph_characterization +
, http://dbpedia.org/resource/Dynamic_programming +
, http://dbpedia.org/resource/Graph_bandwidth +
, http://dbpedia.org/resource/NP-completeness +
, http://dbpedia.org/resource/Empty_graph +
, http://dbpedia.org/resource/Graph_coloring +
, http://dbpedia.org/resource/File:3x3_grid_graph_haven.svg +
, http://dbpedia.org/resource/File:Partial_3-tree_forbidden_minors.svg +
, http://dbpedia.org/resource/Outerplanar_graph +
, http://dbpedia.org/resource/File:Tree_decomposition.svg +
, http://dbpedia.org/resource/Monadic_second-order_logic +
, http://dbpedia.org/resource/Vertex_separator +
, http://dbpedia.org/resource/Logic_of_graphs +
, http://dbpedia.org/resource/Cycle_graph +
, http://dbpedia.org/resource/Cactus_graph +
, http://dbpedia.org/resource/Partition_of_a_set +
, http://dbpedia.org/resource/Tree-depth +
, http://dbpedia.org/resource/Register_allocation +
, http://dbpedia.org/resource/Apex_graph +
, http://dbpedia.org/resource/Complete_lattice +
, http://dbpedia.org/resource/Courcelle%27s_theorem +
, http://dbpedia.org/resource/Hitting_set +
, http://dbpedia.org/resource/Degeneracy_%28graph_theory%29 +
, http://dbpedia.org/resource/Degree_%28graph_theory%29 +
, http://dbpedia.org/resource/Monotonicity +
, http://dbpedia.org/resource/Branch_and_bound +
, http://dbpedia.org/resource/Series%E2%80%93parallel_graph +
, http://dbpedia.org/resource/Tree_%28graph_theory%29 +
, http://dbpedia.org/resource/Upper_bound +
, http://dbpedia.org/resource/Integer +
, http://dbpedia.org/resource/Tree_decomposition +
, http://dbpedia.org/resource/Category:Graph_minor_theory +
, http://dbpedia.org/resource/Grid_graph +
, http://dbpedia.org/resource/Clique_%28graph_theory%29 +
, http://dbpedia.org/resource/Anytime_algorithm +
, http://dbpedia.org/resource/1-planar_graph +
, http://dbpedia.org/resource/Halin_graph +
, http://dbpedia.org/resource/Interval_graph +
, http://dbpedia.org/resource/Combinatorica +
, http://dbpedia.org/resource/Halin%27s_grid_theorem +
, http://dbpedia.org/resource/Pentagonal_prism +
, http://dbpedia.org/resource/Algorithmica +
, http://dbpedia.org/resource/K-tree +
, http://dbpedia.org/resource/Information_and_Computation +
, http://dbpedia.org/resource/Path_graph +
, http://dbpedia.org/resource/Prism_graph +
, http://dbpedia.org/resource/SIAM_Journal_on_Discrete_Mathematics +
, http://dbpedia.org/resource/Graph_minor +
, http://dbpedia.org/resource/Pursuit%E2%80%93evasion +
, http://dbpedia.org/resource/Structured_programming +
, http://dbpedia.org/resource/Compiler +
, http://dbpedia.org/resource/Diameter_%28graph_theory%29 +
, http://dbpedia.org/resource/Maximum_clique +
, http://dbpedia.org/resource/Pseudoforest +
, http://dbpedia.org/resource/Discrete_Applied_Mathematics +
, http://dbpedia.org/resource/Hadwiger_number +
, http://dbpedia.org/resource/Haven_%28graph_theory%29 +
, http://dbpedia.org/resource/Neil_Robertson_%28mathematician%29 +
, http://dbpedia.org/resource/Universal_vertex +
|
| http://dbpedia.org/property/author1Link
|
Neil Robertson
|
| http://dbpedia.org/property/author2Link
|
Paul Seymour
|
| http://dbpedia.org/property/authorlink
|
Rudolf Halin
|
| http://dbpedia.org/property/first
|
Paul
, Umberto
, Francesco
, Neil
, Rudolf
|
| http://dbpedia.org/property/last
|
Brioschi
, Robertson
, Seymour
, Bertelè
, Halin
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Sub +
, http://dbpedia.org/resource/Template:Sup +
, http://dbpedia.org/resource/Template:Mvar +
, http://dbpedia.org/resource/Template:Main +
, http://dbpedia.org/resource/Template:Sfnp +
, http://dbpedia.org/resource/Template:Harvtxt +
, http://dbpedia.org/resource/Template:Math +
, http://dbpedia.org/resource/Template:Short_description +
, http://dbpedia.org/resource/Template:Sfrac +
, http://dbpedia.org/resource/Template:Refbegin +
, http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Refend +
, http://dbpedia.org/resource/Template:Unsolved +
, http://dbpedia.org/resource/Template:Citation +
, http://dbpedia.org/resource/Template:Harvs +
|
| http://dbpedia.org/property/year
|
1972
, 1976
, 1984
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Graph_minor_theory +
, http://dbpedia.org/resource/Category:Graph_invariants +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Number +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Treewidth?oldid=1124268108&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/3x3_grid_graph_haven.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Partial_3-tree_forbidden_minors.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Tree_decomposition.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Treewidth +
|
| owl:sameAs |
http://uk.dbpedia.org/resource/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BD%D0%B0_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D0%B0_%28%D1%82%D0%B5%D0%BE%D1%80%D1%96%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D1%96%D0%B2%29 +
, http://dbpedia.org/resource/Treewidth +
, http://hu.dbpedia.org/resource/Fasz%C3%A9less%C3%A9g +
, http://yago-knowledge.org/resource/Treewidth +
, http://fr.dbpedia.org/resource/Largeur_arborescente +
, http://fa.dbpedia.org/resource/%D8%B9%D8%B1%D8%B6_%D8%AF%D8%B1%D8%AE%D8%AA +
, https://global.dbpedia.org/id/4hDNE +
, http://de.dbpedia.org/resource/Baumweite +
, http://rdf.freebase.com/ns/m.0r4rwn3 +
, http://ru.dbpedia.org/resource/%D0%94%D1%80%D0%B5%D0%B2%D0%B5%D1%81%D0%BD%D0%B0%D1%8F_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D0%B0_%28%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2%29 +
, http://www.wikidata.org/entity/Q5067368 +
|
| rdf:type |
http://dbpedia.org/class/yago/Concept105835747 +
, http://dbpedia.org/class/yago/WikicatGraphInvariants +
, http://dbpedia.org/class/yago/Invariant105850432 +
, http://dbpedia.org/class/yago/Property105849040 +
, http://dbpedia.org/class/yago/Feature105849789 +
, http://dbpedia.org/class/yago/PsychologicalFeature100023100 +
, http://dbpedia.org/class/yago/Cognition100023271 +
, http://dbpedia.org/class/yago/Abstraction100002137 +
, http://dbpedia.org/class/yago/Idea105833840 +
, http://dbpedia.org/class/yago/Content105809192 +
|
| rdfs:comment |
En théorie des graphes et en informatique … En théorie des graphes et en informatique théorique, la largeur arborescente ou largeur d'arbre d'un graphe (treewidth en anglais) est un nombre qui, intuitivement, mesure s'il est proche d'un arbre. Elle peut être définie de plusieurs manières[Lesquelles ?], notamment en utilisant la décomposition arborescente.n utilisant la décomposition arborescente.
, Die Baumweite ist ein Begriff aus der Grap … Die Baumweite ist ein Begriff aus der Graphentheorie. Sie sagt aus, wie "baum-ähnlich" ein Graph ist. Da viele Algorithmen auf Bäumen (oder Baumzerlegungen) effizient laufen, die dies auf allgemeinenGraphen nicht tun, ist es interessant, die Baumweite zu kennen. Ein verwandter Begriff ist die Pfadweite. Der Begriff wurde 1972 von Umberto Bertelè und Francesco Brioschi eingeführt, unabhängig von Rudolf Halin 1976 und erneut unabhängig von Neil Robertson und Paul Seymour 1984. von Neil Robertson und Paul Seymour 1984.
, В теории графов древесная ширина неориенти … В теории графов древесная ширина неориентированного графа — это число, ассоциированное с графом. Древесную ширину можно определить несколькими эквивалентными путями: как размер наибольшего множества вершин в древесном разложении, как размер наибольшей клики в хордальном дополнении графа, как максимальный порядок убежища при описании стратегии игры преследования на графе или как максимальный порядок ежевики, набора связных подграфов, которые касаются друг друга.Древесная ширина часто используется в качестве параметра в анализе алгоритмов на графах. Графы с шириной дерева, не превосходящей k, называются частичными k-деревьями. Многие другие хорошо изученные семейства графов также имеют ограниченную ширину дерева.ов также имеют ограниченную ширину дерева.
, In graph theory, the treewidth of an undir … In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.raph families also have bounded treewidth.
, В теорії графів деревна ширина неорієнтова … В теорії графів деревна ширина неорієнтованого графу — це число, асоційоване з графом. Деревну ширину можна визначити декількома еквівалентними способами: як розмір найбільшої множини вершин у деревному розкладі, як розмір найбільшої кліки в хордальному доповненні графу, як найбільший порядок укриття під час опису стратегії гри переслідування на графі або як найбільший порядок ожини, набору зв'язних підграфів, які дотикаються один з одним. Деревна ширина часто використовується як параметр в аналізі алгоритмів на графах. Графи з шириною дерева, що не перевищує k, називаються частковими k-деревами. Багато інших добре вивчених сімейств графів також мають обмежену ширину дерева.графів також мають обмежену ширину дерева.
|
| rdfs:label |
Древесная ширина (теория графов)
, Largeur arborescente
, Treewidth
, Деревна ширина (теорія графів)
, Baumweite
|
