Autor Tema: Suma del grado de todos los vertices de un grafo G

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

12 Septiembre, 2019, 08:17 am
Leído 1036 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 \) la suma del grado de todos los vertices es igual a dos veces el número de aristas.
"Haz de las Matemáticas tu pasión".

12 Septiembre, 2019, 09:08 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 \) la suma del grado de todos los vertices es igual a dos veces el número de aristas.

Ten en cuenta que el grado de un vértice es el número de aristas incidentes en él.

Cada arista incide exactamente en dos vértices.

Por tanto la suma del grado de todos los vértices es el doble del número de aristas.

Saludos.

18 Noviembre, 2019, 03:39 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 \) la suma del grado de todos los vertices es igual a dos veces el número de aristas.

Ten en cuenta que el grado de un vértice es el número de aristas incidentes en él.

Cada arista incide exactamente en dos vértices.

Por tanto la suma del grado de todos los vértices es el doble del número de aristas.

Saludos.

Muchas Gracias, estaba pensando si existe una demostracion mas formal para este problema. Matematicamente, se tiene:

Para todo grafo \( G=(V,E) \), se tiene que \( \displaystyle\sum_{v\in V}\deg(v)=2|E|. \)
"Haz de las Matemáticas tu pasión".

18 Noviembre, 2019, 08:21 am
Respuesta #3

Luis Fuentes

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

Muchas Gracias, estaba pensando si existe una demostracion mas formal para este problema. Matematicamente, se tiene:

Para todo grafo \( G=(V,E) \), se tiene que \( \displaystyle\sum_{v\in V}\deg(v)=2|E|. \)

Tienes una concepción errónea de demostración. El argumento que te di es totalmente riguroso. Y parece que lo que te gusta es escribirlo de forma pedante, pensado que así queda mejor.  A larga eso es un error; porque normalmente en esas escrituras pedantes, se pierden las ideas; puede parecer muy formal, pero no se entiende lo que se ha hecho.

Deberías de reflexionar sobre ello. He perdido la cuenta de cuantos problemas sobre grafos has preguntado, sin aportar casi nada por tu parte. Y además no parece que veas más claros problemas elementales frente a otros que si son más complicados. Tu aparente obsesión por pruebas "formales", frente a entender las cosas me parece que no te está ayudando. Me gustaría que compartieses aquí que opinas sobre esto que digo, para poder ayudarte mejor. Obviamente es cosa tuya hacerlo o no.

Volviendo al problema, voy a reescribir la idea de forma pedante. Considera el conjunto de incidencia:

\( X=\{(a,v)\in Aristas\times Vertices|v\in a\} \)

Para cada vértice \( v\in V \) hay \( (a_1,v),\dots,(a_{deg(v)},v) \) elementos en \( X \), es decir un total de \( deg(v) \) elementos. Por tanto:

\( \displaystyle\sum_{v\in V}deg(v)=cardinal(X) \)

Para cada arista \( a\in Aristas \) hay \( (a,v),(a,v') \) elementos en \( X \), siendo \( v \) y \( v' \) los vértices que une \( a \). Por tanto:

\( cardinal(X)=\displaystyle\sum_{a\in Aristas}2=2cardinal(Aristas) \)

Saludos.