12.4: Notas históricas

Última actualización
Guardar como PDF

Page ID: 118512

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

El algoritmo de Kruskal fue publicado en 1956 por Joseph B. Kruskal en un artículo de tres páginas que apareció en Proceedings of the American Mathematical Society. Robert C. Prim publicó el algoritmo que ahora lleva su nombre al año siguiente en The Bell System Technical Journal. El artículo de Prim se centra en la aplicación del problema del árbol de expansión de peso mínimo (o longitud o costo) a las redes telefónicas. Estaba al tanto del trabajo previo de Kruskal, ya que eran compañeros de Laboratorios Bell en el momento en que publicó su trabajo. Resulta que Prim había sido golpeado hasta el puñetazo por el matemático checo Vojtěch Jarník en 1929, por lo que algunos se refieren al algoritmo de Prim como el algoritmo de Jarník. (Más tarde fue redescubierta por Dijkstra, por lo que algunos también adjuntan su nombre, refiriéndose a él como el algoritmo Dijkstra-Jarník-Prim.) Edsger Dijkstra publicó su algoritmo para encontrar los caminos más cortos en 1959 en un artículo de tres páginas que aparece en Numerische Mathematik. De hecho, el algoritmo de Dijkstra había sido descubierto (en una forma equivalente) por Edward F. Moore dos años antes. Su resultado apareció en Proceedings of an International Symposium on the Theory of Switching.