Subbab 5.6 Menghitung Pohon Berlabel

Berapa banyak pohon yang memiliki himpunan simpul \([n]=\{1,2,\dots,n\}\text{?}\) Misalkan \(T_n\) menyatakan jumlah ini. Untuk \(n=1\text{,}\) jelas hanya ada satu pohon. Demikian pula, untuk \(n=2\text{,}\) hanya ada satu pohon, yang isomorfik dengan \(\bfK_2\text{.}\) Ketika menentukan \(T_3\text{,}\) akhirnya ada sedikit pekerjaan yang perlu dilakukan; namun, pekerjaan itu tidak banyak karena semua pohon pada \(3\) simpul isomorfik dengan \(\bfP_3\text{.}\) Jadi, terdapat \(T_3=3\) pohon berlabel pada \(3\) simpul, sesuai dengan pilihan simpul mana yang berderajat \(2\text{.}\) Ketika \(n=4\text{,}\) kita dapat memulai dengan menghitung banyaknya pohon yang tidak isomorfik dan mempertimbangkan dua kasus, bergantung pada apakah pohon tersebut memiliki simpul berderajat \(3\text{.}\) Jika ada simpul berderajat \(3\text{,}\) pohon tersebut isomorfik dengan \(\bfK_{1,3}\text{.}\) Jika tidak ada simpul berderajat tiga, pohon tersebut isomorfik dengan \(\bfP_4\text{,}\) sebab dalam graf seperti itu harus ada tepat dua simpul berderajat \(2\text{.}\) Terdapat empat pelabelan dengan \([4]\) untuk \(\bfK_{1,3}\) (pilih simpul berderajat tiga). Berapa banyak pelabelan dengan \([4]\) yang ada untuk \(\bfP_4\text{?}\) Terdapat \(C(4,2)\) cara untuk memilih label \(i,j\) yang diberikan kepada simpul-simpul berderajat \(2\text{,}\) dan dua cara untuk memilih salah satu label yang tersisa agar bertetangga dengan \(i\text{.}\) Jadi, terdapat \(12\) cara untuk melabeli \(\bfP_4\) dengan \([4]\text{,}\) sehingga \(T_4=16\text{.}\)

Sampai di sini, tampaknya mulai terbentuk suatu pola. Mungkin untuk setiap \(n\geq 1\) berlaku \(T_n = n^{n-2}\text{.}\) Memang demikian, tetapi mari kita lihat hasilnya untuk \(n=5\) sebelum membuktikannya secara umum. Apa saja pohon yang tidak isomorfik pada lima simpul? Tentu ada \(\bfK_{1,4}\) dan \(\bfP_5\text{,}\) serta ada pula pohon ketiga yang ditampilkan pada Gambar 5.39. Setelah memikirkannya selama satu atau dua menit, Anda seharusnya dapat meyakinkan diri bahwa hanya inilah semua kemungkinannya. Berapa banyak pelabelan dengan \([5]\) yang dimiliki setiap pohon tersebut? Terdapat \(5\) pelabelan untuk \(\bfK_{1,4}\) karena ada \(5\) cara untuk memilih simpul berderajat \(4\text{.}\) Untuk \(\bfP_5\text{,}\) terdapat \(5\) cara untuk memilih simpul tengah lintasan, \(C(4,2)=6\) cara untuk melabeli dua simpul berderajat \(2\) yang tersisa setelah simpul tengah dilabeli, lalu \(2\) cara untuk melabeli simpul-simpul berderajat \(1\text{.}\) Hasilnya adalah \(60\) pelabelan. Untuk pohon terakhir, terdapat \(5\) cara untuk melabeli simpul berderajat \(3\text{,}\) \(C(4,2)=6\) cara untuk melabeli dua daun yang bertetangga dengan simpul berderajat \(3\text{,}\) dan \(2\) cara untuk melabeli dua simpul yang tersisa, sehingga diperoleh \(60\) pelabelan. Oleh karena itu, \(T_5=125=5^3=5^{5-2}\text{.}\)

dijelaskan secara terperinci setelah gambar — Gambar 5.39. Pohon-pohon yang tidak isomorfik pada \(n=5\) simpul

Ternyata kita memang berada di jalur yang benar, dan sekarang kita akan membuktikan pernyataan berikut:

Teorema 5.40. Rumus Cayley.

Banyaknya \(T_n\) pohon berlabel pada \(n\) simpul adalah \(n^{n-2}\text{.}\)

Hasil ini biasanya disebut Rumus Cayley, meskipun hasil-hasil ekuivalen telah dibuktikan lebih dahulu oleh James J. Sylvester (1857) dan Carl W. Borchardt (1860). Nama Cayley paling sering dilekatkan pada hasil ini karena dialah orang pertama yang menyatakan dan membuktikannya dengan terminologi teori graf (pada 1889). (Meskipun dapat pula diperdebatkan bahwa Cayley sebenarnya hanya membuktikannya untuk \(n=6\text{,}\) lalu menyatakan bahwa bukti tersebut dapat diperluas dengan mudah untuk semua nilai \(n\) lainnya; apakah perluasan semacam itu benar-benar dapat dilakukan masih menjadi bahan perdebatan.) Rumus Cayley memiliki banyak bukti yang berbeda, dan kebanyakan di antaranya sangat elegan. Jika Anda tertarik pada penyajian beberapa bukti, kami menganjurkan Anda membaca bab tentang Rumus Cayley dalam Proofs from THE BOOK karya Aigner, Ziegler, dan Hofmann, yang memuat empat bukti berbeda, masing-masing menggunakan teknik pembuktian yang berbeda. Di sini kami memberikan bukti kelima, yang dikemukakan oleh Prüfer dan diterbitkan pada 1918. Menariknya, meskipun bukti Prüfer muncul setelah sebagian besar terminologi teori graf terbentuk, tampaknya ia tidak mengetahuinya dan bekerja dalam konteks permutasi serta terminologinya sendiri, padahal pendekatannya jelas memuat gagasan-gagasan teori graf. Kita akan menggunakan teknik rekursif untuk menemukan bijeksi antara himpunan pohon berlabel pada \(n\) simpul dan sebuah himpunan alami berukuran \(n^{n-2}\text{,}\) yaitu himpunan string dengan panjang \(n-2\) yang simbol-simbolnya berasal dari \([n]\text{.}\)

Kita mendefinisikan algoritma rekursif yang menerima sebuah pohon \(\bfT\) pada \(k\geq 2\) simpul yang dilabeli dengan elemen-elemen suatu himpunan \(S\) berukuran \(k\) yang terdiri atas bilangan bulat positif, lalu menghasilkan sebuah string dengan panjang \(k-2\) yang simbol-simbolnya merupakan elemen \(S\text{.}\) (Himpunan \(S\) biasanya adalah \([k]\text{,}\) tetapi untuk mendefinisikan prosedur rekursif, kita perlu memperbolehkannya berupa sembarang himpunan yang terdiri atas \(k\) bilangan bulat positif.) String ini disebut kode Prüfer dari pohon \(\bfT\text{.}\) Misalkan \(\prufer(\bfT)\) menyatakan kode Prüfer dari pohon \(\bfT\text{,}\) dan jika \(v\) merupakan daun dari \(\bfT\text{,}\) misalkan \(\bfT-v\) menyatakan pohon yang diperoleh dari \(\bfT\) dengan menghapus \(v\) (i.e., subgraf yang diinduksi oleh semua simpul lainnya). Selanjutnya, kita dapat mendefinisikan \(\prufer(\bfT)\) secara rekursif melalui prosedur berikut.

Jika \(\bfT\cong \bfK_2\text{,}\) kembalikan string kosong.
Jika tidak, misalkan \(v\) adalah daun dari \(\bfT\) dengan label terkecil dan misalkan \(u\) adalah tetangga tunggalnya. Misalkan \(i\) adalah label dari \(u\text{.}\) Kembalikan \((i,\prufer(\bfT-v))\text{.}\)

Contoh 5.41.

Sebelum menggunakan kode Prüfer untuk membuktikan Rumus Cayley, mari kita luangkan waktu sejenak untuk memastikan bahwa kita memahami cara menghitungnya dari sebuah pohon. Perhatikan pohon dengan \(9\) simpul, \(\bfT\text{,}\) pada Gambar 5.42.

Bagaimana kita menghitung \(\prufer(\bfT)\text{?}\) Karena \(\bfT\) memiliki lebih dari dua simpul, kita menggunakan langkah kedua dan memperoleh bahwa \(v\) adalah simpul berlabel \(2\text{,}\) sedangkan \(u\) adalah simpul berlabel \(6\text{,}\) sehingga \(\prufer(\bfT)=(6,\prufer(\bfT-v))\text{.}\) Graf \(\bfT-v\) ditampilkan pada Gambar 5.43.

Panggilan rekursif \(\prufer(\bfT-v)\) menghasilkan \((6,\prufer(\bfT-v-v'))\text{,}\) dengan \(v'\) sebagai simpul berlabel \(5\text{.}\) Dengan melanjutkan proses secara rekursif, simpul berikutnya yang dihapus adalah \(6\text{,}\) sehingga \(4\) ditambahkan ke string. Kemudian \(7\) dihapus, sehingga \(3\) ditambahkan. Berikutnya, \(8\) dihapus, sehingga \(1\) ditambahkan. Setelah itu, \(1\) dihapus, sehingga \(4\) ditambahkan. Akhirnya, \(4\) dihapus, sehingga \(3\) ditambahkan. Panggilan rekursif terakhir menerima subpohon yang isomorfik dengan \(\bfK_2\text{,}\) dengan simpul berlabel \(3\) dan \(9\text{,}\) lalu mengembalikan string kosong. Jadi, \(\prufer(\bfT)=6643143\text{.}\)

Sekarang kita siap memberikan bukti Rumus Cayley.

Bukti.

Jelas bahwa \(\prufer(\bfT)\) menerima sebuah pohon berlabel dengan \(n\) simpul yang label-labelnya berasal dari \([n]\text{,}\) lalu menghasilkan sebuah string dengan panjang \(n-2\) yang simbol-simbolnya merupakan elemen \([n]\text{.}\) Yang masih perlu kita lakukan adalah menentukan cara untuk menerima string semacam itu dan membangun sebuah pohon berlabel dengan \(n\) simpul darinya. Jika kita dapat menemukan konstruksi semacam itu, kita akan memperoleh bijeksi antara himpunan \(\mathcal{T}_n\) pohon berlabel pada \(n\) simpul dan himpunan string dengan panjang \(n-2\) yang simbol-simbolnya berasal dari \([n]\text{.}\) Hal ini akan mengakibatkan \(T_n=n^{n-2}\) .

Pertama, mari kita perhatikan perilaku \(\prufer(\bfT)\text{.}\) Bilangan apa saja yang sebenarnya muncul dalam kode Prüfer? Bilangan-bilangan yang muncul dalam kode Prüfer merupakan label simpul-simpul bukan daun dari \(\bfT\text{.}\) Label sebuah daun tidak mungkin muncul karena kita selalu mencatat label tetangga dari daun yang sedang dihapus, dan satu-satunya keadaan ketika kita akan menghapus tetangga suatu daun adalah ketika tetangga tersebut juga merupakan daun. Hal ini hanya dapat terjadi jika \(\bfT\cong\bfK_2\text{,}\) dan dalam kasus itu \(\prufer(\bfT)\) hanya menghasilkan string kosong. Sebaliknya, sebelum sebuah simpul yang semula bukan daun dapat menjadi daun, salah satu tetangganya harus dihapus dan label simpul tersebut akan dicatat. Jadi, jika \(I\subset [n]\) merupakan himpunan simbol yang muncul dalam \(\prufer(\bfT)\text{,}\) label daun-daun dari \(\bfT\) tepat merupakan elemen-elemen \([n]-I\text{.}\)

Setelah mengetahui label mana saja yang dimiliki daun-daun \(\bfT\text{,}\) kita siap menggunakan induksi untuk menyelesaikan bukti. Tujuan kita adalah menunjukkan bahwa untuk sebuah string \(\bfs=s_1s_2\cdots s_{n-2}\) yang simbol-simbolnya berasal dari suatu himpunan \(S\) dengan \(n\) elemen, terdapat tepat satu pohon \(\bfT\) dengan \(\prufer(\bfT) = \bfs\text{.}\) Jika \(n=2\text{,}\) satu-satunya string semacam itu adalah string kosong dan kedua elemen himpunan label sama-sama menjadi label daun. Untuk himpunan label baku, elemen-elemen itu adalah \(1\) dan \(2\text{,}\) sehingga kita hanya dapat membangun \(\bfK_2\text{.}\) Sekarang, misalkan hasil tersebut berlaku untuk suatu \(m\geq 2\text{,}\) dan kita berusaha membuktikannya untuk \(m+1\text{.}\) Dengan melakukan pelabelan ulang yang mempertahankan urutan jika diperlukan, kita dapat menggunakan himpunan label baku pada langkah berikut. Kita memiliki string \(\bfs = s_1s_2\cdots s_{m-1}\) dengan simbol-simbol dari \([m+1]\text{.}\) Misalkan \(I\) adalah himpunan simbol yang muncul dalam \(\bfs\text{,}\) dan misalkan \(k\) adalah elemen terkecil dari \([m+1]-I\text{.}\) Berdasarkan paragraf sebelumnya, kita mengetahui bahwa \(k\) adalah label sebuah daun dari \(\bfT\) dan bahwa tetangga tunggalnya merupakan simpul berlabel \(s_1\text{.}\) String \(\bfs'=s_2s_3\cdots s_{m-1}\) memiliki panjang \(m-2\text{,}\) dan karena \(k\) tidak muncul dalam \(\bfs\text{,}\) simbol-simbolnya berasal dari \(S=[m+1]-\{k\}\text{,}\) yang berukuran \(m\text{.}\) Jadi, berdasarkan induksi, terdapat tepat satu pohon \(\bfT'\) dengan kode Prüfer \(\bfs'\text{.}\) Kita membentuk \(\bfT\) dari \(\bfT'\) dengan menempelkan sebuah daun berlabel \(k\) pada simpul \(\bfT'\) yang berlabel \(s_1\text{,}\) sehingga diperoleh pohon dengan sifat yang diinginkan.

Contoh 5.44.

Kita menutup bagian ini dengan sebuah contoh cara menggunakan kode Prüfer untuk membangun pohon berlabel. Perhatikan string \(\bfs=75531\) sebagai kode Prüfer. Pohon \(\bfT\) yang bersesuaian dengan \(\bfs\) memiliki \(7\) simpul, dan daun-daunnya berlabel \(2\text{,}\) \(4\text{,}\) dan \(6\text{.}\) Langkah induksi dalam bukti kita menempelkan simpul berlabel \(2\) pada simpul berlabel \(7\) dalam pohon \(\bfT'\) dengan kode Prüfer \(5531\) dan label simpul \(\{1,3,4,5,6,7\}\text{,}\) karena \(2\) digunakan untuk melabeli simpul terakhir yang ditambahkan. Apa saja daun dari \(\bfT'\text{?}\) Simbol-simbol dalam \(\{4,6,7\}\) tidak muncul dalam \(5531\text{,}\) sehingga simbol-simbol tersebut pasti merupakan label daun. Konstruksi kita menyatakan bahwa simpul berlabel \(4\) ditempelkan pada simpul berlabel \(5\) dalam pohon yang diperoleh melalui induksi. Pada Gambar 5.45, kita menunjukkan bagaimana proses rekursif ini berlanjut.

Kode Prüfer	Himpunan label	Sisi yang ditambahkan
75531	\(\{1,2,3,4,5,6,7\}\)	2–7
5531	\(\{1,3,4,5,6,7\}\)	4–5
531	\(\{1,3,5,6,7\}\)	6–5
31	\(\{1,3,5,7\}\)	5–3
1	\(\{1,3,7\}\)	3–1
(string kosong)	\(\{1,7\}\)	1–7

Gambar 5.45. Mengubah kode Prüfer \(75531\) menjadi pohon berlabel

Kita membentuk setiap baris dari baris di atasnya dengan menghapus label pertama yang digunakan pada sisi yang ditambahkan dari himpunan label, serta menghapus simbol pertama dari kode Prüfer. Setelah kode Prüfer menjadi string kosong, kita mengetahui bahwa kedua label yang tersisa harus menjadi label yang ditempatkan pada kedua ujung \(\bfK_2\) untuk mulai membangun \(\bfT\text{.}\) Selanjutnya, kita bergerak kembali ke atas sepanjang kolom sisi yang ditambahkan sambil menambahkan simpul baru dan sisi yang ditunjukkan. Pohon yang kita bangun dengan cara ini ditampilkan pada Gambar 5.46.

Sblm Ke Atas Lnjt