Minimum spanning tree
http://dbpedia.org/resource/Minimum_spanning_tree an entity of type: Thing
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
Мінімальне кістякове дерево у зв'язаному, зваженому, неорієнтованому графі — це кістяк цього графу, що має мінімальну можливу вагу, де під вагою дерева розуміється сума ваг його ребер.
rdf:langString
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).
rdf:langString
Минимальное остовное дерево (или минимальное покрывающее дерево) в (неориентированном) связном взвешенном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
rdf:langString
最小生成树是一副连通加权无向图中一棵权值最小的生成树。 在一給定的無向圖 中， 代表連接頂點 u 與頂點 v 的邊（即 ），而 代表此邊的權重，若存在 T 為 E 的子集（即 ）且 (V, T) 為樹，使得 的 w(T) 最小，則此 T 為 G 的最小生成樹。 最小生成樹其實是最小權重生成樹的簡稱。 一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的每一连通分量同样有最小生成树，它们的并被称为最小生成森林。 以有線電視電纜的架設為例，若只能沿著街道佈線，則以街道為邊，而路口為頂點，其中必然有一最小生成樹能使佈線成本最低。
rdf:langString
Στη Θεωρία Γράφων και στην Επιστήμη Υπολογιστών, συχνά συναντάται το πρόβλημα της εύρεσης του ελάχιστου διασυνδετικού ή γεννητικού δέντρου ενός γράφου με βάρη στις ακμές. Το πρόβλημα συνίσταται στην εύρεση ενός δέντρου με κορυφές αυτές του γράφου και ακμές ένα υποσύνολο των ακμών του γράφου, τέτοιο ώστε το άθροισμα των βαρών τους να είναι το ελάχιστο δυνατό.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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].
rdf:langString
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.
rdf:langString
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.
rdf:langString
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 .
rdf:langString
rdf:langString
MST-Heuristik
rdf:langString
Ελάχιστο γεννητικό δέντρο
rdf:langString
Minimuma generanta arbo
rdf:langString
Árbol recubridor mínimo
rdf:langString
Pohon rentang minimum
rdf:langString
Albero ricoprente minimo
rdf:langString
Arbre couvrant de poids minimal
rdf:langString
Minimum spanning tree
rdf:langString
Minimaal opspannende boom
rdf:langString
Minimalne drzewo rozpinające
rdf:langString
Árvore de extensão mínima
rdf:langString
Minimalt uppspännande träd
rdf:langString
Минимальное остовное дерево
rdf:langString
最小生成树
rdf:langString
Мінімальне кістякове дерево
xsd:integer
41795
xsd:integer
1123166618
rdf:langString
Στη Θεωρία Γράφων και στην Επιστήμη Υπολογιστών, συχνά συναντάται το πρόβλημα της εύρεσης του ελάχιστου διασυνδετικού ή γεννητικού δέντρου ενός γράφου με βάρη στις ακμές. Το πρόβλημα συνίσταται στην εύρεση ενός δέντρου με κορυφές αυτές του γράφου και ακμές ένα υποσύνολο των ακμών του γράφου, τέτοιο ώστε το άθροισμα των βαρών τους να είναι το ελάχιστο δυνατό. Αλλιώς, το πρόβλημα μπορεί να διατυπωθεί ως πρόβλημα για την εύρεση ενός υποσυνόλου των ακμών του γραφήματος, ώστε το νέο υπογράφημα που προκύπτει να είναι συνεκτικό και το άθροισμα των βαρών των ακμών του να είναι το ελάχιστο δυνατό. Εδώ, δεν είναι σαφές αν η λύση του προβλήματος αποτελεί δέντρο. Όμως, αν το υπογράφημα που προκύπτει ως λύση έχει κύκλο, τότε αφαιρώντας μια ακμή από τον κύκλο (την βαρύτερη) το υπογράφημα παραμένει συνεκτικό και το άθροισμα των βαρών των ακμών του είναι ακόμη μικρότερο (αφού έχουμε αφαιρέσει μια ακμή). Επομένως, δεν γίνεται η λύση του προβλήματος να περιέχει κύκλο, γιατί τότε δεν θα έχει το ελάχιστο δυνατό άθροισμα βαρών. Και αφού επιπλέον το υπογράφημα πρέπει να είναι συνεκτικό, εξορισμού προκύπτει ότι η λύση θα είναι ένα δέντρο.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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).
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
Мінімальне кістякове дерево у зв'язаному, зваженому, неорієнтованому графі — це кістяк цього графу, що має мінімальну можливу вагу, де під вагою дерева розуміється сума ваг його ребер.
rdf:langString
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).
rdf:langString
Минимальное остовное дерево (или минимальное покрывающее дерево) в (неориентированном) связном взвешенном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
rdf:langString
最小生成树是一副连通加权无向图中一棵权值最小的生成树。 在一給定的無向圖 中， 代表連接頂點 u 與頂點 v 的邊（即 ），而 代表此邊的權重，若存在 T 為 E 的子集（即 ）且 (V, T) 為樹，使得 的 w(T) 最小，則此 T 為 G 的最小生成樹。 最小生成樹其實是最小權重生成樹的簡稱。 一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的每一连通分量同样有最小生成树，它们的并被称为最小生成森林。 以有線電視電纜的架設為例，若只能沿著街道佈線，則以街道為邊，而路口為頂點，其中必然有一最小生成樹能使佈線成本最低。
xsd:nonNegativeInteger
44596
