A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

Bee_see

  • one year ago

Draw all non-isomorphic trees on 4 vertices. There are only 2 of them.

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

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

    I don't understand the text for how to find the non-isomorphic trees for n vertices.

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

    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?

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

    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.

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

    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.

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

    why can't the graphs for 3 vertices be drawn like..|dw:1441339802826:dw|? why only straight?

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

    They could, but it would make no difference. They would still be the same graphs.

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

    All that matters is which vertices are connected through which edges.

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

    how are they the same graph?

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

    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|

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

    ok

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

    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.

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

    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.

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

    Here's an example with trees|dw:1441340784337:dw| Can you guess if these two are isomorphic?

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

    I guess they are isomorphic...But I'm just guessing...

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

    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..

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

    these*

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

    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.

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

    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|

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

    By the left and right I mean the graphs in the earlier post|dw:1441341985270:dw|

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

    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.

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

    That's fine. I will re-read the text.

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

    good luck

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

    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.

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.