1 Answers
In the mathematical field of graph theory, the pancake graph Pn or n-pancake graph is a graph whose vertices are the permutations of n symbols from 1 to n and its edges are given between permutations transitive by prefix reversals.
Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. Obtaining the pancake number is equivalent to the problem of obtaining the diameter of the pancake graph.
The pancake graph of dimension n, Pn, is a regular graph with n ! {\displaystyle n!} vertices. Its degree is n − 1, hence, according to the handshaking lemma, it has 1 2 n ! {\displaystyle {\dfrac {1}{2}}~n!\left} edges. Pn can be constructed recursively from n copies of Pn−1, by assigning a different element from the set {1, 2, …, n} as a suffix to each copy.