A community for students.
Here's the question you clicked on:
 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
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

dan815
 one year ago
Best ResponseYou've already chosen the best response.1edges of g1 are 12,15,23,34,45 and the same edges are present in g2

dan815
 one year ago
Best ResponseYou've already chosen the best response.1i was thinking its some case like, taking a look at all the 3 degree vertices, because that subgraph also has to be isomorphic

dan815
 one year ago
Best ResponseYou've already chosen the best response.1if we can just show one of those is not isomorphic then it will save so much time

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1nm I did not click the link

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1for sure list there verts and degree.

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1If they are dif they are not iso, if you think they are iso then you should give the iso :)

dan815
 one year ago
Best ResponseYou've already chosen the best response.1i 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

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1Well, 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.

dan815
 one year ago
Best ResponseYou've already chosen the best response.1so that that isnt simplfying anything T_T

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1yeah I am just noticing this.

dan815
 one year ago
Best ResponseYou've already chosen the best response.1and all have 18 edges too dang

dan815
 one year ago
Best ResponseYou've already chosen the best response.1thyeyre not gonna make it that easyh

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1I would use some algebraic graph theory then. Have you learned about adjacency matrices?

dan815
 one year ago
Best ResponseYou've already chosen the best response.1no not yet, but i do know how to construct one, have not learned anything like what they can be really used for

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1Also the graphs are iso iff their compliments are iso...if that helps.

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1If one adjacency is jsut a permutation of the other, then they are isomorphic.

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1H, 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.

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1look at cycle lengths. Every graph that has all 3 degree verts contains a cycle :) maybe dif sized ones?

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1Can you find a 6 cycle for the one on the right?

dan815
 one year ago
Best ResponseYou've already chosen the best response.1oh thats a good idea, maybe max cycles

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1nm there is a 6 cycle, but maybe some others also...

dan815
 one year ago
Best ResponseYou've already chosen the best response.1i found a cycle with 12 vertices for the left one do u see any longer one

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1no need to find the max, if there is not a 12 in the other two then they are not isomorphic

dan815
 one year ago
Best ResponseYou've already chosen the best response.1yeah thats what i was hoping to find

dan815
 one year ago
Best ResponseYou've already chosen the best response.1the right most one i cannot find one as long as 12, can you

dan815
 one year ago
Best ResponseYou've already chosen the best response.1thanks im gonna work on this problem with this cycles stuff, this should make some progress, count the number of different cycles and stuff

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1well 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.

dan815
 one year ago
Best ResponseYou've already chosen the best response.1you know i was thining, so if we just write that edge connectivity matrix

dan815
 one year ago
Best ResponseYou've already chosen the best response.1get a compujter to compute all the different cycles from the matrix?

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1That would find if they are not iso, but that does not imply they are...

dan815
 one year ago
Best ResponseYou've already chosen the best response.1yeah thats true, okay but can u explain this equation a bit more

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1Read about the adjacency matrix rout. I think there is a standard way to find the perm matrix if they exists.

dan815
 one year ago
Best ResponseYou've already chosen the best response.1i 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

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1one for columns one for rows? Something like that... I proved it last year, but I forget the detail on the proof.

dan815
 one year ago
Best ResponseYou've already chosen the best response.1that might be a little to much for me to take in right now, how about something simpler like this

dan815
 one year ago
Best ResponseYou've already chosen the best response.1if there is a permutation of these rows such that the 2 matrices are equal then does that mean they are isomorphic

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1for sure, because the identity matrix is a permutation matrix

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1wait, that didnt make sense what I said... lol

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1I bet they are, and it would give you the isomorphism

dan815
 one year ago
Best ResponseYou've already chosen the best response.1okay 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

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1I am not sure... Algebraic graph theory starts in 12 days :)

dan815
 one year ago
Best ResponseYou've already chosen the best response.1oh 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

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1But 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.

dan815
 one year ago
Best ResponseYou've already chosen the best response.1hmm quite interseting ill look into this more later

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.1as far as the column thing...

Empty
 one year ago
Best ResponseYou've already chosen the best response.0intuition 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.

dan815
 one year ago
Best ResponseYou've already chosen the best response.1both the row and column permutation has to take place so that the edges and their correponding edges are same?

dan815
 one year ago
Best ResponseYou've already chosen the best response.1and their corresponding vertices* are the same

Empty
 one year ago
Best ResponseYou've already chosen the best response.0Yeah 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.