Question

Call graphs$\mathbf{G}\mathbf{and}\mathbf{H}$ isomorphic if the nodes of $\mathit{G}$may be reordered so that it is identical to $\mathit{H}$.

Let $\mathbf{ISO}=\left\{\mathbf{hG},\mathbf{Hi}|\mathbf{G}\mathbf{and}\mathbf{H}\mathbf{are}\mathbf{isomorphic}\mathbf{graphs}\right\}.$Show that $\mathit{I}\mathit{S}\mathit{O}\mathbf{}\mathbf{\in }\mathit{N}\mathit{P}$.

Short answer

Therefore, the solution is$ISO\in NP$ .

Step-by-step solution

To Isomorphism Graph

Isomorphism of graphs is a well-known$NP$ issue. Consider the graph $G_1$with $V_1$vertices and $E_1$edges. Consider the graph $G_2$, which consists of $V_2$vertices and $E_2$dges.

To Retaining Edges & Degrees

Researchers can demonstrate whether charts are invariant if we can create a function that maps $V_1$ into $V_2$ while retaining all the edges and degrees of each vertex. One node's degree is the number of edges it possesses.

Which indicates that graphs $G_1$and $G_2$must have the same number of nodes and have the same overall degree numbers. However, this is insufficient. It's conceivable to have graphs with the same overall degree numbers that don't match or can't be remapped.

Since it can be decided within polynomial time, this is an $NP$problem. The most basic method might take exponential time to complete. This method would verify all potential remapping combinations. Some combinations might be reduced by excluding specific situations, but it would still be factorial.

$GandH$are integers, a nondeterministic polynomial time method for$lSO$ runs as continues to follow: " $OninputhG,Hi,whereGandHareintegers$, a pseudo random quadratic algorithm for $ISO$operates.

To Graph the undirected

Undirected graphs:

1. Where m become the amount of $gandH$nodes. $REJECT$if they do not have the same number of nodes.

2. Generate a combination of m items in a nondeterministic manner.

3. Verify whether$(X,y)$is indeed an edge of $G$is an edge of$HforeachpairofGnodesxandy$.

Accept if everyone agrees.

If any of them vary, less important-cancel." Stage 2 may be accomplished non-deterministically in polynomial time. The first and third stages require polynomial time.

Hence $ISO\in NP$.