Reverse-delete algorithm (original) (raw)
The reverse-delete algorithm is an algorithm in graph theory used to obtain a minimum spanning tree from a given connected, edge-weighted graph. It first appeared in , but it should not be confused with Kruskal's algorithm which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.
| Property | Value |
|---|---|
| dbo:abstract | The reverse-delete algorithm is an algorithm in graph theory used to obtain a minimum spanning tree from a given connected, edge-weighted graph. It first appeared in , but it should not be confused with Kruskal's algorithm which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph. This algorithm is a greedy algorithm, choosing the best choice given any situation. It is the reverse of Kruskal's algorithm, which is another greedy algorithm to find a minimum spanning tree. Kruskal’s algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with the original graph and deletes edges from it. The algorithm works as follows: * Start with graph G, which contains a list of edges E. * Go through E in decreasing order of edge weights. * For each edge, check if deleting the edge will further disconnect the graph. * Perform any deletion that does not lead to additional disconnection. (en) Алгоритм обратного удаления — это алгоритм в теории графов, использующийся для получения минимального остовного дерева из данного связного рёберно взвешенного графа. Впервые алгоритм появился в статье Краскала, но не следует его путать с алгоритмом Краскала, который появился в той же статье. Если граф не связен, этот алгоритм найдёт минимальное остовное дерево для каждой отдельной части графа. Множество этих минимальных остовных деревьев называется минимальным остовным лесом, который содержит все вершины графа. Алгоритм является жадным алгоритмом, дающим лучшее решение. Он противоположен алгоритму Краскала, который является другим жадным алгоритмом поиска минимального остовного дерева. Алгоритм Краскала начинает с пустого графа и добавляет рёбра, в то время как алгоритм обратного удаления начинает с исходного графа и удаляет рёбра из него. Алгоритм работает следующим образом: * Начинаем с графа G, который содержит список рёбер E. * Проходим через E в порядке убывания веса рёбер. * Для каждого ребра проверяем, не приводит ли его удаление к несвязному графу. * Осуществляем удаления, не приводящие к несвязности графа. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Reverse_Delete_0.svg?width=300 |
| dbo:wikiPageID | 9516059 (xsd:integer) |
| dbo:wikiPageLength | 8699 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1083605955 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Prim's_algorithm dbr:Big-O_notation dbr:Algorithm dbc:Spanning_tree dbr:Kruskal's_algorithm dbr:Proceedings_of_the_American_Mathematical_Society dbc:Graph_algorithms dbr:Weighted_graph dbr:Graph_theory dbr:Dijkstra's_algorithm dbr:Borůvka's_algorithm dbr:Greedy_algorithm dbr:Minimum_spanning_tree dbr:Symposium_on_Theory_of_Computing dbr:File:Reverse_Delete_0.svg dbr:File:Reverse_Delete_1.svg dbr:File:Reverse_Delete_2.svg dbr:File:Reverse_Delete_3.svg dbr:File:Reverse_Delete_4.svg dbr:File:Reverse_Delete_5.svg dbr:File:Reverse_Delete_6.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Harvtxt dbt:Short_description dbt:Sic |
| dct:subject | dbc:Spanning_tree dbc:Graph_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | The reverse-delete algorithm is an algorithm in graph theory used to obtain a minimum spanning tree from a given connected, edge-weighted graph. It first appeared in , but it should not be confused with Kruskal's algorithm which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph. (en) Алгоритм обратного удаления — это алгоритм в теории графов, использующийся для получения минимального остовного дерева из данного связного рёберно взвешенного графа. Впервые алгоритм появился в статье Краскала, но не следует его путать с алгоритмом Краскала, который появился в той же статье. Если граф не связен, этот алгоритм найдёт минимальное остовное дерево для каждой отдельной части графа. Множество этих минимальных остовных деревьев называется минимальным остовным лесом, который содержит все вершины графа. (ru) |
| rdfs:label | Reverse-delete algorithm (en) Алгоритм обратного удаления (ru) |
| owl:sameAs | freebase:Reverse-delete algorithm yago-res:Reverse-delete algorithm wikidata:Reverse-delete algorithm dbpedia-fa:Reverse-delete algorithm dbpedia-ru:Reverse-delete algorithm dbpedia-sr:Reverse-delete algorithm dbpedia-th:Reverse-delete algorithm https://global.dbpedia.org/id/4a3ax |
| prov:wasDerivedFrom | wikipedia-en:Reverse-delete_algorithm?oldid=1083605955&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Reverse_Delete_0.svg wiki-commons:Special:FilePath/Reverse_Delete_1.svg wiki-commons:Special:FilePath/Reverse_Delete_2.svg wiki-commons:Special:FilePath/Reverse_Delete_3.svg wiki-commons:Special:FilePath/Reverse_Delete_4.svg wiki-commons:Special:FilePath/Reverse_Delete_5.svg wiki-commons:Special:FilePath/Reverse_Delete_6.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Reverse-delete_algorithm |
| is dbo:wikiPageRedirects of | dbr:Reverse-Delete_algorithm |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Kruskal's_algorithm dbr:Minimum_spanning_tree dbr:Expected_linear_time_MST_algorithm dbr:Reverse-Delete_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Reverse-delete_algorithm |
