BEBERAPA APLIKASI GRAF DAN KOMBINATORIAL UNTUK MENENTUKAN JUMLAH ISOMER SENYAWA KIMIA Reisha Humaira – NIM 13505047 Program Studi Teknik Informatika Institut Teknologi Bandung Jl. Ganesha 10, Bandung E-mail :
[email protected]
Abstrak Makalah ini membahas tentang aplikasi beberapa konsep yang ada pada matematika diskrit dalam ilmu kimia. Pembahasan pada makalah ini ditekankan pada aplikasi teori graf dan kombinatorial untuk menghitung jumlah isomer beberapa senyawa kimia. Perhitungan yang dibahas meliputi penentuan jumlah isomer pada senyawa karbon dan senyawa klorin. Masalah perhitungan jumlah isomer senyawa kimia telah diteliti selama lebih dari 125 tahun. Berbagai metode telah dikembangkan untuk menyelesaikan persoalan ini. Awalnya digunakan metode “draw and count”. Ini sebuah metode yang sangat sederhana, dan tentunya hanya bisa diterapkan pada senyawa kimia yang strukturnya sederhana pula. Sekitar tahun 1874, Arthur Cayley menghitung jumlah isomer yang dimiliki oleh senyawa alkana menggunakan graf. Dari sini lahir konsep Cayley graph dan Cayley tree. Struktur senyawa alkana digambarkan sebagai graf. Jumlah isomer yang ada berkorespondensi dengan jumlah graf yang bisa dibuat. Graf yang dibuat tetap harus sesuai dengan kaidah-kaidah yang ada dalam kimia. Karena struktur graf dari senyawa alkana merupakan pohon, maka perhitungan dilakukan melalui pohon, yaitu Cayley tree. Penghitungan jumlah isomer menggunakan pohon masih memiliki kekurangan. Tahun 1936, George Pólya menggunakan metode kombinatorial untuk menentukan jumlah isomer. Struktur suatu senyawa kimia digambarkan dengan graf yang sesuai, selanjutnya menggunakan serangkaian perhitungan yang melibatkan permutasi dan kombinasi akan diperoleh rumusan umum untuk menghitung jumlah isomer senyawa tersebut. Perhitungan dengan metode ini ternyata memberikan hasil yang lebih baik dan bisa diaplikasikan lebih luas lagi. Kata kunci: aplikasi graf, aplikasi kombinatorial, isomer kimia, Cayley, Pólya’s Enumeration Theorem.
1. Pendahuluan Berbagai teori dalam matematika diskrit bisa diaplikasikan dalam ilmu kimia. Teori graf bisa diterapkan dalam struktur kuantum elektronis, mekanika molekul, simulasi fase kondensasi, desain struktur molekul, polimer, topografi energi potensial, dan makromolekul biologik (termasuk protein). Belakangan, penerapan graf dan kombinatorial terutama berkaitan dengan isomer struktur molekul terutama molekul yang mengandung karbon, serta spektroskopi. Isomerisme bahan kimia merupakan konsep yang sangat penting dalam kimia modern. Suatu pertanyaan klasik yang sering diajukan tentang konsep isomer ini adalah berapakah jumlah isomer yang dimiliki oleh suatu senyawa. Pada
awal dikenalnya isomer dalam kimia, jumlah isomer dari suatu senyawa ditentukan dengan cara menggambar lalu menghitungnya (“draw and count” method). Metode ini mungkin dilakukan terhadap senyawa yang mempunyai struktur yang sederhana. Akan tetapi, secara umum dibutuhkan metode yang lebih rasional. Tahun 1874, Cayley menghitung jumlah isomer senyawa alkana menggunakan konsep graf. Metode lain juga terus dikembangkan. Tahun 1936, metode penghitungan jumlah isomer semakin maju. George Pólya membuat teorema yang sangat penting untuk kimia teoritis. Pólya memakai kombinatorial untuk menentukan jumlah isomer senyawa kimia. Teori Pólya ini sangat relevan untuk berbagai jenis perhitungan kombinatorik.
1
senyawa yang masih berada dalam satu gugus fungsi, sementara isomer fungsional berkaitan dengan isomer pada gugus fungsi yang berbeda.
2. Konsep Isomer dalam Kimia Isomer pertama kali dikenal pada tahun 1827. Friedrich Woehler menemukan bahwa antara cyanic acid dan fulminic acid terdapat karakteristik yang berbeda, padahal keduanya memiliki komposisi kimia yang identik. Saat itu, pengetahuan yang berkembang, bahan kimia akan berbeda karakteristiknya hanya jika memiliki komposisi kimia yang berbeda pula. Kemudian tahun 1828 Woehler juga menemukan hal yang sama antara urea dan ammonium cyanate. Pada tahun 1830, Jöns Jakob Berzelius menggunakan istilah isomer untuk menggambarkan fenomena ini.
Contoh :
Dalam kimia, senyawa-senyawa kimia yang mempunyai komposisi atom penyusun (rumus kimia) yang sama, tetapi struktur kimianya berbeda disebut isomer. Isomer dikelompokkan sebagai berikut.
Gambar 2 Isomer struktur (a) dengan (b) adalah isomer posisi, sementara (a) dengan (c) atau (b) dengan (c) adalah isomer fungsional. 2.
Gambar 1 Pengelompokan isomer 1.
Isomer struktur (structural isomers/ constitutional isomers) Pada isomer struktur, atom-atom atau gugus fungsi penyusun senyawa tersusun dengan cara yang berbeda. Pada senyawa organik, isomer struktur ini bisa dibedakan lagi atas isomer posisi (position isomerism) dan isomer fungsional (functional group isomerism). Isomer posisi berkaitan dengan posisi atom yang berbeda pada
Isomer ruang stereoisomers)
(spatial
isomers/
Pada isomer ruang, struktur dari susunan atom penyusun senyawa adalah sama, tetapi posisi atom-atom itu secara geometri dalam ruang berbeda. Isomer ruang dibedakan atas enantiomers dimana isomer tersebut saling bercerminan dan diastereomers di mana isomer tidak saling bercerminan. Diastereomers dibagi lagi atas dua kelompok, yaitu conformational isomerism (conformers) jika isomer bisa diperoleh dari rotasi ikatan kimianya dan cis-trans isomerism jika rotasi tidak mungkin dilakukan. Akan tetapi perlu digarisbawahi bahwa tidak semua conformers termasuk diastereomers jika hasil rotasi pada conformers saling bercerminan. Contoh :
2
(a)
(b)
(c) Gambar 3 Isomer ruang (a) adalah enantiomers, (b) adalah conformers, dan (c) adalah cis-trans isomerism Dalam makalah ini, isomer yang dimaksud adalah isomer struktur. Jadi, istilah “isomer” mengacu kepada isomer struktur.
3. Aplikasi Graf untuk Menghitung Jumlah Isomer Senyawa Karbon 3.1 Hubungan Graf dengan Ilmu Kimia Sejarah graf dimulai dengan permasalahan tentang jembatan Königsberg yang ditulis oleh Leonhard Euler dalam paper-nya Seven Bridges of Königsberg (1736).
Berbagai istilah dalam graf sebenarnya juga digunakan dalam kimia, hanya saja dengan nama yang berbeda. Istilah dalam Teori Graf Graph (graf) Vertex (simpul) Edge (sisi) Degree of vertex (derajat simpul) Tree (pohon) Bipartite graph Perfect matching Adjacency matrix Characteristic polynomial
Istilah Kimia Structural formula (rumus struktur) Atom Chemical bond (ikatan kimia) Valency of atom (valensi atom) Acyclic structure Alternant structure Kekule structure Huckel matrix Secular polynomial
Struktur senyawa kimia bisa digambarkan sebagai graf dengan atom-atom sebagai simpul dan ikatan antar atom sebagai sisi. Penggunaan graf untuk menggambarkan struktur senyawa kimia antara lain banyak ditemukan dalam kimia organik. Hidrokarbon sebagai salah satu senyawa organik merupakan senyawa kimia yang hanya mengandung atom karbon dan hidrogen. Hidrokarbon bisa dibagi atas hidrokarbon asiklik (alifatik) dan siklik. Hidrokarbon asiklik memiliki struktur pohon, dan bisa dibagi atas tiga kelompok.
C
A
Lebih dari satu abad kemudian, Arthur Cayley mempelajari bagian dari graf, yaitu pohon. Studinya ini membawa banyak pengaruh ke dalam kimia teoritis. Cayley menghubungkan studinya tentang pohon dengan studi tentang komposisi kimia. Meleburnya ide yang datang dari matematika dengan ilmu kimia ini berkembang sebagai bagian dari perkembangan terminologi dasar dalam teori graf. Istilah graf (graph) sendiri diperkenalkan oleh Sylvester dalam paper-nya Nature tahun 1878.
D
1. 2.
B
Gambar 4 Jembatan Königsberg dan graf yang merepresentasikannya
3.
Alkana, hanya mengandung ikatan tunggal (σ), rumus umumnya CnH2n+2. Alkena, mengandung ikatan rangkap (π), rumus umumnya CnH2n. Alkuna, mengandung ikatan rangkap tiga (π), rumus umumnya CnH2n-2.
Struktur hidrokarbon asiklik digambarkan sebagai berikut.
dengan
graf
3
Cayley graph yang juga dikenal dengan nama Cayley colour graph dibentuk sebagai berikut. • • •
Setiap elemen gi dari G menjadi simpul vi Setiap elemen si dari S menjadi warna ci Terdapat sisi berarah dari v1 ke v2 jika g2 = g1 × si.
Struktur Cayley graph tidaklah unik. Jika S mempunyai n elemen, maka tiap simpul akan mempunyai n busur masuk dan n busur keluar. Jika elemen S simetris (s-1 juga elemen S), maka sisi berarah yang menghubungkan s dan s-1 umumnya diganti dengan sebuah sisi tak berarah.
Gambar 5 Graf untuk hidrokarbon asiklik Sementara hidrokarbon siklik ditandai dengan adanya struktur tertutup seperti cincin. Kelompok ini dibagi atas dua kategori. 1. 2.
Cayley graph juga bisa terbentuk dari himpunan sejumlah permutasi {Pi} elemen-elemen. Menghubungkan setiap pasangan permutasi {Pi,Pj} jika Pk {Pi} = Pj untuk Pk ∈ S akan menghasilkan Cayley graph. Gambar berikut mengilustrasikan permutasi {1, 2, 4, 3} dan {3, 4, 2, 1} yang menghasilkan graf seperti kubus.
Sikloalkana, hanya mengandung ikatan tunggal (σ), rumus umumnya CnH2n. Hidrkarbon aromatik, berdasarkan permutasi molekul benzena, rumus umumnya C6H6.
Struktur hidrokarbon siklik dengan graf bisa digambarkan sebagai berikut.
Gambar 7 Cayley graph
Gambar 6 Graf untuk hidrokarbon siklik
3.2 Penggunaan Graf Terkait dengan Isomer Senyawa Karbon 3.2.1 Cayley Graph Misalkan G dan S himpunan di mana S ⊆ G dan I ∉ S. Cayley graph sehubungan dengan (G,S) didefinisikan sebagai graf berarah yang mempunyai suatu simpul yang berhubungan dengan elemen himpunan dan sisi berarah (g,h) sehingga g h-1∈ S.
Berikut daftar graf yang merupakan Cayley graph yang tidak berarah yang dibentuk oleh sejumlah permutasi. Cayley Graph 16-cell graph
Circulant graph Ci12 (1,3) Complete bipartite graph K4,4
Permutasi {{1,2,4,3}, {2,1,3,4}, {2,1,4,3}, {3,4,1,2}, {3,4,2,1}} {{1,2,3,5,4}, {1,2,4,3,5}, {2,1,3,5,4}, {2,1,5,4,3}} {{1,2,4,3}, {2,1,3,4}, {3,4,2,1}} {{1,2,4,3}, {2,1,3,4}, {3,4,1,2}, {4,3,2,1}} {{1,2,4,5,6,3}, {2,1,4,5,6,3}}
4
Complete graph K6
Cubical graph
Cubic symmetric graph F24 A
Cubic symmetric graph F60 A Cubic vertextransitive graph Ct19 Cubic vertextransitive graph Ct23 Cubic vertextransitive graph Ct28 Cubic vertextransitive graph Ct37 Cubic vertextransitive graph Ct38 Cubic vertextransitive graph Ct41 Cubic vertextransitive graph Ct42 Cuboctahedral graph
5-cycle graph 6-cycle graph
8-cycle graph 10-cycle graph 12-cycle graph Franklin graph
{{1,3,2}, {2,1,3}, {2,3,1}, {3,2,1}} {{1,2,4,3}, {1,3,2,4}, {1,3,4,2}, {1,4,3,2}} {{1,2,4,3}, {1,3,2,4}, {1,3,4,2}, {1,4,2,3}, {1,4,3,2}} {{1,2,4,3}, {3,4,2,1}} {{1,2,4,3}, {2,1,3,4}, {3,4,1,2}} {{1,2,3,5,4}, {1,4,5,3,2}} {{1,2,4,3}, {1,3,2,4}, {3,2,1,4}} {{1,2,3,4,6,5}, {2,5,4,6,3,1}} {{1,3,2,5,4}, {2,1,4,3,5}, {4,5,3,1,2}} {{1,2,3,4,6,5}, {1,2,4,3,6,5}, {5,6,3,4,1,2}} {{1,2,3,4,6,5}, {2,3,1,5,6,4}} {{1,3,2,5,4}, {2,3,4,1,5}}
Great rhombicuboctahedral graph Icosahedral graph
4-Möbius ladder Octahedral graph
Pappus graph 2-path graph
{{1,2,4,3}, {1,3,2,4},{3,4,1,2}} {{1,2,3,4,5,7,6}, {2,3,1,6,7,4,5}} {{1,2,4,3}, {1,3,2,4},{2,1,4,3}} {{1,2,3,4,5,7,6}, {2,3,4,1,6,5,7}} {{1,3,4,2}, {2,3,1,4}} {{1,3,4,2}, {1,4,2,3}, {2,3,1,4}} {{1,3,4,2}, {1,4,2,3}, {2,3,1,4}, {3,1,2,4}} {{1,2,4,5,3}, {1,3,4,2,5}} {{2,3,4,5,1}, {5,1,2,3,4}} {{1,3,2}, {2,1,3}} {{1,2,4,3}, {1,3,2,4}} {{1,2,3,5,4}, {1,2,4,3,5}} {{1,2,4,3}, {3,4,1,2}} {{1,2,3,5,4}, {1,4,5,2,3}} {{1,3,2,5,4}, {2,1,4,3,5}} {{1,2,3,5,4}, {2,1,4,3,5}} {{1,2,3,5,4}, {1,2,4,3,5}, {2,1,3,5,4}}
Pentatope graph 5-prism graph 6-prism graph Small rhombicosidodecahedral graph Small rhombicuboctahedral graph
Snub cubical graph
Square antiprism graph
Square graph
{{1,2,3,4,5,7,6}, {1,2,3,4,6,5,7}, {1,2,4,3,5,7,6}} {{1,2,3,4,5,7,6}, {1,2,3,4,6,5,7}, {1,3,2,5,4,7,6}} {{1,3,4,2}, {2,1,4,3}, {2,3,1,4}} {{1,3,4,2}, {1,4,2,3}, {2,1,4,3}, {2,3,1,4}} {{1,3,4,2}, {1,4,2,3}, {2,1,4,3}, {2,3,1,4}, {3,1,2,4}} {{1,2,4,3}, {2,1,4,3}, {3,4,1,2}} {{1,3,2}, {2,1,3}, {2,3,1}} {{1,2,4,3}, {1,3,2,4}, {1,3,4,2}} {{1,2,4,3}, {1,3,2,4}, {1,3,4,2}, {1,4,2,3}} {{1,2,4,5,3}, {2,1,4,5,3}} {{1,2,4,5,3}, {2,1,4,5,3}} {{1,2,3,4,6,5}, {2,3,1,5,4,6}} {{2,1}} {{1,3,2}} {{2,3,4,5,1}, {3,4,5,1,2}} {{1,3,2,5,4}, {2,4,1,5,3}} {{1,3,2,5,4}, {2,4,1,5,3}} {{1,2,3,5,4}, {2,1,4,5,3}} {{1,2,3,5,4}, {2,1,4,5,3}} {{1,2,4,5,3}, {3,4,2,5,1}} {{1,3,4,2}, {2,3,4,1}} {{1,3,4,2}, {1,4,2,3}, {2,3,4,1}} {{1,3,4,2}, {1,4,2,3}, {2,3,4,1}, {4,1,2,3}} {{1,2,4,5,3}, {1,3,4,5,2}} {{1,2,4,3}, {2,3,1,4}, {2,3,4,1}} {{1,2,4,3}, {2,3,1,4}, {2,3,4,1}, {3,1,2,4}} {{1,2,4,3}, {2,3,1,4}, {2,3,4,1}, {3,1,2,4}, {4,1,2,3}} {{1,2,4,3}, {3,4,1,2}, {3,4,2,1}} {{1,2,4,3}, {3,4,1,2}, {3,4,2,1}, {4,3,1,2}} {{1,2,4,3}, {2,1,3,4}}
5
Tesseract graph
Tetrahedral graph
Triangle graph
Triangular prism graph
Truncated cubical graph
Truncated dodecahedral graph Truncated icosahedral graph Truncated octahedral graph
Truncated tetrahedral graph
Utility graph K3,3
{{1,2,3,5,4}, {1,3,2,4,5}} {{1,2,3,4,6,5}, {1,2,4,3,5,6}, {3,4,2,1,5,6}} {{2,1,4,3}, {3,4,2,1}} {{1,2,4,3}, {2,1,3,4}, {2,1,4,3}} {{1,3,2,5,4}, {1,4,5,3,2}} {{2,3,1}} {{1,3,4,2}, {1,4,2,3}} {{1,2,4,5,3}, {1,2,5,3,4}} {{1,3,2}, {2,3,1}}
Gambar 8 Dihedral group D7 Gambar berikut adalah Cayley graph untuk alternating group A4 menggunakan (2, 1, 4, 3) dan (2, 3, 1, 4) sebagai pembentuknya.
{{1,2,4,3}, {1,3,4,2}} {{1,2,4,3}, {1,3,4,2}, {1,4,2,3}} {{1,2,3,5,4}, {1,2,4,5,3}} {{1,2,4,3}, {2,3,1,4}} {{1,2,4,3}, {2,3,1,4}, {3,1,2,4}} {{1,2,3,5,4}, {1,3,4,2,5}} {{1,2,4,5,3}, {3,4,1,2,5}} {{1,3,2,5,4}, {2,3,4,5,1}} {{1,2,4,3}, {2,3,4,1}}
Gambar 9 Alternating group A4 Cayley graph untuk himpunan tak terhingga menghasilkan bentuk geometri yang menarik. Sebagai contoh, Cayley graph untuk free group dengan dua elemen pembentuk digambarkan seperti berikut.
{{1,2,4,3}, {1,3,2,4}, {2,1,3,4}} {{1,2,3,5,4}, {1,3,4,5,2}} {{1,3,4,2}, {2,1,4,3}} {{1,3,4,2}, {1,4,2,3}, {2,1,4,3}} {{1,2,4,5,3}, {1,3,2,5,4}} {{1,3,2}, {2,1,3}, 3,2,1}} {{1,2,4,3}, {1,3,2,4}, {1,4,3,2}} {{1,2,3,5,4}, {2,3,1,5,4}} {{1,2,3,5,4}, {2,3,1,5,4}}
Sebagai contoh, dihedral group D7 adalah permutasi terhadap 14 elemen. Gambar di sebelah kiri menunjukkan Cayley graph untuk permutasi (7, 1, 2, 3, 4, 5, 6) and (7, 6, 5, 4, 3, 2, 1), sementara gambar di sebelah kanan adalah untuk D7 yang dibentuk oleh (7, 1, 2, 3, 4, 5, 6) and (6, 7, 1, 2, 3, 4, 5).
Gambar 10 Cayley graph untuk himpunan tak terhingga
3.2.2 Cayley Tree Cayley graph di mana setiap simpul terhubung dengan n simpul lainnya, dinamakan n-Cayley tree.
6
Gambar 11 Cayley tree Gambar di atas menunjukkan sejumlah 3-Cayley tree, yang juga dikenal sebagai pohon biner (binary trees). Cayley tree bisa digambarkan sebagai suatu struktur yang terus mengembang dari simpul pusat dengan semua simpul disusun melingkari simpul pada level sebelumnya seperti gambar berikut.
4 5 6 7 8 9 10 11 12 13
1 2 2 6 9 20 37 86 183 419
1 1 3 3 9 15 38 73 174 380
2 3 5 9 18 35 75 159 357 799
Kenyataannya terdapat sedikit kesalahan pada perhitungan Cayley. Herrmann (1880) menggunakan metode berbeda dengan Cayley dan memberikan hasil yang benar, 355 (untuk n = 12) dan 802 (untuk n = 13) untuk total isomer. Akan tetapi ia tidak menyebutkan jumlah untuk centered dan bicentered. Istilah centered dan bicentered didefinisikan sebagai berikut. Suatu pohon dengan diameter 2m mempunyai sebuah simpul yang unik disebut center, pada titik tengah lintasan yang panjangnya 2m. Pada pohon dengan diameter 2m+1 terdapat pasangan simpul yang unik disebut bicenters, pada pertengahan lintasan yang panjangnya 2m+1. Istilah ini diperkenalkan oleh Jordan sekitar tahun 1869.
Gambar 12 3-Cayley tree Jika h adalah tinggi pohon dan sebagai konvensi, akar pohon mempunyai h = 0, maka jumlah simpul pada aras (level) k bisa dihitung dengan Nk = h(h − 1)(k − 1) untuk k > 0.
Cayley menggunakan pendekatan dengan konsep center dan bicenters untuk menyederhanakan persoalan tentang pohon berakar (rooted trees). Namun pendekatan ini menjadi lemah karena konsep diameter pada pohon tidak relevan lagi. Mungkin karena itu para ahli yang lain tidak menggunakan metode Cayley ini. Perhitungan Cayley terhadap jumlah isomer alkana ini bisa dijabarkan seperti berikut.
3.2.3 Jumlah Isomer Senyawa Alkana Cayley mencoba menghitung jumlah isomer senyawa alkana CnH2n+2 menggunakan 4-Cayley tree. Cayley menghubungkan struktur molekul alkana dengan graf, di mana atom-atom karbon adalah simpul dan ikatan kovalen antara atom karbon dengan hidrogen adalah sisi. Hasil perhitungan Cayley bisa dilihat pada tabel berikut. n 1 2 3
centered 1 0 1
bicentered 0 1 0
total 1 1 1
Untuk suatu k-Cayley trees, misalkan Th,n adalah jumlah pohon berakar (k-1)-ary dengan n adalah simpul dan tinggi pohon maksimum h. Sebagai konvensi, pohon kosong mempunyai h = -1. Th(z) = ∑ n >= 0 Th,n zn. Maka T-1 (z) = 1, T0 (z) = 1+ z, dan untuk h>1,
Th+1 (z) = 1+ z Sk-1 (Th (z)) di mana Sm (f(z)) adalah hasil dari substitusi f(z) ke cycle index. Sebagai contoh,
S3 (f(z)) = ( f(z)3 +3 f(z) f(z2) + 2 f(z3)) / 3!
7
Misalkan C2h,n adalah jumlah center dari kCayley trees dengan n adalah simpul dan 2h adalah diameter pohon. Ambil C2h(z) = ∑ n >= 0 C2h,n zn. Dengan menghapus simpul center dan sisi yang berdekatan dengannya kita akan memperoleh sejumlah pohon yang berkorespondensi dengan k-tuple pohon berakar (k-1)-ary dengan tinggi maksimum h-1. Paling tidak terdapat dua pohon yang tingginya tepat h1. Karena itu
C2h = ( 1+ z Sk (Th-1 (z))) – (1+ z Sk (Th-2 (z))) – (Th-1 (z) – Th-2 (z))(Th-1 (z) – 1) Tiga ekspresi dalam persamaan di atas masingmasing menghitung k-tuple pohon dengan tinggi maksimum h-1, k-tuple pohon dengan tinggi maksimum h-2, dan pohon dengan tepat satu subpohon yang tingginya h-1. Selanjutnya, misalkan Cn adalah jumlah k-Cayley trees dengan n buah simpul, dan C(z) = ∑ n >= 0 Cnzn. Maka
C(z) = ∑ h >= 0 C2h(z) Untuk k = 4 diperoleh
C(z) = z + z3 + z4 + 2 z5 + 2 z6 + 6 z7 + 9 z8 + 20 z9 + 37 z10 + 86 z11 + 181 z12 + 422 z13 + ... Ini adalah perbaikan dari hasil perhitungan Cayley. Untuk bicenters, perhitungannya lebih mudah. Misalkan B2h+1,n adalah jumlah bicenter dari kCayley trees dengan n adalah jumlah simpul dan 2h+1 adalah diameter pohon. Ambil B2h+1 (z) = ∑ n >= 0 B2h+1,n zn, Bn adalah jumlah bicenter dari k-Cayley trees yang memiliki n simpul, dan B(z) = ∑ n >= 0 Bn zn. Karena sebuah pohon bicenter berkorespondensi dengan pasangan pohon berakar (k-1)-ary dengan tinggi tepat h diperoleh
B2h+1(z) = S2 (Th (z) – Th-1(z)) dan
B(z) = ∑ h >= 0 B2h+1 (z) Untuk k = 4 diperoleh
B(z) = z2 + z4 + z5 + 3 z6 + 3 z7 + 9 z8 + 15 z9 + 38 z10 + 73 z11 + 174 z12 + 380 z13 + ...
Selanjutnya, jumlah isomer untuk senyawa alkana dapat dihitung
C(z) + B(z) = z + z2 + z3 + 2 z4 + 3 z5 + 5 z6 + 9 z7 + 18 z8 + 35 z9 + 75 z10 + 159 z11 + 355 z12 + 802 z13 + ... . Hasil perhitungan jumlah isomer senyawa alkana yang dilakukan oleh Henze dan Blair (n juga menunjukkan jumlah simpul) menggunakan perumusan di atas, bisa dilihat pada tabel berikut. n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ...
centered 1 0 1 1 2 2 6 9 20 37 86 181 422 943 2223 5225 12613 30513 74883 184484 458561 1145406 ...
bicentered 0 1 0 1 1 3 3 9 15 38 73 174 380 915 2124 5134 12281 30010 73401 181835 452165 1133252 ...
total 1 1 1 2 3 5 9 18 35 75 159 355 802 1858 4347 10359 24894 60523 148284 366319 910726 2278658 ...
Di sini hasil perhitungan untuk n = 19 masih salah, 147284 seharusnya 148284. Penghitungan jumlah isomer alkana juga dibahas oleh Schiff, Losanitsch, Henze dan Blaire, Perry, Pólya, Harary dan Norman, Lederberg, Read, Robinson, Harary dan Balaban, Bergeron, serta Labelle dan Leroux. Mereka tidak menggunakan metode yang dipakai Cayley. Yang jelas, sejauh ini mereka tidak membahas jumlah untuk isomer centered dan bicentered. Kesalahan yang ada pada hasil perhitungan Cayley membuat permasalahan ini terus dikembangkan oleh para ahli untuk memperoleh hasil yang lebih baik.
8
4. Aplikasi Kombinatorial untuk Menghitung Jumlah Isomer Senyawa Klorin Metode Cayley terus dikembangkan hingga pada tahun 1936 George Pólya memperkenalkan teoremanya (Pólya’s Enumeration Theorem), teori yang cukup penting dalam kimia teoritis.
Sekarang misalkan kita akan membuat sebuah kalung menggunakan lima buah manik-manik. Gambar berikut menunjukkan semua kemungkinan yang ada.
Dalam tulisannya, Pólya menggunakan metode kombinatorial, cara yang lebih singkat dan ilustratif untuk menghitung jumlah isomer senyawa kimia. Metode ini bisa diilustrasikan seperti contoh berikut. Misalkan kita mempunyai sebuah kotak dan sejumlah manik-manik untuk membuat sebuah kalung. Manik-manik tersebut terdiri atas dua warna, yakni hitam (b) dan putih (w). Jika kita ingin meletakkan sebuah manik-manik ke dalam kotak tersebut, ada dua cara yang bisa dilakukan, yaitu memasukkan manik-manik berwarna hitam atau manik-manik berwarna putih. Dua cara ini diperoleh dari b+w.
Jika ada dua buah kotak yang berbeda, ada empat cara yang bisa dilakukan untuk memasukkan sebuah manik-manik di setiap kotak seperti pada gambar berikut.
Persoalan ini tidak bisa disamakan dengan persoalan memasukkan manik-manik ke dalam lima buah kotak. Untuk persoalan memasukkan manik-manik ke kotak, kemungkinan yang ada dihitung dengan (b+w)5 = b5 + 5b4w + 10b3w2 + 10b2w3 + 5bw4 + w5 Sementara untuk kalung, manik-manik itu tersusun melingkar, bentuk yang simetris dianggap sama. Persamaan di atas tidak bisa digunakan. Hal ini akan sama dengan persoalan permutasi siklik
Empat cara ini diperoleh dari persamaan (b+w)2 = b2 + 2bw + w2 Secara umum, jika terdapat n buah kotak, banyaknya cara yang bisa dilakukan untuk memasukkan sebuah manik-manik ke tiap kotak bisa dihitung dengan
yang menghasilkan permutasi sebagai berikut.
di mana terdapat n-k buah kotak yang berisi manik-manik hitam dan k buah kotak yang berisi manik-manik putih dan
9
4. 5.
berbeda yang bisa menempati posisi substitusi. Mensubstitusikan hasil figure counting series yang diperoleh ke dalam cycle index. Menghitung hasil akhir.
Aplikasi metode kombinatorial Pólya untuk menghitung jumlah isomer senyawa kimia bisa dilihat pada dua contoh berikut.
4.1 Jumlah Isomer Senyawa Polychlorinated naphthalenes Cycle index Z(G) untuk suatu himpunan G didefinisikan sebagai berikut.
Molekul senyawa polychlorinated naphthalene termasuk dalam kelompok D2h. Tapi berdasarkan letak atom klorin pada molekulnya, kelompok D2 telah cukup menggambarkan permutasi pada cincin naphthalene.
di mana |G| adalah urutan himpunan G, p adalah jumlah titik yang dipermutasikan, h adalah jumlah permutasi G yang mengandung a1, a2, … siklus. f adalah variabel. Kembali ke persoalan sebelumnya, Z(D5) (D5 adalah pentagon) dirumuskan
Teorema Pólya diperoleh dengan mensubstitusikan f dengan figure counting series, di sini
Gambar 13 Graf untuk senyawa polychlorinated naphthalene Titik-titik pada D2 mengandung empat elemen simetris yaitu E, C2(x), C2(y), dan C2(z). Kita akan memperoleh permutasi seperti berikut.
fnm = (bn + wn)m Dengan mensubstitusikan rumusan fnm ke Z(D5) diperoleh
= b5 + b4w + 2b3w2 + 2b2w3 + bw2 + w5 Penggunaan metode kombinatorial Pólya untuk menghitung jumlah isomer senyawa kimia mengikuti langkah-langkah berikut. 1. 2. 3.
Mengidentifikasi titik-titik yang simetris pada molekul. Menghitung cycle index yang menggambarkan senyawa induk. Menghitung figure counting series yang menggambarkan jumlah atom yang
Nilai cycle index untuk persoalan ini adalah
dan nilai figure counting series
fnm = (1+ xn)m di mana pangkat n pada x adalah jumlah cincin naphthalene yang mengandung n ligan klorin. Angka 1 menunjukkan tidak adanya ligan klorin.
10
Selanjutnya melalui counting diperoleh
substitusi
nilai
figure
Karena itu, permutasi yang lebih tepat untuk persoalan senyawa polychlorinated biphenyls ini adalah sebagai berikut.
= 1 + 2x + 10x2 + 14x3 + 22x4 + 14x5 + 10x6 + 2x7 + x8 Hasil akhir ini menunjukkan jumlah isomer senyawa polychlorinated naphthalenes.
4.2 Jumlah Isomer Senyawa Polychlorinated biphenyls Di sini struktur molekul senyawa polychlorinated biphenyls bisa digambarkan sebagai berikut.
Permutasi yang baru ini akan menghasilkan nilai cycle index Gambar 14 Graf untuk senyawa polychlorinated biphenyls Seperti prosedur yang digunakan pada persoalan sebelumnya, kita akan memperoleh permutasi seperti berikut.
dan nilai figure counting series
fnm = (1+ xn)m Akhirnya akan diperoleh jumlah isomer untuk senyawa polychlorinated biphenyls memenuhi F(PCB) = 1 + 3x + 12x2 + 24x3 + 42x4 + 46x5 + 42x6 + 24x7 + 12x8 + 3x9 + x10
5. Kesimpulan Akan tetapi, nilai cycle index
tidak bisa digunakan untuk menghitung jumlah isomer yang tepat. Hal ini dikarenakan rotasi terhadap ikatan C–C yang menghubungkan dua cincin phenyl harus diperhitungkan. Rotasi ini akan menghasilkan elemen simetris lainnya. Rotasi terhadap cincin phenyl (12345) menghasilkan permutasi berikut.
Kesimpulan yang dapat dimbil dari pembahasan tentang aplikasi graf dan kombinatorial dalam menentukan jumlah isomer senyawa kimia ini adalah: 1. Sejumlah teori yang ada dalam matematika diskrit seperti graf dan kombinatorial bisa diterapkan dalam ilmu kimia. Bahkan penggunaannya menjadi makin penting dengan makin berkembangnya penelitian dalam kimia teoritis. 2. Graf digunakan untuk menggambarkan struktur suatu senyawa kimia di mana atom-atom merupakan simpul dan ikatan antar atom merupakan sisi.
11
3.
4.
Melalui graf dari senyawa kimia tersebut kita bisa menghitung jumlah isomer yang dimiliki senyawa bersangkutan. Metode lain yang bisa digunakan untuk menghitung jumlah isomer adalah menggunakan kombinatorial. Metode ini melibatkan perhitungan permutasi dan kombinasi.
DAFTAR PUSTAKA
[1] Ballard, Kevin. (2003). Computerized Isomer Enumeration of the Alkane Series. http://www.scctm.org/Awards/Ballard_Pap er.pdf. Tanggal akses: 28 Desember 2006 pukul 15:45. [2] Bytautas, Laimutis; Klein, Douglas J.; dan Schmalz, Thomas G. (2000). All Acyclic Hydrocarbons: Formula Periodic Table and Property Overlap Plots Via Chemical Combinatorics. http://www.osti.gov/energy citations/servlets/purl/15013847-aaKEp7/ native/15013847.pdf. Tanggal akses: 29 Desember 2006 pukul 16:00. [3] Dobrov, Bella. (2005). Some Applications of Graph Polynomials in Chemistry. http:// www.cs.technion.ac.il/~janos/COURSES/23 8900/chemistry-all.ps. Tanggal akses: 29 Desember 2006 pukul 16:00. [4] Matamala, Adelio R. (2002). Pólya's Combinatorial Method and The Isomer Enumeration Problem. http://www.scielo.cl/ scielo.php. Tanggal akses: 29 Desember 2006 pukul 16:00. [5] Munir, Rinaldi. (2004). Diktat Kuliah IF2151 Matematika Diskrit Edisi Keempat. Departemen Teknik Informatika, Institut Teknologi Bandung.
[6] National Academy of Sciences. (2006). Examples of Constructive Crossfertilization Between the Mathematical Sciences and Chemistry. http://www.nap. edu/html/mctcc/chap3.html. Tanggal akses: 28 Desember 2006 pukul 15:45. [7] National Academy of Sciences. (2006). Mathematical Research Opportunities from Theoretical / Computational Chemistry. http://www.nap.edu/readingroom/books/mc tcc/chap4.1.html. Tanggal akses: 29 Desember 2006 pukul 16:00. [8] Pegg, Ed Jr.; Rowland, Todd; dan Weisstein, Eric W. Cayley Graph. (2006). http://mathworld.wolfram.com/CayleyGrap h.html. Tanggal akses: 28 Desember 2006 pukul 15:45. [9] Rains, E. M. dan Sloane, N. J. A. (1999). On Cayley's Enumeration of Alkanes (or 4Valent Trees). http://www.cs.uwaterloo. ca/journals/JIS/cayley.html. Tanggal akses: 29 Desember 2006 pukul 16:00. [10] Weisstein, Eric W. (2006). Cayley Tree. http://mathworld.wolfram.com/CayleyTree. html. Tanggal akses: 28 Desember 2006 pukul 15:45. [11] Wikipedia. (2006). Cayley Graph. http://en. wikipedia.org/wiki/Cayley_graph. Tanggal akses: 28 Desember 2006 pukul 15:45. [12] Wikipedia. (2006). Graph Theory. http://en. wikipedia.org/wiki/Graph_theory. Tanggal akses: 29 Desember 2006 pukul 16:00. [13] Wikipedia. (2007). Bethe Lattice. http://en. wikipedia.org/wiki/Cayley_tree. Tanggal akses: 2 Januari 2007 pukul 09:00. [14] Wikipedia. (2007). Isomer. http://en.wiki pedia.org/wiki/Isomer. Tanggal akses: 2 Januari 2007 pukul 13:30.
12
