Preguntas etiquetadas con graph-theory

15
Mantener el orden en una lista en

El problema de mantenimiento de la orden (o "mantener el orden en una lista") es apoyar las operaciones: singleton: crea una lista con un elemento, le devuelve un puntero insertAfter: dado un puntero a un elemento, inserta un nuevo elemento después de él, devolviendo un puntero al nuevo...

15
Subgrafiar isomorfismo con un árbol

Si tenemos un gran gráfico (dirigido) y un árbol enraizado más pequeño H , ¿cuál es la complejidad más conocida para encontrar subgrafías de G isomorfas a H ? Soy consciente de los resultados para el isomorfismo de subárbol donde G y H son árboles y también donde G es plano o tiene un ancho de...

14
Golpear ciclos impares

¿Se sabe algo sobre el siguiente problema? ¿Tiene sentido? Como se llama ¿Es trivialmente equivalente a algún otro problema? ¿Cuál es la complejidad del tiempo? Dado un gráfico G = (V, E) no dirigido (general / planar / acotado / etc.), Encuentre un subconjunto máximo de aristas E ', de modo que...

14
¿Es la equivalencia eta para funciones compatible con la operación seq de Haskell?

Lema: Suponiendo equivalencia eta tenemos eso (\x -> ⊥) = ⊥ :: A -> B. Prueba: ⊥ = (\x -> ⊥ x)por equivalencia eta y (\x -> ⊥ x) = (\x -> ⊥)por reducción bajo la lambda. El informe Haskell 2010, sección 6.2 especifica la seqfunción mediante dos ecuaciones: seq :: a -> b ->...