A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

CAN SOMEBODY HELP ME FIND A HAMILTON PATH BELOW.

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

    |dw:1435337695042:dw|

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

    Since circles have no vertices is there a rule for it to? I know we can only go through each vertice once right, mhm this seems pretty interesting.

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

    yes , it has to go through one vertix once

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

    The hint given is that the graph is symmetric around the vertix p

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

    no solution ?

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

    How'd you come up with that

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

    i bruteforced : Notice that the hamiltonian path, if it exists, contains exactly 15 edges. We have 27 edges, so total number of choices = \( \binom{27}{15}\)

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

    all of them have repeated vertices, so...

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

    Niceee

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

    im not 100% sure of my method though @SithsAndGiggles

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

    |dw:1435355081518:dw|

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

    http://goo.gl/T1jynP

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

    Mathematica agrees, the graph isn't Hamiltonian.

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

    thnks for checking @SithsAndGiggles do the commands work in wolfram ? if so can you please share them, just want to check how much time wolfram takes..

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

    I don't think W|A supports all the graph theory functions that Mma does, but it's worth a check. Snapshot below (some of the cluttered code is cut off).

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

    `HamiltonianGraphQ` returns `True` if the graph is Hamiltonian, `False` otherwise. As for W|A, I think the character count for the actual graph is too high.

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

    Apparently it's almost instantaneous? I don't know how complex the algorithm being used for the Hamiltonian test is.

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

    Oh then im sure Mma is using some kindof hueristics; the bruteforce method took more than 10 minutes to finish on my laptop

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