**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Graph isomorphism

Summary

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H
such that any two vertices u and v of G are adjacent in G if and only if and are adjacent in H. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection.
If an isomorphism exists between two graphs, then the graphs are called isomorphic and denoted as . In the case when the bijection is a mapping of a graph onto itself, i.e., when G and H are one and the same graph, the bijection is called an automorphism of G.
If a graph is finite, we can prove it to be bijective by showing it is one-one/onto; no need to show both.
Graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. A set of graphs isomorphic to each other is called an isomorphism class of graphs. The question of whether graph isomorphism can be determined in polynomial time is a major unsolved problem in computer science, known as the Graph Isomorphism problem.
The two graphs shown below are isomorphic, despite their different looking drawings
In the above definition, graphs are understood to be undirected non-labeled non-weighted graphs. However, the notion of isomorphic may be applied to all other variants of the notion of graph, by adding the requirements to preserve the corresponding additional elements of structure: arc directions, edge weights, etc., with the following exception.
For labeled graphs, two definitions of isomorphism are in use.
Under one definition, an isomorphism is a vertex bijection which is both edge-preserving and label-preserving.
Under another definition, an isomorphism is an edge-preserving vertex bijection which preserves equivalence classes of labels, i.e., vertices with equivalent (e.g., the same) labels are mapped onto the vertices with equivalent labels and vice versa; same with edge labels.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related units (3)

Related MOOCs (1)

Related concepts (20)

Related courses (28)

Related publications (244)

Related people (49)

La transition énergique suisse / Energiewende in der Schweiz

EE-548: Audio engineering

This lecture is oriented towards the study of audio engineering, with a special focus on room acoustics applications. The learning outcomes will be the techniques for microphones and loudspeaker desig

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications.

MATH-260(a): Discrete mathematics

Study of structures and concepts that do not require the notion of continuity. Graph theory, or study of general countable sets are some of the areas that are covered by discrete mathematics. Emphasis

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational complexity class NP-intermediate. It is known that the graph isomorphism problem is in the low hierarchy of class NP, which implies that it is not NP-complete unless the polynomial time hierarchy collapses to its second level.

In computational complexity theory, a problem is NP-complete when: It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no". When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) solution. The correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.

Related lectures (153)

Learning from the Interconnected World with Graphs

Explores learning from interconnected data using graphs, covering challenges, GNN design, research landscapes, and democratization of Graph ML.

Analyzing Limits: Indeterminate Forms

Explores handling indeterminate forms in limits through simplification and extracting dominant terms for effective evaluation.

Graph Neural Networks: Interconnected World

Explores learning from interconnected data with graphs, covering modern ML research goals, pioneering methods, interdisciplinary applications, and democratization of graph ML.

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to Z(i)Z(j)(-1). The least-squares formulation is nonconvex. To avoid its local minim ...

We prove the non-planarity of a family of 3-regular graphs constructed from the solutions to the Markoff equation x2 + y2 + z2 = xyz modulo prime numbers greater than 7. The proof uses Euler characteristic and an enumeration of the short cycles in these gr ...