- Tytuł:
-
Some Ideas about Connected Graphs Isomorphism
Kilka pomysłów na temat izomorfizmu połączonych wykresów - Autorzy:
-
Marchenko, L.
Podgornaya, V. - Powiązania:
- https://bibliotekanauki.pl/articles/88384.pdf
- Data publikacji:
- 2018
- Wydawca:
- Politechnika Białostocka. Oficyna Wydawnicza Politechniki Białostockiej
- Tematy:
-
wykres
cykl
zestaw tnący
przestrzeń wektorowa
niezmienny algorytm izomorfizmu
graph
cycle
cutting set
vector space
invariant
isomorphism algorithm - Opis:
-
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.
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. - Źródło:
-
Advances in Computer Science Research; 2018, 14; 105-123
2300-715X - Pojawia się w:
- Advances in Computer Science Research
- Dostawca treści:
- Biblioteka Nauki
Artykuł