Por que os gráficos perfeitos são chamados de perfeitos?

16

Desculpe, se esta é uma pergunta ingênua, mas não consegui encontrar a justificativa em nenhum dos principais livros de texto como Bondy-Murty, Diestel ou West. Os gráficos perfeitos têm muitas propriedades bonitas, mas qual é a única razão pela qual são chamados de perfeitos? Ou é apenas uma preferência estética de Berge?

graph-theory co.combinatorics terminology graph-colouring Arindam Pal
fonte
Presumivelmente, ele originalmente os chamou de parfait e não perfeito. Significa quase a mesma coisa. Possivelmente, algum falante de francês aqui poderia nos dizer se o parfait em francês é um significado ligeiramente menos absoluto do que perfeito em inglês.
31512 Peter Peter Shor
6
O significado é exatamente o mesmo em nossa língua e na sua.
Anthony Labarre

Respostas:

16

Os gráficos perfeitos foram motivados pela teoria da transmissão de informações originada por Shannon, ou seja, Shannon Capacity of graphs . eles são chamados de "perfeitos" por Berge porque podem ser usados ​​para modelar erros de transposição de canais de informação sem ruído ou "perfeitos" na transmissão chamados "confusos". da introdução em [3], que também tem uma história muito detalhada no primeiro capítulo, escrita por Berge.

Quando Claude Berge definiu gráficos perfeitos em 1961, ele foi motivado por um problema muito prático: como maximizar a taxa na qual as informações são enviadas através de um canal de transmissão (barulhento), evitando a introdução de erros devido às imperfeições físicas do sistema ?

[1] C. Berge, A história dos gráficos perfeitos, Southeast Asian Bull. Matemática. 20, n. ° 1 (1996) 5-10.
[2] C. Berge, Motivações e história de algumas de minhas conjecturas, Matemática Discreta 165-166 (1997) 61-70.
[3] Perfect Graphs, de Jorge L. Ramírez-Alfonsín (editor), Bruce A. Reed (editor), JLR Alfonsin (autor). Wiley. Ch1, Origens e Genesis de Berge & Ramírez-Alfonsín

vzn
fonte
11
Suspeito que esta resposta possa ter mais explicações. Para gráficos perfeitos, a capacidade de erro zero de símbolo único (codificando as informações sem o uso de códigos de bloco) é igual à capacidade de erro zero assintótico. Assim, você pode calcular facilmente a capacidade de erro zero e pode ser obtida usando o código mais simples possível. Um dos célebres resultados de Lovász foi o cálculo dessa capacidade para o ciclo de cinco ciclos, o gráfico não perfeito mais simples. E, a menos que tenha sido feito progresso nos últimos dois anos, ainda não sabemos o que é para os sete ciclos.
quer
Gosto da brevidade da resposta, em conjunto com as citações. Este é um tópico na periferia para mim, e esta resposta curta é bastante útil como introdução a um assunto complexo.
DukeZhou 10/0118