2 votos

Arborescencia de un gráfico

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

enter image description here

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)

2voto

paulinho Puntos 364

Declaración $A$ es cierto: se está proponiendo que el peso mínimo de arborescencia del grafo sea mayor que la suma de los pesos mínimos de salida de cada vértice. Esto es cierto porque para cada vértice $v \in V \backslash \{r\}$ la arborescencia mínima debe contener al menos una arista dirigida desde $v$ a algún otro vértice. En caso contrario, $v$ no está conectado al resto del grafo y no existe un camino dirigido desde $v$ a $r$ una contradicción.

Declaración $B$ es falso: se propone que el peso mínimo de arborescencia de un grafo sea mayor que la suma de los mínimos entrante pesos de cada vértice. Consideremos el gráfico formado por tres vértices, $v_1, v_2, v_3$ y aristas dirigidas $w(v_2 \rightarrow v_1) = 1, w(v_3 \rightarrow v_1) = 1, w(v_3 \rightarrow v_2) = 5$ . La arborescencia mínima tiene raíz $v_1$ se compone de las aristas $\{ v_3 \rightarrow v_1, v_3 \rightarrow v_2 \}$ y tiene peso $2$ . Mientras tanto, la suma de los pesos mínimos de entrada de cada vértice son $5 + 1 = 6$ . La idea aquí es que, aunque debe haber aristas de salida de cada vértice en la arborescencia, no es necesario que haya aristas de entrada a cada vértice.

Declaración $C$ es falso: considere un gráfico con $n$ vértices, $\{v_0, v_1 ,\cdots v_{n - 1} \} $ tal que existe una arista dirigida desde $v_i \implies v_{(i + 1) \text{ mod } n}$ . Se trata de un gráfico cíclico muy simple con $n$ vértices. Elija cualquier $v_i$ como $r$ y tenemos una arborescencia mínima enraizada en ese vértice. Pero esta arborescencia mínima (que es también el propio gráfico) contiene $n$ bordes.

Declaraciones $D$ y $E$ también son falsas, utilizando el mismo contraejemplo de arriba. Sin embargo, hay que tener en cuenta que si la declaración $E$ en su lugar " $w^*$ es menor que o igual a el peso del ciclo hamiltoniano mínimo dirigido", entonces esto sería cierto. Esto se debe a que el propio ciclo hamiltoniano es una arborescencia, por lo que cualquier arborescencia mínima debe tener un peso menor o igual a ella.

2voto

Especially Lime Puntos 51

Paulinho tiene razón en que A es verdadero y B es falso.

De hecho, todas las demás opciones son verdaderas (lo cual es bueno, ya que significa que sólo hay una respuesta correcta a la pregunta).

En primer lugar, C es verdadera porque en una arborescencia mínima cada vértice tiene como máximo una arista saliente (y $r$ no tiene ninguno). Para ver esto, supongamos $x$ tiene dos aristas de salida en la arborescencia, a $y$ y $z$ . Dado que existe un camino dirigido desde $y$ a $r$ podemos eliminar la arista $xz$ y cada vértice sigue teniendo un camino hacia $r$ , dando una arborescencia de menor peso ya que $w(xz)>0$ . Del mismo modo, si $r$ tiene una arista de salida podemos eliminarla sin romper ninguna ruta hacia $r$ . Dado que claramente todos los vértices, excepto $r$ debe tener al menos una arista de salida, hay exactamente $n-1$ bordes. También se deduce que no hay ciclos. Supongamos que hay un ciclo en la arborescencia. Si incluye $r$ , $r$ tiene un borde de salida, lo que demostramos que no podía suceder. Si no es así, hay algún camino desde un vértice del ciclo hasta $r$ . En el punto en el que este camino deja el ciclo, hay dos aristas de salida, una a lo largo del ciclo y otra a lo largo del camino, pero de nuevo sabemos que esto no puede ocurrir.

Por último, si hay un ciclo de Hamilton en el grafo, podemos tomar todas las aristas del ciclo excepto la que sale de $r$ . Esto es una arborescencia, y su peso es estrictamente menor que el del ciclo, ya que eliminamos una arista. (Esto demuestra por qué el contraejemplo de paulinho no es válido - la arista que sale de $r$ es superfluo).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X