# TDA | Practica 4 ejercicio 11 ## Consigna - $11.\star$Una empresa de comunicaciones modela su red usando un grafo $G$ donde cada arista tiene una capacidad positiva que representa su ancho de banda. El anchode banda de la red es el maximo $k$ tal que $G_k$ es conexo, donde $G_k$ es el subgrafo generador de $G$ que se obtiene de eliminar las aristas de peso menor a $k$ (Figura 2). -  - a) Proponer un algoritmo eficiente para determinar el ancho de banda de una red dada - b) La empresa está dispuesta a hacer una inversión que consiste en actualizar algunos enlaces (aristas) a un ancho de banda que, para la tecnología existente, es virtualmente infinito. Antes de decidir la inversión, quieren determinar cuál es el ancho de banda que se podría obtener si se reemplazan $i$ aristas $\forall i \Rightarrow 0\leq i < n$. - Proponer un algoritmo que dado $G$ determine el vector $a_0, \dots, a_{n-1}$ talque $a_i$ es el ancho de banda máximo que se puede obtener si se reemplazan $i$ aristas de $G$. ## Resolución ### a) - Yo pienso que por lo que me dice, tiene pinta de que hay que plantear un maximin. - Buscamos el máximo $k$ para el cual el grafo mantiene conexitud, tras eliminar todas las aristas con peso inferior a $k$. - IDEA: Kruskal con disjoint-set - Ordenar aristas por peso (ord asc) - Construir el AGM - Maximin-$k$ - Tiene una complejidad asintotica de $O(m \ log \ m)$ siendo $m = |E(G)|$ ### b) - TBD, no entiendo bien lo que me piden.