Pancake graph

rdf:langString Pancake graph

rdf:langString Pancake graph

rdf:langString n − 1

rdf:langString see in the article

rdf:langString see in the article

rdf:langString The pancake graph P4 can be constructed recursively from 4 copies of P3 by assigning a different element from the set {1, 2, 3, 4} as a suffix to each copy.

rdf:langString 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 vertices. Its degree is n − 1, hence, according to the handshaking lemma, it has 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.

rdf:langString n − 1

rdf:langString Pn