10 Abril, 2020, 05:35 *
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: LISTADO ACTUALIZADO DE CURSOS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Conjunto independiente maximal 2  (Leído 324 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.110



Ver Perfil WWW
« : 27 Octubre, 2019, 18:24 »

Demuestre que todo conjunto independiente maximal de un grafo [texx]G[/texx] contiene al menos [texx]\Big\lceil \dfrac{n(G)}{\Delta(G)+1}\Big\rceil[/texx] vértices. Luego, demuestre que para todo grafo [texx]G[/texx] se cumple que [texx]\alpha(G)\ge \dfrac{n(G)}{\Delta(G)+1}.[/texx]
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: 46.144


Ver Perfil
« Respuesta #1 : 28 Octubre, 2019, 07:19 »

Hola

 
Demuestre que todo conjunto independiente maximal de un grafo [texx]G[/texx] contiene al menos [texx]\Big\lceil \dfrac{n(G)}{\Delta(G)+1}\Big\rceil[/texx] vértices. Luego, demuestre que para todo grafo [texx]G[/texx] se cumple que [texx]\alpha(G)\ge \dfrac{n(G)}{\Delta(G)+1}.[/texx]

 Mira por aquí:

https://math.stackexchange.com/questions/1686209/prove-forall-graphs-alphag-ge-fracn-deltag1?rq=1

ó aplica esto:

http://rinconmatematico.com/foros/index.php?topic=111048.msg439044#msg439044

Saludos.
En línea
Julio_fmat
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 2.110



Ver Perfil WWW
« Respuesta #2 : 03 Noviembre, 2019, 20:35 »

Hola

 
Demuestre que todo conjunto independiente maximal de un grafo [texx]G[/texx] contiene al menos [texx]\Big\lceil \dfrac{n(G)}{\Delta(G)+1}\Big\rceil[/texx] vértices. Luego, demuestre que para todo grafo [texx]G[/texx] se cumple que [texx]\alpha(G)\ge \dfrac{n(G)}{\Delta(G)+1}.[/texx]

 Mira por aquí:

https://math.stackexchange.com/questions/1686209/prove-forall-graphs-alphag-ge-fracn-deltag1?rq=1

ó aplica esto:

http://rinconmatematico.com/foros/index.php?topic=111048.msg439044#msg439044

Saludos.

Muchas Gracias, notamos que [texx]\alpha(G)\ge \displaystyle\sum_{v\in V(G)}\dfrac{1}{d(v)+1}=\displaystyle\sum_{v\in V(G)}(1+d(v))^{-1}\ge \dfrac{|G|}{\Delta(G)+1}=\dfrac{n(G)}{\Delta(G)+1}.[/texx]

¿Esta correcto? Ahora faltaria probar que todo conjunto independiente maximal de un grafo [texx]G[/texx] contiene al menos [texx]\Big\lceil \dfrac{n(G)}{\Delta(G)+1}\Big\rceil[/texx] vertices, donde [texx]\lceil .\rceil[/texx] es la funcion techo.
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: 46.144


Ver Perfil
« Respuesta #3 : 04 Noviembre, 2019, 07:51 »

Hola

¿Esta correcto? Ahora faltaria probar que todo conjunto independiente maximal de un grafo [texx]G[/texx] contiene al menos [texx]\Big\lceil \dfrac{n(G)}{\Delta(G)+1}\Big\rceil[/texx] vertices, donde [texx]\lceil .\rceil[/texx] es la funcion techo.

Lo tienes probado en el enlace que te indiqué:

https://math.stackexchange.com/questions/1686209/prove-forall-graphs-alphag-ge-fracn-deltag1?rq=1

Saludos.
En línea
Julio_fmat
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 2.110



Ver Perfil WWW
« Respuesta #4 : 15 Noviembre, 2019, 05:17 »

Hola

¿Esta correcto? Ahora faltaria probar que todo conjunto independiente maximal de un grafo [texx]G[/texx] contiene al menos [texx]\Big\lceil \dfrac{n(G)}{\Delta(G)+1}\Big\rceil[/texx] vertices, donde [texx]\lceil .\rceil[/texx] es la funcion techo.

Lo tienes probado en el enlace que te indiqué:

https://math.stackexchange.com/questions/1686209/prove-forall-graphs-alphag-ge-fracn-deltag1?rq=1

Saludos.

Gracias, ahora que lo pienso un poco mejor y revisando un apunte que tengo. Otra solucion seria formar un conjunto independiente [texx]S[/texx] y de ahi demostrar la desigualdad, aunque esta forma no logro comprenderla... ¿Alguien me puede ayudar?
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: 46.144


Ver Perfil
« Respuesta #5 : 15 Noviembre, 2019, 05:54 »

Hola

Gracias, ahora que lo pienso un poco mejor y revisando un apunte que tengo. Otra solucion seria formar un conjunto independiente [texx]S[/texx] y de ahi demostrar la desigualdad, aunque esta forma no logro comprenderla... ¿Alguien me puede ayudar?

Sea [texx]v_1,v_2,\ldots,v_k[/texx] un conjunto independiente maximal de [texx]S[/texx]. Para cada vértice [texx]v_i[/texx] hay a lo sumo [texx]\Delta(G)[/texx] vértices unidos a él por aristas, luego en total, el conjunto formado por todos los vértices [texx]v_i[/texx] y sus posibles vértices anexos tiene cardinal:

[texx]card\leq k(\Delta(G)+1)[/texx]

Si [texx]k(\delta(G)+1)[/texx] fuese menor que [texx]n(G)[/texx] habría un vértice que no es anexo a ninguno de los vértices del conjunto independiente maximal, pero eso contradice su maximalidad como conjunto independiente.

Por tanto:

[texx]k(\delta(G)+1)\geq n(G)[/texx]

Es decir;

[texx]k\geq \dfrac{n(G)}{\delta(G)+1}[/texx]

Como [texx]k[/texx] es entero:

[texx]k\geq \Big\lceil\dfrac{n(G)}{\delta(G)+1}\Big\rceil[/texx]

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!