The following theorem allows the completion of the game in reverse by exchanging the roles of pegs and holes. Known examples of freely solvable graphs include the Petersen graph, the platonic solids, the Archimedean solids, the complete graph, and the complete -partite graph. We are motivated by the above comments to give examples of freely solvable graphs in this paper. Also shows that, if is freely solvable and is obtained by appending a pendent vertex to any vertex of, then is (at worst) solvable. However, determining whether a specific graph is freely solvable is NP-hard. In, it is shown that, of the nonisomorphic connected graphs on seven vertices or less, only are not freely solvable. The right graph in this figure is freely solvable.Īn example of an unsolvable, a solvable, and a freely solvable graph. The middle graph in Figure 2 is solvable but not freely solvable. In Figure 2, the left graph is not solvable. A graph is distance 2-solvable if there exists some vertex so that, starting with a hole in, there exists an associated terminal state consisting of two pegs that are distance 2 apart. A graph is freely solvable if this is true for all vertices. Ī graph is solvable if there exists some vertex so that, starting with a hole in, there exists an associated terminal state consisting of a single peg. If there are pegs in vertices and and a hole in, then we allow the peg in to jump over the peg in into the hole in provided that. For all undefined graph theory terminology, refer to West. Because of the restrictions of peg solitaire, we will assume that all graphs are finite, undirected, and connected graphs with no loops or multiple edges. A graph,, is a set of vertices,, and a set of edges. In, this notion is generalized to graphs.
0 Comments
Leave a Reply. |