Autor Tema: Dados un grafo, una relación de equivalencia responder consignas

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

05 Febrero, 2020, 08:39 pm
Leído 266 veces

manooooh

  • Matemático
  • Mensajes: 2.748
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola!

Sea un grafo \[ G=(V,A,\varphi) \] (\[ V \] vértices, \[ A \] aristas y \[ \varphi \] función de incidencia \[ \varphi\colon A\to V^{(2)} \], con \[ V^{(2)} \] conjunto de subconjuntos de \[ 1 \] o \[ 2 \] elementos de \[ V \]). En el conjunto de vértices \[ V \], se define la relación \[vRw\iff g(v)=g(w),\;\text{donde \(g\) es la función grado}.\] a) Demostrar que \[ R \] es de equivalencia.

b) Indicar las clases de equivalencia en un grafo bipartito completo \[ K_{n,m} \] y en un grafo completo \[ K_n \].

c) Indicar si es cierto: Si \[ a \] es arista puente, y \[ \varphi(a)=\{v_i,v_j\} \], entonces \[ \operatorname{cl}(v_i)=\operatorname{cl}(v_j) \].




a)

Reflexiva: Para todo \[ v\in V \] se cumple que \[ g(v)=g(v) \], por tanto \[ vRv \].

Simétrica: Para todo \[ v,w\in V \] si \[ vRw \] se tiene que \[ g(v)=g(w) \], luego por propiedad simétrica de la igualdad es \[ g(w)=g(v) \], de donde \[ wRv \].

Transitiva: Para todo \[ v,w,t \], si \[ vRw \] y \[ wRt \] entonces \[ g(v)=g(w) \] y \[ g(w)=g(t) \]. Luego por la propiedad transitiva de la igualdad, \[ g(v)=g(t) \], es decir \[ vRt \].

Por tanto \[ R \] es de equivalencia.



b) No sé cómo responder ???. Sé que la cantidad de vértices en un \[ K_{n,m} \] es \[ n+m \] y en un \[ K_n \] es \[ n \].



c) ¿Qué es la clase de equivalencia de un vértice \[ v \]?



¿Está bien el inciso (a)? ¿Qué hay del resto?

Gracias!!
Saludos

05 Febrero, 2020, 10:39 pm
Respuesta #1

manooooh

  • Matemático
  • Mensajes: 2.748
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Lo encontré resuelto por el profesor. El apartado (a) es tal cual. Luego dice:

b)

En un grafo bipartito completo \[ K_{n,m} \], si \[ n \] y \[ m \] son distintos, como los \[ n \] primeros vértices tienen todos grado \[ m \], conforman una clase de equivalencia, y los \[ m \] segundos vértices al tener todos grado \[ n \] son la otra clase de equivalencia.

¿Cómo se justifica que no hay más clases de equivalencia que las que genere \[ n \] y \[ m \]?

Por ejemplo, en el \[ K_{3,2} \], las clases son \[ \{v_1,v_2,v_3\} \] y \[ \{v_4,v_5\} \].

Si \[ n=m \], habría una sola clase. Por ejemplo, en el \[ K_{3,3} \], todos tienen grado \[ 3 \], conforman una única clase.

En un grafo completo \[ K_n \], como todos tienen grado \[ n-1 \], son una única clase de equivalencia.

Por ejemplo, en el \[ K_5 \], todos tienen el mismo grado: \[ 4 \].

c) Es falso. Un contraejemplo:


La arista \[ \{5,6\} \] es puente, y sin embargo \[ g(5)=3 \] y \[ g(6)=1 \], por lo tanto no están en la misma clase.

Saludos

06 Febrero, 2020, 03:37 am
Respuesta #2

Luis Fuentes

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

En un grafo bipartito completo \[ K_{n,m} \], si \[ n \] y \[ m \] son distintos, como los \[ n \] primeros vértices tienen todos grado \[ m \], conforman una clase de equivalencia, y los \[ m \] segundos vértices al tener todos grado \[ n \] son la otra clase de equivalencia.

¿Cómo se justifica que no hay más clases de equivalencia que las que genere \[ n \] y \[ m \]?

La idea es muy sencilla. Dos vértices están en la misma clase si y sólo si tienen el mismo grado.

En cada grafo hay tantas clases distintas como grados diferentes de vértices.

En un  grafo bipartito completo \[ K_{n,m} \] sólo hay vértices de grado \[ n \] y vértices de grado \[ m \].

Saludos.