UllmannAlgorithmus

The Ullmann algorithm is a classic algorithm used for solving the graph isomorphism problem, which involves determining whether two graphs are structurally equivalent. It was developed by Rudolf Ullmann in 1976 and is notable for its systematic approach to exploring all possible mappings between the vertices of two graphs.

The algorithm operates by constructing a matrix, known as the "feasibility matrix," which keeps track of potential vertex mappings. Initially, all entries in this matrix are set to 1, indicating that any vertex in the first graph could potentially map to any vertex in the second graph. As the algorithm progresses, it prunes the search space by setting entries to 0 when it determines that a particular mapping is not possible.

The Ullmann algorithm employs a backtracking strategy to explore the feasibility matrix. It starts with an empty mapping and iteratively attempts to extend it by mapping vertices from the first graph to the second graph. If an extension leads to a valid partial mapping, the algorithm continues to the next vertex. If no valid extension is possible, it backtracks to the previous vertex and tries a different mapping.

One of the key advantages of the Ullmann algorithm is its simplicity and clarity. However, it can be computationally expensive, especially for large graphs, due to its exhaustive search nature. Over the years, various optimizations and enhancements have been proposed to improve its efficiency, such as the use of pruning techniques and the incorporation of heuristics.

Despite its computational challenges, the Ullmann algorithm remains a fundamental tool in graph theory and has been the basis for many subsequent algorithms and techniques in the field. Its systematic approach to graph isomorphism has laid the groundwork for more advanced methods and continues to be studied and applied in various domains, including computer science, biology, and chemistry.