Buenas. Leyendo el libro me surgio duda de como deduce que hay 2k nodos que quedan "sin ser tocados". Ya que si hace k uniones involucra 2k nodos, pero eso no es lo que dice el libro. Tomé como ejemplo 5 nodos y le agregué 2 aristas. Esto hace union entre 4 nodos y me deja 1 "sin haber sido tocado". Gracias
En respuesta a Mateo Piñeiro Aguilera
Re: Kruskal's Algorithm. Duda puntual
En realidad dice "all but at most 2k elements" osea, todos menos como máximo 2k elementos. Si hubieran n elementos en total, n-2k quedarían sin tocar como máximo
acabo de ver esta respuesta. ahi va, es lo que dice Tatiana.
J
J
hola Mateo:
la traducción de esa frase sería algo como: "Una operación de Unión puede considerar como máximo dos de estos conjuntos originales de un solo elemento, por lo que después de cualquier secuencia de k operaciones de Unión todos los elementos de S, excepto como máximo 2k, han quedado sin tocar." esta escrito un poco raro pero el "all but at most 2k elements" quiere decir algo como "todos excepto como mucho 2k elementos", así que lo que estas pensando esta bien.
saludos
J