Processing math: 100%

1 votos

Conectividad de aristas en el gráfico

Dejemos que λ(G) sea la conectividad de los bordes.

¿Alguien puede ayudarme con estas dos afirmaciones si son ciertas y, si es así, por qué?

λ(G)λ(Ge)

λ(Gv)λ(G)1

Creo que ambas cosas son ciertas, pero me cuesta probarlas.

EDITAR: La conectividad de las aristas se define como el tamaño del corte de arista más pequeño del gráfico

3voto

Salomo Puntos 1972

Por el Teorema de Menger, λ(G)=k si y sólo si k es el número máximo tal que, para cada par de vértices distintos s,t Hay por lo menos k borde-desunido s - t - caminos.

Si, para cada par de vértices distintos s,tV(Ge) Hay por lo menos k borde-desunido s - t -sendas en Ge entonces también hay al menos k borde-desunido s - t -sendas en G para cada par de vértices distintos s,tV(G) Por lo tanto, λ(G)λ(Ge) .

λ(Gv)λ(G)1 no se sostiene en general. Por ejemplo, G=(V,E) con V={v1,,v5} , E={{vi,vj}ij,i,j{1,2,3,4}}{{v1,v5}} . En este caso, λ(G)=1 pero λ(Gv5)=3 .

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