informatica

Ingeniería Mecánica
Aplicación de un algoritmo de reducción de grafos al Método de los Grafos Dicromáticos
 RESUMEN
El presente artículo propone una vía para la descomposición de grafos representativos de modelos matemáticos, de tal manera que se conservan las relaciones entre los vértices del grafo original. Para ello se definen las relaciones de equivalencia y las particiones necesariaspara la aplicación de un algoritmo de reducción de grafos a un grafo obtenido a partir de la aplicación del Método de los Grafos Dicromáticos, dicho método ha sido utilizado en función del diseño racional y de la solución de problemas computacionales en ingeniería mecánica. La propuesta constituye un aporte para el análisis de modelos matemáticos de grandes dimensiones, así como para facilitar laautomatización del mencionado método.
METODOS 
A continuación se enuncian notaciones y definiciones tomadas de [28] necesarias para la comprensión de los resultados presentados:
Definición 1: Se denomina partición del conjunto A, a una clase P de subconjuntos de A que satisface las siguientes condiciones:

Definición 2: Sean los conjuntos A y B no necesariamente distintos, se dice que R es unarelación binaria de A en B si R es un subconjunto de pares ordenados A×B, es decir si R ⊆ A×B.
Si A=B, entonces se dice que R es una relación binaria en A.
Definición 3: Una relación binaria R en un conjunto A es una relación de equivalencia si y sólo si R es reflexiva, simétrica y transitiva.
Definición 4: Sea R una relación de equivalencia entre los elementos de un conjunto A y sea a âˆˆ A,se denomina clase de equivalencia por R de a y se denota mediante [a] al conjunto de las x, x âˆˆ A, que mantienen con a la relación R, es decir. [a]={x|(a,x) âˆˆ R}.
Definición 5: Sea un grafo G=(V,E) y una relación de equivalencia R sobre V, vi es interior si ∀vj âˆˆ V, tal que vi y vj son adyacentes se cumple que R(vi,vj) ([vi]=[vj]). En otro caso vi es exterior.
Definición 6: Se denominacamino desde el vértice vi al vértice vj en un grafo G=(V,E) a la secuencia de vértices Ca=v1,v2,…,vn, si 
A partir de las definiciones anteriores, los autores enuncian la siguiente definición de grafo reducido:
Definición 7: Sean G y Gr dos grafos y Rr un conjunto de reglas de reescritura de grafos, se dice que Gr es un grafo reducido a partir de G, si al aplicar las reglas de reescrituraespecificadas en Rr al grafo Gr se obtiene el grafo G.
Breve descripción del Método de los Grafos Dicromáticos
En la figura 1 se puede apreciar el esquema de ejecución del MGD. Inicialmente se construye el grafo del modelo, cuyos vértices representan las variables con un color y las ecuaciones (relaciones) con otro y las aristas simbolizan cuáles variables se encuentran en cada ecuación. Una vezplanteado un problema de cómputo determinado, se descartan de dicho grafo las variables de entrada (datos), quedando transformado así en el grafo de la situación. A partir de este, suprimiendo las componentes conexas (islas) que no contengan variables de salida, se obtiene el grafo del problema. Este último grafo es sometido a un pareo que orienta, hacia su correspondiente variable, a una sola de lasaristas conectadas con cada ecuación, de modo que el mismo sea un pareo máximo. Así pasa a obtenerse una nueva representación llamada grafo del problema pareado. Posteriormente se obtiene el grafo del resolvente, asignándole orientación, de variable a ecuación, a las aristas que aún no la tienen. Para los problemas que no pueden ser caracterizados plenamente, a partir de este grafo del resolventees necesario obtener un nuevo grafo llamado problema canónico (si el problema tiene un pareo perfecto ya se encuentra en su forma canónica) y de este se llega al resolvente definitivo. A partir de dicho resolvente (que ya se encuentra en su forma canónica) se alcanza el grafo del algoritmo descartando los caminos que no conducen a ninguna de las variables de salida definidas al plantear el...