1

I'm making a game of line. I have some points and some lines connect them. When player first touch at 1 point the point is marked as "Choosed". Then player touch another point, if there a line connect them the line will be disappear and the second point is marked as "Choosed". Player win when all the line are disappear. I search and see that the game level must contain an Euler path to be able to be finished. But how can I generate level for my game?

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
Kẻ Xấu Xa
  • 11
  • 3

1 Answers1

2

An euler path exists if and only if at most two vertices have odd degree, and the graph is connected.

This means you can first construct a random connected graph, and randomly choose to connect vertices with odd degree, until you reach 0/2 nodes with odd degree.

amit
  • 175,853
  • 27
  • 231
  • 333
  • thank you, do you have an algorithm to generate graphs, which look nice or symmetry? – Kẻ Xấu Xa Sep 29 '15 at 04:43
  • Great idea! It might be worth mentioning that you’re always guaranteed to have an even number of nodes of odd degree via the handshaking lemma, so this will always work. (Though you also need to ensure the graph is connected, right?) – templatetypedef Jan 14 '20 at 16:57