Gráficas ponderadas y árboles recubridores

Diremos que una gráfica (no dirigida y sin lazos) es ponderada si cada una de sus aristas tiene un valor numérico asignado. Este valor, al que generalmente llamamos peso, puede representar, por ejemplo, tiempos, distancias, ganancias o costos de recorrido de las propias aristas en el contexto del problema que se está trabajando, entre muchas otras posibilidades. Como las aristas no tienen orientación, el peso o costo es el mismo en un sentido que en otro, y se considera que el costo entre dos vértices sin arista es infinito.

Pensemos en una gráfica ponderada $G(V_0,E_0)$ que sea conexa. Como ya hemos mencionado en secciones anteriores, los árboles son las gráficas mínimas que permiten que una gráfica conexa conserve esa propiedad y permiten recorridos entre cualquier par de vértices. De esta forma, diremos que un árbol $T(V_1,E_1)$ es un árbol recubridor de $G$ siempre que $V_0=V_1$, es decir, siempre que ambos tengan los mismos vértices.

Los árboles recubridores nos permiten eliminar redundancias y mantener la gráfica conexa con el mínimo número de aristas, sin embargo, dada una gráfica conexa pueden existir varios árboles recubridores.

Si nuestra gráfica conexa sin lazos no está ponderada, entonces cualquier árbol recubridor nos permite conectar todos los vértices de forma óptima. Sin embargo, si la gráfica está ponderada la solución no es tan simple, además de que podemos estar interesados en recubrimientos de costo mínimo, pero también de costo máximo.

En el siguiente espacio puedes experimentar con gráficas ponderadas generadas aleatoriamente y buscar sus árboles recubridores mínimos o máximos. Los puntos rojos pueden desplazarse de la misma forma que en la sección de Inicio. Los pesos de las aristas aparecen como números cercanos a ellas. Una vez generada una gráfica ponderada puedes ajustar el número de vértices entre 0 y 11 y también es posible cambiar la probabilidad de conexión entre vértices. Si escojes 0 en este control, la gráfica no tendrá vértices, mientras que el valor de 1 conectará absolutamente todos los vértices de la gráfica. Para seleccionar o eliminar una arista como parte del árbol recubridor puedes presionar sobre el punto gris que está en el punto medio del segmento correspondiente. Si la gráfica resultante de la generación aleatoria no es conexa entonces los árboles tendrán peso mínimo infinito y no serán realizables, si esto sucede aumenta la probabilidad de conexión entre aristas y oprime Reiniciar.

Una vez que explores las formas de encontrar árboles recubridores minimos o máximos es conveniente que conozcas los algoritmos de Kruskal y Prim que se presentan a continuación. Entonces podrás regresar a la escena anterior y, realizando varios ejemplos, verificar que ambos algoritmos producen álboles recubridores con peso o costo óptimos.