Anda mungkin sudah pernah diperkenalkan dengan masalah optimisasi. Mahasiswa kalkulus di seluruh dunia mengenal persoalan petani yang berusaha memagari lahan seluas mungkin dengan panjang pagar tertentu, atau orang yang hendak menyeberangi sungai di bagian hilir dari posisinya sekarang dan harus menentukan titik penyeberangan berdasarkan kecepatan berlari dan berenang. Namun, masalah-masalah ini pada dasarnya bersifat kontinu. Secara teori, Anda dapat menyeberangi sungai di titik mana pun yang diinginkan, sekalipun koordinatnya irasional. (Baiklah, tidak benar-benar irasional, tetapi berupa hampiran desimal yang baik.) Dalam mata kuliah ini, kita akan mengkaji beberapa masalah optimisasi yang tidak kontinu karena hanya nilai bilangan bulat bagi variabelnya yang masuk akal. Ternyata, banyak di antaranya sangat sulit diselesaikan secara umum.
Graf tak berarah dengan sepuluh simpul berlabel A, B, C, D, E, F, G, H, J, dan K. Angka di samping setiap sisi menyatakan bobot sisi tersebut; misalnya, sisi dari E ke G berbobot 11, sedangkan sisi dari D ke B berbobot 2.
Misalkan Ariel adalah tenaga penjualan yang berpangkalan di kota \(A\text{.}\) Dalam urutan apa Ariel harus mengunjungi kota-kota lainnya agar melewati masing-masing kota sekurang-kurangnya sekali dan akhirnya kembali ke pangkalannya—dengan tetap meminimumkan jarak total yang ditempuh? Dapatkah Ariel melakukan perjalanan semacam itu dengan mengunjungi setiap kota tepat sekali?
Sanjay adalah insinyur pemeriksa jalan raya dan harus melintasi setiap jalan raya tiap bulan. Pangkalan Sanjay berada di kota \(E\text{.}\) Dalam urutan apa Sanjay harus melintasi jalan-jalan raya tersebut untuk meminimumkan jarak total yang ditempuh? Dapatkah Sanjay melakukan perjalanan semacam itu dengan melintasi setiap jalan raya tepat sekali?
Sekarang misalkan simpul-simpulnya adalah lokasi kantor cabang sebuah bank di Atlanta dan bobot pada suatu sisi menyatakan biaya, dalam jutaan dolar, untuk membangun sambungan data berkapasitas tinggi antara kantor cabang di kedua ujung sisi itu. Dalam model ini, jika tidak ada sisi di antara dua kantor cabang, biaya pembangunan sambungan data bagi pasangan tersebut dianggap terlampau tinggi (di sini kita mungkin tergoda untuk mengatakan bahwa biayanya tak hingga, tetapi para penulis tidak mengaku memahami arti kata itu).
Tantangan kita adalah menentukan sambungan data mana yang perlu dibangun agar terbentuk jaringan tempat setiap kantor cabang dapat berkomunikasi dengan kantor cabang lainnya. Kita mengasumsikan bahwa data dapat mengalir ke kedua arah pada sambungan yang dibangun dan dapat diteruskan melalui sebanyak apa pun sambungan data. Jadi, agar komunikasi sepenuhnya dimungkinkan, kita perlu membangun sebuah pohon merentang dalam jaringan ini. Pada Gambar 1.20, graf \(G\) ditampilkan di sebelah kiri dan salah satu dari sekian banyak pohon merentangnya di sebelah kanan.
Dua panel menggunakan tujuh simpul berlabel A hingga G. Panel kiri memperlihatkan graf berbobot lengkap dengan sebelas sisi. Panel kanan mempertahankan keenam sisi berbobot 12, 25, 19, 18, 23, dan 19 yang menghubungkan seluruh simpul tanpa membentuk siklus, sehingga menjadi pohon merentang.
Bobot pohon merentang adalah jumlah bobot sisi-sisinya. Dalam model kita, jumlah ini menyatakan biaya, sekali lagi dalam jutaan dolar, untuk membangun sambungan data yang berkaitan dengan sisi-sisi dalam pohon merentang. Untuk pohon merentang pada Gambar 1.20, jumlah tersebut adalah
Berapa banyak pohon merentang yang dimiliki graf ini? Untuk graf besar, misalnya graf dengan \(2875\) simpul, apakah masuk akal mencari semua pohon merentang lalu sekadar mengambil yang berbiaya minimum? Secara khusus, untuk bilangan bulat positif \(n\text{,}\) berapa banyak pohon yang memiliki himpunan simpul \(\{1,2,3,\dots,n\}\text{?}\)
