Árbol de expansión : Un árbol de expansión (T) de un grafo no dirigido (G) es un subgrafo que es un árbol que incluye todos los vértices de un grafo (G) y el número mínimo de aristas necesarias para conectar el grafo (G) . Y es un conjunto máximo conocido de aristas sin ciclos.
Propiedades:
- Si un gráfico (G) no está conectado, entonces no contiene un árbol de expansión (es decir, tiene muchos bosques de árboles de expansión).
- Si un gráfico (G) tiene V vértices, entonces el árbol de expansión de ese gráfico G tiene V-1 aristas.
- En el caso de un gráfico completo ( K n ) no dirigido, etiquetado y no ponderado, el número de posibles árboles de expansión se puede encontrar utilizando la fórmula de Cayley : K n = n n-2 .
- Para el gráfico K 3 (es decir, el gráfico completo de 3 vértices), el número de posibles árboles de expansión es 3 3-2 = 3 1 = 3.
Posibles árboles de expansión en el gráfico K 3
- El número de árboles de expansión mínimos de un gráfico que no sea un gráfico completo puede averiguarse utilizando el teorema de Kirchhoff .
El camino más corto:
Camino más corto (A, B, D, E) entre los vértices A y E en el gráfico dirigido ponderado
- El camino más corto entre dos vértices (por ejemplo, entre A y E ) en un gráfico tal que la suma de los pesos de los bordes que están presentes en el camino (es decir , ABDE ) es mínima entre todos los caminos posibles entre A y E.
- La ruta más corta se puede encontrar para gráficos dirigidos, no dirigidos o mixtos.
- El problema para encontrar el camino más corto se puede categorizar como
- Fuente única: la ruta más corta: en esto, la ruta más corta se calcula desde un vértice de origen a todos los demás vértices presentes dentro del gráfico.
- El camino más corto de destino único: en este caso, el camino más corto se calcula desde todos los vértices en el gráfico dirigido a un vértice de destino único. Esto se puede convertir en un solo par con el problema del camino más corto invirtiendo los bordes del gráfico dirigido.
- Todos los pares el camino más corto: En este, se calcula el camino más corto entre cada par de vértices.
Las siguientes son las diferencias entre el árbol de expansión mínimo (MST) y la ruta más corta:
| Árbol de expansión mínimo (MST) | El camino más corto |
| En MST no hay origen ni destino, pero es el subconjunto (árbol) del gráfico ( G ) el que conecta todos los vértices del gráfico G sin ningún ciclo y con el mínimo peso de arista total posible. | Hay un origen y un destino, y hay que encontrar el camino más corto entre ellos. |
| El gráfico (G) debe estar conectado, no dirigido, ponderado por los bordes y etiquetado. | No es necesario que el Gráfico (G) esté conectado, no dirigido, ponderado por los bordes, etiquetado. |
|
Aquí no se realiza la relajación de los bordes , sino que el peso mínimo de los bordes se elige uno por uno del conjunto de todos los pesos de los bordes (ordenados según el peso mínimo) y el árbol está formado por ellos (es decir, no debe haber ningún ciclo). |
Aquí se realiza la relajación de bordes .
|
| En este caso, se puede formar un árbol de expansión mínimo, pero generalmente no se utilizan ciclos de borde de pesos negativos. Usando la propiedad de ciclo de MST, se puede seleccionar el peso de borde mínimo entre todos los pesos de borde en el ciclo de borde negativo. | Si el gráfico está conectado, y si un ciclo de borde de peso negativo está presente en el gráfico. Entonces no se puede calcular la ruta más corta, pero el ciclo de flanco negativo se puede detectar utilizando el algoritmo de Bellman-Ford. |
| En el caso de un gráfico desconectado , no se puede formar el árbol de expansión mínimo, pero se pueden formar muchos bosques de árboles de expansión. | En el caso de un grafo inconexo , la distancia entre dos vértices presentes en dos componentes diferentes es infinito. |
|
Aquí, el enfoque Greedy se usa para encontrar MST para un gráfico, por ejemplo, el algoritmo de Prim y el algoritmo de Kruskal . |
|
| Si hay N vértices presentes dentro del gráfico G, entonces el árbol de expansión mínimo del gráfico contendrá N-1 aristas y N vértices. | Si hay N vértices presentes dentro del gráfico G , entonces en el camino más corto entre dos vértices puede haber como máximo N-1 aristas, y como máximo N vértices pueden estar presentes en el camino más corto. |
| Se utiliza en el diseño de redes (redes informáticas, redes de telecomunicaciones, redes de suministro de agua) y en aplicaciones de diseño de circuitos, y muchas más. | Se utiliza para averiguar la dirección entre ubicaciones físicas como en Google Maps. |
Publicación traducida automáticamente
Artículo escrito por goutamnagpal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA