Autor Tema: Vértices de un grafo

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

12 Septiembre, 2019, 08:28 am
Leído 1290 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 grafo \( G \) tiene un vértice \( v \) tal que \( d(v)\le 2m(G)/n(G) \) y un vértice \( w \) tal que \( d(w)\ge 2m(G)/n(G). \).
Decida si es posible afirmar que todo grafo tiene un vértice \( v \) tal que \( d(v)<2m(G)/n(G). \)


Hola, ¿cómo puedo resolver este problema?
"Haz de las Matemáticas tu pasión".

12 Septiembre, 2019, 09:35 am
Respuesta #1

Luis Fuentes

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

Demuestre que todo grafo \( G \) tiene un vertice \( v \) tal que \( d(v)\le 2m(G)/n(G) \) y un vertice \( w \) tal que \( d(w)\ge 2m(G)/n(G). \) Decida si es posible afirmar que todo grafo tiene un vértice \( v \) tal que \( d(v)<2m(G)/n(G). \)


Hola, ¿cómo puedo resolver este problema?

Es bueno que aclares la notación. ¿A qué llamas \( m(G) \) y \( n(G) \)?.

Saludos.

14 Septiembre, 2019, 07:18 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 grafo \( G \) tiene un vertice \( v \) tal que \( d(v)\le 2m(G)/n(G) \) y un vertice \( w \) tal que \( d(w)\ge 2m(G)/n(G). \) Decida si es posible afirmar que todo grafo tiene un vértice \( v \) tal que \( d(v)<2m(G)/n(G). \)


Hola, ¿cómo puedo resolver este problema?

Es bueno que aclares la notación. ¿A qué llamas \( m(G) \) y \( n(G) \)?.

Saludos.

Hola,

\( m(G)=\left |{E(G)}\right | \) denota a la cardinalidad del conjunto de aristas de \( G \) y \( n(G)=\left |{V(G)}\right | \) denota la cardinalidad del conjunto de vertices de \( G \).
"Haz de las Matemáticas tu pasión".

15 Septiembre, 2019, 10:12 pm
Respuesta #3

Luis Fuentes

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

\( m(G)=\left |{E(G)}\right | \) denota a la cardinalidad del conjunto de aristas de \( G \) y \( n(G)=\left |{V(G)}\right | \) denota la cardinalidad del conjunto de vertices de \( G \).

Bien en ese caso recuerda que en otro hilo viste que la suma de grados de todos los vértices es el doble del número de aristas:

\( \displaystyle\sum_{v\in V}deg(v)=2m \)

Entonces:

1) Supón que para todo \( v\in B \) se cumple que \( deg(v)<2m/n \) y llega a una contradicción.
2) Supón que para todo \( v\in B \) se cumple que \( deg(v)>2m/n \) y llega a una contradicción.
3) Para la última cuestión piensa por ejemplo en el grafo completo \( K_3 \).

Saludos.

18 Noviembre, 2019, 04:55 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

\( m(G)=\left |{E(G)}\right | \) denota a la cardinalidad del conjunto de aristas de \( G \) y \( n(G)=\left |{V(G)}\right | \) denota la cardinalidad del conjunto de vertices de \( G \).

Bien en ese caso recuerda que en otro hilo viste que la suma de grados de todos los vértices es el doble del número de aristas:

\( \displaystyle\sum_{v\in V}deg(v)=2m \)

Entonces:

1) Supón que para todo \( v\in B \) se cumple que \( deg(v)<2m/n \) y llega a una contradicción.
2) Supón que para todo \( v\in B \) se cumple que \( deg(v)>2m/n \) y llega a una contradicción.
3) Para la última cuestión piensa por ejemplo en el grafo completo \( K_3 \).

Saludos.

Muchas Gracias, entonces tenemos lo siguiente:

1) Supongamos que para todo \( v\in B \) se tiene que \( d(v)=\deg(v)>\dfrac{2m}{n}\hspace{1.0cm} (1) \).

Como \( \displaystyle\sum_{v\in V}\deg(v)=2m \), entonces aplicando sumas en ambos miembros de (1) tenemos que \( \displaystyle\sum_{v\in V}\deg(v)>\displaystyle\sum_{v\in V} \dfrac{2m}{n} \), esto implica que \( 2m>n\left(\dfrac{2m}{n} \right)\implies 2m>2m \), contradiccion. Por lo tanto, \( d(v)\le \dfrac{2m(G)}{n(G)}. \)

2) Aqui pienso que te equivocaste en el vertice y en la desigualdad, es al reves... Deberia ser para todo \( w\in B \) se tiene que \( d(w)<\dfrac{2m(G)}{n(G)}\hspace{1.0cm} (2). \) En forma analoga, como \( \displaystyle\sum_{v\in V}\deg(v)=2m \), tenemos que aplicando sumas en (2) se tiene \( \displaystyle\sum_{w\in V}\deg(w)<\displaystyle\sum_{w\in V}\dfrac{2m}{n} \), esto implica que \( 2m<n\left(\dfrac{2m}{n}\right)\implies 2m<2m \), contradiccion. Por lo tanto, \( d(w)\ge \dfrac{2m(G)}{n(G)}. \)

3) La parte 3) no me queda claro el ejemplo que diste...  :banghead:
"Haz de las Matemáticas tu pasión".

18 Noviembre, 2019, 08:28 am
Respuesta #5

Luis Fuentes

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

1) Supongamos que para todo \( v\in B \) se tiene que \( d(v)=\deg(v)>\dfrac{2m}{n}\hspace{1.0cm} (1) \).

Como \( \displaystyle\sum_{v\in V}\deg(v)=2m \), entonces aplicando sumas en ambos miembros de (1) tenemos que \( \displaystyle\sum_{v\in V}\deg(v)>\displaystyle\sum_{v\in V} \dfrac{2m}{n} \), esto implica que \( 2m>n\left(\dfrac{2m}{n} \right)\implies 2m>2m \), contradiccion. Por lo tanto, \( d(v)\le \dfrac{2m(G)}{n(G)}. \)

2) Aqui pienso que te equivocaste en el vertice y en la desigualdad, es al reves... Deberia ser para todo \( w\in B \) se tiene que \( d(w)<\dfrac{2m(G)}{n(G)}\hspace{1.0cm} (2). \) En forma analoga, como \( \displaystyle\sum_{v\in V}\deg(v)=2m \), tenemos que aplicando sumas en (2) se tiene \( \displaystyle\sum_{w\in V}\deg(w)<\displaystyle\sum_{w\in V}\dfrac{2m}{n} \), esto implica que \( 2m<n\left(\dfrac{2m}{n}\right)\implies 2m<2m \), contradiccion. Por lo tanto, \( d(w)\ge \dfrac{2m(G)}{n(G)}. \)

No me equivocado en nada. Lo que pasa es que lo que yo te he indicado en (1) tu lo has probado en (2) y viceversa.

Parece que das importancia al que el vértice se llame \( v \) o \( w \) y eso es intrascendente: ¡llámale como quieras!.

Esto vuelve a reafirmarme en la idea que me ronda por la cabeza cuando leo tus preguntas; intentas fijarte en el formalismo sin entender las ideas. Error.

Citar
3) La parte 3) no me queda claro el ejemplo que diste...  :banghead:

Pues sinceramente no entiendo que es lo que no te queda claro. ¿Has trabajado el ejemplo?.

1) ¿Sabes que grafo es \( K_3 \)?.
2) ¿Sabes cuantas aristas \( m \)  tiene?.
3) ¿Sabes cuantos vértices \( n \) tiene?
4) ¿Sabes calcular el grado de todos los vértices de \( K_3 \)?.
5) ¿Tiene el grafo \( K_3 \) algún vértice con \( deg(v)<2m/n \)?.

Saludos.