Ask Your Question
1

Algorithm implementation in Sage

asked 2013-03-14 00:22:04 -0500

Mohab gravatar image

updated 2015-07-31 10:55:42 -0500

FrédéricC gravatar image

Input: Two undirected simple graphs G1 and G2, each having n vertices. Output: True if G1 ? = G2; False otherwise.

for i ? 1,2 do
  Ai ? adjacency matrix of Gi
  pi ? permutation equivalence class of Ai
  A0 i ? lexicographically maximal element of pi
if A0 1 = A0 2 then
  return True
return False

anyone have any idea how to implement this in Sage ?

edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted
1

answered 2013-03-14 06:08:21 -0500

fidbc gravatar image

You can test if $G_1\cong G_2$ using the following function f.

sage: f = lambda g,h: g.is_isomorphic(h)
sage: G = graphs.CubeGraph(3)
sage: H = graphs.HexahedralGraph()
sage: f(G,H)
True

If you really want to use the canonical label then, given a Graph g, you can obtain it by using g.canonical_label() and then just compare the adjacency matrices.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-03-14 00:22:04 -0500

Seen: 127 times

Last updated: Mar 14 '13