Treewidth (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (de) 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. (fr) 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. (en) В теории графов древесная ширина неориентированного графа — это число, ассоциированное с графом. Древесную ширину можно определить несколькими эквивалентными путями: как размер наибольшего множества вершин в древесном разложении, как размер наибольшей клики в хордальном дополнении графа, как максимальный порядок убежища при описании стратегии игры преследования на графе или как максимальный порядок ежевики, набора связных подграфов, которые касаются друг друга.Древесная ширина часто используется в качестве параметра в анализе алгоритмов на графах. Графы с шириной дерева, не превосходящей k, называются частичными k-деревьями. Многие другие хорошо изученные семейства графов также имеют ограниченную ширину дерева. Понятие ширины дерева ввёл Халин основываясь на другом параметре, числе Хадвигера, с которым древесная ширина имеет ряд общих свойств. Позже древесную ширину переоткрыли Робертсон и Сеймур, и с тех пор она изучалась многими авторами. (ru) В теорії графів деревна ширина неорієнтованого графу — це число, асоційоване з графом. Деревну ширину можна визначити декількома еквівалентними способами: як розмір найбільшої множини вершин у деревному розкладі, як розмір найбільшої кліки в хордальному доповненні графу, як найбільший порядок укриття під час опису стратегії гри переслідування на графі або як найбільший порядок ожини, набору зв'язних підграфів, які дотикаються один з одним. Деревна ширина часто використовується як параметр в аналізі алгоритмів на графах. Графи з шириною дерева, що не перевищує k, називаються частковими k-деревами. Багато інших добре вивчених сімейств графів також мають обмежену ширину дерева. Поняття ширини дерева ввів Халін ґрунтуючись на іншому параметрі, , з яким деревна ширина має низку спільних властивостей. Пізніше деревну ширину перевідкрили Робертсон і Сеймур, і відтоді її вивчали багато авторів. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Tree_decomposition.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ https://books.google.com/books%3Fid=baw3LMwm-y8C&pg=PA37 https://books.google.com/books%3Fid=i3S9_GnHZwYC&pg=PA969%7Cquote=Another http://erikdemaine.org/papers/GridMinors_Combinatorica/paper.pdf https://www.aaai.org/Library/AAAI/1997/aaai97-029.php |
| dbo:wikiPageID | 3987086 (xsd:integer) |
| dbo:wikiPageLength | 42012 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124268108 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Branch_and_bound dbr:Degeneracy_(graph_theory) dbr:Algorithm dbr:Algorithmica dbr:Anytime_algorithm dbr:Apollonian_network dbc:Graph_minor_theory dbr:Best-first_search dbr:Path_graph dbr:Pathwidth dbr:Paul_Seymour_(mathematician) dbr:Undirected_graph dbr:Upper_bound dbr:Vertex_separator dbr:Degree_(graph_theory) dbr:Information_and_Computation dbr:Register_allocation dbr:Pseudoforest dbr:1-planar_graph dbc:Graph_invariants dbr:Compiler dbr:Complete_graph dbr:Control-flow_graph dbr:Pursuit–evasion dbr:Graph_bandwidth dbr:Graph_coloring dbr:Graph_minor dbr:Bramble_(graph_theory) dbr:Monotonicity dbr:NP-hard dbr:SIAM_Journal_on_Computing dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Proper_interval_graph dbr:Apex_graph dbr:Logic_of_graphs dbr:Cactus_graph dbr:Chordal_completion dbr:Structured_programming dbr:Clique_(graph_theory) dbr:Combinatorica dbr:Complete_lattice dbr:Halin's_grid_theorem dbr:Halin_graph dbr:Tree_(graph_theory) dbr:Tree_decomposition dbr:Wagner_graph dbr:K-tree dbr:Cycle_graph dbr:Dynamic_programming dbr:Forbidden_graph_characterization dbr:Outerplanar_graph dbr:Partition_of_a_set dbr:Diameter_(graph_theory) dbr:Discrete_Applied_Mathematics dbr:Discrete_Mathematics_(journal) dbr:Graph_theory dbr:Hitting_set dbr:Journal_of_Combinatorial_Theory dbr:Journal_of_the_ACM dbr:Tree-depth dbr:Hadwiger_number dbr:Haven_(graph_theory) dbr:Interval_graph dbr:Courcelle's_theorem dbr:Pentagonal_prism dbr:Chordal_graph dbr:Bidimensionality dbr:Big_O_notation dbr:Planar_graph dbr:Springer_Science+Business_Media dbr:Empty_graph dbr:Integer dbr:Neil_Robertson_(mathematician) dbr:Octahedron dbr:Monadic_second-order_logic dbr:Partial_k-tree dbr:Prism_graph dbr:NP-completeness dbr:Universal_vertex dbr:Polyhedral_graph dbr:Series–parallel_graph dbr:Maximum_clique dbr:Parameterized_complexity dbr:SIAM_Journal_on_Matrix_Analysis_and_Applications dbr:Grid_graph dbr:File:Tree_decomposition.svg dbr:File:3x3_grid_graph_haven.svg dbr:File:Partial_3-tree_forbidden_minors.svg |
| dbp:author1Link | Neil Robertson (en) |
| dbp:author2Link | Paul Seymour (en) |
| dbp:authorlink | Rudolf Halin (en) |
| dbp:first | Neil (en) Paul (en) Rudolf (en) Umberto (en) Francesco (en) |
| dbp:last | Robertson (en) Seymour (en) Brioschi (en) Halin (en) Bertelè (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Main dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Sfrac dbt:Short_description dbt:Sub dbt:Sup dbt:Harvs dbt:Unsolved |
| dbp:year | 1972 (xsd:integer) 1976 (xsd:integer) 1984 (xsd:integer) |
| dct:subject | dbc:Graph_minor_theory dbc:Graph_invariants |
| gold:hypernym | dbr:Number |
| rdf:type | yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphInvariants |
| rdfs:comment | 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. (de) 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. (fr) 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. (en) В теории графов древесная ширина неориентированного графа — это число, ассоциированное с графом. Древесную ширину можно определить несколькими эквивалентными путями: как размер наибольшего множества вершин в древесном разложении, как размер наибольшей клики в хордальном дополнении графа, как максимальный порядок убежища при описании стратегии игры преследования на графе или как максимальный порядок ежевики, набора связных подграфов, которые касаются друг друга.Древесная ширина часто используется в качестве параметра в анализе алгоритмов на графах. Графы с шириной дерева, не превосходящей k, называются частичными k-деревьями. Многие другие хорошо изученные семейства графов также имеют ограниченную ширину дерева. (ru) В теорії графів деревна ширина неорієнтованого графу — це число, асоційоване з графом. Деревну ширину можна визначити декількома еквівалентними способами: як розмір найбільшої множини вершин у деревному розкладі, як розмір найбільшої кліки в хордальному доповненні графу, як найбільший порядок укриття під час опису стратегії гри переслідування на графі або як найбільший порядок ожини, набору зв'язних підграфів, які дотикаються один з одним. Деревна ширина часто використовується як параметр в аналізі алгоритмів на графах. Графи з шириною дерева, що не перевищує k, називаються частковими k-деревами. Багато інших добре вивчених сімейств графів також мають обмежену ширину дерева. (uk) |
| rdfs:label | Baumweite (de) Largeur arborescente (fr) Treewidth (en) Древесная ширина (теория графов) (ru) Деревна ширина (теорія графів) (uk) |
| owl:sameAs | freebase:Treewidth yago-res:Treewidth wikidata:Treewidth dbpedia-de:Treewidth dbpedia-fa:Treewidth dbpedia-fr:Treewidth dbpedia-hu:Treewidth dbpedia-ru:Treewidth dbpedia-uk:Treewidth https://global.dbpedia.org/id/4hDNE |
| prov:wasDerivedFrom | wikipedia-en:Treewidth?oldid=1124268108&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Tree_decomposition.svg wiki-commons:Special:FilePath/3x3_grid_graph_haven.svg wiki-commons:Special:FilePath/Partial_3-tree_forbidden_minors.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Treewidth |
| is dbo:wikiPageDisambiguates of | dbr:Width_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Tree-width dbr:Tree_width dbr:Grid_minor_theorem |
| is dbo:wikiPageWikiLink of | dbr:Queue_number dbr:Wiener_index dbr:Bayesian_network dbr:Book_embedding dbr:Degeneracy_(graph_theory) dbr:Hosoya_index dbr:Julia_Chuzhoy dbr:List_of_graph_theory_topics dbr:Pathwidth dbr:Paul_Seymour_(mathematician) dbr:David_Wood_(mathematician) dbr:Decomposition_method_(constraint_satisfaction) dbr:Derek_Corneil dbr:Indifference_graph dbr:Intersection_number_(graph_theory) dbr:Precoloring_extension dbr:Robertson–Seymour_theorem dbr:1-planar_graph dbr:Color-coding dbr:Pursuit–evasion dbr:Clique-sum dbr:Clique-width dbr:Glossary_of_graph_theory dbr:Graph_homomorphism dbr:Graph_minor dbr:Bramble_(graph_theory) dbr:Branch-decomposition dbr:Model_checking dbr:Conjunctive_query dbr:Constraint_composite_graph dbr:Constraint_satisfaction_problem dbr:Contraction_hierarchies dbr:Cop_number dbr:Equitable_coloring dbr:Erdős–Pósa_theorem dbr:Apex_graph dbr:Linkless_embedding dbr:Logic_of_graphs dbr:Chordal_completion dbr:Feedback_arc_set dbr:Halin's_grid_theorem dbr:Halin_graph dbr:Perfect_graph dbr:Planar_separator_theorem dbr:Succinct_game dbr:Matching_polynomial dbr:Matroid_minor dbr:Tree_decomposition dbr:Wagner_graph dbr:Junction_tree_algorithm dbr:K-minimum_spanning_tree dbr:K-outerplanar_graph dbr:K-tree dbr:Trémaux_tree dbr:Unrooted_binary_tree dbr:Cutwidth dbr:Dynamic_programming dbr:Edge_coloring dbr:Forbidden_graph_characterization dbr:Null_graph dbr:Outerplanar_graph dbr:Goldner–Harary_graph dbr:Graph_isomorphism_problem dbr:Harborth's_conjecture dbr:List_of_NP-complete_problems dbr:Tree-depth dbr:Variable_elimination dbr:Vida_Dujmović dbr:Hadwiger_number dbr:Haven_(graph_theory) dbr:Courcelle's_theorem dbr:Ω-automaton dbr:Chordal_graph dbr:Bidimensionality dbr:Width_(disambiguation) dbr:Distance-hereditary_graph dbr:Planar_graph dbr:Circle_graph dbr:Grundy_number dbr:Implicit_graph dbr:Metric_dimension_(graph_theory) dbr:Caterpillar_tree dbr:Klam_value dbr:Longest_path_problem dbr:Monadic_second-order_logic dbr:Strong_orientation dbr:Exponential_time_hypothesis dbr:Partial_k-tree dbr:Prism_graph dbr:Monochromatic_triangle dbr:Rudolf_Halin dbr:Series–parallel_graph dbr:Permutation_graph dbr:Rank-width dbr:S2S_(mathematics) dbr:Twin-width dbr:Stefan_Szeider dbr:Tree-width dbr:Tree_width dbr:Grid_minor_theorem |
| is foaf:primaryTopic of | wikipedia-en:Treewidth |
