This HTML5 document contains 363 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-elhttp://el.dbpedia.org/resource/
n54http://citeseer.ist.psu.edu/
dbthttp://dbpedia.org/resource/Template:
dbpedia-cyhttp://cy.dbpedia.org/resource/
dbpedia-svhttp://sv.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
n6http://dbpedia.org/resource/Chu–Liu/
n16http://hy.dbpedia.org/resource/
dbrhttp://dbpedia.org/resource/
n51http://www.boost.org/libs/graph/doc/
dbpedia-hrhttp://hr.dbpedia.org/resource/
dbpedia-hehttp://he.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
n20http://commons.wikimedia.org/wiki/Special:FilePath/
dcthttp://purl.org/dc/terms/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n25http://dbpedia.org/resource/File:
dbphttp://dbpedia.org/property/
dbpedia-eohttp://eo.dbpedia.org/resource/
n29http://ur.dbpedia.org/resource/
n42http://www.cs.jhu.edu/~jason/papers/
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-ukhttp://uk.dbpedia.org/resource/
dbpedia-idhttp://id.dbpedia.org/resource/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbohttp://dbpedia.org/ontology/
dbpedia-vihttp://vi.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
n22http://www.cs.sunysb.edu/~algorith/files/
dbpedia-huhttp://hu.dbpedia.org/resource/
dbpedia-skhttp://sk.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-thhttp://th.dbpedia.org/resource/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbpedia-rohttp://ro.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbpedia-nlhttp://nl.dbpedia.org/resource/
n53https://global.dbpedia.org/id/
yago-reshttp://yago-knowledge.org/resource/
dbpedia-slhttp://sl.dbpedia.org/resource/
dbpedia-ithttp://it.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
foafhttp://xmlns.com/foaf/0.1/
n35https://web.archive.org/web/20100317031339/http:/www.codeplex.com/
dbpedia-simplehttp://simple.dbpedia.org/resource/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbr:Prim's_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Proximity_problems
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Quantum_complexity_theory
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:List_of_algorithms
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:MENTOR_routing_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimum_weight_spanning_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Pathfinder_network
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Bernard_Chazelle
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:David_Eppstein
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:David_Karger
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:List_of_graph_theory_topics
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:List_of_important_publications_in_theoretical_computer_science
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Reverse-delete_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Vojtěch_Jarník
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Decision_tree_model
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Independence_Theory_in_Combinatorics
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Pseudoforest
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Vickrey–Clarke–Groves_mechanism
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Geometric_graph_theory
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Geometric_spanner
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Rectilinear_Steiner_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Geometry
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Graph-tool
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Dan_Willard
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Applications_of_minimum_spanning_trees
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Applications_of_the_minimum_spanning_tree_problem
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Léon_Croizat
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Steiner_point_(computational_geometry)
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Steiner_tree_problem
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Combinatorial_optimization
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Commercial_vehicle_operation
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Component_(graph_theory)
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Kruskal's_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Priority_queue
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Random_minimum_spanning_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Spanning_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Spanning_tree_(disambiguation)
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageDisambiguates
dbr:Minimum_spanning_tree
Subject Item
dbr:Matroid_minor
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Maximum_agreement_subtree_problem
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Stock_correlation_network
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Travelling_salesman_problem
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Widest_path_problem
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Disparity_filter_algorithm_of_weighted_network
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Distributed_minimum_spanning_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Galactic_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Karger's_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Leader_election
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimum_spanning_tree-based_segmentation
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Algorithms_for_finding_minimum_spanning_trees
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:D-ary_heap
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Dual_graph
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Euclidean_minimum_spanning_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Otakar_Borůvka
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Parallel_algorithms_for_the_minimum_spanning_tree_problem
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Parametric_search
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Dijkstra_Prize
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Edmonds'_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Flow_cytometry_bioinformatics
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Godfried_Toussaint
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Graph_theory
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Graphic_matroid
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Kinetic_Euclidean_minimum_spanning_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Kinetic_minimum_spanning_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:List_of_NP-complete_problems
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Rectilinear_minimum_spanning_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Asymptotically_optimal_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:AF-heap
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Ackermann_function
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:K-set_(geometry)
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Single-linkage_clustering
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Dijkstra's_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Disjoint-set_data_structure
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Borůvka's_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Spanning_Tree_Protocol
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Greedoid
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Greedy_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Greedy_geometric_spanner
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimum_bottleneck_spanning_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimum_spanning_tree
rdf:type
yago:Attribute100024264 yago:Difficulty114408086 yago:State100024720 dbo:Plant yago:Condition113920835 owl:Thing yago:Problem114410605 yago:Abstraction100002137 yago:WikicatPolynomial-timeProblems
rdfs:label
最小生成树 Albero ricoprente minimo Минимальное остовное дерево Árvore de extensão mínima MST-Heuristik Minimalne drzewo rozpinające Minimaal opspannende boom Мінімальне кістякове дерево Ελάχιστο γεννητικό δέντρο Árbol recubridor mínimo Minimum spanning tree Arbre couvrant de poids minimal Minimalt uppspännande träd Pohon rentang minimum Minimuma generanta arbo
rdfs:comment
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 . 最小生成树是一副连通加权无向图中一棵权值最小的生成树。 在一給定的無向圖 中, 代表連接頂點 u 與頂點 v 的邊(即 ),而 代表此邊的權重,若存在 T 為 E 的子集(即 )且 (V, T) 為樹,使得 的 w(T) 最小,則此 T 為 G 的最小生成樹。 最小生成樹其實是最小權重生成樹的簡稱。 一个连通图可能有多个生成树。当图中的边具有权值时,总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言,对于非连通无向图来说,它的每一连通分量同样有最小生成树,它们的并被称为最小生成森林。 以有線電視電纜的架設為例,若只能沿著街道佈線,則以街道為邊,而路口為頂點,其中必然有一最小生成樹能使佈線成本最低。 Στη Θεωρία Γράφων και στην Επιστήμη Υπολογιστών, συχνά συναντάται το πρόβλημα της εύρεσης του ελάχιστου διασυνδετικού ή γεννητικού δέντρου ενός γράφου με βάρη στις ακμές. Το πρόβλημα συνίσταται στην εύρεση ενός δέντρου με κορυφές αυτές του γράφου και ακμές ένα υποσύνολο των ακμών του γράφου, τέτοιο ώστε το άθροισμα των βαρών τους να είναι το ελάχιστο δυνατό. 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. 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. 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 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). 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. 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. Мінімальне кістякове дерево у зв'язаному, зваженому, неорієнтованому графі — це кістяк цього графу, що має мінімальну можливу вагу, де під вагою дерева розуміється сума ваг його ребер. 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. 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]. 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. 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. Минимальное остовное дерево (или минимальное покрывающее дерево) в (неориентированном) связном взвешенном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
rdfs:seeAlso
dbr:Decision_tree_model
foaf:depiction
n20:Minimum_spanning_tree.svg n20:Multiple_minimum_spanning_trees.svg n20:Msp-the-cut-correct.svg
dct:subject
dbc:Polynomial-time_problems dbc:Spanning_tree
dbo:wikiPageID
41795
dbo:wikiPageRevisionID
1123166618
dbo:wikiPageWikiLink
dbr:Regionalisation n6:Edmonds_algorithm dbr:Proof_by_contradiction dbr:Glossary_of_graph_theory dbr:Conditional_random_field dbr:Connected_component_(graph_theory) dbr:Vijaya_Ramachandran dbr:Handwriting_recognition dbc:Polynomial-time_problems dbr:Directed_graph dbr:Euclidean_minimum_spanning_tree dbr:Otakar_Borůvka dbr:Widest_path_problem dbr:Feature_extraction dbr:Christofides_algorithm dbr:Svante_Janson dbr:Finite_impulse_response dbr:Observability dbr:Alan_M._Frieze dbr:P_(complexity) dbr:NP-hard dbr:Distributed_minimum_spanning_tree dbr:Parsing dbr:Bernard_Chazelle dbr:Jaroslav_Nešetřil dbr:Apéry's_constant dbr:Brute-force_search dbr:Reverse-delete_algorithm dbr:Cycle_(graph_theory) dbr:Computer_vision n25:Msp-the-cut-correct.svg n25:Multiple_minimum_spanning_trees.svg dbr:Vojtěch_Jarník dbr:Spanning_tree dbr:Edsger_W._Dijkstra dbr:Ecotoxicology dbr:Gene_expression dbr:Degree-constrained_spanning_tree dbr:Natural_language_processing dbr:Cut_(graph_theory) dbr:Vertex_(graph_theory) n25:Minimum_spanning_tree.svg dbr:Triangle_inequality dbr:Parallel_algorithm dbr:Arborescence_(graph_theory) dbr:NP-Complete dbr:Minimum_bottleneck_spanning_tree dbr:Hierarchical_clustering dbc:Spanning_tree dbr:K-minimum_spanning_tree dbr:Image_segmentation dbr:Matching_(graph_theory) dbr:Rectilinear_distance dbr:Circuit_design dbr:FP_(complexity) dbr:Seth_Pettie dbr:Rectilinear_minimum_spanning_tree dbr:Riemann_zeta_function dbr:Traveling_salesman_problem dbr:Introduction_to_Algorithms dbr:Connected_graph dbr:Graph_contraction dbr:Ackermann_function dbr:Soft_heap dbr:Borůvka's_algorithm dbr:Expected_linear_time_MST_algorithm dbr:Taxonomy_(general) dbr:Capacitated_minimum_spanning_tree dbr:Big_O_notation dbr:Maximum_flow_problem dbr:Charles_E._Leiserson dbr:Prim's_algorithm dbr:Extended_real_number_line dbr:Transport_network dbr:Clifford_Stein dbr:Electrical_grid dbr:Minimum_spanning_tree-based_segmentation dbr:Path_(graph_theory) dbr:Computer_network dbr:Cluster_analysis dbr:Image_registration dbr:Broadcasting_(networking) dbr:Complete_graph dbr:Water_supply_network dbr:Steiner_tree dbr:J._Michael_Steele dbr:Single-linkage_clustering dbr:Decision_problem dbr:External_sorting dbr:Greedy_algorithm dbr:Decision_tree dbr:Kruskal's_algorithm dbr:Telecommunications_network dbr:Moravia dbr:Central_limit_theorem dbr:Robert_C._Prim dbr:Thomas_H._Cormen dbr:Reductio_ad_absurdum dbr:Process_control dbr:Ronald_L._Rivest dbr:Distributed_computing
dbo:wikiPageExternalLink
n22:minimum-spanning-tree.shtml n35:quickgraph n42:eisner.mst-tutorial.pdf n51:table_of_contents.html n54:nesetril00otakar.html
owl:sameAs
dbpedia-sk:Minimálna_kostra_grafu dbpedia-nl:Minimaal_opspannende_boom dbpedia-cy:Coeden_rhychwantu_leiaf dbpedia-hr:Minimalno_razapinjuće_stablo n16:Նվազագույն_ակնթարթային_ծառ yago-res:Minimum_spanning_tree wikidata:Q240464 wikidata:Q15833247 dbpedia-id:Pohon_rentang_minimum dbpedia-hu:Minimális_feszítőfa dbpedia-pl:Minimalne_drzewo_rozpinające dbpedia-simple:Minimum_spanning_tree dbpedia-es:Árbol_recubridor_mínimo n29:Minimum_spanning_tree dbpedia-eo:Minimuma_generanta_arbo dbpedia-uk:Мінімальне_кістякове_дерево dbpedia-de:MST-Heuristik dbpedia-sl:Minimalno_vpeto_drevo dbpedia-pt:Árvore_de_extensão_mínima freebase:m.0bh75 dbpedia-he:עץ_פורש_מינימלי dbpedia-el:Ελάχιστο_γεννητικό_δέντρο dbpedia-sv:Minimalt_uppspännande_träd dbpedia-th:ต้นไม้แบบทอดข้ามน้อยสุด dbpedia-sr:Разапињуће_стабло_минималног_степена dbpedia-ru:Минимальное_остовное_дерево dbpedia-fr:Arbre_couvrant_de_poids_minimal dbpedia-ro:Arbore_minim_de_acoperire dbpedia-fa:درخت_پوشای_کمینه dbpedia-zh:最小生成树 dbpedia-vi:Cây_bao_trùm_nhỏ_nhất dbpedia-it:Albero_ricoprente_minimo n53:ZvQJ
dbp:wikiPageUsesTemplate
dbt:Commons_category dbt:Short_description dbt:Harvtxt dbt:See_also dbt:Mvar dbt:Sub dbt:Further dbt:Sup dbt:Use_American_English dbt:Citation_needed dbt:Regular_polygon_minimum_spanning_tree.svg dbt:Not_a_typo dbt:Math dbt:Isbn dbt:Reflist dbt:Center dbt:Sfrac
dbo:thumbnail
n20:Minimum_spanning_tree.svg?width=300
dbo:abstract
Мінімальне кістякове дерево у зв'язаному, зваженому, неорієнтованому графі — це кістяк цього графу, що має мінімальну можливу вагу, де під вагою дерева розуміється сума ваг його ребер. 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. 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. 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. 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. 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. 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). 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. Στη Θεωρία Γράφων και στην Επιστήμη Υπολογιστών, συχνά συναντάται το πρόβλημα της εύρεσης του ελάχιστου διασυνδετικού ή γεννητικού δέντρου ενός γράφου με βάρη στις ακμές. Το πρόβλημα συνίσταται στην εύρεση ενός δέντρου με κορυφές αυτές του γράφου και ακμές ένα υποσύνολο των ακμών του γράφου, τέτοιο ώστε το άθροισμα των βαρών τους να είναι το ελάχιστο δυνατό. Αλλιώς, το πρόβλημα μπορεί να διατυπωθεί ως πρόβλημα για την εύρεση ενός υποσυνόλου των ακμών του γραφήματος, ώστε το νέο υπογράφημα που προκύπτει να είναι συνεκτικό και το άθροισμα των βαρών των ακμών του να είναι το ελάχιστο δυνατό. Εδώ, δεν είναι σαφές αν η λύση του προβλήματος αποτελεί δέντρο. Όμως, αν το υπογράφημα που προκύπτει ως λύση έχει κύκλο, τότε αφαιρώντας μια ακμή από τον κύκλο (την βαρύτερη) το υπογράφημα παραμένει συνεκτικό και το άθροισμα των βαρών των ακμών του είναι ακόμη μικρότερο (αφού έχουμε αφαιρέσει μια ακμή). Επομένως, δεν γίνεται η λύση του προβλήματος να περιέχει κύκλο, γιατί τότε δεν θα έχει το ελάχιστο δυνατό άθροισμα βαρών. Και αφού επιπλέον το υπογράφημα πρέπει να είναι συνεκτικό, εξορισμού προκύπτει ότι η λύση θα είναι ένα δέντρο. 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. Минимальное остовное дерево (или минимальное покрывающее дерево) в (неориентированном) связном взвешенном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер. 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). 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. 最小生成树是一副连通加权无向图中一棵权值最小的生成树。 在一給定的無向圖 中, 代表連接頂點 u 與頂點 v 的邊(即 ),而 代表此邊的權重,若存在 T 為 E 的子集(即 )且 (V, T) 為樹,使得 的 w(T) 最小,則此 T 為 G 的最小生成樹。 最小生成樹其實是最小權重生成樹的簡稱。 一个连通图可能有多个生成树。当图中的边具有权值时,总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言,对于非连通无向图来说,它的每一连通分量同样有最小生成树,它们的并被称为最小生成森林。 以有線電視電纜的架設為例,若只能沿著街道佈線,則以街道為邊,而路口為頂點,其中必然有一最小生成樹能使佈線成本最低。 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.
gold:hypernym
dbr:Tree
prov:wasDerivedFrom
wikipedia-en:Minimum_spanning_tree?oldid=1123166618&ns=0
dbo:wikiPageLength
44596
foaf:isPrimaryTopicOf
wikipedia-en:Minimum_spanning_tree
Subject Item
dbr:Open_energy_system_databases
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Cartesian_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Christofides_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Kirchhoff's_theorem
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:MSP
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:MST
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageDisambiguates
dbr:Minimum_spanning_tree
Subject Item
dbr:Multiple_Spanning_Tree_Protocol
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Shortest-path_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Nearest-neighbor_chain_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Shortest-path_graph
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Trajectory_inference
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Expected_linear_time_MST_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:List_of_terms_relating_to_algorithms_and_data_structures
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:List_of_unsolved_problems_in_computer_science
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Robert_C._Prim
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Wisdom_of_the_crowd
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:NP-completeness
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Multilocus_sequence_typing
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Solver
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Soft_heap
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Spatial_network
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Panbiogeography
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Overfitting
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Parallel_algorithms_for_minimum_spanning_trees
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Parallel_coordinates
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Parallel_external_memory
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimum_Spanning_Tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Min_spanning_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimal_spanning_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimum_Weight_Spanning_Tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimum_cost_spanning_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimum_k-edge-connected_spanning_network_problem
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimum_k-node-connected_spanning_network_problem
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimum_spanning_forest
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimum_spanning_tree_problem
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimum_spanning_trees
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Minimum_weight_spanning_forest
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Shortest_spanning_tree
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Spanning_tree_algorithm
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
dbr:Spanning_tree_problem
dbo:wikiPageWikiLink
dbr:Minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Minimum_spanning_tree
Subject Item
wikipedia-en:Minimum_spanning_tree
foaf:primaryTopic
dbr:Minimum_spanning_tree