About: Cycle basis

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Cycle basis Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/c/5g6Y8QpniN

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.

Attributes	Values
rdfs:label	Cycle basis (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)
foaf:depiction
dct:subject	Algebraic graph theory
Wikipage page ID	24778911 (xsd:integer)
Wikipage revision ID	1117781811 (xsd:integer)
Link from a Wikipage to another Wikipage	Multigraph Mac Lane's planarity criterion Basis (linear algebra) Approximation algorithm Best, worst and average case Cycle space Undirected graph Vector space Degree (graph theory) Cheminformatics Nearest neighbor graph Orientation (graph theory) Nucleic acid tertiary structure Gaussian elimination Glossary of graph theory Gomory–Hu tree Graph minor Bounded set NP-hard Spanning tree Matroid Peripheral cycle Algebraic graph theory Distributed computing K-vertex-connected graph Linear independence Cut (graph theory) Cut space Dual graph Eulerian path Finite field Forbidden graph characterization Outerplanar graph Graph theory Kinematics Simplicial complex RNA Ring (mathematics) Structural rigidity Haplotype Tetrahedron Bioinformatics Homology (mathematics) Dijkstra's algorithm Planar graph Square pyramid Circuit rank Free abelian group Connected component (graph theory) Greedy algorithm Polynomial time Integer SNP (complexity) Vertex (graph theory) Symmetric difference Euler characteristic Forest (graph theory) Molecular graph Veblen's theorem Eulerian graph Hamiltonian cycle Induced cycle Simple cycle Integer program Shortest path tree Homology group
sameAs	Cycle basis Cycle basis Cycle basis Cycle basis Cycle basis
dbp:wikiPageUsesTemplate	dbt:Harvtxt dbt:Reflist dbt:Short_description
thumbnail	wiki-commons:Special:FilePath/Cycle_space_addition.svg?width=300
has 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)
gold:hypernym	Set
prov:wasDerivedFrom	wikipedia-en:Cycle_basis?oldid=1117781811&ns=0
page length (characters) of wiki page	25621 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Cycle_basis
is Link from a Wikipage to another Wikipage of	Mac Lane's planarity criterion Cycle (graph theory) Cycle space Gomory–Hu tree Antonio Zamora Phosphorus oxoacid Spanning tree

Faceted Search & Find service v1.17_git147 as of Sep 06 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3332 as of Dec 5 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 59 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software