Some Ideas about Connected Graphs Isomorphism

• Autorzy: Marchenko L. , Podgornaya V.

Identyfikatory

DOI

10.24427/acsr-2018-vol14-0007

Warianty tytułu

Kilka pomysłów na temat izomorfizmu połączonych wykresów

• Języki publikacji: EN

Abstrakty

EN

In the paper we investigate the existence of graphs isomorphism and the search for invariants of connected graphs. A new graph invariant is formulated. It can be used to detect isomorphism of connected graphs. The vector space of all simple cycles of the graph and their edge-disjoint unions (cycle space) and the vector space of all cutting sets of the graph and their edge-disjoint unions (cut space) are constructed in the article for finding a new graph invariant. The authors investigate the method of constructing these vector spaces: cycle space and cut space. A new estimate of the dimensions of these vector spaces of the graph is given. The obtained invariant is demonstrated on a concrete example. A counterexample is constructed to confirm the fact that the proposed invariant can be used as a necessary but not sufficient condition for graphs isomorphism. A heuristic algorithm is proposed for constructing a one-to-one correspondence between sets of vertices of isomorphic graphs.

PL

W artykule badamy istnienie izomorfizmów między grafami oraz poszukujemy niezmienników grafów spójnych. Tworzony jest nowy niezmienniczy graf. Metoda może służyć do wykrywania izomorfizmów między grafami spójnymi. W pracy użyto pojęcia przestrzeni wektorowej wszystkich prostych cykli grafu i ich sum względem rozłącznych krawędzi oraz przestrzeni wektorowej wszystkich zbiorów grafów uciętych i ich rozłącznych krawędziowo sum. Zbadano metodę konstruowania takich przestrzeni wektorowych: przestrzeni cyklicznej i przestrzeni cięcia. Podano nowe oszacowanie wymiarów tych tego typu przestrzeni wektorowych grafów. Otrzymany niezmiennik jest pokazany na konkretnym przykładzie. W pracy podano kontrprzykład, aby potwierdzić fakt, że zaproponowany niezmiennik może być użyty jako warunek konieczny, ale niewystarczający dla izomorfizmu grafów.

Słowa kluczowe

EN

graph; cycle; cutting set; vector space; invariant; isomorphism algorithm

PL

wykres; cykl; zestaw tnący; przestrzeń wektorowa; niezmienny algorytm izomorfizmu

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Advances in Computer Science Research
• Rocznik: 2018
• Tom: Nr 14
• Strony: 105--123
• Opis fizyczny: Bibliogr. 16 poz., rys., wykr.

Twórcy

autor

Marchenko L.

• Faculty of Mathematics and Programming Technologies, Francisk Scorina Gomel State University, Gomel, Belarus

autor

Podgornaya V.

• V.A.Belyi Metal-polymer Research Institute of National Academy of Sciences of Belarus, Gomel, Belarus

Bibliografia

• [1] Нечепуренко М. И.: Алгоритмы и программы решения задач на графах и сетях. Новосибирск, Наука, 1996.
• [2] Карелин В. П. Теория и средства поддержки принятия решений в организационно-технологических системах: дис....дра техн. наука, Таганрог ТРТУ 1995.
• [3] Бернштейн Л. , Карелин В. П., Целых А. Н., Модели и методы принятия решений в интегрированных интелектуальных системах, Ростов/Д, Изд-во РГУ, 1999.
• [4] Пинчук В. П.: Табличные инварианты на графах и ихприменение//Кибернетика и системный анализ, Институт кибернетики НАН Украины, 2001, Но. 4.
• [5] Карелин В. П. Задача распознавания изоморфизма графов. Прикладное значение и подходы к решению, Вестник Таганрoгского института управления и экономики, 2015, Но. 1,С. 102-106.
• [6] Пономаренко И. Н.: Проблема изоморфизма графов: Алгоритмические аспекты,СПб., 2010, 57 с.
• [7] Погребной Ан.В., Погребной В.К.: Метод дифференциации вершин графа и решение проблемы изоморфизма // Известия Томского политехнического университета. Инжиниринг георесурсов. - 2015.- Т. 326. - Но. 6.- С. 34-45.
• [8] Батенков К. А. Числовые характеристики структур сетей связи. Труды СПИИРАН, 2017, Вып. 53, С. 5-28.
• [9] L. Babai, Eugene M. Luks: Canonical labeling of graphs. Proc. 15th ACM Symp. on Theory of Computing, 1983, pp. 171-183.
• [10] Leszló Babai: Graph Isomorphism in Quasipolynomial Time . Submitted 19 January, 2016. -V. 1 submitted 11 December, 2015; originally announced December 2015. [https://arxiv.org/search/cs?searchtype=author&query=Babai%2C+L].
• [11] Ландо С.К.: Графы и топология. М., ВШЭ, 2018., 78 с.
• [12] Сами М., Тхуласираман К.: Графы, сети и алгоритмы. М., Книга Требованию, 2013, 450 с.
• [13] Носов В.И., Бернштейн Т.В., Носкова Н.В., Храмова Т.В. Элементы теории графов: Учебное пособие под редакцией В.И. Носова, СибГУТИ, Новосибирск, 2008, 107 с.
• [14] Кристофидес Н. Теория графов. Алгоритмический подход. Издатепьство: Мир, 1978. 432 с.
• [15] Горбатов В.А. Фундаментальные основы дискретной математики. Учебное пособие. М.: Наука. Физматлит, 544 с.
• [16] Kolasinska E. On a Minimum Cycle Basis of a Graph, Zastosowania Matematyki, 16, 4 (1980), p. 631-639.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).