Почему идеальные графики называются идеальными?

16

Извините, если это наивный вопрос, но я не смог найти оправдания ни в одном из основных учебников, таких как Бонди-Мёрти, Дистел или Уэст. У совершенных графиков есть много прекрасных свойств, но какова единственная причина, по которой их называют идеальными? Или это просто эстетическое предпочтение Берге?

graph-theory co.combinatorics terminology graph-colouring Ариндам Пал
источник
Предположительно, он изначально называл их парфе и не идеален. Это означает почти то же самое. Возможно, кто-то из говорящих по-французски здесь мог бы сказать нам, является ли парфе на французском языке немного менее абсолютным по значению, чем идеальный на английском.
Питер Шор
6
Значение в нашем языке точно такое же, как и в вашем.
Энтони Лабарр,

Ответы:

16

совершенные графы были сначала мотивированы теорией передачи информации, возникшей из Шеннона, т.е. Шеннона. Емкость графов . Берге называет их «идеальными», потому что они могут использоваться для моделирования бесшумного или «идеального» информационного канала с ошибками преобразования в передаче, называемыми «смешанными». из вступления в [3], которое также имеет очень подробную историю в 1-й главе, сделанной Берге.

Когда Клод Берге определил идеальные графики в 1961 году, он был мотивирован очень практической проблемой: как мы максимизируем скорость, с которой информация отправляется через (шумный) канал передачи, избегая при этом появления ошибок из-за физических недостатков системы ?

[1] К. Берге, История совершенных графов, Юго-Восточная Азия. Математика 20, № 1 (1996) 5-10.
[2] К. Берге, Мотивации и история некоторых моих предположений, Дискретная математика 165-166 (1997) 61-70.
[3] Идеальные графики Хорхе Л. Рамирес-Альфонсин (редактор), Брюс А. Рид (редактор), JLR Альфонсин (автор). Wiley. Ch1, Происхождение и Происхождение Берге и Рамирес-Альфонсин

ВЗН
источник
11
Я подозреваю, что этот ответ мог бы использовать больше объяснения. Для совершенных графиков емкость одного символа с нулевой ошибкой (кодирование информации без использования блочных кодов) равна асимптотической емкости с нулевой ошибкой. Таким образом, вы можете легко рассчитать емкость с нулевой ошибкой, и ее можно получить, используя самый простой код. Одним из знаменитых результатов Ловаша было вычисление этой способности для пятициклового, самого простого неидеального графика. И если прогресс не был достигнут за последние пару лет, мы все еще не знаем, что это за семичастный цикл.
Питер Шор
Мне нравится краткость ответа в сочетании с цитатами. Это тема на периферии для меня, и этот короткий ответ весьма полезен в качестве введения в сложную тему.
DukeZhou