01 - Introduction

02 - Passive Resistive Electrical Circuits

03 - Derived Circuit

04 - Definition of Signature of Electrical Currents and Orderly List of Vertices

05 - Orderly List Construction Algorithm Example

06 - Proposal of the Theorem on Graph Isomorphism Problem

07 - Demonstration 1

08 - Demonstration 2

09 - Determination of the Isomorphic Bijective Mappings

10 - Search in Graphs

11 - How Many and What Are the Isomorphic Bijective Mappings?

12 - Philosophizing

     If two graphs G₁(V₁, E₁) and G₂(V₂, E₂) are isomorphic, there is at least one bijective mapping f:V₁-> V₂ where (f(v_i), f(v_j)) belongs to E₂ if and only if (v_i, v_j) to belong to E₁. This means that, being isomorphic, the graphs present a coincident geometrical representation.

Illustrating, given the graphs G above and G' below, isomorphic:

a bijective mapping f:V -> V' that attends the conditions above defined, that we will call of isomorphic bijective mapping, would be:

f(1) = 1, f(2) = 5, f(3) = 4, f(4) = 3, f(5) = 2

     The existence of at least one of these mappings demonstrates that the graphs are isomorphic, what implies that they can be represented by coincident geometrical figures. In the case of G and G' it's trivial the view of this fact, but with big graphs it's extremely difficult such vision.
 
2 - Passive Resistive Electrical Circuits

     If we apply determinate electrical tension in any pair of nodes, the electrical currents that will flow in each resistor of the circuit will just depend of the values of its resistance and of the particular topology in that they are arranged, in function of its interconnections, not making absolutely any difference the geometrical form in that they are set up in the circuit: circular shape, triangular, linear, heapped, chaotic, etc. (Of course we are considering by worthless factors as electrical induction, spurious capacitances, present electromagnetism in the environment, etc.)

     This fact suggests an efficient algorithm to discover if two graphs G₁(V₁,E₁) and G₂(V₂,E₂) are isomorphic and, case they are, to find the isomorphic bijective mappings f:V₁-> V₂.

     Therefore, so as a resistive electrical circuit can be modeled by a graph (a multigraph when there are resistors in parallel), inversely, a graph also can be object of metamorphosis in a passive resistive electrical circuit, where the edges become in resistors and the vertices in nodes.
 
3 - Derived Circuit

     We can, then, associate for each vertex and edge of the original graph a node and a resistor in the derived circuit, that we will name, respectively, corresponding node and resistor to the original vertex and edge.

     Since now, considering the unity between original graph and derived circuit, whenever there are not ambiguities, we will refer to the nodes and resistors of the derived circuit as vertices and edges of the original graph, respectively. therefore, when we refer to circulating currents in the edges, incident in the vertices and present tensions in the vertices of original graph, you would understand corresponding currents in the resistors, incident in the nodes and present tensions in the nodes of derived circuit.

4 - Definition of Signature of Electrical Currents and Orderly List of Vertices

     Solution = (i_i, i_j, i_k, ... , i_m) where i_i<= i_j <= i_k <= ... <= i_m

     An original n-vertex graph originates one derived circuit with n nodes, therefore there are (n² - n)/2 different pairs of nodes in this circuit. if we apply a tension of 1 V on each one these pairs we will arrive to one sequence, that will be disposed in crescent order, of (n² - n)/2 solutions. (In the sorting of solutions, its elements are compared one by one of the left for right: if there is a different pair this fact will indicate the precedence).

     To such ordered sequence of solutions we will give the name Signature of Electrical Currents of graph – or just signature:

     Signature = ((i_i1, i_j1, i_k1, ..., i_m1), (i_i2, i_j2, i_k2, ..., i_m2),..., (i_ix, i_jx, i_kx, ..., i_mx))

     Obs.: A null graph formed by only one vertex does not present any solution and will have signature equal to (), but if it be formed by two isolated vertices there will be one solution equal to () and its signature will be equal to (()).

    We can, having calculated the signature, to order the vertices of a graph in a list (that we name orderly list), by the orderly sequences of values of the incident currents on them, considering all the solutions. We define as equivalent vertices those whose such sequences of incident currents (that we name incident currents (vertex)) are equal. Equivalent vertices occupy the same position of order inside of the orderly list. Every vertex is equivalent to itself, it's obvious. If v_i and v_j are equivalent, all adjacent vertices to v_i are equivalent, one-to-one, to all adjacent ones to v_j; else the flow of the currents on them would be different, and, consequently, they wouldn't can be equivalent.

     Orderly List = [v_i, v_j, v_k, ..., v_n] where v_i <= v_j<= v_k <= ... <= v_n.

     v_x > v_y if degree (v_x) > degree (v_y) or if degree (v_x) = degree (v_y) and incident currents (v_x) > incident currents (v_y). (Obs.: The elements of the incident currents are compared one by one of the left for right: an eventual different pair will indicate the precedence). If v_z = v_w they are equivalent and we say that they occupy the same position of order inside of the orderly list.

    Obs.: We don't need handle approximations, since direct methods to solve the linear systems can supply exact solutions, where all currents will be presented in rational form p/q, where p and q are integers (for example, if 3*i = 1, then i = 1/3, rather than i = 0.333...).

     Similarly, we define as equivalent edges those whose sequences of flowing currents on them are equal. Note that two edges (v_i, v_j) and (v_k, v_l) are equivalent if and only if v_i is equivalent to v_k and v_j is equivalent to v_l: we can say that equivalent edges link pairs of equivalent vertices; otherwise the incident currents and, consequently, the electrical tensions on these vertices would be different, implying in different flowing currents on the edges, disabling the fact of they to be equivalent.

     Signature and orderly list examples for graph G({1,2,3},{(1,2),(1,3)}) below:

     Observe that the values 1 ohm and 1 V are arbitrary values. But there is not generality loss when using them, or to any other, since, because of the proportionality of the Ohm's Law, being used any values of R ohms and V volts we arrive to proportional signatures, according to the factor V/R.

5 - Orderly List Construction Algorithm Example

     Algorithm example: at the beginning we will identify the vertices of the graph labeling them of 1 to n and, soon after, we will arbitrate that the positive direction of the currents will always be of the smaller vertex for the larger. Starting from there, in each pair of vertices v_i and v_j, belonging to some k-vertex and a-edge connected component, we will apply 1 V and to calculate the circulating currents in each edge. For this calculation, we can build a type of generating tree (a spanning tree without the vertex v_j) with root in v_i, but without to reach the vertex v_j, with algorithm 0(k+a). This tree will have k - 1 vertices (because v_j is out) and k - 2 edges (remaining a - k + 2 edges). The Kirchhoff's Current Law - where the algebraic sum of the incident currents in a node is equal to zero - in each one of these vertices, except v_i, will find k - 2 independent equations. Being increased each one of the edges that remained or we will close a simple cycle in the tree or we will connect it to the vertex v_j. In the first case (reminding that for resistors of 1 ohm the tension and the current on them are the same) we will determine more an independent equation using the Kirchhoff's Voltage Law - in that the algebraic sum of the present tensions in the cycle is equal to zero; in the second case we will have a path between v_i and v_j that will result, according to the same Law, in more an independent equation, in that the sum of the present tensions in the edges of the path is equal to 1 V. Then, when included all the edges remaining there will be (k – 2) + (a - k + 2) = a independent equations, determining a linear system with a equations and a unknown amounts (the currents in each edge), solvable, by direct methods, with algorithms 0(a³). The currents in the other - if there are - connected components of the graph will be equal to zero for the solution in screen. The process is repeated for all the (n² - n)/2 pairs of vertices of the graph. Then, all the m currents in each solution, and all the (n² - n)/2 solutions will be ordered and the orderly list will be constructed - in inferior time that 0(n²m³), and we will have, after all, the orderly list of the graph.

     Of course, if the two vertices where the tension was applied belong to distinct connected components, all currents will be equal to zero.

6 - Proposal of Theorem on Graph Isomorphism Problem

     The determination if two graphs are isomorphic consists in to calculate and to compare the respective orderly lists of vertices: if the lists are equal (the vertices in the two lists are, one-to-one, equivalent), the graphs are isomorphic; if the lists are different, the graphs are not isomorphic.

     In fact, the proposed theorem establishes a new way to do the representation of a graph - to write its orderly list and incident currents in every vertex - as alternative, for example, to adjacency matrices or to chained lists, with the advantage that isomorphic graphs will have, automatically, identical representations; but with the disadvantages: it has extensive representation and it demands very much processing time to find, starting from orderly lists and incident currents in every vertex, the adjacency group among the vertices of the graph, that is the important information stored in the graph. A method of interesting representation, then, would be to work with two redundant representations, a traditional one and, beside this, the orderly list and incident currents in every vertex.

     Why is the orderly list and incident currents in every vertex much more extensive than the other representations? Because it contain redundant information, considering that the solutions are not, in general, independent one of the other ones: only a subset of solutions - sometimes only one solution - in that there is flow of currents in every vertex of the graph is enough for to determine its complete orderly list. Alternative theorems to the proposed, that search for to avoid such redundancies, would be, however, of difficult manipulation, by to involve complex operations and treatment of several private cases in the determination of a solution in function of another.

7 - Demonstration 1

     The proof of the need is trivial: if two graphs are isomorphic, they can be represented by coincident geometrical illustrations in relation to vertices and edges. Therefore, the respective derived circuits - that, let us remind, are built considering the disposition of the vertices and edges of the graph - will be, consequently, identical. Identical circuits will present identical behaviors when submitted to the same tensions, producing, obviously, the same orderly list.

     The proof of the sufficiency is more elaborated: let us make a reduction to absurdity, considering that two graphs G₁(V₁, E₁) and G₂(V₂, E₂) aren't isomorphic and present, however, identical orderly lists.

     Since the graphs present the same orderly lists, they are, necessarily, constituted by the same numbers of edges and vertices, whose degrees are, one-to-one, equal, because if this isn't true, the amount of incident currents in the vertices of the orderly list wouldn't be the same – and the orderly lists wouldn't can be equal.

     As the graphs aren't isomorphic, its complements also are not. The complement of a graph G(V, E) is the graph ~G(V, E'), where (v_i, v_j) belongs to E' if and only if does not belong to E. In the determination of the equations that compose the linear system for each solution in a graph, we can determine the corresponding equations for its complement considering that the currents in this will flow between the not adjacent vertices. We will find, then, two linear systems, one for the graph, another for its complement.

     In a complete graph, the signature is composed of trivial solutions: in the edge between the two vertices where 1 V was applied a current of 1 A will flow and in the adjacent edges to these vertices, 1/2 A will circulate; in the other edges the current will be zero. This fact results of the resolution, in each solution, of the linear system formed by the equations constituted by all the possible currents in a graph. In the previous paragraph we arrived to two linear systems, formed by the equations that considered some times presence other times absence of edge. But if we consider all the edges, we will have a complete graph; therefore, the agglutination of these two linear systems will result in the linear system of the complete graph. Such agglutination would occurs by the sum of the resultant equations of the Kirchhoff's Current Law, juxtaposition of the resultant of the Kirchhoff's Voltage Law, and construction of new equations, by Kirchhoff's Voltage Law, including the currents that, eventually, do not appear in the anterior equations, forming, so, the linear system with all possible currents in the complete graph. Inversely, since the linear systems for complete n-vertex graphs are predefined, because all the solutions are of the type mentioned in the beginning of this paragraph, the concerning linear systems to the complement of a graph depend of the graph and vice versa, implying in interdependent orderly lists.

     Reminding that G₁ and G₂ are not isomorphic, in all the possible bijective mappings f:V₁ -> V₂ there is at least one edge (v_i, v_j) belonging to E₁ where (f(v_i), f(v_j)) doesn't belong to E₂ and one edge (f(v_k), f(v_l)) belonging to E₂ where (v_k, v_l) doesn't belong to E₁. Think in all n! possible bijective mappings. Let respectively ~G₁ and ~G₂ be the complements of G₁ and G₂. As G₁ and G₂ have identical orderly lists, ~G₁ and ~G₂ also have it. That is to say, if we to agglutinate the concerning linear systems to the solutions of ~G₂ - because they are the same ones that ~G₁ - with the ones of G₁ we will find the concerning linear system to the complete graph of |V₁ | vertices (K_{|V1 |}).

     When we label again the vertices of ~G₂ according to any bijective mappings f:V₂ -> V₁, however, we will see that there will always be at least one edge (v_i, v_j) in ~G₂ that also belongs to G₁. Consider all n! possible bijective mappings. Considering that the number of edges in ~G₂ is the same in ~G₁, and that their sum in ~G₁ and G₁ is the same that exists in the corresponding complete graph, there will always be in the concerning linear systems for ~G₂ and G₁ the lack of at least one current in their equations, because at least the edge (v_i, v_j) is appearing twice, doing that another doesn't appear, disabling that these linear systems determine the linear system that appears in the complete graph, that involves all the currents in all the edges. That is to say, the concerning linear systems for ~G₂ are, unavoidably, different from the concerning ones to ~G₁, implying that the concerning sets of solutions for ~G₁ and ~G₂ are different, that, consequently, will imply that the concerning sets of solutions to G₁ and G₂ are different - that enters in contradiction with the fact of its orderly lists to be the same. Then, if the graphs aren't isomorphic, present, necessarily, different orderly lists.

     These different linear systems result in different solutions because the difference is the lack of at least one current in its correspondent equations, and it isn't only difference by linear transformations. Then, if all solutions are equal for the two graphs, G₁ and G₂, this indicates that its linear systems are equal, where the visible differences are caused by only linear transformations and permutation of the unknown amounts. Then, if the graphs have the same orderly list, its complements too have it, and, consequently, in some of the n! possible bijective mappings, and after the application of the appropriate linear transformations, the equations which compose the linear systems for ~G₁ and ~G₂ will be exactly equal in the two complements: then, ~G₂ and G₁ determine a complete |V₁|-vertex graph, where it's all possible currents in any graph of |V₁| vertices. Then, unavoidably, ~G₂ is the complement of G₁. Otherwise, it will fail currents (edges) for the complete graph.

     In fact, the solutions determine the linear systems, that, by their time, determine the structure of the graph.

     Obs.: Of course, in not isomorphic graphs, some solutions in a graph can be equal to solutions in the other graph. This fact occurs if there are Wheatstone's bridges or isomorphic components in the graphs. But, in all these special cases, the same solution results of different linear systems because there is not flow of electrical currents in the not isomorphic subgraphs - where at least the 'double' edges (v_i, v_j) stay inside the graphs. Observe that it's the flow of currents which reveals the structure of the graphs; then, the parts of the graphs where there is not flow of currents remain hidden. Fortunately, in several other solutions there is flow of currents in these hidden not isomorphic subgraphs, and then the respective solutions show its differences - in special in the corresponding solutions to the pairs (v_i, v_j).

     Therefore, if the graphs present the same orderly lists they are, necessarily, isomorphic.

8 - Demonstration 2

     Let f:V₁ -> V₂  be bijective mappings, with the condition that in every instance f(v_i) = v_j, v_i is equivalent to v_j. There will be, in such mapping, p edges (v_i, v_j) belonging to E₁ where (f(v_i), f(v_j)) doesn't belong to E₂ and p edges (f(v_k), f(v_l)) belonging to E₂ where (v_k, v_l) doesn't belong to E₁, where always p > 0, for the graphs aren't isomorphic. We choose, from among all these, a mapping in that p is a minimum value. We name p as the number of discordant edges. Look that every edge of a graph has an equivalent edge in the other graph, because the graphs present the same orderly list. Then, every discordant edge in a graph has an equivalent discordant edge in the other one, considering that every not discordant edge in a graph has an equivalent one in the other graph (edges linking equivalent pairs of vertices).

     If we have two not isomorphic graphs generating identical orderly lists, presenting an arbitrary number of discordant edges, we can build two not isomorphic graphs, generating identical orderly lists, and presenting only 1 (one) discordant edge between them:

     Starting at this mapping, we will add the edges (v_i, v_j) in the graph G₁ and (f(v_k), f(v_l)) in the graph G₂, if (v_k, v_l) and (f(v_i), f(v_j)) are equivalent and belong to E₁ and to E₂, and (v_i, v_j) and (f(v_k), f(v_l)) don't belong to E₁ and to E₂, respectively. After the increase of this pair of edges the process is repeated recursively of the begin: again, the orderly lists are constructed and other pair of edges is increased - up to p to be equal to 1 (one). Then, the addition of more one edge would change the graphs in isomorphic graphs.

     The addition of these edges doesn't destroy the equality of the orderly lists, since (v_i, v_j) and (f(v_k), f(v_l)) are equivalent (these edges link equivalent pairs of vertices, which will continue equivalent, because the electrical perturbation will be propagated in the same way for all vertices of the two graphs, since that all adjacent vertices to v_i and v_j are, one-to-one, equivalent to all adjacent vertices to f(v_k) and f(v_l), for v_i and v_j, and f(v_k) and f(v_l) are equivalent, respectively).

     All discordant edges are equivalent, one-to-one, in the two graphs; then the process - that can be visualized as an operation of to complete the graphs, up to they to stand almost isomorphic - do not suffer risk of to stop by fail of equivalent discordant edges.

    Then, if there are two graphs not isomorphic, presenting an any number of discordant edges, and having identical orderly list, then there are ones presenting only one discordant edge. Now, to prove the theorem, it's enough to prove that it is impossible there are two graphs not isomorphic, presenting only one discordant edge and identical orderly lists.

     Let us make, again, a reduction to absurdity, considering that there are two n-vertex and m-edge graphs, not isomorphic, presenting only one discordant edge, and having identical orderly list. Then, there are ones where m is a minimum, that is to say, there aren't n-vertex ones presenting less edges.

     Let G₁(V₁, E₁) and G₂(V₂, E₂)  be two isomorphic n-vertex graphs, where the removal of equivalent edges (v_i, v_j) and (v_k, v_l) of G₁ and G₂, respectively, change the graphs in not isomorphic graphs, presenting only one discordant edge, identical orderly list, and having the minimum of edges. 

     Let f:V₁ -> V₂  be any isomorphic bijective mapping on G₁ and G₂. There should not be an isomorphic bijective mapping where the instances f(v_i) = v_k and f(v_j) = v_l, otherwise with the removal of the edges (v_i, v_j) and (v_k, v_l) of G₁ and G₂, respectively, this mapping - and the graphs - would continue isomorphic. Then, there are, in any mapping, the occurrences f(v_i) = v_x and f(v_j) = v_y, where (v_x, v_y) is different of (v_k, v_l), and consequently, also there are f(v_w) = v_k and f(v_z) = v_l, where (v_w, v_z) is different of (v_i, v_j). If there are edges beside these two, there will be the instances f(v_r1) = v_r2 and f(v_s1) = v_s2, where (v_r1, v_s1) and (v_r2, v_s2) are different of (v_i, v_j) and (v_k, v_l), respectively. Now, if we remove these two edges, the mapping - and the graphs - will continue isomorphic. After this removal, the fact of that there are not any isomorphic bijective mapping where the instances f(v_i) = v_k and f(v_j) = v_l continues valid: otherwise, a such isomorphic mapping would continue isomorphic with the increase of the removed edge, and then this fact would be false in the begin of this paragraph (before of this removal), but there it is true by hypothesis. Then, the removal of these edges will do the graphs to be not isomorphic presenting only one discordant edge, now presenting less edges; but, by hypothesis, the anterior not isomorphic graphs have the minimum of edges. To win the contradiction we can say that there aren't more edges in the graphs beside (v_i, v_j) and (v_w, v_z) in G₁ and (v_k, v_l) and (v_x, v_y) in G₂. However, 2-edge graphs don't can be not isomorphic and to present identical orderly lists, it's obvious. Then, there isn't a value of m that is a minimum. Then, there are not n-vertex and m-edge graphs, not isomorphic, presenting only one discordant edge and having identical orderly list.

     (Observe that, for isomorphic graphs, this fact also proves that, for every v_i in G₁, there will be in at least one isomorphic bijective mapping the instance f(v_i) = v_k, where v_k in G₂ is equivalent to v_i; otherwise the removal of any two equivalent edges (v_i, v_j) and (v_k, v_l) of G₁ and G₂, respectively, would change the graphs in not isomorphic graphs, presenting only one discordant edge and identical orderly list).

     The same reasoning can be used for any pair of edges in any-vertex graphs, and it will be impossible to build two graphs not isomorphic, presenting identical orderly lists and only one discordant edge: consequently, it will be impossible there to be these graphs presenting any number of discordant edges. Then, if the graphs have the same orderly list, they are isomorphic.

9 - Determination of the Isomorphic Bijective Mappings

     The first association, in each connected component, will be made between two equivalent vertices still not associated, one of each orderly list. To standardize the process, choose it from among ones of smallest order. After this:

     Let A₁ and A₂ be the sets of vertices associated of G₁ and G₂, respectively, where all v_a1 in A₁ are associated to all v_a2 in A₂ (one-to-one, it's obvious); and let v_c1 in G₁ and v_c2 in G₂ be vertices chosen as candidates to associate by to be - except the first vertices to to associate in each connected component - adjacent to some vertex in A₁ and A₂, respectively. They only can associate indeed if obey the conditions below:

     1 - All the adjacent vertices to v_c1 in A₁ are associated to the adjacent vertices to v_c2 in A₂ (one-to-one, it's obvious);

     2 - The incident currents in all v_a1 in A₁, in the solutions corresponding to the formed pairs by v_c1 and all v_a1 in A₁, are the same to the incidents in the respective v_a2 in A₂, in the corresponding solutions, respectively, to the formed pairs by v_c2 and all v_a2 in A₂.

     The conditions derive of the fact that the construction of the isomorphic bijective mapping can be considered as the reconstruction of the connected components of the two graphs starting from initial vertices (the rootses of each tree of the forest of associations, as we will see later), in that each reconstructed vertex (associated) maintains identical relationships of adjacency and flows of currents in the two graphs, in relation to the vertices already reconstructed (we can disrespect the still not reconstructed vertices, by they to be not still with its positions defined in the reconstruction).

     This set of associations will supply an isomorphic bijective mapping: if v_1x was associated to v_2y, then f(v_1x) = v_2y.

     Considering that the two graphs are isomorphic, this method always works. In fact, it should fail only if:

     - There are not candidates after the first association which obey the conditions.

     If the incident currents in all associated vertices are equal in all solutions, this indicates that the associated vertices are, one-to-one, in isomorphic positions into the graphs: the subgraphs S₁ of G₁ and S₂ of G₂, formed by the associated vertices and edges linking them, are isomorphic - this is proved in the paragraph below; the subgraphs R₁ of G₁ and R₂ of G₂, formed by the not associated vertices and edges linking them, also are isomorphic - otherwise, the flow of the currents in their vertices would be different, implying in different flow in S₁ and S₂ - and the conditions wouldn't be obeyed in the anterior association. If S₁ and R₁, and S₂ and R₂ are isomorphic, respectively, then the process is in right path, because the determined mapping by the associations up to this moment is a subset of an isomorphic bijective mapping. Imagining the two derived circuits in coincident positions of the space, in all the possible isomorphic bijective mappings, and the flow of the currents on them, it's easy see it. Then, always there will be candidates which will obey the conditions.

     This generated bijective mapping is necessarily isomorphic: (v_i, v_j) belongs to E₁ if and only if (f(v_i), f(v_j)) to belong to E₂. Otherwise, when v_i and f(v_i) or v_j and f(v_j) should be candidates they should not obey the condition 1: considering v_i and f(v_i) associated before than v_j and f(v_j), when v_j and f(v_j) should be candidates, v_j should be adjacent to v_i and f(v_j) should not be adjacent to f(v_i) (or v_j should not be adjacent to v_i and f(v_i) should be adjacent to f(v_j)). They should not can, then, obey the condition 1, which says that all vertices in A₁ adjacent to v_c1 must be associated to all vertices in A₂ adjacent to v_c2 (one to one, it's obvious). Then, the association between v_j and f(v_j) never should happen. the same thing occurs if v_j and f(v_j) are associated before than v_i and f(v_i).

     This method of determination of an isomorphic bijective mapping can be visualized geometrically as the construction of a generating forest of the graphs, where the root of the first tree represents the association between two equivalent vertices from among ones of smallest order, one of each orderly list, growing in depth or width starting from there, observing, in the other associations - that will represent increment of leaves to the forest in construction - beside of the equivalence, also the adjacency among the vertices already associated and the candidates to the association as well as the related currents in the vertices candidates. This generating forest will contain so much trees how many there are connected components in the isomorphic graphs.

     When all the vertices of a connected component have been associated, that is to say there is not any vertex adjacent to the associated vertices that it has not been associated still, and there are still not associated vertices, this will indicate that there are still vertices in another connected component, being born of there other tree as in the beginning of the process, with the difference that the first association - that will constitute the root of this new tree - will be between two equivalent vertices from among ones of smallest order not yet associated.

     The process is applied on all the connected components of the graphs, until reaching all the vertices of the two graphs, building a forest – that we can call of forest of associations - of so much trees how many there are these connected components. The vertices of this forest can be labeled with a composition between the labels of the two associated vertices that gave them origin.

10 - Search in Graphs

When walking for a graph in the traditional way, the choices of the initial vertex and of what incident edge to the marked vertex to explore constitute arbitrary alternatives - that generate ambiguities - only having only option in the choice of what marked vertex to choose to explore some still not explored edge - always the more or the less recently reached, case the search is in depth or width, respectively.

For to walk systematically in a graph G, we start from the orderly list. The initial vertex will be chosen from among the vertices positioned in the beginning of the orderly list. And we will explore, from among the not yet explored incident in the chosen marked vertex, the incident edge in the vertex of smallest order in the list, and in case of more than one alternative, the edge (v_i, v_j) whose corresponding solution - found one when applying the tension on v_i and v_j - results in the smallest sequences of currents in the edges already explored, according to the exploration order. If, nevertheless, there is choice among more than one edge, there is automorphism in the graph, not having ambiguity, just alternative walks that drive us to isomorphic searches. The process is repeated in all the connected components of the graph, being chosen, as initial vertex in them, one from among the vertices of smallest order not yet explored.

11 - How Many and What Are the Isomorphic Bijective Mappings?

In the figure 7, for example, we have 2 vertices occupying the first position in each orderly list, resulting in 2 alternatives. After, we have 2 candidates in each graph attending to the conditions to associate, resulting in more 2 alternatives. After this last choice we will just have only options of association up to the finish of the first tree. In the choice of vertices not yet associated for root of the second tree, just one option remained us in the position of order 0 of the list, and again here there are 2 candidates in each graph attending to the conditions to associate, resulting in more 2 alternatives, and later also remaining only options until the end of the second tree. We can, then, to build up to 8 (2*2*2) different isomorphic bijective mappings for these graphs.

12 - Philosophizing

The orderly list of vertices at the same time depends of the global structure of the graph and admits polynomial time algorithms for its determination.

However, perhaps this theorem causes some surprise by, in a certain way, to invert the that anybody hopes to be the natural order of the mathematical research: first it's discovered something in the field of the pure mathematics, generally considered in the beginning of little practice usefulness, for only some time later - sometimes a long time later - to meet practical applications or applied research areas in that such discovery reveals its pragmatic vocation, when modeling problems of the real world. In the theorem of the signatures in subject, it happens the opposite: not very more than the resolution of a classic and trivial problem of electrical engineering will solve a problem of the mathematics. It's as if something that always just was believed to be modeled mathematically, also could 'to model' the mathematics. Naturally that any mathematician could express this theorem strictly in mathematical terms, without any mention to the physical reality of the that resulted, but this would sound extremely artificial, in addition to it would hinder plenty its understanding and demonstration.

SZWARCFITER, Jayme Luiz (1983), Grafos e algoritmos computacionais, Campus, Rio de Janeiro.

CLOSE, Charles M. (1975), Circuitos lineares, vol. 1, Livros Técnicos e Científicos, Rio de Janeiro.

This page hosted by  Get your own Free Home Page