Referensi awal untuk optimasi diskrit

(Permintaan maaf jika ini salah tempat atau terlalu luas. Saya terbuka untuk saran tentang cara merumuskannya kembali.)

Saya tertarik menelusuri sejarah "kuno" algoritma max-flow, dan algoritma optimasi diskrit secara umum. Ford-Fulkerson adalah pemain inti saya dari titik awal. Apa kemajuan yang signifikan sebelum itu? Seberapa jauh ke belakang kita bisa pergi sambil masih bisa membuat argumen yang masuk akal bahwa seseorang sedang mengerjakan max-flow? Bagaimana dengan algoritma grafik? Bagaimana dengan optimasi diskrit secara umum?

Saya juga akan senang mendapatkan referensi ke tempat-tempat di mana hal ini dibahas.

Biasanya, Schrijver menyediakan sumber sejarah yang bagus. Anda dapat melihat buku dan artikel berikut ini.

• Alexander Schrijver. Optimalisasi Kombinatorial: Polihedra dan Efisiensi. Springer 2003.
• Alexander Schrijver. Teori Pemrograman Linier dan Integer. Wiley 1998.
• Alexander Schrijver. Tentang sejarah transportasi dan masalah aliran maksimum. Pemrograman Matematika 91 (3), 2002, 437-445. http://dx.doi.org/10.1007/s101070100259
• Alexander Schrijver. Tentang sejarah optimasi kombinatorial (hingga 1960). Handbook of Discrete Optimization, Elsevier, 2005. http://homepages.cwi.nl/~lex/files/histco.pdf

Kebanyakan orang mengutip kertas "Bridges of Königsburg" Euler tahun 1741 sebagai algoritma grafik tertua. Sayangnya, Euler tidak benar-benar menggambarkan algoritmenya secara detail, tetapi hanya memberikan contoh yang setengah hati:

“Ketika telah ditentukan bahwa perjalanan seperti itu dapat dilakukan, seseorang masih harus menemukan bagaimana hal itu harus diatur. Untuk ini saya menggunakan aturan berikut: biarkan pasangan jembatan yang mengarah dari satu area ke area yang lain dihilangkan secara mental, dengan demikian sangat mengurangi jumlah jembatan; itu kemudian tugas yang mudah untuk membangun rute yang diperlukan melintasi jembatan yang tersisa. dan jembatan yang telah dihapus tidak akan secara signifikan mengubah rute yang ditemukan, karena akan menjadi jelas setelah sedikit berpikir. Karena itu saya tidak menganggap perlu untuk memberikan perincian lebih lanjut mengenai penemuan rute. ”

Bukti lengkap pertama bahwa semua grafik yang terhubung bahkan memiliki tur Euler tampaknya karena Heirholzer lebih dari seabad kemudian.

• Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae 8: 128–140, 1741. Dipersembahkan ke Akademi St. Petersburg pada 26 Agustus 1735. Dicetak ulang di Opera Omnia 1 (7): 1–10.

• Carl Hierholzer. "Jangan lewatkan Möglichkeit, einen Linienzug Ohne Wiederholung und ohne Unterbrechnung zu umfahren. Mathematische Annalen 6: 30–32, 1873.