| http://dbpedia.org/ontology/abstract
|
In graph theory, a branch-decomposition of … In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G. Branchwidth is closely related to tree-width: for all graphs, both of these numbers are within a constant factor of each other, and both quantities may be characterized by forbidden minors. And as with treewidth, many graph optimization problems may be solved efficiently for graphs of small branchwidth. However, unlike treewidth, the branchwidth of planar graphs may be computed exactly, in polynomial time. Branch-decompositions and branchwidth may also be generalized from graphs to matroids.so be generalized from graphs to matroids.
, В теории графов декомпозиция на ветви неор … В теории графов декомпозиция на ветви неориентированного графа G — это иерархическая кластеризация рёбер графа G, представленная некорневым бинарным деревом T с рёбрами из G в качестве листьев. Удаление любого ребра из T делит рёбра графа G на два подграфа, а шириной декомпозиции считается максимальное число общих вершин в любом подграфе, полученным таким образом.Ширина ветвления графа G — это минимальная ширина любой декомпозиции графа G на ветви. Ширина ветвления тесно связана с древесной шириной — для всех графов они находятся в пределах постоянного множителя друг от друга и обе величины могут быть описаны запрещёнными минорами. Как и для древесной ширины, многие задачи оптимизации на графах могут быть эффективно решены на графах с малой шириной ветвления. Однако, в отличие от древесной ширины, ширина ветвления планарного графа может быть вычислена точно за полиномиальное время. Декомпозиция на ветви и ширина ветвления могут быть обобщены с графов на матроиды. могут быть обобщены с графов на матроиды.
, У теорії графів гілкова декомпозиція неорі … У теорії графів гілкова декомпозиція неорієнтованого графа G — це ієрархічна кластеризація ребер графа G, представлена некореневим двійковим деревом T з ребрами з G як листками. Видалення будь-якого ребра з T поділяє ребра графа G на два підграфи, а шириною декомпозиції вважають найбільшу кількість спільних вершин у будь-якому підграфі, отриманому в такий спосіб. Ширина галуження графа G це найменша ширина будь-якої гілкової декомпозиції графа G. Ширина галуження тісно пов'язана з деревною шириною — для всіх графів вони лежать у межах сталого множника одна від одної, і обидві величини можна описати забороненими мінорами. Як і для деревної ширини, багато задач оптимізації на графах можна ефективно розв'язати на графах із малою шириною галуження. Проте, на відміну деревної ширини, ширину галуження планарного графа можна обчислити точно за поліноміальний час. Гілкову декомпозицію та ширину галуження можна узагальнити з графів на матроїди.ня можна узагальнити з графів на матроїди.
, Στην θεωρία γράφων, μια κλαδοαποσύνθεση (b … Στην θεωρία γράφων, μια κλαδοαποσύνθεση (branch decomposition) ενός γραφήματος είναι ένα ζεύγος όπου το είναι ένα τριαδικό δέντρο (ένα δέντρο με όλες τις εσωτερικές κορυφές βαθμού 3) και το είναι μια 1-1 και επί αντιστοιχία των φύλλων του με τις ακμές του . Για κάθε ακμή του , το γράφημα αποτελείται από δύο δέντρα και , τα φύλα των οποίων ορίζουν (μέσω της )μια διαμέριση του συνόλου των ακμών του την οποία καλούμε -διαμέριση.ων ακμών του την οποία καλούμε -διαμέριση.
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/Branch-decomposition.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
http://www.icm2006.org/proceedings/Vol_III/contents/ICM_Vol_3_41.pdf +
, http://www.math.uwaterloo.ca/~jfgeelen/publications/grid.pdf +
, http://www.fi.muni.cz/~hlineny/Research/papers/matr-tw-final.pdf +
, http://www.caam.rice.edu/caam/trs/2000/TR00-17.ps +
, https://web.archive.org/web/20100924110915/http:/www.math.uwaterloo.ca/~jfgeelen/publications/grid.pdf +
, http://hal.archives-ouvertes.fr/docs/00/04/09/28/PDF/Branchwidth.pdf +
, http://hal.archives-ouvertes.fr/hal-00390623/ +
, https://web.archive.org/web/20120306042705/http:/www.fi.muni.cz/~hlineny/Research/papers/matr-tw-final.pdf +
, https://web.archive.org/web/20110716073653/http:/www.caam.rice.edu/caam/trs/2000/TR00-17.ps +
, http://www.cs.utk.edu/~langston/projects/papers/tmerge.pdf +
|
| http://dbpedia.org/ontology/wikiPageID
|
16823137
|
| http://dbpedia.org/ontology/wikiPageLength
|
20986
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1093782312
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Medial_graph +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/Category:Graph_minor_theory +
, http://dbpedia.org/resource/Journal_of_Combinatorial_Theory +
, http://dbpedia.org/resource/Robertson%E2%80%93Seymour_theorem +
, http://dbpedia.org/resource/Category:Trees_%28graph_theory%29 +
, http://dbpedia.org/resource/Dynamic_programming +
, http://dbpedia.org/resource/Matching_%28graph_theory%29 +
, http://dbpedia.org/resource/Neil_Robertson_%28mathematician%29 +
, http://dbpedia.org/resource/Planar_graphs +
, http://dbpedia.org/resource/Category:Matroid_theory +
, http://dbpedia.org/resource/Star_%28graph_theory%29 +
, http://dbpedia.org/resource/Matroid_minor +
, http://dbpedia.org/resource/Treewidth +
, http://dbpedia.org/resource/Unrooted_binary_tree +
, http://dbpedia.org/resource/Dual_matroid +
, http://dbpedia.org/resource/Matroid_rank +
, http://dbpedia.org/resource/Well-quasi-ordering +
, http://dbpedia.org/resource/Octahedron +
, http://dbpedia.org/resource/Category:Graph_invariants +
, http://dbpedia.org/resource/Spectral_clustering +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/Paul_Seymour_%28mathematician%29 +
, http://dbpedia.org/resource/Robin_Thomas_%28mathematician%29 +
, http://dbpedia.org/resource/Series%E2%80%93parallel_graph +
, http://dbpedia.org/resource/Connected_component_%28graph_theory%29 +
, http://dbpedia.org/resource/Hypercube_graph +
, http://dbpedia.org/resource/Biconnected_component +
, http://dbpedia.org/resource/Polynomial_time +
, http://dbpedia.org/resource/Wagner_graph +
, http://dbpedia.org/resource/Uniform_matroid +
, http://dbpedia.org/resource/Hierarchical_clustering +
, http://dbpedia.org/resource/Path_graph +
, http://dbpedia.org/resource/Matroid_oracle +
, http://dbpedia.org/resource/Tree_decomposition +
, http://dbpedia.org/resource/Parameterized_complexity +
, http://dbpedia.org/resource/Graph_minor +
, http://dbpedia.org/resource/Graphic_matroid +
, http://dbpedia.org/resource/Finite_field +
, http://dbpedia.org/resource/File:Branch-decomposition.svg +
, http://dbpedia.org/resource/File:Branchwidth_3-forbidden_minors.svg +
, http://dbpedia.org/resource/Planar_graph +
, http://dbpedia.org/resource/Forbidden_graph_characterization +
, http://dbpedia.org/resource/Matroid +
, http://dbpedia.org/resource/Forbidden_minor +
, http://dbpedia.org/resource/Undirected_graph +
, http://dbpedia.org/resource/International_Congress_of_Mathematicians +
, http://dbpedia.org/resource/Minor_%28graph_theory%29 +
, http://dbpedia.org/resource/Travelling_salesman_problem +
, http://dbpedia.org/resource/Complete_graph +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Refend +
, http://dbpedia.org/resource/Template:Refbegin +
, http://dbpedia.org/resource/Template:Short_description +
, http://dbpedia.org/resource/Template:Commons_category +
, http://dbpedia.org/resource/Template:Harvtxt +
, http://dbpedia.org/resource/Template:Citation +
, http://dbpedia.org/resource/Template:Sfnp +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Graph_invariants +
, http://dbpedia.org/resource/Category:Graph_minor_theory +
, http://dbpedia.org/resource/Category:Matroid_theory +
, http://dbpedia.org/resource/Category:Trees_%28graph_theory%29 +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Branch-decomposition?oldid=1093782312&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/Branch-decomposition.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Branchwidth_3-forbidden_minors.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Branch-decomposition +
|
| owl:sameAs |
http://yago-knowledge.org/resource/Branch-decomposition +
, https://global.dbpedia.org/id/4b9bE +
, http://el.dbpedia.org/resource/%CE%9A%CE%BB%CE%B1%CE%B4%CE%BF%CF%80%CE%BB%CE%AC%CF%84%CE%BF%CF%82 +
, http://www.wikidata.org/entity/Q4956329 +
, http://uk.dbpedia.org/resource/%D0%93%D1%96%D0%BB%D0%BA%D0%BE%D0%B2%D0%B0_%D0%B4%D0%B5%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D1%96%D1%8F +
, http://dbpedia.org/resource/Branch-decomposition +
, http://rdf.freebase.com/ns/m.0407hs5 +
, http://fa.dbpedia.org/resource/%D8%AA%D8%AC%D8%B2%DB%8C%D9%87_%D8%A7%D9%86%D8%B4%D8%B9%D8%A7%D8%A8%DB%8C +
, http://ru.dbpedia.org/resource/%D0%94%D0%B5%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%B0_%D0%BD%D0%B0_%D0%B2%D0%B5%D1%82%D0%B2%D0%B8 +
|
| rdf:type |
http://dbpedia.org/class/yago/Feature105849789 +
, http://dbpedia.org/class/yago/PsychologicalFeature100023100 +
, 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/Cognition100023271 +
, http://dbpedia.org/class/yago/Idea105833840 +
, http://dbpedia.org/class/yago/Content105809192 +
, http://dbpedia.org/class/yago/Abstraction100002137 +
|
| rdfs:comment |
В теории графов декомпозиция на ветви неор … В теории графов декомпозиция на ветви неориентированного графа G — это иерархическая кластеризация рёбер графа G, представленная некорневым бинарным деревом T с рёбрами из G в качестве листьев. Удаление любого ребра из T делит рёбра графа G на два подграфа, а шириной декомпозиции считается максимальное число общих вершин в любом подграфе, полученным таким образом.Ширина ветвления графа G — это минимальная ширина любой декомпозиции графа G на ветви.ирина любой декомпозиции графа G на ветви.
, Στην θεωρία γράφων, μια κλαδοαποσύνθεση (b … Στην θεωρία γράφων, μια κλαδοαποσύνθεση (branch decomposition) ενός γραφήματος είναι ένα ζεύγος όπου το είναι ένα τριαδικό δέντρο (ένα δέντρο με όλες τις εσωτερικές κορυφές βαθμού 3) και το είναι μια 1-1 και επί αντιστοιχία των φύλλων του με τις ακμές του . Για κάθε ακμή του , το γράφημα αποτελείται από δύο δέντρα και , τα φύλα των οποίων ορίζουν (μέσω της )μια διαμέριση του συνόλου των ακμών του την οποία καλούμε -διαμέριση.ων ακμών του την οποία καλούμε -διαμέριση.
, In graph theory, a branch-decomposition of … In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G.um width of any branch-decomposition of G.
, У теорії графів гілкова декомпозиція неорі … У теорії графів гілкова декомпозиція неорієнтованого графа G — це ієрархічна кластеризація ребер графа G, представлена некореневим двійковим деревом T з ребрами з G як листками. Видалення будь-якого ребра з T поділяє ребра графа G на два підграфи, а шириною декомпозиції вважають найбільшу кількість спільних вершин у будь-якому підграфі, отриманому в такий спосіб. Ширина галуження графа G це найменша ширина будь-якої гілкової декомпозиції графа G.а будь-якої гілкової декомпозиції графа G.
|
| rdfs:label |
Декомпозиция графа на ветви
, Κλαδοπλάτος
, Гілкова декомпозиція
, Branch-decomposition
|
