Problem badania izomorfizmu grafów

• Autorzy: Dutkiewicz L. , Kijanka P. , Słoboda M.

Warianty tytułu

EN

Problem of graph isomorphism testing

• Języki publikacji: PL

Abstrakty

PL

Artykuł dotyczy problemu izomorfizmu grafów. Przedstawione jest pokrótce to zagadnienie wraz z podstawowymi pojęciami. Zaproponowany i opisany został nowy algorytm sprawdzający, czy dane dwa grafy są izomorficzne. Opiera się on głównie na specjalnej metodzie heurystycznego oznaczania poszczególnych wierzchołków każdego z grafów. Wartość tego oznaczenia, tzw. stopnia zagłębionego, określana jest na podstawie struktury połączeń danego grafu. Przeprowadzone zostały również badania porównawcze szybkości działania zaproponowanego algorytmu oraz innych znanych algorytmów rozwiązujących problem izomorfizmu grafów. Przedstawione i omówione są wyniki wykonanych eksperymentów.

EN

The presented article refers to graph isomorphism problem. Basic terminology has been presented. A new graph isomorphism algorithm has been proposed and described. This algorithm is based on special heuristic method of marking the vertices of both examined graphs. Marking values depend on structure of the graph and degrees of its vertices. Tests of new algorithm and comparisons with other algorithms have been performed. Results of experiments have been presented.

Słowa kluczowe

PL

izomorfizm grafów; grafy

EN

graph isomorphism

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2003
• Tom: T. 7, z. 1-2
• Strony: 83--88
• Opis fizyczny: Bibliogr. 9 poz., tab.

Twórcy

autor

Dutkiewicz L.

• Katedra Automatyki, Akademia Górniczo-Hutnicza w Krakowie

autor

Kijanka P.

• Student kierunku automatyka i robotyka na AGH

autor

Słoboda M.

• Student kierunku automatyka i robotyka na AGH

Bibliografia

• [1] Gross J., Yellen J.: Graph theory and its applications. Baca Raton, CRC Press 1999
• [2] Jankowski B.: Grafy. Algorytmy w Pascalu. Warszawa, ZNI MIKOM 1998
• [3] Klin M.Ch., Póschel R., Rosenbaum K.: Algebra stosowana dla matematyków i informatyków. Warszawa, WNT 1992
• [4] Korzan B.: Elementy teorii grafów i sieci. Warszawa, WNT 1978
• [5] Kulikowski J.L.: Zarys teorii grafów. Warszawa, PWN 1986
• [6] Reingold E.M., Nievergelt J., Deo N.: Algorytmy kombinatoryczne. Warszawa, PWN 1985
• [7] Sysło M., Narsingh D., Kowalik J.S.: Algorytmy optymalizacji dyskretnej z programami w języku Pascal. Warszawa, PWN 1993
• [8] Ullman J.R.: An Algorithm for Subgraph Isomorphism. Journal of the Association for Computing Machinery, vol. 23, No. 1, 1976, 31-42
• [9] Wilson R.J.: Wprowadzenie do teorii grafów. Warszawa, PWN 1985