Detección de amibas locales y globales. Algoritmos y resultados teóricos.

Ponente(s): Jorge René González Martínez, Marcos E. González Laffitte Amanda Montejano Cantoral

Dada una gráfica (grafo) $G$ un reemplazo de aristas es remover una arista $e\in G$ y añadir una arista $e'\in\bar{G}$. Se dice que el reemplazo de aristas es admisible, si la gráfica resultante $G'=G-e+e'$ es isomorfa a $G$. En este contexto definimos una amiba local como una gráfica $G$ tal que toda copia de $G$ en el conjunto de vértices $V(G)$ puede ser obtenida mediante una sucesión de reemplazos admisibles- De igual forma definimos una amiba global como una gráfica $G$ tal que $Gcup tK_1$ es amiba local, para algún $t>0$. .En esta charla mostramos algunos algoritmos para determinar si una gráfica es una amiba y algunas obstrucciones que encontramos al momento de tratar de hacer algoritmos más eficientes, el número de amibas de hasta 12 vértices y que casi toda gráfica no es una amiba.