Notices
Results 1 to 9 of 9

Thread: Graph Isomorphism (Planar Graph).

  1. #1 Graph Isomorphism (Planar Graph). 
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    Given “Simple” graphs G, H. Total number of vertices, edges and degree of all vertices are same in G and H. The adjacency matrix of graph G is M1. G has total VG vertices. To find G and H are isomorphic,
    1. Create matrix NG from M1 which would be filled with vertex degree of G from lowest value to highest (in a row).
    2. Create adjacency matrix M2 from M1 according to NG.
    3. Find the degree which is least in NG (say, degree x was found total tx times in NG).Find it’s corresponding vertices in M2, mark them as ‘w’.
    4. Create tx arrays (say, they are g1 [], g2[]….gt[]).
    5. Run “Breadth-first search” (BFS) in all ‘w’ for VG/tx vertices.
    6. While running, for each ‘w’ (parent), array gy[] would be filled according to it’s children’s degree of vertex.
    7. After finishing each “Level”, fill array with ‘l’.
    8. Do step 1 to 7 for graph H.
    9. Compare arrays of G and H. If “Bijection” happens, proceed to step 10, otherwise not isomorphic.
    10. In G, take any “w” marked vertices(say this is wa ), find the distances from other “w” vertices(using BFS), keep it in array, say in ha[].
    up to step 10, works for Planer Graph.

    .....(unfinished)
    Remarks:
    1. Arrays created in step 6, 7 are unique due to step 1, 2.
    2. If two ‘w’ are connected with one edge only and this happens z times then z/2 vertices are left out. These vertices are also manageable.
    3. tx< (VG/2) +1.


    Last edited by jim198810; September 7th, 2014 at 05:22 AM.
    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Two large regular graphs would confuse this algorithm and you'd be left to check all permutations of all vertices in step 9.


    Reply With Quote  
     

  4. #3  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    Quote Originally Posted by MagiMaster View Post
    Two large regular graphs would confuse this algorithm and you'd be left to check all permutations of all vertices in step 9.
    In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency(Wikipedia), in this case, tx= VG (see remark 3)… I am not Concerned about this. This is probably the only special case and also “manageable” though I have not included it here.Thanks.
    Reply With Quote  
     

  5. #4  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    And I have a marvelous proof of this fact but this forum post is too small to contain it.....
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  6. #5  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Quote Originally Posted by jim198810 View Post
    Quote Originally Posted by MagiMaster View Post
    Two large regular graphs would confuse this algorithm and you'd be left to check all permutations of all vertices in step 9.
    In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency(Wikipedia), in this case, tx= VG (see remark 3)… I am not Concerned about this. This is probably the only special case and also “manageable” though I have not included it here.Thanks.
    Yes... although I wouldn't really call that a special case as any graph that's even half regular (that is, half the vertices have the same degree) will cause your algorithm headaches.
    Reply With Quote  
     

  7. #6  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    @ river_rat , you don't nedd to quote Fermat , it is unnecessary. Of course i don't have rigorous proof.If I had, I would not come to this forum for discussion.But yes, I have some arguments, i am checking it currently. whether I have a proof or not I am going to share my arguments within a few days.Any counterexample would help me and that was the main reason I shared in this forum.







    @MagiMaster, yet I am not concerned about regular graph.I gave algo: for simple graph and my main concern was "crossing". I have included steps 10 to 13.Same degree vertices cause problem when they cross in one graph and do not in another.You may check now.

    The whole algorithm is quite big and i am writing it part by part.

    Thanks both of you!!
    Reply With Quote  
     

  8. #7  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Just to be clear, for it to be a polynomial time algorithm for graph isomorphism, it needs to handle any and all graphs.

    That said, the algorithm there is getting fairly long. An example might help see how it's all supposed to work.
    Reply With Quote  
     

  9. #8  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    Should work , Any counter example???
    Reply With Quote  
     

  10. #9  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    You probably shouldn't edit such old posts. It makes the rest of the thread kind of confusing.
    Reply With Quote  
     

Similar Threads

  1. Replies: 1
    Last Post: November 19th, 2013, 02:50 PM
  2. Replies: 3
    Last Post: September 10th, 2010, 04:55 AM
  3. Isomorphism
    By Heinsbergrelatz in forum Mathematics
    Replies: 6
    Last Post: August 17th, 2010, 07:42 PM
  4. NCEP REANALYSIS VARIABLE DESCRIPTION
    By golfy82 in forum Environmental Issues
    Replies: 1
    Last Post: August 25th, 2009, 09:19 PM
  5. A good description for this forum?
    By (In)Sanity in forum Criminology and Forensic Science
    Replies: 15
    Last Post: January 20th, 2008, 09:12 AM
Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •