A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

dan815

  • one year ago

draw a graph with 5 vertices that has exactly 22 cycles. a cycle has to start and end with the same vertex, and can only intersect all other vertices only once

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

    |dw:1442366092655:dw|

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

    how to build 22 cyclces exactly with 5 vertices

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

    @Empty

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

    best i can figure is a pentagon. but im only getting 12, maybe you can work off that

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

    you can solve it with brute for algorithm, if u make sure to get rid of the repeating cycles, but im wondering if there is some simple way of figuring out how to construct cycles

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

    |dw:1442368797479:dw|

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

    do you know the brute force algorithm? id be interested in seeing how you go about doing that.

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

    No I dont have one yet, but i was thinking of making one if nothing else. I think it can be made with a few simple rules. Like first drawing out the edge connection matrix lets say v1 v2 v3 v4 v5 v1 0 1 1 1 0 v2 1 v3 . v4 . v5 . .......... we would check for every single possible matrix you can see the possible paths for every vertex and only traverse an edge if it doesnt lead to a vertex you have been to already, or if the vertex you have going to is the starting vertex with some condition statements you can solve for all the paths like this, and to eliminate the identical cycles we have to do a check like this if the path is v1 v2 v3 v4 v5 that is same as v2 v3 v4 v5 v1 v3 v4 v5 v1 v2 ... and so on basically like shifted

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

    you have to also make it follow the official 'graph' definition, no self loops and no multi edges

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

    that can be added as conditions when generating different edge connection matrices

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

    I think this is related to the Euler characteristic equation V-E+F=2

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

    what do you mean

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

    how would you incorporate faces into this

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

    Hmmm I don't know I was thinking the faces would be our cycles or something.

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

    thats kind of interseting lol

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

    finding the actual solution for total number of possible cycles given vertices is still an unsolved question

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

    Well like if you have a loop and you bridge it, you create 2 more loops, can we somehow just build off of this idea?

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

    @ganeshie8 I think the solution is the K5 graph with 1 edge missing, can you confirm with a program or something

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

    I was thinking maybe write a program t hat has all permutations of 1,2,3,4,5 then since we are missing an edge elimnate all the cases where 2 and 5 are together

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

    |dw:1442450749719:dw|

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