prueba $n$-cubo es bipartita

Question

prueba $n$-cube es un grafo bipartito todos $n\ge1$

Este es un problema en mi libro de texto y no puedo averiguar nada y tener una prueba en teoría de grafos mañana agradecería cualquier ayuda ya que no soy muy bueno con las pruebas

Answer 1

Cuando su $n$-cubo de etiquetado, puede asignar las cadenas de vértices de longitud $n$ $(00..0)$ $(11..1)$. Por ejemplo sería un $2$-cubo (o Plaza): %#% $ #% ahora se pueden definir dos subesets de su gráfico $$00\ 01\10\ 11$. Donde $G= (X,Y)$ {vértices que tienen un número par de %#% de #%} y $X=$ {vetices que tienen un número impar de %#% de #%}.

Creando un bordes {$1$} o {$Y=$} inicia en $1$ y $1,0$ se contabilizan todos los bordes y por lo tanto, el grafo son bipartito.

Answer 2

Sugerencia: Si un grafo es bipartito, que significa que puede teñirse los vértices tal que cada vértice negro se conecta a un vértice blanco y viceversa.

Sugerencia: Tener en cuenta la paridad de la suma de las coordenadas.

Answer 3

Los vértices del $n$-cube son vectores $(v_1,v_2,\ldots,v_n)$ $v_i\in{0,1}$ de las entradas. Dos vértices son adyacentes si y sólo si sus vectores representación difieren en exactamente una entrada.

Ahora la partición el vértice en dos subconjuntos, que consta de todos los vértices cuya representación vector tiene un número incluso (resp. impar) de $1$'s. Esta partición da un gráfico bipartito.