PhD Thesis

The conductance electrical model applied to the graph isomorphism: The star method

Work default illustration

Information

  • Started: 01/01/2008
  • Finished: 28/01/2016

Description

The first objective proposed in the research of this thesis was the selection and development of a (preferably simple) model for graphs, thus, the results obtained through the model may be extrapolated to the modelled 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 unlabelled 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 minimises 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.