Determinar $d(Q_k)$ , $e(Q_k)$ , $|Q_k|$ para el gráfico y demostrar que es bipartito

Question

$a)$ Dejemos que $Q_k$ sea el gráfico cuyo conjunto de vértices corresponde al conjunto de todas las secuencias 01- de longitud k, con una arista entre dos vértices si las secuencias difieren exactamente en un lugar. Determine $d(Q_k)$ , $e(Q_k)$ , $|Q_k|$ .

$b)$ Demostrar que $Q_k$ es bipartita.

Answer 1

Comencemos con $d(Q_k)$ . Cada vértice está asociado a una cadena binaria de longitud $k$ . Por lo tanto, estará vinculado a todos (y sólo) los vértices asociados a la cadena obtenida al cambiar exactamente un dígito (por ejemplo, el vértice $000\dots 0$ será adyacente a $10\dots 0$ , $010\dots 0$ etc.) Significa que cada vértice está vinculado exactamente a $k$ otros vértices. Así que $d(Q_k)=k$ .

Obsérvese que el número de cadenas binarias de longitud $k$ es $2^k$ Así que $|Q_k|=2^k$ .

Como hemos determinado el número de nodos y el número de aristas por nodo, es fácil encontrar $e(Q_k)=d(Q_k)|Q_k|/2=k2^{k-1}$ .

Para demostrar que es bipartito, basta con observar que un vértice con un número impar de $0$ s sólo pueden ser adyacentes a un vértice con n número par de $0$ s, ya que requiere que difieran exactamente en un lugar. Por lo tanto, los conjuntos de vértices $A:=\{x:x$ tiene un número par de $0$ s $\}$ y $B:=\{x:x$ tiene un número impar de $0$ s $\}$ describen una bipartición del gráfico.