| dbo:abstract
|
- In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition. There are variants of modular decomposition for undirected graphs and directed graphs. For each undirected graph, this decomposition is unique. This notion can be generalized to other structures (for example directed graphs) and is useful to design efficient algorithms for the recognition of some graph classes, for finding transitive orientations of comparability graphs, for optimization problems on graphs, and for graph drawing. (en)
- Модульное разложение — это разложение графа на подмножества вершин, называемых модулями. Модуль является обобщением компоненты связности графа. В отличие от компонент связности, однако, один модуль может быть собственным подмножеством другого. Модули, поэтому, ведут к рекурсивной (иерархической) декомпозиции графа, а не просто к разбиениям. Существуют варианты модульного разложения для неориентированных графов и ориентированных графов. Для каждого неориентированного графа такая декомпозиция единственна. Это понятие может быть обобщено на другие структуры (например, ориентированные графы) и полезно для разработки эффективных алгоритмов для распознания некоторых классов графов, для поиска транзитивных ориентаций графов сравнимости, для задач оптимизации на графах и для визуализации графов. (ru)
|
| rdfs:comment
|
- In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition. There are variants of modular decomposition for undirected graphs and directed graphs. For each undirected graph, this decomposition is unique. (en)
- Модульное разложение — это разложение графа на подмножества вершин, называемых модулями. Модуль является обобщением компоненты связности графа. В отличие от компонент связности, однако, один модуль может быть собственным подмножеством другого. Модули, поэтому, ведут к рекурсивной (иерархической) декомпозиции графа, а не просто к разбиениям. Существуют варианты модульного разложения для неориентированных графов и ориентированных графов. Для каждого неориентированного графа такая декомпозиция единственна. (ru)
|
