22/02/2020, 00:59:17 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Puedes practicar LATEX con el cómodo editor de Latex online
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Conjuntos dominantes par e impar. Tª de Sutner.  (Leído 132 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Julio_fmat
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 2.083



Ver Perfil WWW
« : 18/11/2019, 01:43:00 »

Demuestre que para todo grafo [texx]G[/texx] existe [texx]W\subset V(G)[/texx] tal que todo vertice en [texx]W[/texx] tiene un numero par de vecinos en [texx]W[/texx] y todo vertice en [texx]V(G)/W[/texx] tiene un numero impar de vecinos en [texx]W.[/texx]
En línea

"Haz de las Matemáticas tu pasión".
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.007


Ver Perfil
« Respuesta #1 : 19/11/2019, 06:58:30 »

Hola

Demuestre que para todo grafo [texx]G[/texx] existe [texx]W\subset V(G)[/texx] tal que todo vertice en [texx]W[/texx] tiene un numero par de vecinos en [texx]W[/texx] y todo vertice en [texx]V(G)/W[/texx] tiene un numero impar de vecinos en [texx]W.[/texx]

Esto es un Teorema que en la bibliografía que he podido consultar se atribuye a Sutner. Aunque no tengo acceso al artículo al parecer está probado aquí:

Sutner, K. (1989). "Linear cellular automata and the garden-of-eden". The Mathematical Intelligencer, 11, 49-53.

No he llegado a encontrar la demostración completa; si algunas ideas (esencialmente aquí) que me permiten reconstruir una:

El problema se puede enfocar así. Sea [texx]A[/texx] la matriz de adyacencia de un grafo, es decir, una matriz [texx]n\times n[/texx] (siendo [texx]n[/texx] el número de vértices) que en la posición [texx]i,j[/texx] vale [texx]1[/texx] si los vértices [texx]i,j[/texx] están relacionados y cero otro caso.

Dado un subconjunto [texx]W[/texx] de vértices podemos asignarle un vector columna [texx]x[/texx], tal que [texx]x_i=1[/texx] si el vértice [texx]i[/texx] está en [texx]W[/texx] y cero en otro caso.

Tanto para el vector columna como para la matriz de adyacencia podemos suponer en lo sucesivo que trabajamos en el cuerpo [texx]\Bbb Z_2[/texx].

Entonces si consideramos el producto [texx]Ax[/texx] es un vector columna que en su posición [texx]i[/texx]-ésima:

- Vale [texx]0[/texx] si el vértice [texx]i[/texx] está unido con un número par de vértices de [texx]W[/texx], es decir, si el vértice [texx]i[/texx] tiene un número par de vecinos en [texx]W[/texx].
- Vale [texx]1[/texx] si el vértice [texx]j[/texx] está unido con un número impar de vértices de [texx]W[/texx], es decir, si el vértice [texx]i[/texx] tiene un número impar de vecinos en [texx]W[/texx].

Para que el conjunto [texx]W[/texx] cumpla lo pedido, [texx]Ax[/texx] tiene que valer [texx]0[/texx] en las posiciones donde [texx]x[/texx] vale [texx]1[/texx] (es decir los vértices de [texx]W[/texx] tienen que tener un número par de vecinos en [texx]W[/texx]) y tiene que valer [texx]1[/texx] en las posiciones donde [texx]x[/texx] vale [texx]0[/texx] (es decir los vértices de [texx]V(G)\setminus W[/texx] tienen que tener un número impar de vecinos en [texx]W[/texx]).

Esto equivale a que, si llamamos [texx]U[/texx] al vector formado sólo por [texx]1s[/texx] se cumpla:

[texx]Ax=U-x[/texx]

Equivalentemente:

[texx](A+Id)x=U[/texx]

Por tanto el problema así reformulado equivale a probar que: dada una matriz simétrica [texx]B\in {\cal M}_{n\times n}(\Bbb Z_2)[/texx] con unos en la diagonal, el sistema [texx]Bx=U[/texx] con [texx]U=(1,1,\ldots,1)^t[/texx] siempre tiene solución.

Lo anterior equivale a que probar que el vector [texx]U[/texx] está en el espacio imagen de la matriz [texx]B[/texx].

Ahora dado que [texx]B[/texx] es simétrica los espacios [texx]ker(B)[/texx] e [texx]Im(B)[/texx] son ortogonales suplementarios, es decir, [texx]Im(B)=ker(B)^\bot[/texx].

Spoiler (click para mostrar u ocultar)

Entonces para probar que [texx]U\in Im(B)[/texx] basta probar que [texx]U=(1,1,\ldots,1)^t\in ker(B)^\bot[/texx], es decir, que para todo [texx]v[/texx] tal que [texx]Bv=0[/texx] se cumple que [texx]v^tU=0[/texx].

Dado que trabajamos en [texx]\Bbb Z_2[/texx] lo anterior equivale a probar que si [texx]Bv=0[/texx] entonces [texx]v[/texx] tiene un número par de unos.

Veamos que esto es cierto por reducción al absurdo. Supongamos que [texx]v[/texx] tienen un número impar de unos. Que [texx]Bv=0[/texx] quieres decir que en cada fila, en las posiciones donde [texx]v[/texx] tiene unos, [texx]B[/texx] tienen en total un número par de unos.

Dicho de otra manera si restringimos [texx]B[/texx] a las filas y columnas donde [texx]v[/texx] tiene unos, tenemos una matriz [texx]B'[/texx] simétrica, con unos en la diagonal, de tamaño [texx]k\times k[/texx] (con k impar) y que en cada fila tiene un número par de unos. Por tanto el número total de unos de la matriz ha de ser par. Pero eso es falso, porque por ser simétrica si tiene [texx]m[/texx] unos por encima de la diagonal tiene también [texx]m[/texx] unos debajo de ella; y en la diagonal tiene [texx]k[/texx] unos. En total [texx]2m+k[/texx] unos; como [texx]k[/texx] es impar tiene un número impar de unos: contradicción.

Saludos.
En línea
Julio_fmat
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 2.083



Ver Perfil WWW
« Respuesta #2 : 20/11/2019, 23:35:26 »

Muchas Gracias, problema interesante.  Aplauso
En línea

"Haz de las Matemáticas tu pasión".
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!