vignette|Le graphe pancake P4 peut être construit récursivement à partir de 4 copies de P3 en assignant un élément différent de l'ensemble {1, 2, 3, 4} comme suffixe à chaque copie.Sommets Arêtes Maille 6, si n > 2Nombre chromatique voir articleIndice chromatique Propriété régulierHamiltonienCayleySommet-transitif ConnectivitéNotation Pn 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 sommets. Son degré est n−1, donc, selon le lemme de prise de contact, il a 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.
Résultats 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 Blanco, Saúl; Buehrle, Charles (2023-06-20). "Bounds on the genus for 2-cell embeddings of prefix-reversal graphs". arXiv:2306.11295:
Propriétés chromatiques 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, indice chromatique .
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 nombre chromatique :
Si , alors
si , alors
si , alors
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 1234567891011121314151617 01 3 45789101113141516171819
Énumération des cycles Dans un graphe de pancake Pn (n ≥ 3), il y a toujours au moins un cycle de longueur ℓ, lorsque (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 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 cycles. Le graphe contient différents 7 cycles.
À propos des 8 cycles du graphe de pancakes Pn (n ≥ 4) : le graphe contient différents 8 cycles ; un ensemble maximal de 8 cycles indépendants contient 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() 1 2 3 4 5 6 7 8 910 11 12 13 14 15 16 17 0 1 3 4 5 7 8 910 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 pancakes, se situe entre n et 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 à n. Trente ans plus tard, il a été amélioré et est devenu 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 le graphe des pancakes brûlés est régulier, son ordre est , son degré est .
Pour sa variante, David S. Cohen (plus connu sous son pseudonyme « David X. Cohen ») et Manuel Blum ont prouvé en 1995 que (lorsque la limite supérieure n'est vraie que si ). +Numéros de crêpes brûlées() 1 2 3 4 5 6 7 8 910 11 12 1 4 6 810 12 14 15 17 18 19 21 La maille d'un graphe de pancakes brûlés est :
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 ExplicationOrdre Degré Circonférence (si n>2) graphe d'inversion de préfixe non signé Le problème original du tri des pancakes graphe d'inversion non signé Le problème initial avec deux spatules graphe d'inversion de préfixe signé Le problème du pancake brûlé graphe d'inversion signé Le problème des pancakes brûlées à deux spatules
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.
Références
Catégorie:Théorie des graphes