Teoría de grafos repartir juego

Question

Los jugadores de Ruby y Bob dado un grafo no dirigido y un número $N$. Primera colores de Rubí $N$ vértices rojo, entonces Bob colores $N$ vértices azul (que debe ser distinta de la de Ruby opciones). Después, todos los demás puntos de la gráfica se dan el color de cualquier color que están más cerca de (camino más corto) con vínculos a la izquierda en blanco. El jugador con más de su color en la gráfica resultante es el que gana.

Puede que el primer jugador siempre gana (o lazo)?

Un poco de contexto: Este problema se me ocurrió de un móvil juego de puzzle. Mi conocimiento de la teoría de grafos es bastante mínima, por lo que no tengo mucha maquinaria para resolverlo (pero he pasado un rato con pequeños gráficos, siempre es capaz de encontrar una inmejorable estrategia para el primer jugador). Mis pensamientos son para marcar los puntos como tener una ventaja en comparación con sus vecinos, la máxima de que me imagino proporciona un triunfo con N=1. Para mayor N a pesar de que la dinámica de obtener mucho más difícil para mí expresar. No parece ser un aspecto de espaciado que no estoy seguro de cómo formalizar (quizá recogiendo los vértices que minimizar su menor distancia a cualquier punto).

También si alguien ha oído hablar de un problema similar antes (específicamente relacionadas con colorear un gráfico basado en el camino más corto para un color de vértice) o tiene referencias yo estaría encantado de leerlas, pero fue incapaz de encontrar mucho ya que no estoy seguro de qué buscar.

Answer 1

Creo que el primer jugador no siempre se puede garantizar un empate, incluso cuando $N=1$. Algunas observaciones:

• Dado un grafo $G$ y un subconjunto de vértices $X \subset V(G)$, siempre podemos modificar$G$, de modo que los jugadores están obligados a elegir un vértice en $X$: agregar un enorme conjunto independiente $I$ $G$y hacer que todos los vértices en $I$ adyacente sólo a los vértices en $X$, por lo que si un jugador juega fuera de $X$ y el otro que juega dentro de ella, entonces el jugador dentro de $X$ agarra todos los vértices en $I$ y gana incluso si el otro jugador obtiene todo lo demás.

• Este truco también nos permite asignar número entero no negativo pesos a los bordes, y calcular distancias de acuerdo a los pesos: subdividir cada borde de un número apropiado de veces, y elegir nuestro subconjunto $X$, de modo que el interior de los vértices de las filiales de los bordes no son factibles para jugar en. (Edit: Como originalmente escrito esto no funciona, porque los jugadores en la modificación de la gráfica de puntuación de puntos para las filiales de los bordes, pero creo que se puede hacer para trabajar si "blow up" de la real vértices en grandes pandillas o grandes conjuntos independientes, por lo que el valor de conseguir uno más "real vértice" supera con mucho el valor de los nuevos vértices dentro de todas las filiales de los bordes. Esta transformación no se muy preservar las reglas del juego: en el transformado gráfico, Bob es esencialmente permite elegir un vértice ya elegido por Alice, por lo que la transforma gráfico es más amigable con el Bob de la gráfica original, pero si el punto está por venir para arriba con un gráfico donde Bob puede garantizar una victoria, entonces esto no es un problema para nosotros.)

Una vez que hayas hecho estos trucos, creo que se puede crear una piedra-papel-tijeras escenario usando el bipartito completo gráfico de $K_{3,3}$. Decir que los tres vértices de una partita conjunto se $R,P,S$ y que los tres vértices de la otra serie se $X,Y,Z$. El vértice $R$ pesos $1,2,3$ $X,Y,Z$respectivamente; $P$ pesos $3,1,2$, e $S$ pesos $2,3,1$. Los jugadores sólo pueden jugar en $\{R,P,S\}$, a través de los trucos.

Ahora, si Alice recoge $R$, entonces Bob recoge $P$ y consigue $Y,Z$ frente a la de Alice $X$. ($S$ es equidistante a ambos $R$$P$). Si Alice recoge $P$, Bob recoge $S$ y consigue $X,Z$ frente a la de Alice $Y$. Si Alice recoge $S$, Bob recoge $R$ y consigue $X,Y$ frente a la de Alice $Z$.

Answer 2

Puedo demostrar que para el primer jugador (Ruby) es posible no perder en los casos más sencillos para la gráfica dada $G$ $n$ vértices.

1. La dominación número $\gamma(G)\le N$. De hecho, en este caso en su mover en el primer jugador puede asegurar que la red de vértices constituyen dominantes en su conjunto. A continuación, después de que el segundo jugador se mueva sólo $N$ vértices de color por él se convertirá en azul, porque no cualquier red vértice tiene un rojo vecino, así que si no era de color por el segundo jugador entonces se convierte en rojo si no tiene azul vecino o se queda en blanco en caso contrario.

2. El gráfico de $G$ es un árbol y $N=1$. Por Jordan el Teorema de 1869 (que he demostrado de forma independiente hace unas horas :-) ), $G$ tiene un vértice $v$ cuya eliminación se desconecta el árbol en componentes de tamaño en la mayoría de las $n/2$. Así que si el primer jugador de color en el vértice $v$, el segundo jugador después de que su movimiento va a hacer solo azul vértices de uno de los componentes conectados, cuyo tamaño es en la mayoría de las $n/2$. El resto de los vértices se volverá rojo.

3. El gráfico de $G$ es un ciclo. Deje que el primer jugador de color de las agujas del reloj vértices $v_1,\dots, v_N,v_{N+1}=v_1$ asegurando que su eliminación se desconecta el ciclo vital de los componentes cuyo tamaño difiere a la mayoría de los $1$. Deja que estos tamaños de ser$l$$l+1$. Para cualquier $i<N$ denotar el de las agujas del reloj camino (sin su segundo punto final) de un vértice $v_i$ a un vértice $v_{i+1}$$[v_i,v_{i+1})$. Considere la posibilidad de un componente $C$ delimitada por los vértices $v_i$$v_{i+1}$. Si el segundo jugador de color de un vértice $v$$C$, $C$ con sus dos límite de rojo los vértices se divide en dos rutas de $v_i,\dots, v$ $v,\dots, v_{i+1}$ con los criterios de valoración de diferentes colores. Por simetría, después de la final de colorear cada uno de ellos tendrá igual número de negro y rojo los vértices. Pero aquí el azul vértice $v$ fue contado dos veces, como un extremo de cada una de las rutas. Teniendo esto en cuenta, vemos que el segundo jugador no obtiene ningún beneficio a las agujas del reloj camino de $[v_i,v_{i+1})$. Si el segundo jugador de color de más de un vértice $v$$C$, entonces se puede asegurar a todos los vértices $[v_i,v_{i+1})$ pero $v_i$ ser azul, pero al costo de que todos los vértices a algunas de las agujas del reloj camino de $[v_j,v_{j+1})$ será de color rojo. Así que él gana en la mayoría de las $l+1$ vértices en$[v_i,v_{i+1})$, pero pierde al menos $l+1$ vértices en $[v_j,v_{j+1})$. Así se obtiene ninguna ganancia en este caso también.