Dados los vértices y los bordes de un gráfico, ¿cómo se verifica que el gráfico sea un hipercubo?

Answer 1

Aunque se desconoce si el problema general del isomorfismo del gráfico se puede resolver de manera eficiente, en este caso específico, podemos explotar la estructura regular del gráfico del hipercubo para encontrar un isomorfismo en el tiempo polinomial.

Para un gráfico [matemático] G [/ matemático], deje que [matemático] G ^ * [/ matemático] sea el gráfico definido contrayendo caras cuadradas a aristas y aristas a vértices:

• Los vértices de [matemática] G ^ * [/ matemática] son ​​los bordes dirigidos [matemática] (u, v) [/ matemática] de [matemática] G [/ matemática].
• [math] ((u, v), (u ‘, v’)) [/ math] es un borde de [math] G ^ * [/ math] si y solo si [math] (u, v, v ‘ , u ‘) [/ math] es un (no trivial) de 4 ciclos en [math] G [/ math].

Entonces, [matemática] G [/ matemática] es un gráfico de hipercubos [matemática] n [/ matemática] si y solo si [matemática] G [/ matemática] tiene vértices [matemáticos] 2 ^ n [/ matemáticos], [matemática ] n2 ^ {n-1} [/ math] bordes, y (si [math] n> 0 [/ math]) un componente conectado arbitrario de [math] G ^ * [/ math] es un [math] (n – 1) Gráfico de hipercubo [/ math].

Si es así, a partir de un etiquetado de ese componente de [math] G ^ * [/ math] con [math] (n – 1) [/ math] -bit cadenas, podemos recuperar un etiquetado de [math] G [/ math ] con [math] n [/ math] -bit cadenas: si [math] (u, v) [/ math] está etiquetado [math] b_0b_1 \ ldots b_ {n-2} [/ math], entonces [math] u [/ math] puede etiquetarse [math] b_0b_1 \ ldots b_ {n-2} 0 [/ math] y [math] v [/ math] puede etiquetarse [math] b_0b_1 \ ldots b_ {n-2} 1 [/matemáticas].

Answer 2

Primero verifica el número de vértices. Para que el gráfico sea un hipercubo, necesita vértices [matemáticos] 2 ^ n [/ matemáticos] para algunos [matemáticos] n [/ matemáticos]. Si existe una [matemática] n [/ matemática], verifique que el grado de cada vértice sea [matemática] n [/ matemática].

Ahora intentaremos construir el isomorfismo entre el gráfico dado [matemática] G [/ matemática] y el n-hipercubo. A continuación, usaré cadenas de [matemáticas] n [/ matemáticas] 0s y 1s para denotar los vértices del hipercubo.

Comenzamos eligiendo un vértice arbitrario de [math] G [/ math]. Etiquetamos este vértice 00 … 00 y sus vecinos (en cualquier orden) obtendrán todas las etiquetas posibles con un solo 1.

Ahora deduciremos las etiquetas para todos los demás vértices. Para hacerlo, simplemente procesamos todas las cadenas de bits restantes en orden lexicográfico. Mostraré la construcción en un ejemplo. Queremos determinar qué vértice de [matemáticas] G [/ matemáticas] debería obtener la etiqueta z = 1001010. Encuentre los dos últimos 1s en esta cadena (tenga en cuenta que hay al menos dos de ellos). Sea u = 1000010, v = 1001000 yw = 1000000 los tres vértices que obtenemos al cambiar algunos de esos 1s a 0s. Tenga en cuenta que las tres etiquetas u, v, w ya se han asignado a algunos vértices en [math] G [/ math]. En el hipercubo, u y v tienen exactamente dos vecinos en común: z y w. Por lo tanto, en [matemáticas] G [/ matemáticas] los vértices que se etiquetaron como u y v también deben tener dos vecinos en común: un vértice etiquetado w y un vértice no etiquetado. Ese vértice obtiene la etiqueta z.

Si algo falla durante esta fase, sabemos que [math] G [/ math] no es un hipercubo. De lo contrario, hacemos una verificación final: para cada borde de [math] G [/ math] verificamos que conecta dos vértices con etiquetas que solo difieren en un solo bit.

Answer 3

Expresar coordenadas de vértice en binario.
Examine todos los n (n-1) pares de vértices tomados de dos en dos.
Cuando las coordenadas difieren en un bit, deben estar unidas por un borde.
Cuando las coordenadas no difieren en un bit, no se deben unir.