Graphe pancake

Dans le domaine mathématique de la théorie des graphes, le graphe pancake Pn 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, Pn, est un graphe régulier avec n ! {\displaystyle n!} sommets. Son degré est n−1, donc, selon le lemme de prise de contact, il a 1 2 n ! ( n − 1 ) {\displaystyle {\dfrac {1}{2}}~n!\left(n-1\right)} bords. Pn peut être construit de manière récursive à partir de n copies de Pn − 1, en attribuant un élément différent de l'ensemble {1, 2,…, n } comme suffixe à chaque copie.
Pn (n ≥ 4) est super connecté et hyper connecté.
Leur maille est de
Le genre γ (Pn) de Pn est borné en bas et en haut par :
On connaît certaines propriétés de coloration des graphiques des graphes de pancakes.
Un graphe de pancakes Pn ( n ≥ 3) a un nombre chromatique total de χ t ( P n ) = n {\displaystyle \chi _{t}(P_{n})=n} , indice chromatique χ e ( P n ) = n − 1 {\displaystyle \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 χ ( P n ) {\displaystyle \chi (P_{n})} nombre chromatique :
Si 4 ≤ n ≤ 8 {\displaystyle 4\leq n\leq 8} , alors
si 9 ≤ n ≤ 16 {\displaystyle 9\leq n\leq 16} , alors
si n ≥ 17 {\displaystyle n\geq 17} , alors
Le tableau suivant présente les valeurs spécifiques des nombres chromatiques pour un certain nombre de petits n.
Dans un graphe de pancake Pn (n ≥ 3), il y a toujours au moins un cycle de longueur ℓ, lorsque 6 ≤ ℓ ≤ n ! {\displaystyle 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 Pn (n ≥ 4) : chaque sommet appartient à exactement un 6 cycles. Le graphe contient n ! 6 {\displaystyle {\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 Pn (n ≥ 4) : chaque sommet appartient à 7 ⋅ ( n − 3 ) {\displaystyle 7\cdot (n-3)} 7 cycles. Le graphe contient n ! ⋅ ( n − 3 ) {\displaystyle n!\cdot (n-3)} différents 7 cycles.
À propos des 8 cycles du graphe de pancakes Pn (n ≥ 4) : le graphe contient n ! ( n 3 + 12 n 2 − 103 n + 176 ) 16 {\displaystyle {\frac {n!(n^{3}+12n^{2}-103n+176)}{16}}} différents 8 cycles ; un ensemble maximal de 8 cycles indépendants contient n ! 8 {\displaystyle {\frac {n!}{8}}} d'entre eux.
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.
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 14 {\displaystyle {15 \over 14}} n et 18 11 {\displaystyle {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 à 5 3 {\displaystyle {\frac {5}{3}}} n. Trente ans plus tard, il a été amélioré et est devenu 18 11 {\displaystyle {\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.
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 ′ {\displaystyle P'_{n}} le graphe des pancakes brûlés est régulier, son ordre est 2 n ⋅ n ! {\displaystyle 2^{n}\cdot n!} , son degré est n {\displaystyle n} .
Pour sa variante, David S. Cohen (plus connu sous son pseudonyme « David X. Cohen ») et Manuel Blum ont prouvé en 1995 que 3 n / 2 ≤ P n ′ ≤ 2 n − 2 {\displaystyle 3n/2\leq P'_{n}\leq 2n-2} (lorsque la limite supérieure n'est vraie que si n > 9 {\displaystyle n>9} ).
La maille d'un graphe de pancakes brûlés est :
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.
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.