Property |
Value |
dbo:abstract
|
- En teoria de grafs, l'algorisme de Kruskal és un algorisme que serveix per trobar l'arbre generador amb el menor pes que connecta tots els punts d'un graf. Es tracta d'un algorisme voraç, ja que troba l'arbre generador mínim per un graf ponderat connex afegint arcs de pes superior en cada pas. Això significa que troba un subconjunt d'arestes que formen un arbre que inclou cada vèrtex, tal que el pes total de les arestes és el mínim. Si el graf no és connex troba un bosc generador mínim (un arbre generador mínim per a cada component connex). Aquest algorisme va aparèixer per primer cop a Proceedings of the American Mathematical Society, pp. 48–50 el 1956 i va ser escrit per Joseph Kruskal. Altres algorismes per aquest problema poden ser l'algorisme de Prim, l'algorisme d'eliminació cap enrere o l'algorisme de Borůvka. (ca)
- En teoria de grafs, l'algorisme de Kruskal és un algorisme que serveix per trobar l'arbre generador amb el menor pes que connecta tots els punts d'un graf. Es tracta d'un algorisme voraç, ja que troba l'arbre generador mínim per un graf ponderat connex afegint arcs de pes superior en cada pas. Això significa que troba un subconjunt d'arestes que formen un arbre que inclou cada vèrtex, tal que el pes total de les arestes és el mínim. Si el graf no és connex troba un bosc generador mínim (un arbre generador mínim per a cada component connex). Aquest algorisme va aparèixer per primer cop a Proceedings of the American Mathematical Society, pp. 48–50 el 1956 i va ser escrit per Joseph Kruskal. Altres algorismes per aquest problema poden ser l'algorisme de Prim, l'algorisme d'eliminació cap enrere o l'algorisme de Borůvka. (ca)
|
dbo:wikiPageID
| |
dbo:wikiPageRevisionID
| |
dct:subject
| |
rdfs:comment
|
- En teoria de grafs, l'algorisme de Kruskal és un algorisme que serveix per trobar l'arbre generador amb el menor pes que connecta tots els punts d'un graf. Es tracta d'un algorisme voraç, ja que troba l'arbre generador mínim per un graf ponderat connex afegint arcs de pes superior en cada pas. Això significa que troba un subconjunt d'arestes que formen un arbre que inclou cada vèrtex, tal que el pes total de les arestes és el mínim. Si el graf no és connex troba un bosc generador mínim (un arbre generador mínim per a cada component connex). (ca)
- En teoria de grafs, l'algorisme de Kruskal és un algorisme que serveix per trobar l'arbre generador amb el menor pes que connecta tots els punts d'un graf. Es tracta d'un algorisme voraç, ja que troba l'arbre generador mínim per un graf ponderat connex afegint arcs de pes superior en cada pas. Això significa que troba un subconjunt d'arestes que formen un arbre que inclou cada vèrtex, tal que el pes total de les arestes és el mínim. Si el graf no és connex troba un bosc generador mínim (un arbre generador mínim per a cada component connex). (ca)
|
rdfs:label
|
- Algorisme de Kruskal (ca)
- Algorisme de Kruskal (ca)
|
prov:wasDerivedFrom
| |
foaf:isPrimaryTopicOf
| |
is foaf:primaryTopic
of | |