Edge contraction (original) (raw)
In der Graphentheorie bezeichnet Kantenkontraktion oder Kontraktion eine grundlegende Operation auf Graphen. Dabei wird eine Kante e entfernt und die beiden anliegenden Knoten werden zu einem neuen Knoten w vereinigt.
| Property | Value |
|---|---|
| dbo:abstract | In der Graphentheorie bezeichnet Kantenkontraktion oder Kontraktion eine grundlegende Operation auf Graphen. Dabei wird eine Kante e entfernt und die beiden anliegenden Knoten werden zu einem neuen Knoten w vereinigt. (de) In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex identification is a less restrictive form of this operation. (en) En théorie des graphes, une contraction d'arête est une opération sur un graphe. Elle consiste, de façon imagée, à contracter une arête d'un graphe, ce qui revient à fusionner ses deux extrémités. Cette opération est fondamentale pour la théorie des mineurs de graphe et elle est utilisée dans certains algorithmes et certaines preuves. (fr) En el campo matemático de la teoría de grafos, una contracción de aristas también llamada contracción de grafos o simplemente contracción es una operación que elimina una arista del grafo al mismo tiempo que fusiona los dos vértices extremos. La contracción es una operación fundamental en la teoría de grafos. La operación de contracción de aristas toma un arista e = uv, la cual es removida del grafo y los dos vértices incidentes u y v son fusionados en un nuevo vértice w, de modo tal que las aristas incidentes a w son las aristas incidentes de u y v Más generalmente, la operación de contracción se puede dar sobre un conjunto de aristas en cualquier orden. Las contracciones de aristas pueden resultar en multigrafos con bucles o aristas múltiples, los que a veces se eliminan con el fin de mantenerse dentro de la clase de grafos simples. La contracción de vértices es otra variante de la operación resta. (es) Nella teoria dei grafi, una contrazione dei grafi è un'operazione che rimuove uno spigolo da un grafo mentre fonde simultaneamente i due vertici che connetteva in precedenza. La contrazione degli spigoli è un'operazione fondamentale nella teoria dei . L'identificazione dei vertici è una forma meno restrittiva di questa operazione. (it) В теории графов стягивание ребра — это операция, которая удаляет ребро из графа, а до этого связанные ребром вершины сливаются в одну вершину. Стягивание ребра является фундаментальной операцией в теории о минорах графов. Отождествление вершин — другая форма этой операции с более слабыми ограничениями. (ru) В теорії графів стягування ребра — це операція, яка видаляє ребро з графу, а до цього зв'язані ребром вершини зливаються в одну вершину. Стягування ребра є фундаментальною операцією в теорії про мінори графів. Ототожнення вершин — інша форма цієї операції зі слабшими обмеженнями. (uk) 在图论中，边收缩是指將一個圖的其中一個邊移除，並將被移除邊的兩個頂點合併，同時保持與被移除邊之頂點相連的其他頂點之連接關係的一種變換，為圖子式理論中的基本運算元之一，然而此種變換不一定是圖論中的變換，亦可以作用於拓樸結構甚至是幾何體，例如邊收縮二十面體，即正二十面體經過一次邊收縮變換後的像。另一種與邊收縮類似的圖論變換為（vertex contraction）是邊收縮變換的一個廣義形式。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Edge_contraction_with_multiple_edges.svg?width=300 |
| dbo:wikiPageID | 3758115 (xsd:integer) |
| dbo:wikiPageLength | 7560 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1117162921 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Connected_graph dbr:Quotient_graph dbr:Chromatic_polynomial dbr:Graph_(discrete_mathematics) dbr:Graph_minor dbr:Path_(graph_theory) dbr:Spanning_tree dbr:Transitive_relation dbr:Partition_of_a_set dbr:Directed_graph dbr:Graph_operations dbr:Graph_theory dbr:Strongly_connected_component dbc:Graph_operations dbr:Vertex_(graph_theory) dbr:Multiple_edge dbr:Proof_by_induction dbr:Simple_graph dbr:Acyclic_directed_graph dbr:Global_graph_coloring_register_allocation dbr:Subdivision_(graph_theory) dbr:File:Edge_contraction.svg dbr:File:Edge_contraction_with_multiple_edges.svg |
| dbp:id | EdgeContraction (en) |
| dbp:title | Edge Contraction (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Math dbt:MathWorld dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Graph_operations |
| gold:hypernym | dbr:Operation |
| rdf:type | yago:Abstraction100002137 yago:Action114006945 yago:Attribute100024264 yago:Operation114008806 yago:WikicatGraphOperations dbo:MilitaryConflict yago:State100024720 |
| rdfs:comment | In der Graphentheorie bezeichnet Kantenkontraktion oder Kontraktion eine grundlegende Operation auf Graphen. Dabei wird eine Kante e entfernt und die beiden anliegenden Knoten werden zu einem neuen Knoten w vereinigt. (de) In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex identification is a less restrictive form of this operation. (en) En théorie des graphes, une contraction d'arête est une opération sur un graphe. Elle consiste, de façon imagée, à contracter une arête d'un graphe, ce qui revient à fusionner ses deux extrémités. Cette opération est fondamentale pour la théorie des mineurs de graphe et elle est utilisée dans certains algorithmes et certaines preuves. (fr) Nella teoria dei grafi, una contrazione dei grafi è un'operazione che rimuove uno spigolo da un grafo mentre fonde simultaneamente i due vertici che connetteva in precedenza. La contrazione degli spigoli è un'operazione fondamentale nella teoria dei . L'identificazione dei vertici è una forma meno restrittiva di questa operazione. (it) В теории графов стягивание ребра — это операция, которая удаляет ребро из графа, а до этого связанные ребром вершины сливаются в одну вершину. Стягивание ребра является фундаментальной операцией в теории о минорах графов. Отождествление вершин — другая форма этой операции с более слабыми ограничениями. (ru) В теорії графів стягування ребра — це операція, яка видаляє ребро з графу, а до цього зв'язані ребром вершини зливаються в одну вершину. Стягування ребра є фундаментальною операцією в теорії про мінори графів. Ототожнення вершин — інша форма цієї операції зі слабшими обмеженнями. (uk) 在图论中，边收缩是指將一個圖的其中一個邊移除，並將被移除邊的兩個頂點合併，同時保持與被移除邊之頂點相連的其他頂點之連接關係的一種變換，為圖子式理論中的基本運算元之一，然而此種變換不一定是圖論中的變換，亦可以作用於拓樸結構甚至是幾何體，例如邊收縮二十面體，即正二十面體經過一次邊收縮變換後的像。另一種與邊收縮類似的圖論變換為（vertex contraction）是邊收縮變換的一個廣義形式。 (zh) En el campo matemático de la teoría de grafos, una contracción de aristas también llamada contracción de grafos o simplemente contracción es una operación que elimina una arista del grafo al mismo tiempo que fusiona los dos vértices extremos. La contracción es una operación fundamental en la teoría de grafos. La operación de contracción de aristas toma un arista e = uv, la cual es removida del grafo y los dos vértices incidentes u y v son fusionados en un nuevo vértice w, de modo tal que las aristas incidentes a w son las aristas incidentes de u y v (es) |
| rdfs:label | Kantenkontraktion (de) Contracción de aristas (es) Contraction d'arête (fr) Edge contraction (en) Contrazione degli spigoli (it) Стягивание ребра (ru) Стягування ребра (uk) 边收缩 (zh) |
| owl:sameAs | freebase:Edge contraction yago-res:Edge contraction wikidata:Edge contraction dbpedia-de:Edge contraction dbpedia-es:Edge contraction dbpedia-fr:Edge contraction dbpedia-hr:Edge contraction dbpedia-hu:Edge contraction dbpedia-it:Edge contraction dbpedia-ru:Edge contraction dbpedia-uk:Edge contraction dbpedia-zh:Edge contraction https://global.dbpedia.org/id/QQEX |
| prov:wasDerivedFrom | wikipedia-en:Edge_contraction?oldid=1117162921&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Edge_contraction.svg wiki-commons:Special:FilePath/Edge_contraction_with_multiple_edges.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Edge_contraction |
| is dbo:wikiPageDisambiguates of | dbr:Contraction |
| is dbo:wikiPageRedirects of | dbr:Graph_contraction dbr:Contraction_(graph_theory) dbr:Contration dbr:Path_contraction dbr:Edge-contraction dbr:Vertex_contraction dbr:Vertex_identification dbr:Vertex_splitting |
| is dbo:wikiPageWikiLink of | dbr:Shallow_minor dbr:Blossom_algorithm dbr:Defective_coloring dbr:Control-flow_graph dbr:Rooted_graph dbr:Quotient_graph dbr:Chromatic_polynomial dbr:Graph_(discrete_mathematics) dbr:Graph_minor dbr:Graph_structure_theorem dbr:Bouquet_graph dbr:Deletion–contraction_formula dbr:Hamiltonian_path_problem dbr:Spanning_tree dbr:Stack-sortable_permutation dbr:Butterfly_graph dbr:Heavy_path_decomposition dbr:Karger's_algorithm dbr:Agreement_forest dbr:Edge-contracted_icosahedron dbr:Forbidden_graph_characterization dbr:Graph-encoded_map dbr:Graph_edit_distance dbr:Graph_operations dbr:Kelmans–Seymour_conjecture dbr:Hadwiger_conjecture_(graph_theory) dbr:Hadwiger_number dbr:Hajós_construction dbr:Abelian_sandpile_model dbr:Homeomorphism_(graph_theory) dbr:Directed_acyclic_graph dbr:Contraction dbr:Graph_contraction dbr:Randomized_algorithm dbr:Tutte_polynomial dbr:Factor-critical_graph dbr:Octadecahedron dbr:Polygon-circle_graph dbr:Truncated_rhombicuboctahedron dbr:Parallel_algorithms_for_minimum_spanning_trees dbr:Tutte–Grothendieck_invariant dbr:Contraction_(graph_theory) dbr:Contration dbr:Path_contraction dbr:Edge-contraction dbr:Vertex_contraction dbr:Vertex_identification dbr:Vertex_splitting |
| is foaf:primaryTopic of | wikipedia-en:Edge_contraction |
