dan815
  • dan815
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
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
jamiebookeater
  • jamiebookeater
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
dan815
  • dan815
|dw:1442453583161:dw|
dan815
  • dan815
edges of g1 are 12,15,23,34,45 and the same edges are present in g2
dan815
  • dan815
i was thinking its some case like, taking a look at all the 3 degree vertices, because that subgraph also has to be isomorphic

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

dan815
  • dan815
if we can just show one of those is not isomorphic then it will save so much time
zzr0ck3r
  • zzr0ck3r
isomorphic to what?
zzr0ck3r
  • zzr0ck3r
nm I did not click the link
dan815
  • dan815
okay :)
zzr0ck3r
  • zzr0ck3r
for sure list there verts and degree.
zzr0ck3r
  • zzr0ck3r
If they are dif they are not iso, if you think they are iso then you should give the iso :)
dan815
  • dan815
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
zzr0ck3r
  • zzr0ck3r
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.
dan815
  • dan815
they all have degree 3
dan815
  • dan815
so that that isnt simplfying anything T_T
zzr0ck3r
  • zzr0ck3r
yeah I am just noticing this.
dan815
  • dan815
and all have 18 edges too dang
dan815
  • dan815
thyeyre not gonna make it that easyh
zzr0ck3r
  • zzr0ck3r
I would use some algebraic graph theory then. Have you learned about adjacency matrices?
dan815
  • dan815
no not yet, but i do know how to construct one, have not learned anything like what they can be really used for
zzr0ck3r
  • zzr0ck3r
Also the graphs are iso iff their compliments are iso...if that helps.
zzr0ck3r
  • zzr0ck3r
If one adjacency is jsut a permutation of the other, then they are isomorphic.
zzr0ck3r
  • zzr0ck3r
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.
zzr0ck3r
  • zzr0ck3r
look at cycle lengths. Every graph that has all 3 degree verts contains a cycle :) maybe dif sized ones?
zzr0ck3r
  • zzr0ck3r
Can you find a 6 cycle for the one on the right?
dan815
  • dan815
oh thats a good idea, maybe max cycles
zzr0ck3r
  • zzr0ck3r
nm there is a 6 cycle, but maybe some others also...
dan815
  • dan815
i found a cycle with 12 vertices for the left one do u see any longer one
zzr0ck3r
  • zzr0ck3r
no need to find the max, if there is not a 12 in the other two then they are not isomorphic
dan815
  • dan815
http://prntscr.com/8h7kyd
dan815
  • dan815
yeah thats what i was hoping to find
dan815
  • dan815
the right most one i cannot find one as long as 12, can you
dan815
  • dan815
thanks im gonna work on this problem with this cycles stuff, this should make some progress, count the number of different cycles and stuff
dan815
  • dan815
nvm i found a 12 T_T
zzr0ck3r
  • zzr0ck3r
same here :(
zzr0ck3r
  • zzr0ck3r
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.
dan815
  • dan815
you know i was thining, so if we just write that edge connectivity matrix
dan815
  • dan815
get a compujter to compute all the different cycles from the matrix?
zzr0ck3r
  • zzr0ck3r
That would find if they are not iso, but that does not imply they are...
dan815
  • dan815
yeah thats true, okay but can u explain this equation a bit more
zzr0ck3r
  • zzr0ck3r
Read about the adjacency matrix rout. I think there is a standard way to find the perm matrix if they exists.
dan815
  • dan815
A_h= p A_g p^t
zzr0ck3r
  • zzr0ck3r
one second
dan815
  • dan815
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
dan815
  • dan815
|dw:1442455292288:dw|
zzr0ck3r
  • zzr0ck3r
http://math.stackexchange.com/questions/331233/showing-two-graphs-isomorphic-using-their-adjacency-matrices
zzr0ck3r
  • zzr0ck3r
one for columns one for rows? Something like that... I proved it last year, but I forget the detail on the proof.
dan815
  • dan815
that might be a little to much for me to take in right now, how about something simpler like this
dan815
  • dan815
if there is a permutation of these rows such that the 2 matrices are equal then does that mean they are isomorphic
zzr0ck3r
  • zzr0ck3r
for sure, because the identity matrix is a permutation matrix
zzr0ck3r
  • zzr0ck3r
wait, that didnt make sense what I said... lol
zzr0ck3r
  • zzr0ck3r
I bet they are, and it would give you the isomorphism
dan815
  • dan815
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
zzr0ck3r
  • zzr0ck3r
I am not sure... Algebraic graph theory starts in 12 days :)
dan815
  • dan815
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
zzr0ck3r
  • zzr0ck3r
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.
dan815
  • dan815
hmm quite interseting ill look into this more later
zzr0ck3r
  • zzr0ck3r
exactly.
zzr0ck3r
  • zzr0ck3r
as far as the column thing...
Empty
  • Empty
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.
dan815
  • dan815
both the row and column permutation has to take place so that the edges and their correponding edges are same?
dan815
  • dan815
and their corresponding vertices* are the same
Empty
  • Empty
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.
dan815
  • dan815
|dw:1442459721077:dw|
dan815
  • dan815
okay i see right there is symmetry across the diagonal
Empty
  • Empty
Yeah looks good, since the bottom half of your matrix is nothing and your matrix is traceless there really are only \(\frac{n(n-1)}{2}\) entries. So you can possibly cut down on some computation time by being tricky not sure exactly how, maybe by doing something with representing your adjacency matrix as like a sum of a triangular matrix and its transpose? \[P^TAP = P^T(T^T+T)P = P^TT^TP+P^TTP = S^T+S\] So it looks like you really only have to do your permutation matrices on the triangular matrix and that's just as good. since you can always just add the matrix to its transpose later.
dan815
  • dan815
okay i see, i think i get the jist of this, ill play around with permuting matrices on matlab
dan815
  • dan815
i got 1 more question, and im done with this, How to construct 22 cycles exactly with 5 vertices, i need to check if K5-1 is a solution, i am trying to do it combinatorically
dan815
  • dan815
K5 is a completely connected graph with 5 vertices, so everything has degree 4, and k5-1 is that graph with 1 edge missing
dan815
  • dan815
any possible k5-1 graph is isomorphic if u can see that
dan815
  • dan815
lets say we consider this graph without that edge missing just for the k5 case
Empty
  • Empty
Well like since it's like saturated with edges isn't there only one way to make k5-1 edge?
dan815
  • dan815
and yeah, thats right only one way to make a k5-1
dan815
  • dan815
for a k5 graph we can have * a max cycle of 5, as any other cycle greater than 5 would mean you visited a vertex more than once
dan815
  • dan815
for 5 cycles _ , _, _, _, _ (1/2)*5!/5 divided by 5 since 1,2,3,4,5 = 2,3,4,5,1 = 3,4,5,1,2=..... multiplied by half because you are counting the reverse direction too 123451= 154321
dan815
  • dan815
for cycles of length 5 5 choose 5 * 1/2*(5-1)! for cycles of length 4 5 Choose 4 * 1/2 * (4-1)! for cycles of length 3 5 choose 3 * 1/2*(3-1)! ----------------------------- For these i have to subtract the cases where vertex 2 and 5 are side by side
dan815
  • dan815
|dw:1442461283774:dw|

Looking for something else?

Not the answer you are looking for? Search for more explanations.