Dejemos que $G=(V,E)$ sea un grafo dirigido con $n(\geq 2)$ vértices, incluyendo un vértice especial $r$ . Cada borde $e \in E$ tiene un peso de arista estrictamente positivo $w(e)$ . Una arborescencia en $G$ arraigado en $r$ es un subgrafo $H$ de $G$ en la que cada vértice $u \in V \backslash \{r\}$ tiene un camino dirigido al vértice especial $r$ . El peso de una arborescencia $H$ es la suma de los pesos de las aristas en $H$ .
Dejemos que $H^*$ sea una arborescencia mínima arraigada en $r$ y $w^*$ el peso de $H^*$ . ¿Cuál de los siguientes es $NOT$ ¿Siempre es cierto?
$A)w^* \geq \sum_{u \in V \backslash \{r\}} \min_{(u,v) \in E} w((u,v))$
$B)w^* \geq \sum_{u \in V \backslash \{r\}} \min_{(v,u) \in E} w((v,u))$
$C)H^*$ tiene exactamente $n-1$ bordes
$D)H^*$ es acíclico
$E)w^*$ es menor que el peso del ciclo hamiltoniano dirigido de mínimo peso en $G$ cuando $G$ tiene un ciclo hamiltoniano dirigido
Lo he intentado así Aquí está diciendo un gráfico dado G
y tiene un vértice especial r
Ahora, H es un subgrafo del grafo G y cada vértice de H que tiene una arista dirigida a r
Ahora pensaba que G es un gráfico como este
Ahora como $H$ es cualquier subgrafo de $G$ Entonces, A) y B) son falsas, siempre hay un subgrafo que contiene el peso mínimo del grafo
C) falso porque $H$ puede no contener exactamente $n-1$ bordes.
E) Falso , porque H y G pueden ser ambos el mismo grafo (es decir, subgrafo impropio)
Un caso definitivamente allí, donde es falso
Ahora D) H es cíclico o no depende totalmente de nuestro diseño del gráfico
Por lo tanto, no siempre es cierto (ver en el diagrama anterior, si H=G, entonces contiene un ciclo)