Dlaczego idealne wykresy nazywane są idealnymi?

16

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?

graph-theory co.combinatorics terminology graph-colouring 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
6
W naszym języku znaczenie jest dokładnie takie samo, jak w twoim.
Anthony Labarre

Odpowiedzi:

16

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
11
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,