A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

dan815

  • one year ago

http://prntscr.com/8h7e70 Isomorphism, two graphs g1,g2 with n vertices are said to be isomorphic, if there is a way to label the graph's vertices vi, such that an edge ViVj in G1 also exists as edge ViVj in G2

  • This Question is Closed
  1. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1442453583161:dw|

  2. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    edges of g1 are 12,15,23,34,45 and the same edges are present in g2

  3. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    i was thinking its some case like, taking a look at all the 3 degree vertices, because that subgraph also has to be isomorphic

  4. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    if we can just show one of those is not isomorphic then it will save so much time

  5. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    isomorphic to what?

  6. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    nm I did not click the link

  7. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    okay :)

  8. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    for sure list there verts and degree.

  9. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    If they are dif they are not iso, if you think they are iso then you should give the iso :)

  10. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    i dont know how to go about labelling them yet to prove isomorphism or not, but i was just thinking about looking at subgraphs of all deg 2, and deg 3 and so on

  11. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Well, that would be good to show they are not iso, these graphs are small enough that if you just list out the verts and degrees you should be able to see the isomorphism.

  12. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    they all have degree 3

  13. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    so that that isnt simplfying anything T_T

  14. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    yeah I am just noticing this.

  15. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    and all have 18 edges too dang

  16. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    thyeyre not gonna make it that easyh

  17. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I would use some algebraic graph theory then. Have you learned about adjacency matrices?

  18. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    no not yet, but i do know how to construct one, have not learned anything like what they can be really used for

  19. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Also the graphs are iso iff their compliments are iso...if that helps.

  20. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    If one adjacency is jsut a permutation of the other, then they are isomorphic.

  21. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    H, G are iso iff there is a permutation matrix P such that \(A_H=PA_GP^T\) where \(A_H,A_G\) are the respective adjacency matrices.

  22. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    look at cycle lengths. Every graph that has all 3 degree verts contains a cycle :) maybe dif sized ones?

  23. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Can you find a 6 cycle for the one on the right?

  24. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    oh thats a good idea, maybe max cycles

  25. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    nm there is a 6 cycle, but maybe some others also...

  26. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    i found a cycle with 12 vertices for the left one do u see any longer one

  27. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    no need to find the max, if there is not a 12 in the other two then they are not isomorphic

  28. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    http://prntscr.com/8h7kyd

  29. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    yeah thats what i was hoping to find

  30. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    the right most one i cannot find one as long as 12, can you

  31. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    thanks im gonna work on this problem with this cycles stuff, this should make some progress, count the number of different cycles and stuff

  32. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    nvm i found a 12 T_T

  33. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    same here :(

  34. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    well like all isomorphisms, there is not a great way to go about it. I htink the matrix rout would be the fastest, but I doubt they want you to use that.

  35. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    you know i was thining, so if we just write that edge connectivity matrix

  36. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    get a compujter to compute all the different cycles from the matrix?

  37. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    That would find if they are not iso, but that does not imply they are...

  38. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    yeah thats true, okay but can u explain this equation a bit more

  39. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Read about the adjacency matrix rout. I think there is a standard way to find the perm matrix if they exists.

  40. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    A_h= p A_g p^t

  41. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    one second

  42. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    i can see when u say if there is a permutations where the matrices are equal then its true, but why is there p to the left and right and why must be the transpose

  43. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1442455292288:dw|

  44. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    one for columns one for rows? Something like that... I proved it last year, but I forget the detail on the proof.

  45. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    that might be a little to much for me to take in right now, how about something simpler like this

  46. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    if there is a permutation of these rows such that the 2 matrices are equal then does that mean they are isomorphic

  47. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    for sure, because the identity matrix is a permutation matrix

  48. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    wait, that didnt make sense what I said... lol

  49. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I bet they are, and it would give you the isomorphism

  50. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    okay so lets say i define my adjaceny matrix, and get a computer to permute all the possiblilities and see if there is a match, does that prove iso

  51. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I am not sure... Algebraic graph theory starts in 12 days :)

  52. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    oh i see why there is a P^T there, do we need to worry about he column permutations as well as row permutations too maybe

  53. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    But if you can get one perm to look like the other, well then you can easily see the isomorphism. They told you to prove it, so unless you have some theorem that says what you asked...I doubt it. They may want the proof via the definition of iso on finite graph.

  54. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    hmm quite interseting ill look into this more later

  55. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    exactly.

  56. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    as far as the column thing...

  57. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    intuition on using permutation matrices on adjacency matrices is simple, remember that matrix multiplication is associative so it doesn't matter what order you do this in. |dw:1442459245739:dw| This corresponds to this multiplication by a permutation matrix: \[P^TAP = B\] where I've swapped the straight rows with the squiggly rows. Don't forget your adjacency matrix is symmetric, so it doesn't really matter. \(A=A^T\) and oh yeah one last note: The right multiplication by P is flipping columns and left multiplication by \(P^{T}\) is flipping the rows.

  58. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    both the row and column permutation has to take place so that the edges and their correponding edges are same?

  59. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    and their corresponding vertices* are the same

  60. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yeah otherwise you'll get a matrix that isn't symmetric. And all adjacency matrices are symmetric so clearly this has to be fixed. This is how you fix that problem.

  61. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1442459721077:dw|