Split (graph theory) (original) (raw)
In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms. Splits and split decompositions were first introduced by , who also studied variants of the same notions for directed graphs.
| Property | Value |
|---|---|
| dbo:abstract | En teoría de grafos, una ruptura de un grafo no dirigido es un corte cuyo conjunto de corte forma un grafo bipartito completo. Un grafo es primo si no tiene ninguna ruptura. Las rupturas de un grafo pueden ser acomodadas siguiendo una estructura de árbol llamada descomposición de ruptura o descomposición conjunta, la cual puede ser construida en tiempo lineal. Esta descomposición ha sido utilizada para el reconocimiento rápido de grafos circulares y grafos de distancia hereditaria, así como para otros problemas en algoritmos de grafos. Las rupturas y descomposiciones de ruptura fueron introducidas por Cunningham (1982), quien también estudió variantes de estas mismas nociones para grafos dirigidos. (es) In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms. Splits and split decompositions were first introduced by , who also studied variants of the same notions for directed graphs. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Split_decomposition.svg?width=300 |
| dbo:wikiPageID | 49923425 (xsd:integer) |
| dbo:wikiPageLength | 10314 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032145002 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Parity_graph dbr:Undirected_graph dbc:Graph_theory_objects dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Graph_coloring dbr:Linear_time dbr:Star_(graph_theory) dbr:Articulation_point dbr:Tree_(graph_theory) dbr:K-edge-connected_graph dbr:K-vertex-connected_graph dbr:Cut_(graph_theory) dbr:Cycle_graph dbr:Dynamic_programming dbr:Bridge_(graph_theory) dbr:Directed_graph dbr:Graph_theory dbr:Bipartite_graph dbr:Distance-hereditary_graph dbr:Dominating_set dbr:Circle_graph dbr:Polynomial_time dbr:Maximum_clique dbr:File:Split_decomposition.svg |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Harvtxt dbt:Mvar dbt:Reflist |
| dct:subject | dbc:Graph_theory_objects |
| rdfs:comment | In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms. Splits and split decompositions were first introduced by , who also studied variants of the same notions for directed graphs. (en) En teoría de grafos, una ruptura de un grafo no dirigido es un corte cuyo conjunto de corte forma un grafo bipartito completo. Un grafo es primo si no tiene ninguna ruptura. Las rupturas de un grafo pueden ser acomodadas siguiendo una estructura de árbol llamada descomposición de ruptura o descomposición conjunta, la cual puede ser construida en tiempo lineal. Esta descomposición ha sido utilizada para el reconocimiento rápido de grafos circulares y grafos de distancia hereditaria, así como para otros problemas en algoritmos de grafos. (es) |
| rdfs:label | Ruptura (teoría de grafos) (es) Split (graph theory) (en) |
| owl:sameAs | wikidata:Split (graph theory) dbpedia-es:Split (graph theory) https://global.dbpedia.org/id/2PWNH yago-res:Split (graph theory) |
| prov:wasDerivedFrom | wikipedia-en:Split_(graph_theory)?oldid=1032145002&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Split_decomposition.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Split_(graph_theory) |
| is dbo:wikiPageDisambiguates of | dbr:Split |
| is dbo:wikiPageRedirects of | dbr:Split_decomposition |
| is dbo:wikiPageWikiLink of | dbr:Glossary_of_graph_theory dbr:Split dbr:Cut_(graph_theory) dbr:Split_decomposition |
| is foaf:primaryTopic of | wikipedia-en:Split_(graph_theory) |
