Autor Tema: Grafo regular

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

23 Septiembre, 2019, 01:55 pm
Leído 994 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Sea \( G \) un grafo regular. ¿Es \( \overline{G} \) regular?

Hola, me dan como Hint usar que \( d_G(v)+d_{\overline{G}}(v)=n-1,
\forall v\in V \). Use reduccion al absurdo.

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

23 Septiembre, 2019, 03:42 pm
Respuesta #1

martiniano

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

¿Dónde te has quedado exactamente? ¿No sabes lo que quiere decir que un grafo sea regular? ¿No entiendes lo que quiere decir \( \bar{G} \)? ¿O acaso \( d_G(v) \)?

Conociendo todo esto la respuesta es bastante inmediata. Un saludo.

24 Septiembre, 2019, 02:28 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

digamos que si, no tengo clara la definición de grafo regular :banghead:. ¿Me puedes ayudar?
"Haz de las Matemáticas tu pasión".

24 Septiembre, 2019, 07:13 am
Respuesta #3

martiniano

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

Un grafo es regiar cuando todos sus vértices tienen el mismo grado, es decir, cuando en cada vértice incide el mismo número de aristas. En la notación que has usado para la ayuda, el grado de un vértice \( v \) en un grafo \( G \) es \( d_G(v) \). ¿Cómo lo ves ahora?

15 Noviembre, 2019, 04:36 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
Sí, claro.

Un grafo es regiar cuando todos sus vértices tienen el mismo grado, es decir, cuando en cada vértice incide el mismo número de aristas. En la notación que has usado para la ayuda, el grado de un vértice \( v \) en un grafo \( G \) es \( d_G(v) \). ¿Cómo lo ves ahora?

Gracias, lo resolvi de la siguiente manera, no se si esta bien, por favor corrijanme si hay algo incorrecto.

Como \( d_G (v)+d_{\overline{G}} (v)=n-1, \forall v\in V \) tenemos que al aplicar maximo esto es

\( \displaystyle\max_{v\in V(G)} d_G (v)+\displaystyle\max_{v\in V(\overline{G})}d_{\overline{G}}(v)=n-1\hspace{8.0mm} (1) \)

Del mismo modo, al aplicar minimo tenemos que

\( \displaystyle\min_{v\in V(G)}d_G (v)+\displaystyle\min_{v\in V(\overline{G})}d_{\overline{G}} (v)=n-1\hspace{8.0mm} (2) \)

Por (1) y (2) tenemos que \( \Delta (G)+\displaystyle\max_{v\in V(\overline{G})} d_{\overline{G}} (v)=\delta (G)+\displaystyle\min_{v\in V(\overline{G})} d_{\overline{G}} (v) \), pero dado que \( G \) es regular, tenemos que

\( \displaystyle\max_{v\in V(\overline{G})} d_{\overline{G}} (v)=\displaystyle\min_{v\in V(\overline{G})} d_{\overline{G}} (v)\implies \Delta (\overline{G})=\delta(\overline{G}). \) Por tanto, \( \overline{G} \) es regular.

PD.: La tecnica por reduccion al absurdo no se me ocurrio..
"Haz de las Matemáticas tu pasión".

15 Noviembre, 2019, 07:57 am
Respuesta #5

Luis Fuentes

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

Gracias, lo resolvi de la siguiente manera, no se si esta bien, por favor corrijanme si hay algo incorrecto.

Te complicas innecesariamente y no está bien.

Citar
Como \( d_G (v)+d_{\overline{G}} (v)=n-1, \forall v\in V \) tenemos que al aplicar maximo esto es

\( \displaystyle\max_{v\in V(G)} d_G (v)+\displaystyle\max_{v\in V(\overline{G})}d_{\overline{G}}(v)=n-1\hspace{8.0mm} (1) \)

Esto no es cierto en general. Que los elementos de dos conjuntos aparejados dos a dos sumen constante, no quiere decir que los máximos tengan esa suma. Por ejemplo:

\( 1+5=2+4=6 \).

Pero no es cierto que \( max\{1,5\}+max\{2,4\}=6 \).

En tu caso si es cierto que se cumple la propiedad, pero porque el grafo es regular; pero eso habría que aclararlo y detallarlo.

Es mucho más sencillo. Si el grafo es regular \( d_G(v)=k \) para todo \( v\in V \). Pero entonces:

\( d_{\bar G}(v)=n-1-d_G(v)=n-1-k \) para todo \( v\in V \)

y por tanto el complementario es regular.

Saludos.