Representación en cadena de 2-stratifices trivalentes con grupo fundamental trivial

Resumen

Proporcionamos un programa Python que es capaz de calcular e imprimir todos los distintos gráficos trivalentes simples conexos de 2-estratificies (ver Gómez-Larrañaga et al. en Topol Proc 52:329–340, 2018) salvo un número elegido de vértices blancos. Nuestro algoritmo utiliza las tres operaciones básicas descritas en (Gómez-Larrañaga et al. en Bol Soc Mat Mex 26:1301–1312, 2020) para construir nuevas gráficas a partir de un conjunto de gráficas. Repetimos este proceso para construir todos los gráficos deseados. El algoritmo incluye una optimización que reduce las repeticiones en la generación de los gráficos; esto se hace reconociendo los vértices blancos equivalentes de un gráfico bajo automorfismo. Usamos una variación del algoritmo AHU para identificar esos vértices y también para distinguir gráficos isomórficos en tiempo lineal. La cadena devuelta por el algoritmo AHU también se utiliza como función hash para buscar gráficos repetidos en tiempo constante amortizado.