Wiktionary英語版

出典：Wiktionary

branch-decomposition

出典:『Wiktionary』 (2024/12/26 16:37 UTC 版)

名詞

branch-decomposition (plural branch-decompositions)

  1. (mathematics) An unrooted binary tree that represents the hierarchical clustering of the edges of an undirected graph.
調べた例文を記録して、効率よく覚えましょう
Weblio会員無料で登録できます
履歴機能 過去に調べた単語を確認できる
語彙力診断 診断回数が4回に増加
マイ単語帳 便利な学習機能付き
マイ例文帳 文章で意味を理解できる
Weblio会員登録(無料)はこちらから▶

ウィキペディア英語版

出典：Wikipedia

Branch-decomposition

出典:『Wikipedia』 (2011/04/01 05:05 UTC 版)

英語による解説

ウィキペディア英語版からの引用
引用

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 and many graph optimization problems may be solved efficiently for graphs of small branchwidth. Branch-decompositions and branchwidth may also be generalized from graphs to matroids.

branch-decompositionのページの著作権