Warum heißen perfekte Graphen perfekt?

16

Entschuldigung, wenn dies eine naive Frage ist, aber ich konnte die Rechtfertigung in keinem der Hauptlehrbücher wie Bondy-Murty, Diestel oder West finden. Perfekte Grafiken haben viele schöne Eigenschaften, aber was ist der einzige Grund, warum sie als perfekt bezeichnet werden? Oder ist es nur eine ästhetische Vorliebe von Berge?

graph-theory co.combinatorics terminology graph-colouring Arindam Pal
quelle
Vermutlich nannte er sie ursprünglich Parfait und nicht perfekt. Es bedeutet fast dasselbe. Möglicherweise könnte uns hier ein französischer Sprecher sagen, ob Parfait in Französisch eine etwas weniger absolute Bedeutung hat als perfekt in Englisch.
Peter Shor
6
Die Bedeutung ist in unserer Sprache genauso wie in Ihrer.
Anthony Labarre

Antworten:

16

Perfekte Graphen wurden zuerst durch die Informationstransmissionstheorie motiviert, die ihren Ursprung in Shannon hatte, dh Shannon Capacity of Graphs . Sie werden von Berge als "perfekt" bezeichnet, da sie verwendet werden können, um einen geräuschlosen oder "perfekten" Informationskanal hinsichtlich Übertragungsfehlern zu modellieren, die als "verwirrend" bezeichnet werden. aus dem Intro in [3], das auch im 1. Kapitel von Berge eine sehr ausführliche Geschichte hat.

Als Claude Berge 1961 perfekte Graphen definierte, war er von einem sehr praktischen Problem motiviert: Wie können wir die Geschwindigkeit maximieren, mit der Informationen über einen (verrauschten) Übertragungskanal gesendet werden, während die Einführung von Fehlern aufgrund der physischen Mängel des Systems vermieden wird? ?

[1] C. Berge, Die Geschichte der perfekten Grafiken, Southeast Asian Bull. Mathematik. 20, Nr. 1 (1996) 5-10.
[2] C. Berge, Motivationen und Geschichte einiger meiner Vermutungen, Discrete Mathematics 165-166 (1997) 61-70.
[3] Perfect Graphs von Jorge L. Ramírez-Alfonsín (Herausgeber), Bruce A. Reed (Herausgeber), JLR Alfonsin (Autor). Wiley. Ch1, Origins and Genesis von Berge & Ramírez-Alfonsín

vzn
quelle
11
Ich vermute, diese Antwort könnte eine genauere Erklärung gebrauchen. Für perfekte Grafiken entspricht die Kapazität für den Nullfehler eines einzelnen Symbols (Codierung der Informationen ohne Verwendung von Blockcodes) der Kapazität für den asymptotischen Nullfehler. Auf diese Weise können Sie leicht die Null-Fehler-Kapazität berechnen, und sie ist unter Verwendung des einfachstmöglichen Codes erhältlich. Eines der berühmtesten Ergebnisse von Lovász war die Berechnung dieser Kapazität für den Fünfzyklus, den einfachsten nicht perfekten Graphen. Und wenn in den letzten Jahren keine Fortschritte erzielt wurden, wissen wir immer noch nicht, was es für den Sieben-Zyklus ist.
Peter Shor
Ich mag die Prägnanz der Antwort in Verbindung mit den Zitaten. Dies ist für mich ein peripheres Thema, und diese kurze Antwort ist sehr nützlich als Einführung in ein komplexes Thema.
DukeZhou