Autor Tema: Conjunto independiente maximal 2

0 Usuarios y 1 Visitante están viendo este tema.

27 Octubre, 2019, 10:24 pm
Leído 1050 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Demuestre que todo conjunto independiente maximal de un grafo \( G \) contiene al menos \( \Big\lceil \dfrac{n(G)}{\Delta(G)+1}\Big\rceil \) vértices. Luego, demuestre que para todo grafo \( G \) se cumple que \( \alpha(G)\ge \dfrac{n(G)}{\Delta(G)+1}. \)
"Haz de las Matemáticas tu pasión".

28 Octubre, 2019, 11:19 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

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

 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.

04 Noviembre, 2019, 12:35 am
Respuesta #2

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Hola

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

 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 \( \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}. \)

¿Esta correcto? Ahora faltaria probar que todo conjunto independiente maximal de un grafo \( G \) contiene al menos \( \Big\lceil \dfrac{n(G)}{\Delta(G)+1}\Big\rceil \) vertices, donde \( \lceil .\rceil \) es la funcion techo.
"Haz de las Matemáticas tu pasión".

04 Noviembre, 2019, 11:51 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

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

15 Noviembre, 2019, 09:17 am
Respuesta #4

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Hola

¿Esta correcto? Ahora faltaria probar que todo conjunto independiente maximal de un grafo \( G \) contiene al menos \( \Big\lceil \dfrac{n(G)}{\Delta(G)+1}\Big\rceil \) vertices, donde \( \lceil .\rceil \) 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 \( S \) y de ahi demostrar la desigualdad, aunque esta forma no logro comprenderla... ¿Alguien me puede ayudar?
"Haz de las Matemáticas tu pasión".

15 Noviembre, 2019, 09:54 am
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

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

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

\( card\leq k(\Delta(G)+1) \)

Si \( k(\delta(G)+1) \) fuese menor que \( n(G) \) 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:

\( k(\delta(G)+1)\geq n(G) \)

Es decir;

\( k\geq \dfrac{n(G)}{\delta(G)+1} \)

Como \( k \) es entero:

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

Saludos.