Autor Tema: Vertices de un grafo 2

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

24 Septiembre, 2019, 02:39 am
Leído 979 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Determine si es verdadera o falsa la siguiente afirmacion: Todo grafo con al menos dos vertices tiene dos vertices distintos \( u \) y \( v \) tal que \( \left |{N(u)}\right |=\left |{N(v)}\right |. \)
"Haz de las Matemáticas tu pasión".

24 Septiembre, 2019, 07:23 am
Respuesta #1

martiniano

  • Moderador Global
  • Mensajes: 1,285
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Se demuestra que es verdadera por reducción al absurdo. Supón que existe un grafo en el que los grados de todos los vértices son distintos. Si un grafo simple tiene \( n \) vértices, el grado de uno de ellos puede tomar \( n \) valores, los que hay entre \( 0 \) y \( n-1 \). Como hay \( n \) vértices y \( n \) valores a tomar no quedará ningún valor sin ser tomado. Ahora bien, el vértice con grado \( 0 \) no está conectado con ningún otro, sin embargo, el que tiene grado \( n-1 \) está conectado con todos los demás. Esto es contradictorio, por lo tanto el enunciado es verdadero.

Un saludo

18 Noviembre, 2019, 03:09 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.

Se demuestra que es verdadera por reducción al absurdo. Supón que existe un grafo en el que los grados de todos los vértices son distintos. Si un grafo simple tiene \( n \) vértices, el grado de uno de ellos puede tomar \( n \) valores, los que hay entre \( 0 \) y \( n-1 \). Como hay \( n \) vértices y \( n \) valores a tomar no quedará ningún valor sin ser tomado. Ahora bien, el vértice con grado \( 0 \) no está conectado con ningún otro, sin embargo, el que tiene grado \( n-1 \) está conectado con todos los demás. Esto es contradictorio, por lo tanto el enunciado es verdadero.

Un saludo

Muchas Gracias, pero por ejemplo, si consideramos un segmento (grafo) \( 1 \)-regular de vertices \( u \) y \( v \) tal que \( u\ne v \), tenemos que puede suceder que \( |N(u)|=\text{deg } u=0 \) y \( |N(v)|= \text{deg } v=1 \), porque el grafo es \( 1 \)-regular. Entonces, bajo esta hipotesis no se tendria la igualdad de los grados..¿o estoy equivocado?
"Haz de las Matemáticas tu pasión".

18 Noviembre, 2019, 07:50 am
Respuesta #3

Luis Fuentes

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

Muchas Gracias, pero por ejemplo, si consideramos un segmento (grafo) \( 1 \)-regular de vertices \( u \) y \( v \) tal que \( u\ne v \), tenemos que puede suceder que \( |N(u)|=\text{deg } u=0 \) y \( |N(v)|= \text{deg } v=1 \), porque el grafo es \( 1 \)-regular. Entonces, bajo esta hipotesis no se tendria la igualdad de los grados..¿o estoy equivocado?

Bufff. Pero si tienes un segmento los dos vértices tienen grado \( 1 \) (cada vértice está conectado con el otro).  ¿Por qué dices que \( |N(u)|=0 \)?. Eso está mal.

Saludos.

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

Muchas Gracias, pero por ejemplo, si consideramos un segmento (grafo) \( 1 \)-regular de vertices \( u \) y \( v \) tal que \( u\ne v \), tenemos que puede suceder que \( |N(u)|=\text{deg } u=0 \) y \( |N(v)|= \text{deg } v=1 \), porque el grafo es \( 1 \)-regular. Entonces, bajo esta hipotesis no se tendria la igualdad de los grados..¿o estoy equivocado?

Bufff. Pero si tienes un segmento los dos vértices tienen grado \( 1 \) (cada vértice está conectado con el otro).  ¿Por qué dices que \( |N(u)|=0 \)?. Eso está mal.

Saludos.

Gracias, ahora me quedo claro, pensaba que \( u \) era un vertice aislado, pero no, ambos están conectados por una arista.

Saludos.
"Haz de las Matemáticas tu pasión".