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

Abstract

[CA]: 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.

[ES]: 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.

[CA]: El primer objectiu proposat en la recerca d’aquesta tesi va ser seleccionar i desenvolupar un model (preferentment senzill) per als grafs de forma tal que, en el model, es pugui aplicar i utilitzar una teoria associada al mateix que sigui consolidada, madura, tancada i, en definitiva, acceptada per tots. D’aquesta forma, els resultats que s’obtenen a través del model són extrapolables als objectes modelitzats: els grafs. El segon objectiu proposat en la recerca, una vegada seleccionat i desenvolupat un model, va ser dissenyar i explotar una aplicació del model que permetés abordar el problema de l’isomorfisme de grafs. El tercer i últim objectiu va ser provar experimentalment el model i la aplicació. El resultat del primer objectiu va ser la selecció i desenvolupament d’un model elèctric on aplica la Teoria de Circuits que compleix els requisits més amunt enunciats. Aquest model serà denominat com a “Model Elèctric de Conductàncies” (CEM en anglès). En el CEM els grafs es transformen en circuits elèctrics de paràmetres concentrats resistius purs (sense fonts, ni inductors, ni condensadors) conservant la topologia del graf. A partir d’aquest punt s’obren multitud de possibilitats amb només contemplar el CEM obtingut d’un o diversos grafs. La complexitat computacional de l’obtenció del CEM a partir d’un grafés sempre polinomial d’ordre dos segons el grau del graf, sent l’algorisme d’obtenció determinista, no iteratiu i no recursiu. Els grafs als quals es pot aplicar el CEM han de ser no dirigits (ponderats o no) i sense etiquetes als nodes. EL resultat del segon objectiu va ser el disseny del “Mètode de l’Estel” (SM en anglès) que, a partir del CEM, permet abordar el problema obert de l’isomorfisme de grafs. Abans d’aplicar el SM s’obté el CEM de dos grafs tots dos de grau N, llavors el SM comença a partir dels dos circuits que modelen, cadascun, un graf. Com a fase prèvia al SM és convenient, però en tot cas opcional, realitzar un filtrat previ amb la finalitat de descartar els parells de grafs que, de forma evident, no podran ser isomorfs. La primera fase del SM consisteix en l’extracció de totes les resistències equivalents dels CEMs vistes des de cada parell de nodes de cada circuit resistiu pur (cadascun amb N(N − 1)/2 valors). En aquesta fase ja s’està en condicions de detectar l’isomorfisme de forma binària excepte falsos positius, aquests seran aquells grafs que, encara no sent isomorfs, presentin el mateix conjunt de resistències equivalents. En una segona fase cadascun dels circuits elèctrics s’aproxima per un circuit elèctric en estel de N +1 nodes i N branques amb un resistor en cada branca. En aquesta aproximació s’han d’obtenir els valors de les N resistències de les branques de l’estel perquè es minimitzi l’error quadràtic mitjà (eqm) entre els valors de les resistències equivalents del circuit original i les resistències equivalents del circuit en estel. En una tercera fase, ordenant aquests valors, s’extreu el mapejat de l’isomorfisme. En la quarta i última fase, amb l’objectiu que el SM sigui exacte, es valida el mapejat obtingut ja que pot haver-se produït un fals positiu. El SM és sempre exacte

si s’arriba fins a la fase de validació. Si en les resitències de l’estel no hi ha valors repetits llavors té una complexitat computacional polinomial d’ordre tres segons el nombre de nodes que, d’altra banda, els experiments corroboren és la majoria dels casos. Però si existeixen valors repetits, el SM ja no té complexitat computacional polinomial, i passa a ser factorial però, en tot cas, ja no segons N sinó segons el nombre màxim de repeticions que es poden produir en els valors de les resistències de les branques de l’estel. Encara així, de la resta de nodes es pot obtenir el mapejat parcial (gairebé total) amb complexitat computacional polinomial pel que, almenys, el SM no malgasta recursos temporals. Por últim, cal dir que els resultats experimentals han estat satisfactoris.