Sí, hay de álgebra lineal y la gráfica teórica de los resultados para este juego, para cualquier arreglo de interruptores y a partir de toda la posición de apagado.
Observe que usted puede construir un gráfico simple de la disposición de las luces, por la toma de las luces de los vértices, y hacer de ellos adyacentes en el grafo si son vecinos.
Gráfico teórico:
(Esto se puede encontrar aquí: Problema 17 en http://books.google.com/books?id=e99fXXYx9zcC&pg=PA42)
La proposición A: Dado un grafo simple gráfico de $G(V,E)$, con conjunto de vértices $V$ y el conjunto de borde $E$, se puede particionar $V$ en dos conjuntos de $V_1$ $V_2$ tal que
$\forall y \in V_1, \ \ |\{ x: \{x,y\} \in E \wedge x \in V_1\}| = 0 \mod 2$
$\forall y \in V_2, \ \ |\{ x: \{x,y\} \in E \wedge x \in V_1\}| = 1 \mod 2$
es decir, en cada vértice $V_1$ es incidente a un incluso el número de vértices en $V_1$ y cualquier vértice no en $V_1$ (es decir, en $V_2$) es incidente a un extraño número de vértices en $V_1$.
$\circ$
Por lo que la selección de los vértices en $V_1$ va a encender todas las luces, si empezamos desde la posición de apagado.
Prueba:
Hacemos frente a un problema muy estrechamente relacionado con.
En primer lugar demostrar que:
La proposición B: Dado un grafo simple gráfico de $G(V,E)$, no es una partición del conjunto de vértices $G$, $V = V_1 \cup V_2$ tal que
$\forall y \in V_1, \ \ |\{ x: \{x,y\} \in E \wedge x \in V_1\}| = 0 \mod 2$
$\forall y \in V_2, \ \ |\{ x: \{x,y\} \in E \wedge x \in V_2\}| = 0 \mod 2$
es decir, en cada vértice $V_1$ es adyacente a un incluso el número de vértices en $V_1$, y en cada vértice $V_2$ es adyacente a un incluso el número de vértices en $V_2$.
$\circ$
La prueba de la Proposición B es por inducción sobre el número de vértices en $G$.
La Base de los casos son fáciles.
Supongamos $G$ $n+1$ vértices. Si todos los vértices de $G$ tienen aún grado, se realiza, mediante la adopción de $V_2 = \emptyset$.
Supongamos $o$ es un vértice con grado impar y deje $o_1, o_2, \cdots, o_k$ ser los vecinos de $o$.
Forma de un gráfico de $G'$ como sigue: Si $o_i$ $o_j$ son adyacentes en $G$, que no son adyacentes en $G'$ y viceversa. También elimina $o$.
$G'$ es un gráfico con $n$ vértices.
Aplicar la hipótesis de inducción a $G'$. Decir que tenemos una partición de $V' = X \cup Y$.
Ahora $o$ debe ser incidente a un número par de vértices en uno de $X$ o $Y$. Decir $X$. Agregar $o$ $X$para obtener una partición para $G$. Podemos demostrar fácilmente que esta partición de $G$ es lo que necesitamos.
$\square$
Ahora a aplicar esto a nuestro problema (Proposición A):
Añadir un nuevo vértice $N$ a G y hacer que sea adyacente a cada vértice, incluso de grado en $G$ para obtener un nuevo gráfico de $G'$.
Aplicar la Proposición B a $G'$. Supongamos que la partición de la satisfacción de la proposición B es $V = X \cup Y$. Fácilmente se puede demostrar que esto es también la partición en $G$ (ignorando $N$) a favor de la proposición A.
Nota: Esto no sólo demuestra la existencia de una solución, pero la inducción de la prueba en realidad le da un O(n^3) tiempo de algoritmo para encontrar la solución.
Álgebra lineal Prueba debido a Noga Alon:
Más de $\mathbb{F}_2$, vamos a $A$ cualquier $n\times n$ matriz simétrica. Podemos demostrar que si $d$ es la diagonal del vector de $A$, $d$ está en el espacio generado por las filas de $A$.
Esto se desprende de la identidad (válido $\mathbb{F}_2$) que
$v^{T}Av = d^{T}v$ donde $u^{T}$ es la transpuesta de a $u$.
Por lo tanto si $v$ está en el espacio nulo de a$A$, $d$ es ortogonal a $v$, y como consecuencia, $d$ es en el espacio fila de a $A$.
Consideramos la matriz a se $B+I$ donde $B$ es la matriz de adyacencia del gráfico correspondiente tenemos, a partir de la disposición de las luces.
