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

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

06 Febrero, 2020, 12:39 am
Leído 910 veces

manooooh

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,054
  • 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

06 Febrero, 2020, 02:39 am
Respuesta #1

manooooh

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,054
  • 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, 07:37 am
Respuesta #2

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • 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.