| dbo:abstract
|
- In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be expressed as a symmetric difference of basis cycles. A fundamental cycle basis may be formed from any spanning tree or spanning forest of the given graph, by selecting the cycles formed by the combination of a path in the tree and a single edge outside the tree. Alternatively, if the edges of the graph have positive weights, the minimum weight cycle basis may be constructed in polynomial time. In planar graphs, the set of bounded cycles of an embedding of the graph forms a cycle basis. The minimum weight cycle basis of a planar graph corresponds to the Gomory–Hu tree of the dual graph. (en)
- Базис циклов неориентированного графа — множество простых циклов, которые образуют базис пространства циклов графа. Таким образом, это минимальный набор циклов, который позволяет любой эйлеров подграф представить как симметрическую разность базисных циклов. Фундаментальный базис циклов может быть образован из любого остовного дерева леса-каркаса заданного графа путём выбора циклов, которые имеют ровно одно ребро, не принадлежащее дереву. Также, если задать рёбрам графа положительные веса, базис циклов минимального веса может быть построен в полиномиальное время. В планарных графах множество циклов ограниченных граней (то есть циклы-границы ограниченных граней — одна, внешняя, грань бесконечна) вложенного в плоскость графа образуют базис циклов. Минимальный по весу базис циклов планарного графа соответствует двойственного графа. (ru)
- Базис циклів неорієнтованого графа — множина простих циклів, що утворюють базис простору циклів графа. Таким чином, це мінімальний набір циклів, який дозволяє будь-який ейлерів підграф подати як симетричну різницю базисних циклів. Фундаментальний базис циклів можна утворити з будь-якого кістякового дерева лісу-каркаса заданого графа вибором циклів, які мають рівно одне ребро, що не належить дереву. Також, якщо задати ребрам графа додатні ваги, базис циклів мінімальної ваги можна побудувати за поліноміальний час. У планарних графах множина циклів обмежених граней (тобто цикли-межі обмежених граней — одна, зовнішня, грань нескінченна) вкладеного в площину графа утворюють базис циклів. Мінімальний за вагою базис циклів планарного графа відповідає двоїстого графа. (uk)
|
| rdfs:comment
|
- In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be expressed as a symmetric difference of basis cycles. In planar graphs, the set of bounded cycles of an embedding of the graph forms a cycle basis. The minimum weight cycle basis of a planar graph corresponds to the Gomory–Hu tree of the dual graph. (en)
- Базис циклов неориентированного графа — множество простых циклов, которые образуют базис пространства циклов графа. Таким образом, это минимальный набор циклов, который позволяет любой эйлеров подграф представить как симметрическую разность базисных циклов. Фундаментальный базис циклов может быть образован из любого остовного дерева леса-каркаса заданного графа путём выбора циклов, которые имеют ровно одно ребро, не принадлежащее дереву. Также, если задать рёбрам графа положительные веса, базис циклов минимального веса может быть построен в полиномиальное время. (ru)
- Базис циклів неорієнтованого графа — множина простих циклів, що утворюють базис простору циклів графа. Таким чином, це мінімальний набір циклів, який дозволяє будь-який ейлерів підграф подати як симетричну різницю базисних циклів. Фундаментальний базис циклів можна утворити з будь-якого кістякового дерева лісу-каркаса заданого графа вибором циклів, які мають рівно одне ребро, що не належить дереву. Також, якщо задати ребрам графа додатні ваги, базис циклів мінімальної ваги можна побудувати за поліноміальний час. (uk)
|
