¿Por qué los gráficos perfectos se llaman perfectos?

16

Lo siento, si esta es una pregunta ingenua, pero no pude encontrar la justificación en ninguno de los principales libros de texto como Bondy-Murty, Diestel u West. Los gráficos perfectos tienen muchas propiedades hermosas, pero ¿cuál es la única razón por la que se llaman perfectos? ¿O es solo una preferencia estética de Berge?

graph-theory co.combinatorics terminology graph-colouring Arindam Pal
fuente
Presumiblemente, originalmente los llamó parfait y no perfectos. Significa casi lo mismo. Posiblemente algún hablante de francés aquí podría decirnos si el parfait en francés tiene un significado ligeramente menos absoluto que el perfecto en inglés.
Peter Shor
66
El significado es exactamente el mismo en nuestro idioma que en el suyo.
Anthony Labarre

Respuestas:

16

Los gráficos perfectos fueron motivados primero por la teoría de transmisión de información que se originó con Shannon, es decir, Shannon Capacidad de los gráficos . Berge los llama "perfectos" porque pueden usarse para modelar un canal de información silencioso o "perfecto" con errores de transposición en la transmisión llamado "confusión". de la introducción en [3], que también tiene una historia muy detallada en el primer capítulo escrito por Berge.

Cuando Claude Berge definió gráficos perfectos en 1961, estaba motivado por un problema muy práctico: ¿cómo maximizamos la velocidad a la que se envía la información a través de un canal de transmisión (ruidoso) mientras evitamos la introducción de errores debido a las imperfecciones físicas del sistema? ?

[1] C. Berge, La historia de los gráficos perfectos, Toro del sudeste asiático. Matemáticas. 20, N ° 1 (1996) 5-10.
[2] C. Berge, Motivaciones e historia de algunas de mis conjeturas, Discrete Mathematics 165-166 (1997) 61-70.
[3] Gráficos perfectos de Jorge L. Ramírez-Alfonsín (Editor), Bruce A. Reed (Editor), JLR Alfonsin (Autor). Wiley Ch1, Orígenes y Génesis por Berge y Ramírez-Alfonsín

vzn
fuente
11
Sospecho que esta respuesta podría usar más explicaciones. Para gráficos perfectos, la capacidad de error cero de un solo símbolo (que codifica la información sin usar códigos de bloque) es igual a la capacidad de error cero asintótica. Por lo tanto, puede calcular fácilmente la capacidad de error cero y se puede obtener utilizando el código más simple posible. Uno de los resultados celebrados de Lovász fue calcular esta capacidad para los cinco ciclos, el gráfico no perfecto más simple. Y a menos que se haya avanzado en los últimos años, todavía no sabemos para qué es el ciclo de siete.
Peter Shor el
Me gusta la brevedad de la respuesta, junto con las citas. Este es un tema en la periferia para mí, y esta breve respuesta es bastante útil como introducción a un tema complejo.
DukeZhou