Demostrar que un grafo HyperCube está conectado, es decir, que hay un camino entre cada par de vértices.
He podido encontrar una prueba para el bipartito, pero tengo curiosidad por saber cómo está relacionado el hipercubo.
Respuestas
¿Demasiados anuncios?
rrirower
Puntos
230
OK, vamos a arreglar un natural $n$ . Dejemos que $X$ sea un conjunto con $n$ elementos.
El $n$ -se define como $G = (V, E)$ , donde $V = \mathcal{P}(X)$ es el conjunto de energía de $X$ y $E$ consiste en todos los pares de subconjuntos $A, B \subseteq X$ que difieren exactamente en un elemento.
Para cualquier $A, B \subseteq X$ , denotémoslo por $d(A, B)$ el número de elementos en el diferencia simétrica de $A$ y $B$ : $d(A, B) = |A \triangle B|$ .
Demostremos por inducción en $k$ la siguiente afirmación: para cada $A, B$ tal que $d(A, B) = k$ hay un camino en $G$ del vértice $A$ al vértice $B$ . Claramente, si conseguimos demostrar esto para todos los enteros no negativos $k$ demostraremos que $G$ está conectado.
La base de la inducción es fácil: para $k=0$ , si $d(A, B) = 0$ entonces $A \triangle B = \varnothing$ Así que $A=B$ y hay una ruta vacía desde $A$ a sí mismo.
Ahora la transición. Supongamos que hemos demostrado la afirmación para algún $k$ y $d(A, B) = k + 1$ . Tenemos que demostrar que hay un camino en $G$ de $A$ a $B$ . El conjunto $A \triangle B$ contiene $k+1$ elementos, por lo que es no vacía. Elija cualquier $x \in A \triangle B$ y establecer $C = A \triangle \{x\}$ .
$A$ y $C$ difieren en un solo elemento, por lo que hay un borde entre $A$ y $C$ . Queda por demostrar que hay un camino desde $C$ a $B$ . Observe que $$C \triangle B = (A \triangle \{x\}) \triangle B = (A \triangle B) \triangle \{x\} = (A \triangle B) \setminus \{x\}.$$ Entonces $d(C, B) = |(A \triangle B) \setminus \{x\}| = (k+1)-1 = k$ y por hipótesis de inducción existe un camino desde $C$ a $B$ . La prueba está completa.
PD: No veo ninguna relación con los grafos bipartitos completos. Sí, el grafo del hipercubo es bipartito, pero ¿y qué?
Jaded
Puntos
593
El gráfico del hipercubo $Q_n$ se define como el grafo con vértices establecidos las cadenas de bits de longitud $n$ (es decir $V(Q_n)=\{0,1\}^n$ ), con dos vértices adyacentes si y sólo si las cadenas de bits correspondientes difieren exactamente en una coordenada. Así, en $Q_4$ El vértice 0010 tiene 4 vecinos, y las cadenas de bits correspondientes a cada uno de los 4 vértices se pueden obtener volteando exactamente una de las 4 coordenadas de 0010. Así, sus 4 vecinos son 1010, 0110, 0000 y 0011.
Dadas dos cadenas de bits cualesquiera de longitud $n$ si difieren exactamente en $k$ coordenadas, entonces podemos empezar en la primera cadena, y volteando una de las $k$ coordenadas a la vez, para obtener finalmente la segunda cadena. Por lo tanto, existe un camino entre estos dos vértices de longitud exactamente $k$ . De hecho, este es también un camino más corto: el camino más corto entre dos vértices cualesquiera del hipercubo tiene una longitud exactamente igual al número de coordenadas en las que las dos cadenas correspondientes difieren en sus valores de bits. Cuando $k \ge 2$ hay muchos de estos caminos más cortos entre los dos vértices dados, ya que el orden en el que elegimos cuál de los $k$ bits a voltear durante cada paso no es único.
En $Q_6$ Los vértices 000000 y 111111 están a una distancia de 6, así como los vértices 111001 y 000110. El diámetro de $Q_n$ es $n$ .
