El modelo eléctrico de conductancias aplicado al isomorfismo de grafos : el método de la estrella

Abstract

The first objective proposed in the research of this thesis was the select and develop a (preferably simple) model for graphs, thus, the results obtained through the model may be extrapolated to the modeled objects: graphs. The theory associated with the model has to be consolidated, mature, closed and, therefore, accepted by all. The second objective proposed in the research, once selected and developed a model, was the design of an application of the model that would address the graph isomorphism problem. The third and final objective was to experimentally test the model and the application. The first objective resulted in the selection and development of an electric model in which applies the Circuit Theory meeting the requirements above mentioned. This model will be called "Conductance Electrical Model" (CEM). In the CEM graphs are transformed into electrical circuits of pure resistive concentrated parameters (without sources, inductors or capacitors) preserving the topology of the graph. From this point opens lots of possibilities with only contemplate the CEM obtained from one or more graphs. The computational complexity of obtaining of the CEM of a graph is always polynomial of order two according to the graph degree. Obtaining the CEM is always deterministic (it is not probabilistic, is not recursive and is not iterative). Graphs (weighted or not) that apply the CEM should be undirected and unlabeled nodes. The second objective resulted in the design of the "Star Method" (SM) which, from the CEM, allows to approach the open problem of isomorphism of graphs. Before applying the SM gets the CEM of two graphs of degree N, then SM begins from the two circuits that model, each one of them, a graph. It is advisable (but in any case optional) to perform a previous filter before starting the SM in order to discard pairs of graphs that, clearly, they may not be isomorphic. The first phase of the SM consists of obtaining all the equivalent resistance of the CEMs views from each pair of nodes in each pure resistive circuit (each with N (N -1)/2 values). At this stage already is if the graphs are isomorphic in binary form except false positive, these are those graphs which, despite not being isomorphic, present the same set of equivalent resistance. In a second phase each of electrical circuits is approximated by an electrical circuit in star with N +1 nodes and N branches (with a resistor in each branch). In this approach, they have get the values of the N resistors of the branches of the star so that minimizes the mean square error (mse) between the values of the equivalent resistance of the original circuit and circuit star equivalent resistances. In a third phase, ordering such values, the mapping of the isomorphism is obtained. In the fourth and final phase the retrieved mapping is validated so that SM is exact (may be caused by a false positive). SM is always exact if it reaches the phase of validation. If the resistances of the star does not have values repeated then it has a polynomial computational complexity of order three according to the number of nodes that, on the other hand, experiments corroborate is the majority of the cases. But if there are repeated values, SM has no polynomial computational complexity, going to be factorial but, in any case, not as N but according to the maximum number of repetitions that occur in the values of the resistances of the branches of the star. Even so, the rest of the nodes can be obtained (almost complete) partial mapping with polynomial computational complexity so that, at least, the SM no wasted temporal resources. Finally, it must be said that the experimental results have been satisfactory.

El primer objetivo propuesto en la investigación de esta tesis fue seleccionar y desarrollar un modelo (preferentemente sencillo) para los grafos de forma tal que, en el modelo, se pueda aplicar y utilizar una teoría asociada al mismo que sea consolidada, madura, cerrada y, en definitiva, aceptada por todos. De esta forma, los resultados que se obtienen a través del modelo son extrapolables a los objetos modelizados: los grafos. El segundo objetivo propuesto en la investigación, una vez seleccionado y desarrollado un modelo, fue diseñar y explotar una aplicación del modelo que permitiera abordar el problema del isomorfismo de grafos. El tercer y último objetivo fue probar experimentalmente el modelo y la aplicación. El resultado del primer objetivo fue la selección y desarrollo de un modelo eléctrico en donde aplica la Teoría de Circuitos que cumple los requisitos más arriba enunciados. Este modelo será denominado como "Modelo Eléctrico de Conductancias" (CEM en inglés). En el CEM los grafos se transforman en circuitos eléctricos de parámetros concentrados resistivos puros (sin fuentes, ni inductores, ni condensadores) conservando la topología del grafo. A partir de este punto se abren multitud de posibilidades con sólo contemplar el CEM obtenido de uno o varios grafos. La complejidad computacional de la obtención del CEM a partir de un grafo es siempre polinomial de orden dos según el grado del grafo, siendo el algoritmo de obtención determinista, no iterativo y no recursivo. Los grafos a los que se puede aplicar el CEM deben ser no dirigidos (ponderados o no) y sin etiquetas en los nodos. EL resultado del segundo objetivo fue el diseño del "Método de la Estrella" (SM en inglés) que, a partir del CEM, permite abordar el problema abierto del isomorfismo de grafos. Antes de aplicar el SM se obtiene el CEM de dos grafos ambos de grado N, entonces el SM comienza a partir de los dos circuitos que modelan, cada uno, un grafo. Como fase previa al SM es conveniente, pero en todo caso opcional, realizar un filtrado previo con el fin de descartar los pares de grafos que, de forma evidente, no podrán ser isomorfos. La primera fase del SM consiste en la extracción de todas las resistencias equivalentes de los CEMs vistas desde cada par de nodos de cada circuito resistivo puro (cada uno con N (N -1)/2 valores). En esta fase ya se está en condiciones de detectar el isomorfismo de forma binaria salvo falsos positivos, estos serán aquellos grafos que, aún no siendo isomorfos, presenten el mismo conjunto de resistencias equivalentes. En una segunda fase cada uno de los circuitos eléctricos se aproxima por un circuito eléctrico en estrella de N +1 nodos y N ramas con un resistor en cada rama. En esta aproximación se han de obtener los valores de los N resistores de las ramas de la estrella para que se minimice el error cuadrático medio (ecm) entre los valores de las resistencias equivalentes del circuito original y las resistencias equivalentes del circuito en estrella. En una tercera fase, ordenando dichos valores, se extrae el mapeado del isomorfismo. En la cuarta y última fase, con el objetivo de que el SM sea exacto, se valida el mapeado obtenido ya que puede haberse producido un falso positivo. El SM es siempre exacto si se llega hasta la fase de validación. Si en las resistencias de la estrella no hay valores repetidos entonces tiene una complejidad computacional polinomial de orden tres según el número de nodos que, por otro lado, los experimentos corroboran es la mayoría de los casos. Pero si existen valores repetidos, el SM ya no tiene complejidad computacional polinomial, y pasa a ser factorial pero, en todo caso, ya no según N sino según el número máximo de repeticiones que se pueden producir en los valores de las resistencias de las ramas de la estrella. Aún así, del resto de nodos se puede obtener el mapeado parcial (casi total) con complejidad computacional polinomial por lo que, al menos, el SM no malgasta recursos temporales.