Pourquoi les graphiques parfaits sont-ils appelés parfaits?

16

Désolé, si c'est une question naïve, mais je n'ai trouvé la justification dans aucun des principaux manuels comme Bondy-Murty, Diestel ou West. Les graphiques parfaits ont de nombreuses propriétés magnifiques, mais quelle est la seule raison pour laquelle ils sont appelés parfaits? Ou est-ce juste une préférence esthétique de Berge?

graph-theory co.combinatorics terminology graph-colouring Arindam Pal
la source
Vraisemblablement, il les appelait à l'origine parfait et pas parfait. Cela signifie presque la même chose. Peut-être qu'un francophone ici pourrait nous dire si parfait en français a un sens un peu moins absolu que parfait en anglais.
Peter Shor
6
Le sens est exactement le même dans notre langue que dans la vôtre.
Anthony Labarre

Réponses:

16

les graphes parfaits ont d'abord été motivés par la théorie de la transmission d'informations provenant de Shannon, c'est-à-dire la capacité des graphes de Shannon . ils sont appelés "parfaits" par Berge car ils peuvent être utilisés pour modéliser un canal d'information silencieux ou "parfait" avec des erreurs de transposition en transmission appelé "confusion". de l'intro dans [3] qui a aussi une histoire très détaillée dans le 1er chapitre coécrit par Berge.

Lorsque Claude Berge a défini des graphiques parfaits en 1961, il était motivé par un problème très pratique: comment maximiser la vitesse à laquelle les informations sont envoyées via un canal de transmission (bruyant) tout en évitant l'introduction d'erreurs en raison des imperfections physiques du système ?

[1] C. Berge, L'histoire des graphiques parfaits, Bull d'Asie du Sud-Est. Math. 20, n ° 1 (1996) 5-10.
[2] C. Berge, Motivations and history of some of my conjectures, Discrete Mathematics 165-166 (1997) 61-70.
[3] Perfect Graphs de Jorge L. Ramírez-Alfonsín (éditeur), Bruce A. Reed (éditeur), JLR Alfonsin (auteur). Wiley. Ch1, Origines et Genèse de Berge & Ramírez-Alfonsín

vzn
la source
11
Je soupçonne que cette réponse pourrait utiliser plus d'explications. Pour des graphiques parfaits, la capacité d'erreur zéro à un seul symbole (encodage des informations sans utiliser de codes de bloc) est égale à la capacité asymptotique d'erreur zéro. Ainsi, vous pouvez facilement calculer la capacité zéro erreur, et elle peut être obtenue en utilisant le code le plus simple possible. L'un des résultats célèbres de Lovász a été de calculer cette capacité pour le graphique à cinq cycles, le plus simple et non parfait. Et à moins que des progrès aient été réalisés au cours des deux dernières années, nous ne savons toujours pas ce que c'est pour les sept cycles.
Peter Shor
J'aime la brièveté de la réponse, en conjonction avec les citations. C'est un sujet à la périphérie pour moi, et cette courte réponse est très utile comme introduction à un sujet complexe.
DukeZhou