En mi búsqueda en Google encontré mucha información sobre lo que la gente hace con los gráficos inductivos, pero ninguna definición. Así que te pregunto, StackExchange, ¿qué es un grafo inductivo? Cuando pienso en la inducción, pienso en la recursión. Pero debe ser una línea de pensamiento errónea, porque ¿no se pueden construir todos los grafos de forma recursiva? Gracias por aclarar mi confusión.
Respuestas
¿Demasiados anuncios?
Tikhon Jelvis
Puntos
121
Aparte de la respuesta teórica sobre grafos, "grafo inductivo" tiene otro significado en la programación funcional, sobre todo en Haskell. Es una representación funcional de un grafo que permite operaciones similares a los tipos de datos inductivos estándar (es decir, listas y árboles), útiles para escribir algoritmos de grafos en un estilo funcional. La idea fue introducida por Martin Erwig en "Grafos inductivos y algoritmos de grafos funcionales" y reificada en su biblioteca gráfica funcional (fgl).
En este contexto, un "tipo de datos inductivo" es uno como una lista o un árbol que se construye de forma única. Dado que sólo hay una forma de construir una lista o un árbol concreto, hay una única forma de coincidencia de patrones en él también. Los grafos, sin embargo, no tienen un orden natural de nodos o aristas, por lo que no son inductivos. (La estructura real que almacena el grafo es sólo un detalle de implementación).
El concepto central de los gráficos inductivos es que podemos ver un gráfico como un tipo de dato inductivo, aunque no se haya construido de esta manera. Podemos hacer coincidir patrones en un grafo y descomponerlo en un solo nodo, sus vértices y el resto del grafo. Sin embargo, como los grafos no son inductivos, hay más de una forma válida de descomponer un grafo de esta manera, por lo que perdemos la canonicidad de los tipos de datos inductivos reales. Esto se resuelve principalmente parametrizando la función de visualización con un nodo específico, permitiéndonos dirigir nuestra descomposición del grafo sobre la marcha.
Si quieres una introducción más descriptiva -con fotos- puedes leer un post que escribí sobre la idea en mi blog .
Los grafos inductivos se implementan eficientemente en términos de un mapa de árbol persistente entre los ids de los nodos (ints) y las etiquetas, basado en árboles patricios big-endianos . Esto permite realizar operaciones eficientes en la base inmutable, dejando que los grafos inductivos se comporten como cualquier otra estructura de datos inmutable y persistente.
Gudmundur Orn
Puntos
853
Para ser justos, yo también he utilizado los motores de búsqueda. Pero dime si alguno de estos te suena:
Wikipedia piensa que los grafos inductivos también pueden ser conocidos como grafos degenerados:
Por otro lado, el libro La teoría de los grafos define un gráfico inductivo en la página 13:
¿Coinciden con los tipos de gráficos inductivos que has estado viendo?
marzieh vahid
Puntos
11
Un gráfico $G$ es $d$ -inductivo si $G$ tiene como máximo $d$ vértices o $G$ tiene un vértice $u$ de grado como máximo $d$ tal que $G \setminus\{ u\}$ es $d$ -inductivo. Equivalentemente, $G$ es $d$ -Inductivo si sus vértices pueden ser numerados de manera que a lo sumo $d$ vecinos de cualquier vértice $v$ tienen números más altos que $v$ .
