Autor Tema: Propiedad de grafos

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

27 Septiembre, 2019, 12:40 am
Leído 1221 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 para todo grafo \( G \) y todo subconjunto \( X \) de \( V(G) \) se cumple que

\( \displaystyle\sum_{x\in X} d_G (x)=2m(G[X])+d_G (X). \)
"Haz de las Matemáticas tu pasión".

27 Septiembre, 2019, 11:59 am
Respuesta #1

Luis Fuentes

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

Demuestre que para todo grafo \( G \) y todo subconjunto \( X \) de \( V(G) \) se cumple que

\( \displaystyle\sum_{x\in X} d_G (x)=2m(G[X])+d_G (X). \)

¿Qué denotas por \( d_G(X) \)?.

Saludos.

11 Octubre, 2019, 03:24 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 para todo grafo \( G \) y todo subconjunto \( X \) de \( V(G) \) se cumple que

\( \displaystyle\sum_{x\in X} d_G (x)=2m(G[X])+d_G (X). \)

¿Qué denotas por \( d_G(X) \)?.

Saludos.

Hola, si mal no recuerdo, se refiere al grado de un vértice, esa es la notación.
"Haz de las Matemáticas tu pasión".

11 Octubre, 2019, 10:47 am
Respuesta #3

Luis Fuentes

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

Hola, si mal no recuerdo, se refiere al grado de un vértice, esa es la notación.

Pero es que ahí tienes \( d_G(X) \) donde \( X \) es un conjunto de vértices, no uno solo.

Me resulta incompresible que plantees un problema en el que no sabes la  notación que se usa y que en ese caso tu primera pregunta no sea que te ayuden a entenderla.

Con las posibles interpretaciones que se me ocurren de \( d_G(X) \) el resultado no es cierto. Así que revisa con cuidado el enunciado.

Saludos.

19 Noviembre, 2019, 03:29 pm
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

Hola, si mal no recuerdo, se refiere al grado de un vértice, esa es la notación.

Pero es que ahí tienes \( d_G(X) \) donde \( X \) es un conjunto de vértices, no uno solo.

Me resulta incompresible que plantees un problema en el que no sabes la  notación que se usa y que en ese caso tu primera pregunta no sea que te ayuden a entenderla.

Con las posibles interpretaciones que se me ocurren de \( d_G(X) \) el resultado no es cierto. Así que revisa con cuidado el enunciado.

Saludos.

Hola, lo revise, y esta bien escrito. ¿Me puedes ayudar con la demostracion? Gracias.

PD.: En el caso de que no estuviera bien escrito, ahi seria culpa de mi Profesor...
"Haz de las Matemáticas tu pasión".

19 Noviembre, 2019, 11:41 pm
Respuesta #5

Luis Fuentes

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

Hola, lo revise, y esta bien escrito. ¿Me puedes ayudar con la demostracion? Gracias..

Sigue sin entrarme en la cabeza que pretendas resolver un problema o que te ayuden a demostrar algo y que no sepas tan siquiera que significa el enunciado.

\( d_G(X) \) no puede ser el grado de un vértice, porque \( X \) son muchos vértices.

Por hacer algo: dado que en general en cualquier grafo el doble del número de aristas es la suma de los grados de los vértices se tiene que:

\( 2m(G[ X])=\displaystyle\sum_{x\in X}deg_{G[X ]}(x) \)

Así que para que la fórmula que te piden probar sea cierta tiene que cumplirse que:

\( d_G(X)=\displaystyle\sum_{x\in X}(deg_G(x)-deg_{G[X ]}(x)) \)

Saludos.

21 Noviembre, 2019, 11:48 am
Respuesta #6

Luis Fuentes

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

Sigue sin entrarme en la cabeza que pretendas resolver un problema o que te ayuden a demostrar algo y que no sepas tan siquiera que significa el enunciado.

\( d_G(X) \) no puede ser el grado de un vértice, porque \( X \) son muchos vértices.

Por hacer algo: dado que en general en cualquier grafo el doble del número de aristas es la suma de los grados de los vértices se tiene que:

\( 2m(G[ X])=\displaystyle\sum_{x\in X}deg_{G[X ]}(x) \)

Así que para que la fórmula que te piden probar sea cierta tiene que cumplirse que:

\( d_G(X)=\displaystyle\sum_{x\in X}(deg_G(x)-deg_{G[X ]}(x)) \)   (*)

A la luz de este otro problema:

http://rinconmatematico.com/foros/index.php?topic=111344.0;topicseen

ya sé que está denotando por \( d_G(X) \); se refiere al número de aristas que unen algún vértice de \( X \) con algún vértice fuera de \( X \); es decir al número de aristas incidentes en \( X \) (colapsado \( X \) como un sólo vértice).

Entonces ese número \( d_G(X) \) contando para cada vértice \( x\in X \) las aristas que lo unen con vértices fuera del conjunto \( X \); o lo que es lo mismo para cada vértice \( x\in X \) al total de aristas incidentes en \( x \), que es \( deg_G(x) \) restándole las aristas que unen \( x \) sólo con vértices de \( X, \) que es \( deg_{G[X ]}(x) \). Eso explica y demuestra la fórmula (*).

Saludos.