| dbo:abstract
|
- Borůvkův algoritmus je algoritmus pro nalezení minimální kostry v grafu, jehož hrany mají různé (prosté) a kladné ohodnocení. (cs)
- Der Algorithmus von Borůvka gilt als erster Algorithmus zum Auffinden minimaler Spannbäume in ungerichteten Graphen. Er wurde 1926 von dem tschechischen Mathematiker Otakar Borůvka beschrieben. Die beiden bekannteren Algorithmen zur Lösung dieses Problems sind der Algorithmus von Prim und der Algorithmus von Kruskal. In der Erstveröffentlichung dieser beiden Algorithmen wird Borůvka jeweils erwähnt. (de)
- Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph,or a minimum spanning forest in the case of a graph that is not connected. It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia.The algorithm was rediscovered by Choquet in 1938; again by , Łukasiewicz, , Steinhaus, and in 1951; and again by Georges Sollin in 1965. This algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature. The algorithm begins by finding the minimum-weight edge incident to each vertex of the graph, and adding all of those edges to the forest.Then, it repeats a similar process of finding the minimum-weight edge from each tree constructed so far to a different tree, and adding all of those edges to the forest.Each repetition of this process reduces the number of trees, within each connected component of the graph, to at most half of this former value,so after logarithmically many repetitions the process finishes. When it does, the set of edges it has added forms the minimum spanning forest. (en)
- El Algoritmo de Borůvka es un algoritmo para encontrar el árbol recubridor mínimo en un grafo ponderado en el que todos sus arcos tienen distinto peso. Fue publicado por primera vez en 1926 por como un método eficiente para construir la red eléctrica de Moravia. El algoritmo fue redescubierto por Choquet en 1938; de nuevo por , Łukasiewicz, , Steinhaus y en 1951; y de nuevo por a principio de la década de 1960. Debido a que fue el único de ellos que era científico en computación, este algoritmo es frecuentemente llamado , especialmente en la literatura sobre computación paralela. (es)
- L'algorithme de Borůvka, est un algorithme de recherche de l'arbre couvrant de poids minimal dans un graphe pondéré. Il est aussi appelé algorithme de Sollin. (fr)
- L'algoritmo di Borůvka è un algoritmo per la ricerca di un albero ricoprente minimo in un grafo in cui il peso di ciascuna coppia di archi sia distinto. Se due archi hanno peso uguale, è sufficiente modificare anche minimamente il peso di uno dei due archi per rendere valido l'algoritmo. L'algoritmo venne pubblicato nel 1926 da come metodo di costruzione di un'efficiente rete elettrica per la Moravia (Repubblica Ceca).L'algoritmo fu riscoperto da Choquet nel 1938; successivamente da , Łukasiewicz, , Steinhaus, e Zubrzycki nel 1951; e ancora da probabilmente all'inizio degli anni '60. Dato che Sollin fu l'unico informatico occidentale in tale lista, questo algoritmo è spesso chiamato algoritmo di Sollin, specialmente nella letteratura del computing parallelo. (it)
- ブルーフカ法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。 (ja)
- Алгори́тм Бору́вки (или алгоритм Борувки — Соллина) — это алгоритм нахождения минимального остовного дерева в графе. Впервые был опубликован в 1926 году в качестве метода нахождения оптимальной электрической сети в Моравии. Несколько раз был переоткрыт, например , и . Последний, кроме того, был единственным западным учёным из этого списка, и поэтому алгоритм часто называют алгоритмом Соллина, особенно в литературе по параллельным вычислениям. (ru)
- O Algoritmo de Borůvka (ou Barůvka como também é conhecido) é um algoritmo para encontrar uma árvore geradora mínima em um grafo para o qual todos os pesos de arestas sejam distintos Este algoritmo caracteriza-se pela divisão do grafo original em vários subgrafos para os quais é calculado a Minimum Spanning Tree (árvore geradora mínima). Ou seja, no fundo, pode ser considerada uma variação de algoritmos como os de Prim e Kruskal. É um algoritmo que, de modo diverso dos algoritmos de Kruskal e Prim, não usa uma fila de prioridades. É um algoritmo com uma velocidade de convergência (ou resolução) bastante rápida. A implementação desse algoritmo pode ser feita de forma recursiva e só termina quando existe apenas um vértice. (pt)
- Algorytm Borůvki – algorytm wyznaczający minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego. Pierwszy raz opublikowany został w 1926 roku przez jako metoda efektywnej konstrukcji sieci energetycznych. Algorytm ten został potem ponownie wymyślony przez w 1938 r., potem przez , Łukasiewicza, Perkala, Steinhausa i Zubrzyckiego w 1951 r. i ostatecznie w latach 60. przez , od którego nazwiska często jest on nazywany „algorytmem Sollina”. (pl)
- Алгоритм Борувки — це алгоритм пошуку мінімального кістякового дерева в графі. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10925 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Borůvkův algoritmus je algoritmus pro nalezení minimální kostry v grafu, jehož hrany mají různé (prosté) a kladné ohodnocení. (cs)
- Der Algorithmus von Borůvka gilt als erster Algorithmus zum Auffinden minimaler Spannbäume in ungerichteten Graphen. Er wurde 1926 von dem tschechischen Mathematiker Otakar Borůvka beschrieben. Die beiden bekannteren Algorithmen zur Lösung dieses Problems sind der Algorithmus von Prim und der Algorithmus von Kruskal. In der Erstveröffentlichung dieser beiden Algorithmen wird Borůvka jeweils erwähnt. (de)
- El Algoritmo de Borůvka es un algoritmo para encontrar el árbol recubridor mínimo en un grafo ponderado en el que todos sus arcos tienen distinto peso. Fue publicado por primera vez en 1926 por como un método eficiente para construir la red eléctrica de Moravia. El algoritmo fue redescubierto por Choquet en 1938; de nuevo por , Łukasiewicz, , Steinhaus y en 1951; y de nuevo por a principio de la década de 1960. Debido a que fue el único de ellos que era científico en computación, este algoritmo es frecuentemente llamado , especialmente en la literatura sobre computación paralela. (es)
- L'algorithme de Borůvka, est un algorithme de recherche de l'arbre couvrant de poids minimal dans un graphe pondéré. Il est aussi appelé algorithme de Sollin. (fr)
- ブルーフカ法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。 (ja)
- Алгори́тм Бору́вки (или алгоритм Борувки — Соллина) — это алгоритм нахождения минимального остовного дерева в графе. Впервые был опубликован в 1926 году в качестве метода нахождения оптимальной электрической сети в Моравии. Несколько раз был переоткрыт, например , и . Последний, кроме того, был единственным западным учёным из этого списка, и поэтому алгоритм часто называют алгоритмом Соллина, особенно в литературе по параллельным вычислениям. (ru)
- Алгоритм Борувки — це алгоритм пошуку мінімального кістякового дерева в графі. (uk)
- Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph,or a minimum spanning forest in the case of a graph that is not connected. It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia.The algorithm was rediscovered by Choquet in 1938; again by , Łukasiewicz, , Steinhaus, and in 1951; and again by Georges Sollin in 1965. This algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature. (en)
- L'algoritmo di Borůvka è un algoritmo per la ricerca di un albero ricoprente minimo in un grafo in cui il peso di ciascuna coppia di archi sia distinto. Se due archi hanno peso uguale, è sufficiente modificare anche minimamente il peso di uno dei due archi per rendere valido l'algoritmo. (it)
- Algorytm Borůvki – algorytm wyznaczający minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego. (pl)
- O Algoritmo de Borůvka (ou Barůvka como também é conhecido) é um algoritmo para encontrar uma árvore geradora mínima em um grafo para o qual todos os pesos de arestas sejam distintos Este algoritmo caracteriza-se pela divisão do grafo original em vários subgrafos para os quais é calculado a Minimum Spanning Tree (árvore geradora mínima). Ou seja, no fundo, pode ser considerada uma variação de algoritmos como os de Prim e Kruskal. É um algoritmo que, de modo diverso dos algoritmos de Kruskal e Prim, não usa uma fila de prioridades. (pt)
|
| rdfs:label
|
- Borůvkův algoritmus (cs)
- Algorithmus von Borůvka (de)
- Borůvka's algorithm (en)
- Algoritmo de Boruvka (es)
- Algorithme de Borůvka (fr)
- Algoritmo di Borůvka (it)
- ブルーフカ法 (ja)
- Algorytm Borůvki (pl)
- Algoritmo de Borůvka (pt)
- Алгоритм Борувки (ru)
- Алгоритм Борувки (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
_Anim.gif?width=300)
_Anim.gif){kind=link}
_Anim.gif){kind=link}
