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.
Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies
Informacja
SZANOWNI CZYTELNICY!
UPRZEJMIE INFORMUJEMY, ŻE BIBLIOTEKA FUNKCJONUJE W NASTĘPUJĄCYCH GODZINACH:
Wypożyczalnia i Czytelnia Główna: poniedziałek – piątek od 9.00 do 19.00