Una implementación del cálculo de la deficiencia de un grafo (bi)orientado

Ponente(s): Juan Antonio Vega Garfias, Dra. Mireya Paredes

Una biorientación de aristas de un grafo simple consiste en reemplazar cada una de sus aristas {x,y}, o bien por la arista (x,y) o la arista (y,x) o por el par de aristas (x,y) y (y,x). Si el digrafo resultante tiene aristas paralelas, se llama grafo biorientado, y en caso contrario, grafo orientado. Los ideales tóricos son una clase especial de ideales primos en un anillo de polinomios, los cuales son generados por binomios. Sea D’ un grafo (bi)orientado y sea P_D’ el ideal tórico asociado a D’. La deficiencia de D’, denotada por def(D’), es la diferencia entre el mínimo número de generadores binomiales de P_D’ y la altura ht(P_D’). En particular, decimos que un grafo no-dirigido G es una intersección completa binomial si para cada grafo orientado D cuyo grafo subyacente es G se tiene: def(D)=0. En este poster mostraremos una implementación para calcular la deficiencia de un grafo (bi)orientado; además, una implementación de un algoritmo polinomial para decidir si G es una intersección completa binomial.