Preguntas etiquetadas con graph-theory

22
Generar un laberinto de defensa de la torre, también conocido como Encontrar los K nodos más vitales ("interdicción de nodo a nodo") en un gráfico de cuadrícula no ponderado

En un juego de defensa de la torre, tienes una grilla NxM con un inicio, un final y una serie de paredes. Los enemigos toman el camino más corto de principio a fin sin atravesar ninguna pared (generalmente no están limitados a la cuadrícula, pero por simplicidad, digamos que lo están. En...

22
Gráficos en los que todos los caminos más cortos son únicos

Estoy buscando gráficos conectados, no ponderados y no direccionados , en los que para cada par , hay una ruta única que se da cuenta de la distancia .G=(V,E)G=(V,E)G=(V,E)u,v∈Vu,v∈Vu,v \in Vu→vu→vu \rightarrow vd(u,v)d(u,v)d(u,v) ¿Es esta clase de gráficos bien conocida? ¿Qué otras propiedades...

22
Flujo eléctrico plano exacto

Considere una red eléctrica modelada como un gráfico plano G, donde cada borde representa una resistencia de 1Ω. ¿Qué tan rápido podemos calcular la resistencia efectiva exacta entre dos vértices en G? De manera equivalente, ¿qué tan rápido podemos calcular la corriente exacta que fluye a lo largo...

22
Problemas NP-hard en caminos

todo el mundo sabe que existen muchos problemas de decisión que son NP-hard en gráficos generales, pero estoy interesado en problemas que son incluso NP-hard cuando el gráfico subyacente es un camino. Entonces, ¿me pueden ayudar a resolver esos problemas? Ya he encontrado una pregunta relacionada...

21
Colorear Gráficos Planos

Considere el conjunto de gráficos planos donde todas las caras internas son triángulos. Si hay un punto interior de grado impar, el gráfico no puede ser de tres colores. Si cada punto interior tiene un grado par, ¿puede ser siempre de tres colores? Idealmente, me gustaría un pequeño...