Cómo buscar los bordes que deben existir en cada árbol recubridor mínimo de un grafo ponderado

votos
0

Dado un grafo ponderado no dirigida, no se conocen los pesos reales de los bordes, sin embargo; En su lugar, cada borde se clasifica como ligero, medio o pesado.

Todos los bordes de luz tienen un peso menor que cualquier borde mediano o pesado.

Todos los bordes del medio tienen un peso más pequeño que cualquier borde pesado

En general, no se sabe nada acerca de la relación entre dos bordes de la misma categoría de peso. Entonces, cómo identificar todas las aristas que deben existir en cada MST de este gráfico? Lo siguiente es lo que pienso: 1. Determinar el número de componentes fuertemente conectados. 2. los bordes compuestas de puntos de articulación deben existir en el MST. 3. El borde más ligero de cada componente conectado debe existir en el MST.

No estoy seguro de si mi pensamiento es correcto o no? Si es correcto, la forma de aplicar el código con java? Muchas gracias.

Publicado el 20/10/2018 a las 10:26
fuente por usuario
En otros idiomas...                            


1 respuestas

votos
0

Jason, yo no voy a entrar en la descripción de cómo implementar el código en Java, pero vamos a ver el proceso de pensamiento detrás del algoritmo para su problema.

Debido a que sus vértices se clasifican en tres categorías de peso, podemos volver a etiquetar con pesos comparativos de la siguiente manera: La luz es 1; Medio es 2; Pesada: 3. De esta manera, se mantienen sus condiciones.

A continuación, podemos utilizar el árbol de expansión mínimo Algoritmo de Kruskal (MST) como lo haría normalmente para crear un árbol de expansión mínimo en un grafo no dirigido ponderado. Este algoritmo es codicioso, por lo que sería ordenar los bordes de ligero a pesado, recoger el siguiente flanco más pequeño con tal de que no crea un ciclo, y luego repetir el paso 2 hasta que todos los vértices están incluidas en el MST. (Ver enlace más abajo para la referencia) https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

Cuando se trata de comprobar que el algoritmo es correcto, hay dos casos posibles.

1). Puede revelar los pesos reales de los bordes en el MST y los excluidos. Compruebe los bordes excluidos y si al agregar un borde excluidos para el MST, que el borde no es el más pesado en el ciclo, intercambiarlo con el borde más pesada. Siga haciendo esto hasta que todos los bordes excluidos originalmente se exploran y el MST mantiene su característica de que contiene todos los vértices. 2). No se pueden revelar los pesos reales de cualquier vértice en el gráfico. En este caso, no hay manera de verificar incluso que su algoritmo creado un árbol de expansión mínimo, por lo que su algoritmo no tendría ninguna manera de comprobar en sí. En cualquier caso, utilizando el algoritmo de Kruskal con pesos comparativos crearía un árbol de expansión que está muy cerca de mínimos, aun sin conocer los pesos reales.

Respondida el 30/11/2018 a las 22:20
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more