A-B-C ABOUT IDENTIFICATION OF GRAPHS

John-Tagore Tevet

Let us try to open the essence of graphs, from that's so far tried to circumvent.

1. What is a graph

Graph is an association of elements with relationships between these that has a certain structure.

Graphs are represented for different purposes. On the early rock paintings have been found the constellations show schemes. Graphs was used also for explain the theological tenets.

Example 1. Graph (structural formula) of isobutane C4H10:

Graphs began to investigate after then when Leonhard Euler in 1736 has solved the problem of routing on the seven bridges between four banks of Königsberg [1].

Example 2. Königsberg’s bridges and corresponding graph:

Also in present time used the graphs mainly for solving the problems of routing and flowing. Already in 1976 considered that such one-sided approach is a hindering factor for studying of graphs [2]. To the essence of graph, to its structure and symmetry properties has the interest practically non-existent. The last explorer was evidently Boris Weisfeiler in 1976 [9].

Definition a graph as an object consisting in node set V and edge set E, G=(V, E), is a half-truth that beget confusions. Essential is to explain the properties of inner organizing (inner building) or structure, i.e. identification of graphs.

Graph is presentable: 1) as a list L of adjacencies; 2) in the form of adjacency matrix E; 3) graphically G, where the elements to “nodes” and relations to “edges” called.

Example 3. List of adjacencies L, corresponding adjacency matrix E and for both corresponded graphs GA and GB:

Explanations:

The outward look and location of the enumerated elements in graph not have something meaning. But on the emotional level it rather engenders some confusion.

One graph can be differs from the other on its looking or its inner organizing (inner-building) or structure S what in ordinarily visually not be opened. Maybe just due to this is to the present days the existence of structure ignored.

We can here make sure that graphs GA and GB have the same structure and these are isomorphic GA @ GB. Ordinarily differentiate in the objects just the “outward” differences and refuse to see some common structure.

Propositions 1. Structure axioms:

P1.1.    Structure S is presentable as a graph G and each graph G has its certain structure S.

P1.2.    Isomorphic graphs have the same structure – structure is the complete invariant of isomorphic graphs.

Identification of graph is based on identification the binary relations between elements [3 - 8]. Binary relation can a “distance relation”, “circle relation”, “clique relation” etc. and is measurable. Binary relation characterized by corresponding binary sign.

2. Identification of the graph

For identification of the graphs uses two each others complementary ways:

Multiplicative identification (products of adjacency matrixes);

Heuristic identification.

Propositions 2. Multiplicative identification: multiplication the adjacency matrixes:

P2.1.       To multiplying the adjacency matrix with itself E´E´E´…=En and fixing in case of each degree n the number p of different multiplicative binary signs enij that as rule enlarges. Forming the sequence vectors ui of different multiplicative binary signs.

P2.2.       In each case if p enlarges (change) must transpose the rows and columns of En correspondingly to the obtained frequency vectors ui.

P2.3.       Stop the multiply if p more no enlarges and to present the current En and the following En+1.

Explanation: Multiplicative signs differentiate the binary signs but no characterize these.

Example 4. Adjacency matrix E and its transposed products E2, E3 of graphs on example 3:

1  2  3  4  5  6| i

                0  1  0  1  0  1| 1

                1  0  1  0  1  1| 2

          E    0  1  0  1  0  1| 3

                1  0  1  0  1  0| 4

                0  1  0  1  0  1| 5

                1  1  1  0  1  0| 6

                                         ui

2  6| 1  3  5| 4     |    i    0 1 3 4   k

4  3| 1  1  1| 3     |    2    0 3 2 1   1

3  4| 1  1  1| 3     |    6    0 3 2 1   1

E2   1  1| 3  3  3| 0     |    1    1 2 3 0   2

1  1| 3  3  3| 0     |    3    1 2 3 0   2

1  1| 3  3  3| 0     |    5    1 2 3 0   2

3  3| 0  0  0| 3     |    4    3 0 3 0   3

ui

 2  6| 1  3  5| 4|   i    0 2 3 6 7 9 10  k

 6  7|10 10 10| 3|   2    0 0 1 1 1 0 3   1

 7  6|10 10 10| 3|   6    0 0 1 1 1 0 3   1

E3   10 10| 2  2  2| 9|   1    0 3 0 0 0 1 2   2

10 10| 2  2  2| 9|   3    0 3 0 0 0 1 2   2

10 10| 2  2  2| 9|   5    0 3 0 0 0 1 2   2

 3  3| 9  9  9| 0|   4    1 0 2 0 0 3 0   3

Explanations:

a)      The set of similar relations (and elements) recognize their position W in the structure. Position W is in group theory known as transitivity domain of automorphisnsms, equivalence class or orbit.

Multiplicative binary signs enij recognize here five positions of binary relations WR and on they base three positions of elements WV.

Propositions 3. Position axioms:

P3.1.       If structural elements (graph nodes) vi , vj , … have in graph G the same position WVk then corresponding sub-graphs (Gi=G\vi) @ (Gj=G\vj) @....   are isomorphic.

P3.2.       If relations (edges) eij, ei*j*, … have in graph G the same binary(+)position WR+n then corresponding greatest subgraphs (Gij=G\eij) @ (Gi*j*=G\ei*j*) @....  are  isomorphic.

P3.3.       If relations (“non-edges”) eij, ei*j*, … have in graph G the same binary(–)position WRn– then corresponding smallest supergraphs (Gij=GÈeij) @ (Gi*j*=GÈei*j*) @....  are isomorphic.

Before elaboration of the multiplicative identification way was elaborated a heuristic way.

Propositions 4. Heuristic identification:

P4.1.       Fix an element i and form its neighborhood Ni, where the elements, connected with i divide according to distance d to entries Cd.

P4.2.       Fix an element j and fix its neighborhood Nj by condition P4.1.

P4.3.       Fix the intersection Ni ÇNj as a binary graph gij, and fix the distance –d between i and j (in case of adjacency collateral distance +d), the number n of elements (nodes) in gij, number q of adjacencies (edges). Fixing the heuristic binary sign ±d.n.q.ij of obtained graph gij.

P4.4.       Realize P4.1 to P4.3 for each pair i,jÎ[1, |V|]. Obtained preliminary heuristic structure model SMH.

P4.5.       Fixing for each row i its frequency vector ui. Transpose the preliminary model SM by frequency vectors ui lexicographically to partial models SMk.

P4.6.       In the framework of SMk transpose the rows and columns lexicographically by position vectors si to complementary partial models. Repeat P4.6 up to complementary transposing no arises.

Explanation: Heuristic binary signs differentiate the binary signs and characterize these.

Example 5. On the Example 3 presented differently enumerated graphs GA and GB, their heuristic binary signs and structure models SMA and SMB with their common product E3:

ui

 3  4| 1  4  5| 2|   iA

 1  2| 1  2  5| 6|        iB    0 2 3 6 7 9 10  k

 6  7|10 10 10| 3|   3    3    0 0 1 1 1 0 3   1

    6|10 10 10| 3|   4    6    0 0 1 1 1 0 3   1

E3         | 2  2  2| 9|   1    1    0 3 0 0 0 1 2   2

…..  |    2  2| 9|   2    4    0 3 0 0 0 1 2   2

     |       2| 9|   5    5    0 3 0 0 0 1 2   2

     |        | 0|   6    2    1 0 2 0 0 3 0   3

Explanations:

”Diverse” graphs GA and GB have equivalent heuristic structure models SMA » SMB and the same multiplicative model E3. This means that structures are equivalent and all on the examples 2 and 4 presented graphs GA and GB are isomorphic GA @ GB.

The binaries are divided to five binary positions WRn, where the “adjacent pairs” or “edges” divided to three binary(+)positions (full line, a dotted, dashed-line) that coincide with heuristic binary signs C, D, E and corresponding multiplicy binary signs 10, 7, 2, and with two binary(–)positions with signs –A and –B and multiplicative signs 9 and 3. In base of these divide the structural elements to three positions WVk.

The column ui constitutes frequency vectors, where each element i characterize its relationships with other elements. On the base of frequency vectors ui obtained the positions of elements WVk.

The column si constitutes position vectors that represent the connecting of i with elements on the position k.

A principal theoretical algorithm of isomorphism recognition exists really – it consists in rearranging (transposing) the rows and columns of adjacency matrices EA of graph GA as yet these coincides with the EB of GB. But this has an essential lacking – it is too complicated, the number of steps can be up to factorial n!

Propositions 5. On the relationships between isomorphism and structural equivalence:

P5.1.    Isomorphism GA@GB is a such one-to-one correspondence, a bijection j: VA®VB, between elements what retains the structure GS of graphs GA and GB.

P5.2.    Isomorphism recognition does not recognize the structure GS and its properties (positions etc.), but the structure models SM and En recognize the structure and its properties with exactness up to isomorphism.

P5.3.    Structural equivalence SMA»SMB and EnA»EnB is a coincidence or bijection j: WA®WB on the level of binary positions WRn and positions of nodes (elements) WVk.

P5.4.    In the case of large symmetric graphs recognizes the products En the binary positions more exact than heuristic models SM, where need to use the binary signs of higher degree. That why it is necessary to treat both in together, bearing in mind also that the heuristic binary signs characterize the essence of relationship itself.

P5.5.    Recognition of the positions by the structure model is more effective than detecting the orbits on the base of the group AutG.

Example 6. To the recognition on the Example 1 represented structure of isobutane suffice use the heuristic model SM:

Explanation: Decomposing the elements C and H to four positions corresponds to actuality. The positions are visually appreciable also on the Example 1.

3. List of tasks that solving based on the identified graphs (structure)

To conclusion it should be emphasized that the recognition of graph’s structure (organizing) is based on the identification (distinction) of binary relations between elements. Binary relation can be measured as a “relation of the distance”, “circle relation”, “clique relation”, etc. Binary relation is recognizable by the corresponding binary sign.

The complex of tasks that are based to recognizing structures is broad, various and novel (differ from up to now set up) [3 - 8]. We list here some.

1.      The relations between structural positions, automorphismsm and group-theoretical orbits.

2.      Structural classification the symmetry properties of graphs.

3.      Measurement the symmetry of graphs.

4.      Analyzing different situations of structural equivalency and graphs isomorphism.

5.      Positional structures that open the “hidden sides” of graphs.

6.      Unknown sides of well-known graphs.

7.      Adjacent structures and reconstruction problem. It is connected with general solving the notorious Ulam’s Conjecture.

8.      Sequences of adjacent structures and their associations – the systems of graph structures.

9.      Probabilistic characteristics of graph’s systems.

10.    The relations of graph systems with classical attributes.

References

1.       Euler. L. Solutio problematis ad geometriam situs pertinentis. – Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128-140.

2.       Mayer, J. Developments recents de la theorie des graphes. – Historia Mathematica 3 (1976) 55-62.

3.       Tevet, J.-T. Semiotic testing of the graphs: a constructive approach and development. S.E.R.R., Tallinn, 2001.

4.                     Hidden sides of the graphs. S.E.R.R. Talinn, 2010.

5.                     Semiotic modeling of the structure. ISBN 9781503367456, Amazon Books. 2014.

6.                     Süsteem. ISBN 9789949388844. S.E.R.R., Tallinn, 2016.

7.                     Systematizing of graphs with n nodes. ISBN 9789949812592. S.E.R.R., Tallinn, 2016.

8.                     What is a graph and how it to study. ISBN 9789949817559. S.E.R.R., Tallinn, 2017.

9.       Weisfeiler, B. On Construction and Identification of Graphs. Springer Lect. Notes Math., 558, 1976 (last issue 2006).