Graphe pancake

Le graphe pancake P₄ peut être construit récursivement à partir de 4 copies de P₃ en assignant un élément différent de l'ensemble {1, 2, 3, 4} comme suffixe à chaque copie.

Sommets $n!$
Arêtes ${\frac {1}{2}}n!(n-1)$
Maille 6, si n > 2
Nombre chromatique voir article
Indice chromatique $n-1$
Propriété régulier
Hamiltonien
Cayley
Sommet-transitif
Connectivité
Notation P_n

Dans le domaine mathématique de la théorie des graphes, le graphe pancake P_n ou n-pancake graph est un graphe dont les sommets sont les permutations de n symboles de 1 à n et ses arêtes sont données entre les permutations transitives par inversions de préfixes.

Le tri de crêpes est le terme familier désignant le problème mathématique du tri d'une pile désordonnée de pancakes par ordre de taille lorsqu'une spatule peut être insérée à n'importe quel endroit de la pile et utilisée pour retourner toutes les pancakes qui se trouvent au-dessus d'elle. Un nombre de pancakes est le nombre minimum de retournements requis pour un nombre donné de pancakes. L'obtention du numéro de pancake équivalente au problème de l'obtention du diamètre du graphe des crêpes.

Le graphe de pancake de dimension n, P_n, est un graphe régulier avec $n!$ sommets. Son degré est n−1, donc, selon le lemme de prise de contact, il a ${\dfrac {1}{2}}~n!\left(n-1\right)$ bords. P_n peut être construit de manière récursive à partir de n copies de P_{n − 1}, en attribuant un élément différent de l'ensemble {1, 2,…, n } comme suffixe à chaque copie.

Résultats

P_n (n ≥ 4) est super connecté et hyper connecté.

Leur maille est de

$g(P_{n})=6,{\text{ if }}n>2.$

Le genre γ (P_n) de P_n est borné en bas et en haut par :

$n!\left({\frac {n-4}{6}}\right)+1\leq \gamma (P_{n})\leq n!\left({\frac {3n-10}{12}}\right)+1.$

Propriétés chromatiques

On connaît certaines propriétés de coloration des graphiques des graphes de pancakes.

Un graphe de pancakes P_n ( n ≥ 3) a un nombre chromatique total de$\chi _{t}(P_{n})=n$, indice chromatique $\chi _{e}(P_{n})=n-1$.

Il existe des algorithmes efficaces pour la coloration (n − 1) appropriée et la n-coloration totale des graphes de pancakes.

Les limites suivantes sont connues pour le $\chi (P_{n})$ nombre chromatique :

Si $4\leq n\leq 8$, alors

$\chi (P_{n})\leq {\begin{cases}n-k,&{\text{if }}n\equiv k{\pmod {4}},k=1,3;\\n-2,&{\text{if }}n\equiv k{\pmod {4}},k=0,2;\end{cases}}$

si $9\leq n\leq 16$, alors

$\chi (P_{n})\leq {\begin{cases}n-(k+2),&{\text{if }}n\equiv k{\pmod {4}},k=1,3;\\n-4,&{\text{if }}n\equiv k{\pmod {4}},k=0,2;\end{cases}}$

si $n\geq 17$, alors

$\chi (P_{n})\leq {\begin{cases}n-(k+4),&{\text{if }}n\equiv k{\pmod {4}},k=1,2,3;\\n-8,&{\text{if }}n\equiv k{\pmod {4}},k=0.\end{cases}}$

Le tableau suivant présente les valeurs spécifiques des nombres chromatiques pour un certain nombre de petits n.

Valeurs spécifiques ou probables du nombre chromatique

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
$\chi (P_{n})$	0	1	3	4	5	7	8	9	10	11	13	14	15	16	17	18	19

Énumération des cycles

Dans un graphe de pancake P_n (n ≥ 3), il y a toujours au moins un cycle de longueur ℓ, lorsque $6\leq \ell \leq n!$ (mais il n'y a pas de cycles de longueur 3, 4 ou 5). Cela implique que le graphe est hamiltonien et que deux sommets quelconques peuvent être reliés par un chemin hamiltonien.

À propos des 6 cycles du graphe de pancakes P_n (n ≥ 4) : chaque sommet appartient à exactement un 6 cycles. Le graphe contient ${\frac {n!}{6}}$ 6 cycles indépendants (disjoints au sommets). A propos des 7-cycles du graphe de pancakes Pn (n ≥ 4) : chaque sommet appartient à

À propos des 7 cycles du graphe de pancakes P_n (n ≥ 4) : chaque sommet appartient à $7\cdot (n-3)$ 7 cycles. Le graphe contient $n!\cdot (n-3)$ différents 7 cycles.

À propos des 8 cycles du graphe de pancakes P_n (n ≥ 4) : le graphe contient ${\frac {n!(n^{3}+12n^{2}-103n+176)}{16}}$ différents 8 cycles ; un ensemble maximal de 8 cycles indépendants contient ${\frac {n!}{8}}$ d'entre eux.

Diamètre

Le problème du tri des pancakes (obtenir le nombre de pancakes) et l'obtention du diamètre du graphe de pancakes sont équivalents. L’une des principales difficultés rencontrées dans la résolution de ce problème est la complexité de la structure cyclique du graphe de pancakes.

Numéros de crêpes
(suite A058986 de l'OEIS)

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
$P_{n}$	0	1	3	4	5	7	8	9	10	11	13	14	15	16	17	18	19

Il a été démontré que le nombre de pancakes, c'est-à-dire le nombre minimum de retournements nécessaire pour trier une pile de n pancakes, se situe entre ${15 \over 14}$n et ${18 \over 11}$n (environ 1,07n et 1,64n), mais la valeur exacte reste un problème ouvert

En 1979, Bill Gates et Christos Papadimitriou ont fixé une limite supérieure à ${\frac {5}{3}}$n. Trente ans plus tard, il a été amélioré et est devenu ${\frac {18}{11}}$n par une équipe de chercheurs de l'Université du Texas à Dallas, dirigée par le professeur fondateur Hal Sudborough (Chitturi et al., 2009).

En 2011, Laurent Bulteau, Guillaume Fertin et Irena Rusu ont prouvé que le problème consistant à trouver la plus courte séquence de retournements la plus courte pour une pile de pancakes donnée est NP-hard, répondant ainsi à une question ouverte depuis plus de trois décennies.

Graphe de pancakes brûlés

Dans une variante appelée problème du pancake brûlé, le fond de chaque pancake de la pile est brûlé et le tri doit être effectué avec la face brûlée de chaque pancake vers le bas. Il s'agit d'une permutation signée, et si un pancake i est "brûlé", un élément négatif i` est mis à la place de i dans la permutation. Le graphe de pancakes brûlés est la représentation graphique de ce problème.

Un $P'_{n}$ le graphe des pancakes brûlés est régulier, son ordre est $2^{n}\cdot n!$, son degré est $n$.

Pour sa variante, David S. Cohen (plus connu sous son pseudonyme « David X. Cohen ») et Manuel Blum ont prouvé en 1995 que $3n/2\leq P'_{n}\leq 2n-2$ (lorsque la limite supérieure n'est vraie que si $n>9$).

Numéros de crêpes brûlées
(suite A078941 de l'OEIS)

$n$	1	2	3	4	5	6	7	8	9	10	11	12
$P'_{n}$	1	4	6	8	10	12	14	15	17	18	19	21

La maille d'un graphe de pancakes brûlés est :

$g(P_{n})=8{\text{, if }}n>2.$

Autres classes de graphes de pancakes

Dans le problème original du tri des pancakes et dans le problème des pancakes brûlés, l'inversion du préfixe est l'opération qui relie deux permutations. Si nous autorisons les inversions sans préfixe (comme si nous retournions avec deux spatules au lieu d'une), alors quatre classes de graphe de pancakes peuvent être définies. Chaque graphe de pancakes est intégré dans tous les graphe de pancakes d'ordre supérieur de la même famille.

Classes de graphiques de crêpes

Nom	Notation	Explication	Ordre	Degré	Circonférence (si n>2)
graphe d'inversion de préfixe non signé	$UP_{n}$	Le problème original du tri des pancakes	$n!$	$n-1$	$6$
graphe d'inversion non signé	$UR_{n}$	Le problème initial avec deux spatules	$n!$	${n \choose 2}$	$4$
graphe d'inversion de préfixe signé	$SP_{n}$	Le problème du pancake brûlé	$2^{n}\cdot n!$	$n$	$8$
graphe d'inversion signé	$SR_{n}$	Le problème des pancakes brûlées à deux spatules	$2^{n}\cdot n!$	${n+1 \choose 2}$	$4$

Applications

Les graphes pancakes possèdent de nombreuses propriétés intéressantes, telles que des structures symétriques et récursives (ce sont des graphes de Cayley, donc transitifs aux sommets), un degré et un diamètre à l'échelle logarithmiques, et sont relativement clairsemés (comparés à l'exemple des hypercubes), une grande attention leur est accordée en tant que modèle de réseaux d'interconnexion pour ordinateurs parallèles. Lorsqu'on considère les graphes de pancakes comme le modèle des réseaux d'interconnexion, le diamètre du graphe est une mesure qui représente le délai de communication.

Le retournement des pancakes a également des applications biologiques, dans le domaine des examens génétiques. Dans un type de mutation à grande échelle, un grand segment du génome est inversé, comme dans le cas du problème de la crêpe brûlée.