Bee_see
  • Bee_see
Draw all non-isomorphic trees on 4 vertices. There are only 2 of them.
Discrete Math
  • 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.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
Bee_see
  • Bee_see
Bee_see
  • Bee_see
I don't understand the text for how to find the non-isomorphic trees for n vertices.
beginnersmind
  • beginnersmind
Do 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?

Looking for something else?

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

More answers

Bee_see
  • Bee_see
I 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
  • beginnersmind
Isomorphic 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
  • Bee_see
why can't the graphs for 3 vertices be drawn like..|dw:1441339802826:dw|? why only straight?
beginnersmind
  • beginnersmind
They could, but it would make no difference. They would still be the same graphs.
beginnersmind
  • beginnersmind
All that matters is which vertices are connected through which edges.
Bee_see
  • Bee_see
how are they the same graph?
beginnersmind
  • beginnersmind
A 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|
Bee_see
  • Bee_see
ok
beginnersmind
  • beginnersmind
So yeah, graphs are lists of vertices and edges (with the two end-vertices 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
  • beginnersmind
E.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
  • beginnersmind
Here's an example with trees|dw:1441340784337:dw| Can you guess if these two are isomorphic?
Bee_see
  • Bee_see
I guess they are isomorphic...But I'm just guessing...
Bee_see
  • Bee_see
you 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..
Bee_see
  • Bee_see
these*
beginnersmind
  • beginnersmind
Yes, 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
  • beginnersmind
I'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
  • beginnersmind
By the left and right I mean the graphs in the earlier post|dw:1441341985270:dw|
beginnersmind
  • beginnersmind
Anyway, 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
  • Bee_see
That's fine. I will re-read the text.
beginnersmind
  • beginnersmind
good luck
zzr0ck3r
  • zzr0ck3r
They 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.

Looking for something else?

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