Mengapa grafik sempurna disebut sempurna?

16

Maaf, jika ini adalah pertanyaan naif, tapi saya tidak dapat menemukan pembenaran di salah satu buku teks utama seperti Bondy-Murty, Diestel atau Barat. Grafik sempurna memiliki banyak properti yang indah, tetapi apa alasan mereka disebut sempurna? Atau itu hanya preferensi estetika oleh Berge?

graph-theory co.combinatorics terminology graph-colouring Arindam Pal
sumber
Agaknya, ia awalnya menyebut mereka parfait dan tidak sempurna. Itu berarti hal yang hampir sama. Mungkin beberapa penutur bahasa Prancis di sini dapat memberi tahu kami apakah parfait dalam bahasa Prancis sedikit kurang berarti daripada sempurna dalam bahasa Inggris.
Peter Shor
6
Artinya persis sama dalam bahasa kita seperti dalam bahasa Anda.
Anthony Labarre

Jawaban:

16

grafik sempurna pertama kali dimotivasi oleh teori transmisi informasi yang berasal dari Shannon yaitu Shannon Capacity of graphs . mereka disebut "sempurna" oleh Berge karena mereka dapat digunakan untuk memodelkan saluran informasi yang tidak bersuara atau "sempurna" dan kesalahan transposisi dalam transmisi yang disebut "pengganggu". dari intro di [3] yang juga memiliki sejarah yang sangat terperinci dalam bab 1 yang ditulis oleh Berge.

Ketika Claude Berge mendefinisikan grafik yang sempurna pada tahun 1961, ia termotivasi oleh masalah yang sangat praktis: bagaimana kita memaksimalkan tingkat di mana informasi dikirim melalui saluran transmisi (berisik) sambil menghindari pengenalan kesalahan karena ketidaksempurnaan fisik dari sistem ?

[1] C. Berge, Sejarah grafik sempurna, Banteng Asia Tenggara. Matematika 20, No.1 (1996) 5-10.
[2] C. Berge, Motivasi dan sejarah beberapa dugaan saya, Matematika Terpisah 165-166 (1997) 61-70.
[3] Grafik Sempurna oleh Jorge L. Ramírez-Alfonsín (Editor), Bruce A. Reed (Editor), JLR Alfonsin (Penulis). Wiley. Ch1, Origins and Genesis oleh Berge & Ramírez-Alfonsín

vzn
sumber
11
Saya menduga jawaban ini bisa menggunakan lebih banyak penjelasan. Untuk grafik sempurna, kapasitas kesalahan nol simbol tunggal (penyandian informasi tanpa menggunakan kode blok) sama dengan kapasitas kesalahan nol asimptotik. Dengan demikian, Anda dapat dengan mudah menghitung kapasitas zero-error, dan dapat diperoleh dengan menggunakan kode sesederhana mungkin. Salah satu hasil terkenal Lovász adalah menghitung kapasitas ini untuk lima siklus, grafik tidak sempurna yang paling sederhana. Dan kecuali jika kemajuan telah dibuat dalam beberapa tahun terakhir, kita masih tidak tahu apa itu untuk siklus tujuh.
Peter Shor
Saya suka ringkasnya jawaban, dalam hubungannya dengan kutipan. Ini adalah topik di pinggiran saya, dan jawaban singkat ini cukup berguna sebagai pengantar topik yang kompleks.
DukeZhou