10 Abril, 2020, 15:23 *
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: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Contar los vértices de grado par en el complemento  (Leído 1045 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Click
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 160


Ver Perfil
« : 11 Septiembre, 2010, 19:14 »

Dado un grafo [texx]G=(V,E)[/texx] sin lazos ni aristas paralelas de [texx]n[/texx] vértices con [texx]n\geq 3[/texx]. Si [texx]G[/texx] tiene un sólo vértice de grado par, ¿Cuántos vértices de [texx]\overline{G}=(V,E^\prime)[/texx] tienen grado par?

Lo único que he podido deducir es que [texx]|V|= n = 2k + 1[/texx] donde hay [texx]2k[/texx] vertices de grado impar y uno de grado par. También sé que
[texx]|E|+|E^\prime|=\displaystyle\frac{n(n-1)}{2}[/texx]
Alguien me puede guiar?

Saludos
En línea
Click
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 160


Ver Perfil
« Respuesta #1 : 11 Septiembre, 2010, 19:25 »

Respondiéndome con un planteo más
Sea [texx]v[/texx] un vértice en [texx]G[/texx] y [texx]v^\prime[/texx] es el mismo vértice en [texx]\overline{G}[/texx]
Puedo asegurar que
[texx]gr(v)+gr(v^\prime) = n-1[/texx]
Donde [texx]n[/texx] era la cantidad de vértices de [texx]G[/texx]
Ahora me queda esta ecuación
[texx]gr(v)+gr(v^\prime) = n-1 = 2k[/texx]

Luego

[texx]gr(v^\prime) = 2k - gr(v)[/texx]
Lo que será par solamente si [texx]gr(v)[/texx] es par, y sucede sólo con el único vértice de grado par. Por lo tanto la respuesta a mi problema sería que la cantidad de vértices de grado par en el complemento es 1?
En línea
Leusss
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 315


Ver Perfil
« Respuesta #2 : 16 Septiembre, 2010, 18:15 »

Hola, Eze.

 Así igual lo hice yo. Te faltaría a lo mejor aclarar por qué [texx]n[/texx] es impar (lo cual ocurre porque la cantidad de vértices de grado impar tiene que ser par, y agregando el vértice de grado par del dato te queda una cantidad impar de vértices).
En línea
Click
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 160


Ver Perfil
« Respuesta #3 : 16 Septiembre, 2010, 18:53 »

Si, no lo volví a escribir porque lo mencioné en el mensaje de arriba.
Lo único que he podido deducir es que [texx]|V|= n = 2k + 1[/texx] donde hay [texx]2k[/texx] vertices de grado impar y uno de grado par.

Gracias
En línea
Leusss
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 315


Ver Perfil
« Respuesta #4 : 16 Septiembre, 2010, 18:56 »

Uh sí no lo había leído bien :lengua_afuera:
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!