Cycle basis (original) (raw)
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.
| Property | Value |
|---|---|
| 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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Cycle_space_addition.svg?width=300 |
| dbo:wikiPageID | 24778911 (xsd:integer) |
| dbo:wikiPageLength | 25621 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1117781811 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Multigraph dbr:Mac_Lane's_planarity_criterion dbr:Basis_(linear_algebra) dbr:Approximation_algorithm dbr:Best,_worst_and_average_case dbr:Cycle_space dbr:Undirected_graph dbr:Vector_space dbr:Degree_(graph_theory) dbr:Cheminformatics dbr:Nearest_neighbor_graph dbr:Orientation_(graph_theory) dbr:Nucleic_acid_tertiary_structure dbr:Gaussian_elimination dbr:Glossary_of_graph_theory dbr:Gomory–Hu_tree dbr:Graph_minor dbr:Bounded_set dbr:NP-hard dbr:Spanning_tree dbr:Matroid dbr:Peripheral_cycle dbc:Algebraic_graph_theory dbr:Distributed_computing dbr:K-vertex-connected_graph dbr:Linear_independence dbr:Cut_(graph_theory) dbr:Cut_space dbr:Dual_graph dbr:Eulerian_path dbr:Finite_field dbr:Forbidden_graph_characterization dbr:Outerplanar_graph dbr:Graph_theory dbr:Kinematics dbr:Simplicial_complex dbr:RNA dbr:Ring_(mathematics) dbr:Structural_rigidity dbr:Haplotype dbr:Tetrahedron dbr:Bioinformatics dbr:Homology_(mathematics) dbr:Dijkstra's_algorithm dbr:Planar_graph dbr:Square_pyramid dbr:Circuit_rank dbr:Free_abelian_group dbr:Connected_component_(graph_theory) dbr:Greedy_algorithm dbr:Polynomial_time dbr:Integer dbr:SNP_(complexity) dbr:Vertex_(graph_theory) dbr:Symmetric_difference dbr:Euler_characteristic dbr:Forest_(graph_theory) dbr:Molecular_graph dbr:Veblen's_theorem dbr:Eulerian_graph dbr:Hamiltonian_cycle dbr:Induced_cycle dbr:Simple_cycle dbr:Integer_program dbr:Shortest_path_tree dbr:Homology_group dbr:File:Cycle_space_addition.svg |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Algebraic_graph_theory |
| gold:hypernym | dbr:Set |
| 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) |
| rdfs:label | Cycle basis (en) Базис циклов (ru) Базис циклів (uk) |
| owl:sameAs | freebase:Cycle basis wikidata:Cycle basis dbpedia-ru:Cycle basis dbpedia-uk:Cycle basis https://global.dbpedia.org/id/erdk |
| prov:wasDerivedFrom | wikipedia-en:Cycle_basis?oldid=1117781811&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Cycle_space_addition.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Cycle_basis |
| is dbo:wikiPageRedirects of | dbr:Smallest_Set_of_Smallest_Rings dbr:Linearly_independent_cycle dbr:Smallest_set_of_smallest_rings |
| is dbo:wikiPageWikiLink of | dbr:Mac_Lane's_planarity_criterion dbr:Cycle_(graph_theory) dbr:Cycle_space dbr:Gomory–Hu_tree dbr:Antonio_Zamora dbr:Phosphorus_oxoacid dbr:Spanning_tree dbr:Dual_graph dbr:Kavitha_Telikepalli dbr:Circuit_rank dbr:Smallest_Set_of_Smallest_Rings dbr:Phosphoric_acids_and_phosphates dbr:Veblen's_theorem dbr:Linearly_independent_cycle dbr:Smallest_set_of_smallest_rings |
| is foaf:primaryTopic of | wikipedia-en:Cycle_basis |
