Tree decomposition (original) (raw)
Stromový rozklad je jeden ze způsobů, jak charakterizovat graf.
| Property | Value |
|---|---|
| dbo:abstract | Stromový rozklad je jeden ze způsobů, jak charakterizovat graf. (cs) En grafeteorio, arbigo ĵetas grafeon al arbo. Oni povas difini per la operacio. La arbo rezultata ankaŭ utilas por rapidigi ian komputadon. En , arbigo grave rolas en problemoj, ekzemple probabla inferencio, kaj . La ideon de arbigo unue proponis (1976). Poste refoje ĝin malkovris kaj (1984). Ĝi estas temo de pluraj studoj ĝis nun. (eo) En teoría de grafos, una descomposición en árbol es una correspondencia de un grafo hacia un árbol, que puede emplearse para definir la anchura del árbol (treewidth) y acelerar así la resolución de ciertos problemas computaciones en grafos. (es) En théorie des graphes, une décomposition arborescente ou décomposition en arbre (en anglais : tree-decomposition) consiste en une décomposition d'un graphe en séparateurs (sous-ensembles de sommets dont la suppression rend le graphe non connexe), connectés dans un arbre. Cette décomposition permet de définir une autre notion importante, la largeur arborescente ou largeur d'arbre (treewidth). Cette méthode a été proposée par Paul Seymour et Neil Robertson dans le cadre de leur théorie sur les mineurs d'un graphe. Elle est aussi connue en apprentissage automatique, où l'on parle d'arbre de jonction, notamment dans l'algorithme de l'arbre de jonction. (fr) In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Tree decompositions are also called junction trees, clique trees, or join trees. They play an important role in problems like probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition. The concept of tree decomposition was originally introduced by Rudolf Halin. Later it was rediscovered by Neil Robertson and Paul Seymour and has since been studied by many other authors. (en) グラフ理論において、木分解とはグラフから木へのマッピングであり、を定義してグラフの上のある種の計算機科学の問題を高速に解くために使われる。 機械学習では、木分解はjunction tree、clique tree、join treeとも呼ばれ、確率伝搬法や制約充足問題、クエリ最適化、en:matrix decompositionのような問題で重要な役割を果たす。 木分解の概念は最初ににより導入された。後に andにより再発見され、以降他の多数の研究者たちに研究されている。 (ja) В теорії графів деревна декомпозиція — це відображення графа в дерево, яке можна використати для визначення деревної ширини графа і прискорення розв'язання певних обчислювальних задач на графах. В галузі машинного навчання деревна декомпозиція називається деревом зчленувань, деревом клік або деревом суміжності. Деревна декомпозиція відіграє важливу роль у задачах, на зразок , , оптимізації запитів СУБД і розкладання матриць. Поняття деревної декомпозиції спочатку запропонував . Пізніше його перевідкрили і і відтоді поняття вивчали багато інших авторів. (uk) В теории графов древесная декомпозиция — это отображение графа в дерево, которое может быть использовано для определения древесной ширины графа и ускорения решения определённых вычислительных задач на графах. В области машинного обучения древесная декомпозиция называется также деревом сочленений, деревом клик или деревом смежности. Древесная декомпозиция играет важную роль в задачах, подобных вероятностному логическому выводу, , оптимизации запросов СУБД и разложения матриц. Понятие древесной декомпозиции было первоначально предложено Халином. Позднее его переоткрыли Робертсон и Сеймур и с тех пор понятие изучалось многими другими авторами. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Tree_decomposition.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ |
| dbo:wikiPageID | 159023 (xsd:integer) |
| dbo:wikiPageLength | 12658 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1110428359 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Belief_propagation dbc:Graph_minor_theory dbr:Approximation_algorithm dbr:Path_graph dbr:Pathwidth dbr:Decomposition_method_(constraint_satisfaction) dbc:Graph_theory_objects dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Bramble_(graph_theory) dbr:Branch-decomposition dbr:Constraint_satisfaction dbr:Machine_learning dbc:Trees_(graph_theory) dbr:Tree_(graph_theory) dbr:Treewidth dbr:Junction_tree_algorithm dbr:Query_optimization dbr:Dynamic_programming dbr:Graph_theory dbr:Journal_of_Combinatorial_Theory dbr:Matrix_decomposition dbr:Haven_(graph_theory) dbr:Intersection_graph dbr:Chordal_graph dbr:Springer_Science+Business_Media dbr:NP-completeness dbr:Maximum_independent_set dbr:File:Tree_decomposition.svg dbr:File:Treedecompsnocolour.JPG |
| dbp:author1Link | Neil Robertson (en) |
| dbp:author2Link | Paul Seymour (en) |
| dbp:authorlink | Rudolf Halin (en) |
| dbp:first | Neil (en) Paul (en) Rudolf (en) |
| dbp:last | Robertson (en) Seymour (en) Halin (en) |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Citation dbt:Citation_needed dbt:Main dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Snd dbt:Sub dbt:Sup dbt:Harvs |
| dbp:year | 1976 (xsd:integer) 1984 (xsd:integer) |
| dcterms:subject | dbc:Graph_minor_theory dbc:Graph_theory_objects dbc:Trees_(graph_theory) |
| gold:hypernym | dbr:Mapping |
| rdf:type | dbo:Software yago:Object100002684 yago:PhysicalEntity100001930 yago:WikicatGraphTheoryObjects |
| rdfs:comment | Stromový rozklad je jeden ze způsobů, jak charakterizovat graf. (cs) En grafeteorio, arbigo ĵetas grafeon al arbo. Oni povas difini per la operacio. La arbo rezultata ankaŭ utilas por rapidigi ian komputadon. En , arbigo grave rolas en problemoj, ekzemple probabla inferencio, kaj . La ideon de arbigo unue proponis (1976). Poste refoje ĝin malkovris kaj (1984). Ĝi estas temo de pluraj studoj ĝis nun. (eo) En teoría de grafos, una descomposición en árbol es una correspondencia de un grafo hacia un árbol, que puede emplearse para definir la anchura del árbol (treewidth) y acelerar así la resolución de ciertos problemas computaciones en grafos. (es) グラフ理論において、木分解とはグラフから木へのマッピングであり、を定義してグラフの上のある種の計算機科学の問題を高速に解くために使われる。 機械学習では、木分解はjunction tree、clique tree、join treeとも呼ばれ、確率伝搬法や制約充足問題、クエリ最適化、en:matrix decompositionのような問題で重要な役割を果たす。 木分解の概念は最初ににより導入された。後に andにより再発見され、以降他の多数の研究者たちに研究されている。 (ja) В теорії графів деревна декомпозиція — це відображення графа в дерево, яке можна використати для визначення деревної ширини графа і прискорення розв'язання певних обчислювальних задач на графах. В галузі машинного навчання деревна декомпозиція називається деревом зчленувань, деревом клік або деревом суміжності. Деревна декомпозиція відіграє важливу роль у задачах, на зразок , , оптимізації запитів СУБД і розкладання матриць. Поняття деревної декомпозиції спочатку запропонував . Пізніше його перевідкрили і і відтоді поняття вивчали багато інших авторів. (uk) En théorie des graphes, une décomposition arborescente ou décomposition en arbre (en anglais : tree-decomposition) consiste en une décomposition d'un graphe en séparateurs (sous-ensembles de sommets dont la suppression rend le graphe non connexe), connectés dans un arbre. Cette décomposition permet de définir une autre notion importante, la largeur arborescente ou largeur d'arbre (treewidth). (fr) In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Tree decompositions are also called junction trees, clique trees, or join trees. They play an important role in problems like probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition. (en) В теории графов древесная декомпозиция — это отображение графа в дерево, которое может быть использовано для определения древесной ширины графа и ускорения решения определённых вычислительных задач на графах. В области машинного обучения древесная декомпозиция называется также деревом сочленений, деревом клик или деревом смежности. Древесная декомпозиция играет важную роль в задачах, подобных вероятностному логическому выводу, , оптимизации запросов СУБД и разложения матриц. (ru) |
| rdfs:label | Stromový rozklad (cs) Arbigo (eo) Descomposición en árbol (es) Décomposition arborescente (fr) 木分解 (ja) Tree decomposition (en) Древесная декомпозиция (ru) Деревна декомпозиція (uk) |
| owl:sameAs | freebase:Tree decomposition yago-res:Tree decomposition wikidata:Tree decomposition dbpedia-cs:Tree decomposition dbpedia-eo:Tree decomposition dbpedia-es:Tree decomposition dbpedia-fa:Tree decomposition dbpedia-fr:Tree decomposition dbpedia-ja:Tree decomposition dbpedia-ru:Tree decomposition dbpedia-sr:Tree decomposition dbpedia-uk:Tree decomposition https://global.dbpedia.org/id/4HZpK |
| prov:wasDerivedFrom | wikipedia-en:Tree_decomposition?oldid=1110428359&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Tree_decomposition.svg wiki-commons:Special:FilePath/Treedecompsnocolour.jpg |
| foaf:isPrimaryTopicOf | wikipedia-en:Tree_decomposition |
| is dbo:wikiPageRedirects of | dbr:Junction_tree dbr:Clique_tree dbr:Clique_trees dbr:Tree_Decomposition dbr:Join_tree dbr:Running_intersection_property dbr:Junction_tree_property |
| is dbo:wikiPageWikiLink of | dbr:Moral_graph dbr:Junction_tree dbr:List_of_graph_theory_topics dbr:Pathwidth dbr:Decomposition_method_(constraint_satisfaction) dbr:Intersection_number_(graph_theory) dbr:Georg_Gottlob dbr:Glossary_of_graph_theory dbr:Graph_structure_theorem dbr:Branch-decomposition dbr:Clique_tree dbr:Clique_trees dbr:Planar_separator_theorem dbr:Bruce_Reed_(mathematician) dbr:Tree_Decomposition dbr:Treewidth dbr:Dynamic_programming dbr:Nicola_Leone dbr:Hans_L._Bodlaender dbr:Tree-depth dbr:Courcelle's_theorem dbr:Chordal_graph dbr:Bruno_Courcelle dbr:SPQR_tree dbr:Join_tree dbr:Partial_k-tree dbr:Rudolf_Halin dbr:Running_intersection_property dbr:Junction_tree_property |
| is foaf:primaryTopic of | wikipedia-en:Tree_decomposition |
