Minimum spanning tree (original) (raw)
Die MST-Heuristik (MST steht für minimum spanning tree bzw. minimaler Spannbaum) dient dazu, das metrische Problem des Handlungsreisenden (TSP) zu approximieren. Dabei geht man wie folgt vor: 1. * Erzeuge einen minimalen Spannbaum für den zugrundeliegenden ungerichteten Graphen 2. * Verdopple jede Kante im resultierenden Spannbaum, was zu einem eulerschen Graphen führt 3. * Wähle einen beliebigen Startknoten und folge den Kanten des verdoppelten Spannbaums im Sinne eines Eulerkreises. Bereits besuchte Knoten werden dabei durch die direkte Kante zum folgenden Knoten übersprungen, sofern es sich nicht um den letzten Knoten des Kreises handelt.
| Property | Value |
|---|---|
| dbo:abstract | Στη Θεωρία Γράφων και στην Επιστήμη Υπολογιστών, συχνά συναντάται το πρόβλημα της εύρεσης του ελάχιστου διασυνδετικού ή γεννητικού δέντρου ενός γράφου με βάρη στις ακμές. Το πρόβλημα συνίσταται στην εύρεση ενός δέντρου με κορυφές αυτές του γράφου και ακμές ένα υποσύνολο των ακμών του γράφου, τέτοιο ώστε το άθροισμα των βαρών τους να είναι το ελάχιστο δυνατό. Αλλιώς, το πρόβλημα μπορεί να διατυπωθεί ως πρόβλημα για την εύρεση ενός υποσυνόλου των ακμών του γραφήματος, ώστε το νέο υπογράφημα που προκύπτει να είναι συνεκτικό και το άθροισμα των βαρών των ακμών του να είναι το ελάχιστο δυνατό. Εδώ, δεν είναι σαφές αν η λύση του προβλήματος αποτελεί δέντρο. Όμως, αν το υπογράφημα που προκύπτει ως λύση έχει κύκλο, τότε αφαιρώντας μια ακμή από τον κύκλο (την βαρύτερη) το υπογράφημα παραμένει συνεκτικό και το άθροισμα των βαρών των ακμών του είναι ακόμη μικρότερο (αφού έχουμε αφαιρέσει μια ακμή). Επομένως, δεν γίνεται η λύση του προβλήματος να περιέχει κύκλο, γιατί τότε δεν θα έχει το ελάχιστο δυνατό άθροισμα βαρών. Και αφού επιπλέον το υπογράφημα πρέπει να είναι συνεκτικό, εξορισμού προκύπτει ότι η λύση θα είναι ένα δέντρο. (el) Donita koneksa, sendirekta grafeo, de tiu grafeo estas subgrafeo kiu estas arbo kaj kunkonektas ĉiujn verticojn. Sola grafeo povas havi multajn malsamajn branĉantajn arbojn. On povas ankaŭ asigni pezon al ĉiu latero, kiu estas nombro prezentanta kiel malfavora ĝi estas, kaj uzi tion por asigni pezon al branĉanta arbo per komputi la sumon de la pezoj de la branĉoj en tiu branĉanta arbo. Minimuma branĉanta arbo aŭ minimum-peza branĉanta arbo estas tiam branĉanta arbo kun pezo malpli ol aŭ egala al la pezo de ĉiu alia branĉanta arbo. Pli ĝenerale, iu ajn sendirekta grafeo havas minimuman branĉantan arbaron. Unu ekzemplo estus kabla televid-kompanio demetanta kablon al nova najbarejo. Se ĝi estas limigita subterigi la kablon nur laŭ certaj vojoj, tiam devus esti grafeo prezentanta tion kiuj punktoj estas koneksaj per tiuj vojoj. Iuj el tiuj vojoj povus esti pli multekostaj, ĉar ili estas pli longaj, aŭ postuli la kablon esti enfosita pli profunde; ĉi tiuj vojoj devus esti prezentitaj per randoj kun pli grandaj pezoj. Branĉanta arbo por tiu grafeo devus esti subaro de tiuj vojoj, kiuj havas neniujn ciklojn sed ankoraŭ trakonektas al ĉiu domo. Tie povus esti kelkaj branĉantaj arboj eblaj. Minimuma branĉanta arbo devus esti unu kun la plej malalta tuteca kosto. En la kazo se de egalpezo, povus esti kelkaj minimumaj branĉantaj arboj; precipe, se ĉiuj pezoj samas, ĉiu branĉanta arbo estas minimumo. Tamen, unu teoremo diras, ke se ĉiu branĉo havas klaran pezon, la minimuma branĉanta arbo estas unika. Tio estas vera en multaj realismaj situacioj, kiel tiu pli supre, kie estas malverŝajne ke iuj ajn du vojoj havas ĝuste la saman koston. Ĉi tiu ankaŭ ĝeneraliĝas al branĉantaj arbaroj. Minimuma branĉanta arbo estas fakte la minimum-kostaj subgrafeaj trakonektantaj ĉiuj verticoj, ĉar subgrafeoj enhavantaj ciklojn necese havas pli tuteca pezo. (eo) Die MST-Heuristik (MST steht für minimum spanning tree bzw. minimaler Spannbaum) dient dazu, das metrische Problem des Handlungsreisenden (TSP) zu approximieren. Dabei geht man wie folgt vor: 1. * Erzeuge einen minimalen Spannbaum für den zugrundeliegenden ungerichteten Graphen 2. * Verdopple jede Kante im resultierenden Spannbaum, was zu einem eulerschen Graphen führt 3. * Wähle einen beliebigen Startknoten und folge den Kanten des verdoppelten Spannbaums im Sinne eines Eulerkreises. Bereits besuchte Knoten werden dabei durch die direkte Kante zum folgenden Knoten übersprungen, sofern es sich nicht um den letzten Knoten des Kreises handelt. (de) Dado un grafo conexo y no dirigido, un árbol recubridor, árbol de cobertura o árbol de expansión de ese grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc.; y se usa para asignar un peso total al árbol recubridor mínimo computando la suma de todos los pesos de las aristas del árbol en cuestión. Un árbol recubridor mínimo o un árbol de expansión mínimo es un árbol recubridor que pesa menos o igual que todos los otros árboles recubridores.Todo grafo tiene un bosque recubridor mínimo. Un ejemplo sería una compañía de cable trazando cable a una nueva vecindad. Si está limitada a trazar el cable por ciertos caminos, entonces se hará un grafo que represente los puntos conectados por esos caminos. Algunos de estos caminos podrán ser más caros que otros, por ser más largos. Estos caminos serían representados por las aristas con mayores pesos. Un árbol recubridor para este grafo sería un subconjunto de estos caminos que no tenga ciclos pero que mantenga conectadas todas las casas.Puede haber más de un árbol recubridor posible. El árbol recubridor mínimo será el de menos coste. En el caso de un empate, porque podría haber más de un árbol recubridor mínimo; en particular, si todos los pesos son iguales, todo árbol recubridor será mínimo. De todas formas, si cada arista tiene un peso distinto existirá solo un árbol recubridor mínimo. La demostración de esto es trivial y se puede hacer por inducción. Esto ocurre en muchas situaciones de la realidad, como con la compañía de cable en el ejemplo anterior, donde es extraño que dos caminos tengan exactamente el mismo coste. Esto también se generaliza para los bosques recubridores. Si los pesos son positivos, el árbol recubridor mínimo es el subgrafo de menor costo posible conectando todos los vértices, ya que los subgrafos que contienen ciclos necesariamente tienen más peso total. (es) A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components. There are many use cases for minimum spanning trees. One example is a telecommunications company trying to lay cable in a new neighborhood. If it is constrained to bury the cable only along certain paths (e.g. roads), then there would be a graph containing the points (e.g. houses) connected by those paths. Some of the paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. Currency is an acceptable unit for edge weight – there is no requirement for edge lengths to obey normal rules of geometry such as the triangle inequality. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects every house; there might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost, representing the least expensive path for laying the cable. (en) En théorie des graphes, étant donné un graphe non orienté connexe dont les arêtes sont pondérées, un arbre couvrant de poids minimal (ACM) de ce graphe est un arbre couvrant (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale (c'est-à-dire de poids inférieur ou égal à celui de tous les autres arbres couvrants du graphe). L'arbre couvrant de poids minimal est aussi connu sous certains autres noms, tel qu’arbre couvrant minimum ou encore arbre sous-tendant minimum[réf. nécessaire]. L'arbre couvrant minimum peut s'interpréter de différentes manières selon ce que représente le graphe. De manière générale si on considère un réseau où un ensemble d'objets doivent être reliés entre eux (par exemple un réseau électrique et des habitations), l'arbre couvrant minimum est la façon de construire un tel réseau en minimisant un coût représenté par le poids des arêtes (par exemple la longueur totale de câble utilisée pour construire un réseau électrique). (fr) Pohon rentang minimum atau pohon rentang berbobot minimum (bahasa Inggris: minimum spanning tree, MST) adalah himpunan bagian dari himpunan garis-garis (edge) suatu graf berbobot tak berarah yang menghubungkan semua titik tanpa membentuk siklus dan dengan total bobot minimum. Dengan kata lain, ini adalah yang total bobotnya minimum. Ada beberapa kasus yang menggunakan pohon rentang minimum. Misalnya, perusahaan telepon mencoba untuk menghubungkan telepon-telepon rumah dengan kabel sehingga kabel yang dipakai sependek mungkin. Di beberapa tempat, mungkin dibutuhkan penggalian sehingga biayanya bertambah. Dengan kata lain, "bobot" garisnya bertambah. Satuan yang biasa dipakai dalam permasalahan ini adalah biaya (cost). Dalam konteks ini, pohon rentang minimum adalah jalur yang menggunakan kabel sependek mungkin atau dengan biaya serendah mungkin. (in) Nella teoria dei grafi, dato un grafo con archi pesati, l'albero ricoprente minimo o albero di copertura di costo minimo (minimum spanning tree, MST) è un albero ricoprente nel quale sommando i pesi degli archi si ottiene un valore minimo. (it) De minimaal opspannende boom van een verbonden, gewogen graaf is de verbonden subgraaf daarvan met het kleinste totale gewicht. Deze kleinste subgraaf is altijd een boom, dat wil zeggen een graaf zonder cycli. Een algoritme om de minimaal opspannende boom te vinden is het algoritme van Prim: * kies een willekeurige knoop, de eerste bezochte knoop * kies de zijde met de laagste waarde verbonden met deze knoop * neem de knoop aan de andere zijde van de zijde op in de verzameling bezochte knopen * kies de zijde met de laagste waarde uit deze verzameling naar een knoop die nog niet is bezocht en voeg deze zijde aan de minimaal opspannende boom toe * neem de nieuwe bereikte knoop op in je verzameling * ga door tot alle knopen van de graaf bezocht zijn Hier een ander algoritme voor is Kruskals algoritme, maar er zijn er meer. Een gegeven graaf kan in het algemeen verschillende minimaal opspannende bomen hebben. Alleen wanneer alle zijden van de graaf een verschillend gewicht hebben is er een unieke, minimaal opspannende boom. (nl) Dado um grafo não orientado , uma árvore de extensão deste grafo é um subgrafo o qual é uma árvore que conecta todos os vértices. Um único grafo pode ter diferentes árvores de extensão. Nós podemos assinalar um peso a cada aresta, que é um número que representa quão desfavorável ela é, e atribuir um peso a árvore de extensão calculado pela soma dos pesos das arestas que a compõem. Uma árvore de extensão mínima (também conhecida como árvore de extensão de peso mínimo ou árvore geradora mínima) é então uma árvore de extensão com peso menor ou igual a cada uma das outras árvores de extensão possíveis. Generalizando mais, qualquer grafo não direcional (não necessariamente conectado) tem uma floresta de árvores mínimas, que é uma união de árvores de extensão mínimas de cada uma de suas . Um exemplo de uso de uma árvore de extensão mínima seria a instalação de fibras óticas num campus de uma faculdade. Cada trecho de fibra ótica entre os prédios possui um custo associado (isto é, o custo da fibra, somado ao custo da instalação da fibra, mão de obra, etc). Com esses dados em mãos (os prédios e os custos de cada trecho de fibra ótica entre todos os prédios), podemos construir uma árvore de extensão que nos diria um jeito de conectarmos todos os prédios sem redundância. Uma árvore geradora mínima desse grafo nos daria uma árvore com o menor custo para fazer essa ligação. (pt) Minimalne drzewo rozpinające (ang. MST, minimum spanning tree) – drzewo rozpinające danego grafu o najmniejszej z możliwych wag, tj. takie, że nie istnieje dla tego grafu inne drzewo rozpinające o mniejszej sumie wag krawędzi. (pl) Мінімальне кістякове дерево у зв'язаному, зваженому, неорієнтованому графі — це кістяк цього графу, що має мінімальну можливу вагу, де під вагою дерева розуміється сума ваг його ребер. (uk) En sammanhängande, oriktad graf kan delas in i ett uppspännande träd, där grafens alla noder finns representerade utan några cykler. Detta görs genom att en delmängd av de ursprungliga kanterna väljs ut på ett sådant sätt att grafen fortfarande är sammanhängande och ett träd. Detta kan göras på flera olika sätt, men om den ursprungliga grafen dessutom är viktad, det vill säga att varje kant har givits en vikt, kan man även definiera trädens vikt som summan av dess viktade kanter. Då är ett minimalt uppspännande träd det uppspännande träd till grafen vars vikt är minimerad (mindre eller lika med vikten för alla andra uppspännande träd till grafen). (sv) Минимальное остовное дерево (или минимальное покрывающее дерево) в (неориентированном) связном взвешенном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер. (ru) 最小生成树是一副连通加权无向图中一棵权值最小的生成树。 在一給定的無向圖 中， 代表連接頂點 u 與頂點 v 的邊（即 ），而 代表此邊的權重，若存在 T 為 E 的子集（即 ）且 (V, T) 為樹，使得 的 w(T) 最小，則此 T 為 G 的最小生成樹。 最小生成樹其實是最小權重生成樹的簡稱。 一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的每一连通分量同样有最小生成树，它们的并被称为最小生成森林。 以有線電視電纜的架設為例，若只能沿著街道佈線，則以街道為邊，而路口為頂點，其中必然有一最小生成樹能使佈線成本最低。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Minimum_spanning_tree.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.cs.sunysb.edu/~algorith/files/minimum-spanning-tree.shtml http://www.cs.jhu.edu/~jason/papers/eisner.mst-tutorial.pdf https://web.archive.org/web/20100317031339/http:/www.codeplex.com/quickgraph http://citeseer.ist.psu.edu/nesetril00otakar.html http://www.boost.org/libs/graph/doc/table_of_contents.html |
| dbo:wikiPageID | 41795 (xsd:integer) |
| dbo:wikiPageLength | 44596 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123166618 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Prim's_algorithm dbr:Electrical_grid dbr:Natural_language_processing dbr:Parsing dbr:Bernard_Chazelle dbr:Arborescence_(graph_theory) dbc:Spanning_tree dbr:Reverse-delete_algorithm dbr:Riemann_zeta_function dbr:Cycle_(graph_theory) dbr:Vojtěch_Jarník dbr:Decision_problem dbr:Decision_tree dbr:Degree-constrained_spanning_tree dbr:Introduction_to_Algorithms dbr:J._Michael_Steele dbr:Reductio_ad_absurdum dbr:Thomas_H._Cormen dbr:Complete_graph dbr:Computer_network dbr:Conditional_random_field dbr:Connected_graph dbr:Matching_(graph_theory) dbr:Maximum_flow_problem dbr:Gene_expression dbr:Telecommunications_network dbr:Circuit_design dbr:Clifford_Stein dbr:Glossary_of_graph_theory dbr:Moravia dbr:NP-hard dbr:Apéry's_constant dbr:Cluster_analysis dbr:Computer_vision dbr:Feature_extraction dbr:Kruskal's_algorithm dbr:P_(complexity) dbr:Parallel_algorithm dbr:Path_(graph_theory) dbr:Spanning_tree dbr:Steiner_tree dbr:Central_limit_theorem dbr:Transport_network dbr:Triangle_inequality dbr:Widest_path_problem dbr:Distributed_computing dbr:Distributed_minimum_spanning_tree dbr:K-minimum_spanning_tree dbr:Minimum_spanning_tree-based_segmentation dbc:Polynomial-time_problems dbr:Cut_(graph_theory) dbr:Edsger_W._Dijkstra dbr:Euclidean_minimum_spanning_tree dbr:Extended_real_number_line dbr:Finite_impulse_response dbr:Broadcasting_(networking) dbr:Otakar_Borůvka dbr:Directed_graph dbr:Handwriting_recognition dbr:Process_control dbr:Proof_by_contradiction dbr:Rectilinear_minimum_spanning_tree dbr:Jaroslav_Nešetřil dbr:Taxonomy_(general) dbr:Ackermann_function dbr:Charles_E._Leiserson dbr:Alan_M._Frieze dbr:Big_O_notation dbr:Svante_Janson dbr:Ecotoxicology dbr:Hierarchical_clustering dbr:Regionalisation dbr:Single-linkage_clustering dbr:Borůvka's_algorithm dbr:Connected_component_(graph_theory) dbr:Greedy_algorithm dbr:Graph_contraction dbr:Image_segmentation dbr:Minimum_bottleneck_spanning_tree dbr:Brute-force_search dbr:Capacitated_minimum_spanning_tree dbr:Christofides_algorithm dbr:Vertex_(graph_theory) dbr:Expected_linear_time_MST_algorithm dbr:External_sorting dbr:FP_(complexity) dbr:Image_registration dbr:Robert_C._Prim dbr:Water_supply_network dbr:Observability dbr:NP-Complete dbr:Vijaya_Ramachandran dbr:Soft_heap dbr:Chu–Liu/Edmonds_algorithm dbr:Traveling_salesman_problem dbr:Rectilinear_distance dbr:Ronald_L._Rivest dbr:File:Minimum_spanning_tree.svg dbr:File:Msp-the-cut-correct.svg dbr:File:Multiple_minimum_spanning_trees.svg dbr:Seth_Pettie |
| dbp:wikiPageUsesTemplate | dbt:Center dbt:Citation_needed dbt:Commons_category dbt:Further dbt:Harvtxt dbt:Math dbt:Mvar dbt:Not_a_typo dbt:Reflist dbt:See_also dbt:Sfrac dbt:Short_description dbt:Sub dbt:Sup dbt:Use_American_English dbt:Isbn dbt:Regular_polygon_minimum_spanning_tree.svg |
| dct:subject | dbc:Spanning_tree dbc:Polynomial-time_problems |
| gold:hypernym | dbr:Tree |
| rdf:type | owl:Thing yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 dbo:Plant yago:State100024720 yago:WikicatPolynomial-timeProblems |
| rdfs:comment | Die MST-Heuristik (MST steht für minimum spanning tree bzw. minimaler Spannbaum) dient dazu, das metrische Problem des Handlungsreisenden (TSP) zu approximieren. Dabei geht man wie folgt vor: 1. * Erzeuge einen minimalen Spannbaum für den zugrundeliegenden ungerichteten Graphen 2. * Verdopple jede Kante im resultierenden Spannbaum, was zu einem eulerschen Graphen führt 3. * Wähle einen beliebigen Startknoten und folge den Kanten des verdoppelten Spannbaums im Sinne eines Eulerkreises. Bereits besuchte Knoten werden dabei durch die direkte Kante zum folgenden Knoten übersprungen, sofern es sich nicht um den letzten Knoten des Kreises handelt. (de) Nella teoria dei grafi, dato un grafo con archi pesati, l'albero ricoprente minimo o albero di copertura di costo minimo (minimum spanning tree, MST) è un albero ricoprente nel quale sommando i pesi degli archi si ottiene un valore minimo. (it) Minimalne drzewo rozpinające (ang. MST, minimum spanning tree) – drzewo rozpinające danego grafu o najmniejszej z możliwych wag, tj. takie, że nie istnieje dla tego grafu inne drzewo rozpinające o mniejszej sumie wag krawędzi. (pl) Мінімальне кістякове дерево у зв'язаному, зваженому, неорієнтованому графі — це кістяк цього графу, що має мінімальну можливу вагу, де під вагою дерева розуміється сума ваг його ребер. (uk) En sammanhängande, oriktad graf kan delas in i ett uppspännande träd, där grafens alla noder finns representerade utan några cykler. Detta görs genom att en delmängd av de ursprungliga kanterna väljs ut på ett sådant sätt att grafen fortfarande är sammanhängande och ett träd. Detta kan göras på flera olika sätt, men om den ursprungliga grafen dessutom är viktad, det vill säga att varje kant har givits en vikt, kan man även definiera trädens vikt som summan av dess viktade kanter. Då är ett minimalt uppspännande träd det uppspännande träd till grafen vars vikt är minimerad (mindre eller lika med vikten för alla andra uppspännande träd till grafen). (sv) Минимальное остовное дерево (или минимальное покрывающее дерево) в (неориентированном) связном взвешенном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер. (ru) 最小生成树是一副连通加权无向图中一棵权值最小的生成树。 在一給定的無向圖 中， 代表連接頂點 u 與頂點 v 的邊（即 ），而 代表此邊的權重，若存在 T 為 E 的子集（即 ）且 (V, T) 為樹，使得 的 w(T) 最小，則此 T 為 G 的最小生成樹。 最小生成樹其實是最小權重生成樹的簡稱。 一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的每一连通分量同样有最小生成树，它们的并被称为最小生成森林。 以有線電視電纜的架設為例，若只能沿著街道佈線，則以街道為邊，而路口為頂點，其中必然有一最小生成樹能使佈線成本最低。 (zh) Στη Θεωρία Γράφων και στην Επιστήμη Υπολογιστών, συχνά συναντάται το πρόβλημα της εύρεσης του ελάχιστου διασυνδετικού ή γεννητικού δέντρου ενός γράφου με βάρη στις ακμές. Το πρόβλημα συνίσταται στην εύρεση ενός δέντρου με κορυφές αυτές του γράφου και ακμές ένα υποσύνολο των ακμών του γράφου, τέτοιο ώστε το άθροισμα των βαρών τους να είναι το ελάχιστο δυνατό. (el) Donita koneksa, sendirekta grafeo, de tiu grafeo estas subgrafeo kiu estas arbo kaj kunkonektas ĉiujn verticojn. Sola grafeo povas havi multajn malsamajn branĉantajn arbojn. On povas ankaŭ asigni pezon al ĉiu latero, kiu estas nombro prezentanta kiel malfavora ĝi estas, kaj uzi tion por asigni pezon al branĉanta arbo per komputi la sumon de la pezoj de la branĉoj en tiu branĉanta arbo. Minimuma branĉanta arbo aŭ minimum-peza branĉanta arbo estas tiam branĉanta arbo kun pezo malpli ol aŭ egala al la pezo de ĉiu alia branĉanta arbo. Pli ĝenerale, iu ajn sendirekta grafeo havas minimuman branĉantan arbaron. (eo) Dado un grafo conexo y no dirigido, un árbol recubridor, árbol de cobertura o árbol de expansión de ese grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc.; y se usa para asignar un peso total al árbol recubridor mínimo computando la suma de todos los pesos de las aristas del árbol en cuestión. Un árbol recubridor mínimo o un árbol de expansión mínimo es un árbol recubridor que pesa menos o igual que todos los otros árboles recubridores.Todo grafo tiene un bosque recubridor mínimo. (es) A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components. (en) En théorie des graphes, étant donné un graphe non orienté connexe dont les arêtes sont pondérées, un arbre couvrant de poids minimal (ACM) de ce graphe est un arbre couvrant (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale (c'est-à-dire de poids inférieur ou égal à celui de tous les autres arbres couvrants du graphe). L'arbre couvrant de poids minimal est aussi connu sous certains autres noms, tel qu’arbre couvrant minimum ou encore arbre sous-tendant minimum[réf. nécessaire]. (fr) Pohon rentang minimum atau pohon rentang berbobot minimum (bahasa Inggris: minimum spanning tree, MST) adalah himpunan bagian dari himpunan garis-garis (edge) suatu graf berbobot tak berarah yang menghubungkan semua titik tanpa membentuk siklus dan dengan total bobot minimum. Dengan kata lain, ini adalah yang total bobotnya minimum. (in) De minimaal opspannende boom van een verbonden, gewogen graaf is de verbonden subgraaf daarvan met het kleinste totale gewicht. Deze kleinste subgraaf is altijd een boom, dat wil zeggen een graaf zonder cycli. Een algoritme om de minimaal opspannende boom te vinden is het algoritme van Prim: Hier een ander algoritme voor is Kruskals algoritme, maar er zijn er meer. Een gegeven graaf kan in het algemeen verschillende minimaal opspannende bomen hebben. Alleen wanneer alle zijden van de graaf een verschillend gewicht hebben is er een unieke, minimaal opspannende boom. (nl) Dado um grafo não orientado , uma árvore de extensão deste grafo é um subgrafo o qual é uma árvore que conecta todos os vértices. Um único grafo pode ter diferentes árvores de extensão. Nós podemos assinalar um peso a cada aresta, que é um número que representa quão desfavorável ela é, e atribuir um peso a árvore de extensão calculado pela soma dos pesos das arestas que a compõem. Uma árvore de extensão mínima (também conhecida como árvore de extensão de peso mínimo ou árvore geradora mínima) é então uma árvore de extensão com peso menor ou igual a cada uma das outras árvores de extensão possíveis. Generalizando mais, qualquer grafo não direcional (não necessariamente conectado) tem uma floresta de árvores mínimas, que é uma união de árvores de extensão mínimas de cada uma de suas . (pt) |
| rdfs:label | MST-Heuristik (de) Ελάχιστο γεννητικό δέντρο (el) Minimuma generanta arbo (eo) Árbol recubridor mínimo (es) Pohon rentang minimum (in) Albero ricoprente minimo (it) Arbre couvrant de poids minimal (fr) Minimum spanning tree (en) Minimaal opspannende boom (nl) Minimalne drzewo rozpinające (pl) Árvore de extensão mínima (pt) Minimalt uppspännande träd (sv) Минимальное остовное дерево (ru) 最小生成树 (zh) Мінімальне кістякове дерево (uk) |
| rdfs:seeAlso | dbr:Decision_tree_model |
| owl:sameAs | freebase:Minimum spanning tree yago-res:Minimum spanning tree wikidata:Minimum spanning tree wikidata:Minimum spanning tree dbpedia-cy:Minimum spanning tree dbpedia-de:Minimum spanning tree dbpedia-el:Minimum spanning tree dbpedia-eo:Minimum spanning tree dbpedia-es:Minimum spanning tree dbpedia-fa:Minimum spanning tree dbpedia-fr:Minimum spanning tree dbpedia-he:Minimum spanning tree dbpedia-hr:Minimum spanning tree dbpedia-hu:Minimum spanning tree http://hy.dbpedia.org/resource/Նվազագույն_ակնթարթային_ծառ dbpedia-id:Minimum spanning tree dbpedia-it:Minimum spanning tree dbpedia-nl:Minimum spanning tree dbpedia-pl:Minimum spanning tree dbpedia-pt:Minimum spanning tree dbpedia-ro:Minimum spanning tree dbpedia-ru:Minimum spanning tree dbpedia-simple:Minimum spanning tree dbpedia-sk:Minimum spanning tree dbpedia-sl:Minimum spanning tree dbpedia-sr:Minimum spanning tree dbpedia-sv:Minimum spanning tree dbpedia-th:Minimum spanning tree dbpedia-uk:Minimum spanning tree http://ur.dbpedia.org/resource/Minimum_spanning_tree dbpedia-vi:Minimum spanning tree dbpedia-zh:Minimum spanning tree https://global.dbpedia.org/id/ZvQJ |
| prov:wasDerivedFrom | wikipedia-en:Minimum_spanning_tree?oldid=1123166618&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Minimum_spanning_tree.svg wiki-commons:Special:FilePath/Msp-the-cut-correct.svg wiki-commons:Special:FilePath/Multiple_minimum_spanning_trees.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Minimum_spanning_tree |
| is dbo:wikiPageDisambiguates of | dbr:Spanning_tree_(disambiguation) dbr:MST |
| is dbo:wikiPageRedirects of | dbr:Minimum_weight_spanning_tree dbr:Applications_of_minimum_spanning_trees dbr:Applications_of_the_minimum_spanning_tree_problem dbr:Algorithms_for_finding_minimum_spanning_trees dbr:Parallel_algorithms_for_the_minimum_spanning_tree_problem dbr:Minimum_Spanning_Tree dbr:Min_spanning_tree dbr:Minimal_spanning_tree dbr:Minimum_Weight_Spanning_Tree dbr:Minimum_cost_spanning_tree dbr:Minimum_k-edge-connected_spanning_network_problem dbr:Minimum_k-node-connected_spanning_network_problem dbr:Minimum_spanning_forest dbr:Minimum_spanning_tree_problem dbr:Minimum_spanning_trees dbr:Minimum_weight_spanning_forest dbr:Shortest_spanning_tree dbr:Spanning_tree_algorithm dbr:Spanning_tree_problem |
| is dbo:wikiPageWikiLink of | dbr:Prim's_algorithm dbr:Proximity_problems dbr:Quantum_complexity_theory dbr:List_of_algorithms dbr:MENTOR_routing_algorithm dbr:Minimum_weight_spanning_tree dbr:Pathfinder_network dbr:Bernard_Chazelle dbr:David_Eppstein dbr:David_Karger dbr:List_of_graph_theory_topics dbr:List_of_important_publications_in_theoretical_computer_science dbr:Reverse-delete_algorithm dbr:Vojtěch_Jarník dbr:Decision_tree_model dbr:Independence_Theory_in_Combinatorics dbr:Pseudoforest dbr:Vickrey–Clarke–Groves_mechanism dbr:Geometric_graph_theory dbr:Geometric_spanner dbr:Rectilinear_Steiner_tree dbr:Geometry dbr:Graph-tool dbr:Dan_Willard dbr:Applications_of_minimum_spanning_trees dbr:Applications_of_the_minimum_spanning_tree_problem dbr:Léon_Croizat dbr:Steiner_point_(computational_geometry) dbr:Steiner_tree_problem dbr:Combinatorial_optimization dbr:Commercial_vehicle_operation dbr:Component_(graph_theory) dbr:Kruskal's_algorithm dbr:Priority_queue dbr:Random_minimum_spanning_tree dbr:Spanning_tree dbr:Spanning_tree_(disambiguation) dbr:Matroid_minor dbr:Maximum_agreement_subtree_problem dbr:Stock_correlation_network dbr:Travelling_salesman_problem dbr:Widest_path_problem dbr:Disparity_filter_algorithm_of_weighted_network dbr:Distributed_minimum_spanning_tree dbr:Galactic_algorithm dbr:Karger's_algorithm dbr:Leader_election dbr:Minimum_spanning_tree-based_segmentation dbr:Algorithms_for_finding_minimum_spanning_trees dbr:D-ary_heap dbr:Dual_graph dbr:Euclidean_minimum_spanning_tree dbr:Otakar_Borůvka dbr:Parallel_algorithms_for_the_minimum_spanning_tree_problem dbr:Parametric_search dbr:Dijkstra_Prize dbr:Edmonds'_algorithm dbr:Flow_cytometry_bioinformatics dbr:Godfried_Toussaint dbr:Graph_theory dbr:Graphic_matroid dbr:Kinetic_Euclidean_minimum_spanning_tree dbr:Kinetic_minimum_spanning_tree dbr:List_of_NP-complete_problems dbr:Rectilinear_minimum_spanning_tree dbr:Asymptotically_optimal_algorithm dbr:AF-heap dbr:Ackermann_function dbr:K-set_(geometry) dbr:Single-linkage_clustering dbr:Dijkstra's_algorithm dbr:Disjoint-set_data_structure dbr:Borůvka's_algorithm dbr:Spanning_Tree_Protocol dbr:Greedoid dbr:Greedy_algorithm dbr:Greedy_geometric_spanner dbr:Minimum_bottleneck_spanning_tree dbr:Open_energy_system_databases dbr:Cartesian_tree dbr:Christofides_algorithm dbr:Kirchhoff's_theorem dbr:MSP dbr:MST dbr:Multiple_Spanning_Tree_Protocol dbr:Shortest-path_tree dbr:Nearest-neighbor_chain_algorithm dbr:Shortest-path_graph dbr:Trajectory_inference dbr:Expected_linear_time_MST_algorithm dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:List_of_unsolved_problems_in_computer_science dbr:Robert_C._Prim dbr:Wisdom_of_the_crowd dbr:NP-completeness dbr:Multilocus_sequence_typing dbr:Solver dbr:Soft_heap dbr:Spatial_network dbr:Panbiogeography dbr:Overfitting dbr:Parallel_algorithms_for_minimum_spanning_trees dbr:Parallel_coordinates dbr:Parallel_external_memory dbr:Minimum_Spanning_Tree dbr:Min_spanning_tree dbr:Minimal_spanning_tree dbr:Minimum_Weight_Spanning_Tree dbr:Minimum_cost_spanning_tree dbr:Minimum_k-edge-connected_spanning_network_problem dbr:Minimum_k-node-connected_spanning_network_problem dbr:Minimum_spanning_forest dbr:Minimum_spanning_tree_problem dbr:Minimum_spanning_trees dbr:Minimum_weight_spanning_forest dbr:Shortest_spanning_tree dbr:Spanning_tree_algorithm dbr:Spanning_tree_problem |
| is foaf:primaryTopic of | wikipedia-en:Minimum_spanning_tree |
