If $G_1$ and $G_2$ have different numbers of vertices, they are not isomorphic, so below, we consider
only the case where $G_1$ and $G_2$ have the same number of vertices. Let $N$ be the number of
vertices in
$G_1$. Formulate as follows.
Decision variables¶
To represent the correspondence between two graphs, we prepare a binary variable table $q$ of
$N\times
N$.
When the $i$-th vertex of $G_1$ corresponds to the $j$-th vertex of $G_2$, the $i$ row $j$ column of
$q$
should be $1$.
For example, comparing the correspondence between the number and color of the vertices connected by
edges
in $G_1$ and $G_2$ in the figure above, the two graphs corresponded as follows.
| Vertices of G1 |
Vertices of G2 |
Color |
| 0 |
0 |
Blue |
| 1 |
2 |
Orange |
| 2 |
4 |
Green |
| 3 |
1 |
Red |
| 4 |
3 |
Purple |
Representing this in a table of binary variables $q$, we have the following.
| G1 \ G2 |
0 |
1 |
2 |
3 |
4 |
| 0 |
1 |
0 |
0 |
0 |
0 |
| 1 |
0 |
0 |
1 |
0 |
0 |
| 2 |
0 |
0 |
0 |
0 |
1 |
| 3 |
0 |
1 |
0 |
0 |
0 |
| 4 |
0 |
0 |
0 |
1 |
0 |
Objective function¶
Since the graph isomorphism problem is to find one that satisfies the conditions, we do not need to
consider the objective function.
Constraints¶
For $q$ to represent an isomorphic map, we need the following.
-
Condition 1: Each vertex of $G_1$ corresponds to one vertex of $G_2$. That is, each row of $q$
has
only one $1$.
-
Condition 2: Each vertex of $G_2$ corresponds to one vertex of $G_1$. That is, each column of $q$
has
only one $1$.
-
Condition 3: If vertices $u$ and $v$ in $G_1$ are connected by an edge, then the $2$ vertices in
$G_2$ corresponding to $u$ and $v$ are also connected by an edge.
-
Condition 4: If vertices $s$ and $t$ in $G_2$ are connected by an edge, then the $2$ vertices of
$G_1$ corresponding to $s$ and $t$ are also connected by an edge.
The conditions 1 and 2 are
\begin{align*}
\sum_{j = 0}^{N-1} q_{i, j} = 1 \quad & \text{for} \quad i \in \{0, 1, \ldots, N-1\} \\
\sum_{i = 0}^{N-1} q_{i, j} = 1 \quad & \text{for} \quad j \in \{0, 1, \ldots, N-1\}.
\end{align*}
Condition 3 can be reworded as "if the vertices $u$ and $v$ of $G_1$ are connected by an edge and the
vertices $s$ and $t$ of $G_2$ are not connected by an edge, $u$ and $s$ and $v$ and $t$ must not
correspond to each other". Thus, this condition can be
$$
q_{u, s} q_{v, t} = 0 \quad \text{for} \quad (u\rightarrow v) \in E_1, (s\rightarrow t) \notin E_2.
$$
Here, $E_1$ and $E_2$ are the edge sets of $G_1$ and $G_2$, respectively.
Similarly, the condition 4 is
$$
q_{u, s} q_{v, t} = 0 \quad \text{for} \quad (u\rightarrow v) \notin E_1, (s\rightarrow t) \in E_2.
$$
If the conditions 1-4 hold, then graphs $G_1$ and $G_2$ are isomorphic. The above completes the
formulation of the graph isomorphism problem.
