Reviews: EE GB DE RU
John-Tagore Tevet| INTRODUCTION | 0 |
| 1. SEMIOTIC ATTRIBUTES AND THEIR USING | 3 |
| 1.1. Semiotic invariants | 3 |
| 1.2. Itemization the regularities | 5 |
| 1.3. Girth and clique regularity | 5 |
| 1.4. Bisymmetry, clique- and strong regularity | 10 |
| 2. SYMMETRY PROBLEM: THE ORBITS | 14 |
| 2.1. Orbits: equal positions in the structure | 14 |
| 2.2. Symmetry kinds and measuring | 17 |
| 2.3. Orbit structures | 18 |
| 3. PROBLEMS OF CANONICAL REPRESENTATION AND ISOMORPHISM | 21 |
| 3.1. Canonical representation the graphs | 21 |
| 3.2. Deep identification the structure | 23 |
| 3.3. Graph isomorphism problem in general | 27 |
| 3.4. Isomorphism recognition by sign matrices | 29 |
| 3.5. Canonical outputs of isomorphism algorithms | 30 |
| 4. PROBLEMS OF ADJACENT STRUCTURES AND RECONSTRUCTIONS | 34 |
| 4.1. Relationships between isomorphic graphs and their (G\vi)-sub-graphs | 34 |
| 4.2. The adjacent structures: greatest sub- and smallest superstructures | 38 |
| 4.3. On the Ulam’s Conjecture | 40 |
| 4.4. Reconstruction: an opposite operation of deconstruction | 41 |
| 5. SPECIFICATIONS | 44 |
| 5.1. Semiotic Identification Principle | 44 |
| 5.2. System Forming Principle | 47 |
| 5.3. Some specifications about the adjacent structures | 49 |
| SUMMARY | 53 |
| REFERENCES | 54 |
Page created June 1st, 2002
Last edition June, 2010
NB! THE GRAPH ISOMORPHISM PROBLEM IS IN P |
||||||||||
| Abstract: There is under investigation the structure of graphs. It is a method, where on the ground of ‘semiotic invariants’ be constructed a canonical presentation mode of the graphs, which can be used to solve some classical and non-classical problems in a compact non-classical way, such as orbits, symmetry properties, orbit- and adjacent structures, girth- and clique regularity, isomorphism classes, reconstructions and others. | ||||||||||