árbol de expansión de cuello de botella mínimo

En un grafo no dirigido G ( V , E )  y una función w  : E → R    , sea S el conjunto de todos los árboles de expansión T _i . Sea B ( T _i ) la arista de peso máximo para cualquier árbol de expansión T _i . Definimos un subconjunto de árboles de expansión de cuello de botella mínimo S ′ tal que para cada T _j  ∈ S ′  y T _k  ∈ S  tenemos B ( T _j )  ≤ B ( T _k )  para todo i y k . ^{[ 2 ]} 

El gráfico de la derecha es un ejemplo de MBST, las aristas rojas en el gráfico forman un MBST de G ( V , E )  .

Una arborescencia de un grafo G es un árbol dirigido de G que contiene un camino dirigido desde un nodo L específico a cada nodo de un subconjunto V ′ de V  \{ L } . El nodo L se denomina raíz de la arborescencia. Una arborescencia es una arborescencia de expansión si V ′  = V \{ L }   . En este caso, el MBST es una arborescencia de expansión con la arista de cuello de botella mínima. Un MBST en este caso se denomina Arborescencia de Expansión de Cuello de Botella Mínimo (MBSA).

El gráfico de la derecha es un ejemplo de MBSA, los bordes rojos en el gráfico forman un MBSA de G ( V , E )  .

El procedimiento tiene dos parámetros de entrada. G es un grafo, w es un arreglo ^de pesos de todas las aristas en el grafo G. ^{[ 6} ]

función MBST(grafo G , pesos w ) E ← el conjunto de aristas de G si | E | = 1 entonces devolver E sino A ← mitad de las aristas en E cuyos pesos no son menores que el peso mediano B ← E - A F ← bosque de G B si F es un árbol de expansión entonces devolver MBST( G B , w ) sino devolver MBST(( G A ) η , w )${\displaystyle \cup }$F

En lo anterior ( G _A ) _η es el subgrafo compuesto por super vértices (considerando los vértices en un componente desconectado como uno solo) y aristas en A .

El algoritmo se ejecuta en tiempo O ( E ), donde E es el número de aristas. Este límite se alcanza de la siguiente manera:

• dividiendo en dos conjuntos con algoritmos de búsqueda de mediana en O ( E )
• encontrar un bosque en O ( E )
• considerando medios bordes en E en cada iteración T(E)=T(E/2)+O(E). Por el teorema maestro , la complejidad temporal total es O ( E ).

NOTA : La estimación del tiempo de ejecución es O(E) en lugar de O(E+V) (recorrer un grafo lleva O(E+V) tiempo), pero en este caso el grafo está conectado, por lo tanto V-1<=E, por lo tanto, O(E+V)=O(E).

En el siguiente ejemplo, los bordes verdes se utilizan para formar un MBST y las áreas rojas discontinuas indican los supervértices formados durante los pasos del algoritmo.

Para un grafo dirigido, el algoritmo de Camerini se centra en encontrar el conjunto de aristas cuyo coste máximo sería el coste de cuello de botella del MBSA. Esto se hace dividiendo el conjunto de aristas E en dos conjuntos A y B y manteniendo el conjunto T , que es el conjunto en el que se sabe que G _T no tiene una arborescencia de expansión, incrementando T en B siempre que la arborescencia máxima de G ( B  ∪ T ) no sea una arborescencia de expansión de G , de lo contrario, disminuimos E en A . La complejidad temporal total es O ( E log E ). ^{[ 5 ] [ 4 ]}    

La función MBSA( G , w , T ) es E ← el conjunto de aristas de G si | E − T | > ​​1 entonces A ← UH(ET) B ← ( E − T) − A F ← BUSH( G PERO ) si F es una arborescencia de expansión de G entonces S ← F MBSA(( G PERO ), w , T ) más MBSA(G, w , TUB );

Gabow y Tarjan proporcionaron una modificación del algoritmo de Dijkstra para la ruta más corta desde un único origen que produce un MBSA. Su algoritmo se ejecuta en tiempo O ( E  + V log V ) si se utiliza un montón de Fibonacci . ^{[ 7 ]}   

Para un grafo G(V,E), F es una colección de vértices en V. Inicialmente, F = { s } donde s es el punto de partida del gráfico G y c ( s ) = - ∞ 1 función MBSA-GT( G , w, T ) 2 repeticiones |V| veces 3 Seleccionar v con c ( v ) mínimo de F ; 4 Elimínelo de la F ; 5 para ∀ edge( v, w ) hacer 6 si w ∉ F o ∉ Tree entonces 7 agregar w a F; 8 c ( w ) = c ( v,w ); 9 p ( w ) = v ; 10 de lo contrario 11 si w ∈ F y c(w) > c(v, w) entonces 12 c ( w ) = c ( v, w ); 13 p ( w ) = v ;