A community for students.
Here's the question you clicked on:
 0 viewing
Bee_see
 one year ago
Draw all nonisomorphic trees on 4 vertices. There are only 2 of them.
Bee_see
 one year ago
Draw all nonisomorphic trees on 4 vertices. There are only 2 of them.

This Question is Closed

Bee_see
 one year ago
Best ResponseYou've already chosen the best response.0I don't understand the text for how to find the nonisomorphic trees for n vertices.

beginnersmind
 one year ago
Best ResponseYou've already chosen the best response.0Do you feel like you have a good handle on what it means for two graphs to be isomorphic? I don't mean reciting the definition, but looking at two graphs and telling if they are isomorphic or not?

Bee_see
 one year ago
Best ResponseYou've already chosen the best response.0I know there are some things that make two graphs isomorphic...same degree sequence, if they are connected, same number of vertices and edges, and the labeling.

beginnersmind
 one year ago
Best ResponseYou've already chosen the best response.0Isomorphic graphs are basically the same with the labels of the vertices rearranged. E.g:dw:1441339530967:dw So anyway, if you look at that tree on 3 vertices, you can see that there are two types of vertices. The middle and the end. This gives you a hint of how you can connect the 4th vertex.

Bee_see
 one year ago
Best ResponseYou've already chosen the best response.0why can't the graphs for 3 vertices be drawn like..dw:1441339802826:dw? why only straight?

beginnersmind
 one year ago
Best ResponseYou've already chosen the best response.0They could, but it would make no difference. They would still be the same graphs.

beginnersmind
 one year ago
Best ResponseYou've already chosen the best response.0All that matters is which vertices are connected through which edges.

Bee_see
 one year ago
Best ResponseYou've already chosen the best response.0how are they the same graph?

beginnersmind
 one year ago
Best ResponseYou've already chosen the best response.0A graph is a list of verticies and a list of edges. Something like this: Vertices: A, B, C Edges: A connected to B B connected to C You can draw these graphs in various ways. Here's 3 drawings all representing the same graph: dw:1441340182327:dw

beginnersmind
 one year ago
Best ResponseYou've already chosen the best response.0So yeah, graphs are lists of vertices and edges (with the two endvertices included). Trees are graphs where you can't go around a circle. Isomorphism is kind of hard to describe in a few lines but if 2 graphs look the same with the names of the vertices removed then they are isomorphic.

beginnersmind
 one year ago
Best ResponseYou've already chosen the best response.0E.g. dw:1441340605627:dw No matter how I try to relabel the vertices of (1), I won't get (2). They are fundamentally different.

beginnersmind
 one year ago
Best ResponseYou've already chosen the best response.0Here's an example with treesdw:1441340784337:dw Can you guess if these two are isomorphic?

Bee_see
 one year ago
Best ResponseYou've already chosen the best response.0I guess they are isomorphic...But I'm just guessing...

Bee_see
 one year ago
Best ResponseYou've already chosen the best response.0you did write to pay attention to the middle and last vertex in the graph with 3 vertices...I see that you added vertices in this different spots..

beginnersmind
 one year ago
Best ResponseYou've already chosen the best response.0Yes, and that's an important difference. Note that the left hand side one vertex is connected to 3 edges. On the right 2 edges is the maximum. I can't change that by shuffling around the names of the vertices.

beginnersmind
 one year ago
Best ResponseYou've already chosen the best response.0I'm going to list the edges for both: On the left hand side we have: L_E = {(A,B) , (B,C) , (B,D)} On the right hand side: R_E = {(A,B) , (B,C) , (C,D)} The question is can I change around the labels so that I get the same pairs for both? An isomorphism of L_E would be to take all vertices and change them to something else. For example A>B, B>C, C>D, D>A The list of edges after our isomorphic transformation would look like this: L_E* = {(B,C) , (C,D) , (C,A)} or graphically dw:1441341810154:dw

beginnersmind
 one year ago
Best ResponseYou've already chosen the best response.0By the left and right I mean the graphs in the earlier postdw:1441341985270:dw

beginnersmind
 one year ago
Best ResponseYou've already chosen the best response.0Anyway, this is getting somewhat long and I'm not sure this is the best format to explain graphs :) I suggest rereading the text, to try to clear up some confusions.

Bee_see
 one year ago
Best ResponseYou've already chosen the best response.0That's fine. I will reread the text.

zzr0ck3r
 one year ago
Best ResponseYou've already chosen the best response.0They are isomorphic if there is a bijection \(\alpha\) between the sets of vertices such that if \(u\) is adjacent to \(v\) then \(\alpha(u)\) is adjacent to \(\alpha(v)\). I am assuming we mean simple graphs, else the definition is a little more technical, but says the same thing.
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.