DonNTU   Masters' portal

Abstract

Introduction

The theory of the graphs is actively applied nowadays in chemistry, informatics and programming, communicative and transport systems, economy, logistics, circuitry for the solution of various tasks. One of major and most difficult tasks of theory of the graphs is finding of topological equivalence. This task steadily affects all areas related to the theory of the graphs in one or another measure. It should be mentioned that universal, qualitative and rapid method of determination of topological equivalence of vertices of the graph is not developed at a present.

Complication of this task consists of necessity to define a moment, stops of agent bypassing the graph. In connection with this problem an application of genetic and neuronetwork algorithms is seemed to be impossible that complicates the process of finding of optimum decision considerably.

1. Subject urgency

The problem of topology arises in increasing frequency both in programming, and in chemistry presently. Generally this task is examined by programmers as it arises when programming movement of the robot on locality which must create the map of locality and define is he set in locality map of which is given initially or that is other locality and a map must be saved.

As check on a bisimulation actively is used when testing, in Petri's networks and LTS (the marked systems of transitions). The topology is a natural language for studying systems connected with creation of the scheme of coherence of atoms in a molecule.

2. Scientific meaningfulness of work

During research the algorithm of movement of agent on the oriented graph with the marked vertices and edges, which will allow to simplify as much as possible a testing process with LTS use, and at Petri's networks comparison at the final stage of development of systems will be received.

3. Master's degree research results

In this master's degree research the algorithms of determination of isomorphism of graphs will be considered. The key element of this work is determination of isomorphism of trees with the marked vertices.

Entrance: graphs G1(s) and G2(t). Graphs: oriented, without multiple arcs, determined.

Matric MATRi is an adjacency of graphs G1 and G2, initial vertices s and t, L1 and L2 a set of labels of vertices of the graph, Vi(G1,G2), Vn(Gn) – vertices of the graph, Gn – new graph, array of new vertices of Smeg(Vn).

Output: Are the graphs equivalent or not topologically.

Method: We build Gn(Vn) on tiers.

Algorithm.

  1. If L(G1)=L(G2) we pass to 2, otherwise to 15. Graphs G1 and G2 are investigated from vertices of V1 (s0) and V1 (t0).
  2. If L1=l2, we pass to 3, otherwise to 15.
  3. We create the vertex the graph Vn and assign it the same number, which the graph G1 has and pass to 4.
  4. Every adjacent vertices of Vi (s) and Vi (t) will be constructed. We build as many edges as many letters in the alphabet of labels. Then pass to 5.
  5. If there will be Vsi=0 and Vti=vi(t) or Vsi= Vi(s) and Vti=0 among the received results, we pass to 15, otherwise 6.
  6. If the leafs Vsi=0 and Vti=0 we delete cross-section and reverse edges, and vertex, otherwise 7.
  7. If leafs in a graph Gn are recurred we pass to 8, otherwise 12.
  8. We stick together the vertices of Vn(si,ti)=Vn(si,ti) and come to 9.
  9. We save the numbers of vertices of Vsi, Vti and mark of vertex of L of the graph G1 save in the array of new vertices of Smeg(Vn) and pass to 10.
  10. We fill an adjacency of MatrGn matrix and pass to 11.
  11. If it is impossible to construct a new tier of Vi, we pass to step 12, otherwise 4.
  12. We move to the tier back and check, can we construct a tier of any of vertices. If yes pass to 4. If no, move till will not get at the beginning, and come to the step 13.
  13. If G1=Gn pass to 14, otherwise 15.
  14. Graphs topologically are equivalent.
  15. Graphs topologically are not equivalent.

ВIn general, the process of the algorithm is shown in Figure 3.

topological

Figure 3 – Algorithm of the topological equivalence
(animation: 8 frames, 10 cycles of repeating, 30,4 kilobytes)
(G1 и G2 – graphs, Gn – graph shows the topological equivalence G1, G2)

Conclusion

The developed algorithm is one of directions the theory of the graphs, namely isomorphism of graphs and represents not only probability-research but also practical interest. The development of algorithm will open a way to а wider application of the theory of counts at robotics design.

Master's degree work is devoted the actual scientific task of association of basic methods of determination of isomorphism of graphs and algebra of language of marking. Within the carried-out researches is executed:

  1. The basic principles of isomorphism are investigated.
  2. Task statement is developed.
  3. On the basis of analysis of literary sources the basic algorithms which can be used in the offered approach to determination of bissimulation trees are selected.

Further researches are directed on the followings aspects:

  1. Completion of base algorithms under the set specification.
  2. Determination of scopes of efficiency of the developed algorithm.
  3. Carrying out mathematical calculation of labour hours and memory on realization.

References

  1. Алексеев В.Е. Графы. Модели Вычислительных структур данных / В.Е. Алексеев, В.А. Таланов. – Нижний Новгород. : НижГУ, 2004. – 294 с.
  2. Башкин В.А. Построение приближений бисимуляции в одноточечных сетях / В.А. Башкин // Труды конференции «Моделирование и анализ информационных систем» – Ярославль: Ярославский государственный университет им. Демидова, 2011. – С. 34–44
  3. Бухштабер В.М. Торическая топология / В.М. Бухштабер // Общеинститутский семинар « Математика и ее приложения» М : Институт им. В.А. Стеклова, 1990. – 35 с.
  4. Бухштабер В.М. Торические действия в топологии и комбинаторике / В. М. Бухштабер, Т. Е. Панов – М : МЦ-НМО, 2004. – 272 с.
  5. Горбиков С.П. Топологической эквивалентности одного типа локальных особенностей динамических систем с ударными взаимодействиями / С.П. Горбиков // Математические заметки, – т.70. – №2. – 2001. – 14 с.
  6. Грунский И.С. Распознавание лабиринтов при помощи конечных автоматов / И.С. Грунский, Е.А. Татаринов // Труды 4 междунар. конф. «Параллельные вычисления и задачи управления», РАСО’2008, 27–29 октября 2008 г., Москва. – М: ИПУ РАН им. В. А. Трапезникова, 2008. – С. 1483–1498.
  7. Грунский И.С. Распознавание конечного графа блуждающим по нему агентом / И.С. Грунский, Е.А. Татаринов // Труды 6 междунар. конф. «Параллельные вычисления и задачи управления», РАСО’2009, 27–29 октября 2009 г., Москва. – М: ИПУ РАН им. В.А. Трапезникова, 2008. – С. 483–498.
  8. Грунский И.С. Об алгебре языков, представимых графами с отмеченными вершинами / И.С. Грунский, Е.А. Пряничникова // Труды Ин-та прикл. математики и механики НАН Украины. – 2009. – т.18. – С. 37–46.
  9. Грунский И.С. Эксперементы с помечеными графами / И. С. Грунский, С. В. Сапунов, Е.А. Татаринов // Восьмая международная научная конференция «Дискретные модели в теории управляющих систем» М: МГУ 2009. – С. 43–45.
  10. Москинова Г.И. Дискретная математика / Москинова Г. И. – М.: Логос, 2000. – 198 с.
  11. Олищук С.А. Базовые графы для построения топологии многопроцессорных систем / С.А. Олищук, М.А. Волк // Конференция «Системы управления, навигации и связи» – Харьков: ХНУР, 2010. – т.16, вып.4. – С.150–158.
  12. Пинчук. В.П. Базовые графы для построения топологии многопроцессорных систем / В.П. Пинчук // Труды 4 конф. «Искусственный интеллект» – Донецк: ГУИиИИ, 2004. – № 4. – С.46–58.
  13. Пришляк А.О. Топологическая эквивалентность векторных полей морса-смейла c beh-2 на трехмерных многообразиях / А.О.Пришляк // Успехи математической науки – т.56. – №2. – 2001. – С. 211–212.
  14. Пряничникова Е.А. О полноте системы аксиом для алгебры языков, представимых ориентированными графами с отмеченными вершинами / Е.А. Пряничникова // Вісник донецького національного університету. Сер. А: Природничі науки. – 2010. – №.1. – С. 259–267.
  15. Пряничникова Е.А. Характеризация языков, представимых в графах с отмеченными вершинами / Е.А. Пряничникова // Труды Ин-та прикл. математики и механики НАН Украины. – 2010. – т.19. – С. 37–46.
  16. Пряничникова Е.А. О полноте системы аксиом для алгебры языков, представимых ориентированными графами с отмеченными вершинами / Е.А. Пряничникова // Вісник донецького національного університету. Сер. А: Природничі науки. – 2010. – №.1. – С. 259–267.
  17. Пряничникова Е.А. Алгебра языков, представимых в отмеченных графах / Е.А. Пряничникова // Theoretical and Applied Aspects of Cybernetics: International Scientific Conference of Students and Young Scientists. – Kyiv. – 2011. – P. 177–179.