Introduction to graph theory/Problems 1

Okay... here's my algorithm for determining graph isomorphims.

Let G1 and G2 be graphs. G1 has m,n vertices and edges; G2 has x,y vertices and edges.

First, does m =x ? If yes = they are potentially isomorphims (as they have the same number of vertices) Next, does n = y ? If yes = they are potentially isomorphims (as they have the same number of edges)

Next, compute eatch vertex degree in G1, and G2. (that is, count how many edges are associated with each vertex).

For G1, sort the vetrex degrees in decending order - we'll call this S1 For G2, sort the vertex degrees in decending order - we'll call this S2

If S1 = S2, they could be isomorphic as they are equal in the sense that the vertex weights are the same.

Loop:

Now from G1 remove all vertices with the weight of (m-1). Now from G2 remove all vertices with the weight of (m-1). Note that the number of edges in G1 and G2 is still equal... how ever the sorted vertex weights may be different! Update the edge count of all vertices

For G1, sort the vetrex degrees in decending order - we'll call this S3 For G2, sort the vertex degrees in decending order - we'll call this S4 If S3 = S4 they could be isomorphic as they are equal in the sense that the vertex weights are the same.

Go back to Loop: and repeat with (m-2), (m-3) until it is 0.

Copyright August 2007, Andrew Walduck. Permission granted to Wikiversity to licences under the GFDL.

andrew.walduck@gmail.com

• <NOTES>*

I tried to prove this: for I = 0 - trival case for I = 1 - trival case assume its true for I = N, then prove N+1. Consider the graph X1 with n, Y1 with n nodes also - they're isomorphisms Add node P to graph X1, and Q to Y1 (the N+1 part) ( If P == Q then the sorted node weight graphs will be the same, if p != Q then the sorted node weight graphs will be different. 3825CJ2N4QJF1