17/02/2020, 19:24:52 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a aladan
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Problema de Grafos 2  (Leído 77 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Julio_fmat
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 2.083



Ver Perfil WWW
« : 19/11/2019, 11:18:05 »

Sea [texx]G[/texx] un grafo de tamaño [texx]\displaystyle{{k}\choose{2}}+1[/texx] y de grado maximo al menos [texx]2[/texx]. Demuestre que existe un conjunto [texx]U\subset V(G)[/texx] tal que [texx]\left |{U}\right |=k+1[/texx] y [texx]G\left[U\right][/texx] no tiene vertices aislados.

Hola, como podemos hacer este problema? :¿eh?:
En línea

"Haz de las Matemáticas tu pasión".
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 45.967


Ver Perfil
« Respuesta #1 : 19/11/2019, 14:12:53 »

Hola

Sea [texx]G[/texx] un grafo de tamaño [texx]\displaystyle{{k}\choose{2}}+1[/texx] y de grado maximo al menos [texx]2[/texx]. Demuestre que existe un conjunto [texx]U\subset V(G)[/texx] tal que [texx]\left |{U}\right |=k+1[/texx] y [texx]G\left[U\right][/texx] no tiene vertices aislados.

Hola, como podemos hacer este problema? :¿eh?:

Como el grado máximo es dos, tiene al menos un vértice [texx]v_1[/texx] de grado dos con dos vecinos [texx]v_2,v_3[/texx].

1) Se cumple que dado un conjunto [texx]U[/texx] cualquiera de [texx]k+1[/texx] vértices conteniendo a [texx]v_1,v_2,v_3[/texx] con dos o más vértices aislados, puede construrirse otro con el mismo número de vértices [texx]k+1[/texx] conteniendo a [texx]v_1,v_2,v_3[/texx] y estrictamente menos vértices aislados.

Spoiler (click para mostrar u ocultar)

2) Por tanto existe un conjunto [texx]U[/texx] de [texx]k+1[/texx] vértices conteniendo a [texx]v_1,v_2,v_3[/texx] conteniendo al lo sumo un vértice aislado.

To be continued…

Continúo:

Dado un conjunto [texx]U[/texx] de [texx]k+1[/texx] vértices conteniendo a [texx]v_1,v_2,v_3[/texx] con exactamente sumo un vértice aislado [texx]v_a[/texx], a lo sumo tiene [texx]\displaystyle\binom{k}{2}<\displaystyle{{k}\choose{2}}+1[/texx] aristas, por tanto hay una arista fuera de [texx]G(U)[/texx] con uno o dos vértices fuera de [texx]U[/texx].

Si esa arista sólo tiene un vértice fuera de [texx]U[/texx], lo sustituimos por el vértice aislado y ya tenemos un conjunto de [texx]k+1[/texx] vértice sin aislados.

Si esa arista tiene dos vértices fuera de [texx]U[/texx], notamos lo siguiente. La componente conexa de G(U) que contiene a [texx]v_1,v_2,v_3[/texx] o bien tiene un vértice de grado 1, que retirado sigue dejando a todos los demás sin aislar o bien tiene todos los vértices de grado mayor que 1, con lo cual retirando cualquiera de ellos sigue dejando a los demás sin aislar. Es decir en cualquier caso tenemos un vértice en esa componente conexa que podemos retirar. Intercambiamos ese vértice y el aislado [texx]v_a[/texx] por los dos vértices de la arista externa y ya tenemos un conjunto sin vértices aislados.

Saludos.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!