Dlaczego idealne wykresy nazywane są idealnymi?

Przepraszam, jeśli to naiwne pytanie, ale nie mogłem znaleźć uzasadnienia w żadnej z głównych książek, takich jak Bondy-Murty, Diestel czy West. Idealne wykresy mają wiele pięknych właściwości, ale jaki jest jedyny powód, dla którego nazywane są idealnymi? A może to tylko preferencja estetyczna Berge?

— Arindam Pal
źródło

Przypuszczalnie nazywał je pierwotnie parfaitem, a nie ideałem. To znaczy prawie to samo. Być może niektórzy mówcy po francusku mogliby powiedzieć nam, czy parfait po francusku ma nieco mniej absolutne znaczenie niż doskonały po angielsku.

— Peter Shor

W naszym języku znaczenie jest dokładnie takie samo, jak w twoim.

— Anthony Labarre

idealne wykresy były najpierw motywowane teorią przekazywania informacji pochodzącą od Shannona, tj. Shannon Pojemność grafów . są one nazywane przez Berge „perfekcyjnym”, ponieważ mogą być używane do modelowania bezszumowych lub „perfekcyjnych” błędów transpozycji kanału informacyjnego w transmisji zwanych „mylącymi”. z intro w [3], który ma również bardzo szczegółową historię w pierwszym rozdziale napisanym przez Berge.

Kiedy Claude Berge zdefiniował doskonałe wykresy w 1961 r., Motywował go bardzo praktyczny problem: jak zmaksymalizować szybkość, z jaką informacje są wysyłane ((głośnym) kanałem transmisji), unikając wprowadzania błędów z powodu fizycznych niedoskonałości systemu ?

[1] C. Berge, Historia doskonałych grafów, byk z Azji Południowo-Wschodniej. Matematyka 20, nr 1 (1996) 5-10.
[2] C. Berge, Motywacje i historia niektórych moich domysłów, Discrete Mathematics 165-166 (1997) 61-70.
[3] Perfect Graphs autorstwa Jorge L. Ramíreza-Alfonsína (redaktor), Bruce A. Reed (redaktor), JLR Alfonsin (autor). Wiley. Ch1, Origins and Genesis autorstwa Berge & Ramírez-Alfonsín

— vzn
źródło

Podejrzewam, że ta odpowiedź mogłaby zawierać więcej wyjaśnień. Dla idealnych wykresów pojemność pojedynczego błędu zerowego błędu (kodowanie informacji bez użycia kodów blokowych) jest równa pojemności asymptotycznego błędu zerowego. W ten sposób można łatwo obliczyć pojemność zerowego błędu i można ją uzyskać przy użyciu najprostszego możliwego kodu. Jednym ze słynnych wyników Lovásza było obliczenie tej pojemności dla pięciocyklowego, najprostszego nie idealnego wykresu. I jeśli nie poczyniono postępów w ciągu ostatnich kilku lat, nadal nie wiemy, co to jest dla siedmiocyklowego cyklu.

— Peter Shor

Podoba mi się zwięzłość odpowiedzi w połączeniu z cytatami. To dla mnie temat na peryferiach, a ta krótka odpowiedź jest bardzo przydatna jako wprowadzenie do złożonego tematu.

— DukeZhou,