kristalografi bidang datar batik capmath.fkip.uns.ac.id/wp-content/uploads/2014/06/ruang-7.pdf ·...

Prosiding SNMPM Universitas Sebelas Maret 2013 Volume 2

Makalah Pendamping: Matematika 1 105

KRISTALOGRAFI BIDANG DATAR BATIK CAP

Kartono1)

, R.Heri Sulistyo Utomo2)

, Priyo Sidik S3)

1) , 2) Jurusan Matematika FMIPA UNDIP

3) Jurusan Informatika FMIPA UNDIP

Jl. Prof. H.Soedarto, SH Tembalang Semarang, e-mail: [email protected]

Abstrak

Pembuatan kain batik cap yang beragam corak memerlukan banyak cap, sehingga modal

awal yang dibutuhkannya cukup besar. Di lain fihak, kain batik cap mendapat persaingan

yang keras dari tekstil printing bermotif batik di pasaran, Kedua hal inilah yang memicu

semakin tertekannya produksi kain batik cap, sehingga diperlukan suatu inovasi dalam

pembuatannya untuk menekan biaya produksinya. Penelitian ini menjawab permasalahan

tersebut dengan melakukan inovasi desain motif dan metode pengecapannya, yang dengan

satu cap dapat dihasilkan beragam corak. Inovasi ini didasarkan pada teori grup simetri dan

kristalografi dua dimensi, sehingga kain batik cap yang dihasilkan ini merupakan grup

kristalografi dua dimensi. Metode pengecapan ini mampu menghasilkan beragram corak

sebanyak 13 kain batik cap dari satu cap saja, sehingga cap ini disebut ajaib (magic). Hasil

penelitian ini bermanfaat dalam mendukung program penguatan sistem inovasi daerah

dalam mengembangkan potensi unggulan daerah, dan pembelajaran matematika yang

kreatif, inovatif dan produktif.

Kata Kunci: batik cap, cap ajaib, motif, corak, kristalografi, simetri

PENDAHULUAN

Penguatan sistem inovasi daerah dalam mengembangkan potensi unggulan daerah

digalakkan oleh pemerintah, termasuk pemerintah Kota Surakarta dengan unggulan batik.

Perkembangan batik diawali dengan adanya batik tulis, yang kemudian diikuti dengan batik cap.

Perkembangan batik pada masa sekarang cukup menggembirakan, permintaan batik tulis

maupun batik cap cukup tinggi, walaupun kebutuhan pasar batik sekarang sebagian sudah

dipenuhi dengan tekstil bermotif batik, bahkan telah dibanjiri produk import.

Batik cap membutuhkan modal awal yang cukup mahal karena bergantung pada harga

tembaga sebagai bahan utama pembuatan capnya. Untuk membuat batik cap yang beragam

motif maka diperlukan banyak cap, sementara harga satu cap relatif lebih mahal dari harga

canting. Harga cap pada kondisi sekarang dengan ukuran 20 cm X 20 cm berkisar Rp. 750.000,-

hingga Rp. 1.250.000,-/motif tergantung kerumitan motifnya. Selain proses pelukisan motif

batik yang menggunakan cap, proses selanjutnya dilakukan dengan cara yang hampir sama

seperti saat membuat batik tulis, misalnya dari proses pewarnaannya yang harus berulang-ulang

untuk mendapatkan warna yang diinginkan, atau dari proses nglorodnya.

Pembuatan batik cap membutuhkan ketelitian yang tinggi. Kualitas batik cap sering

dilihat dari kehalusannya yaitu presisi peletakan cap di sekujur bidang kain, tidak ada garis

sambungan yang meleset atau semuanya pas. Tukang cap harus memastikan agar

menyambungnya pas, sehingga tidak ada garis-garis yang menebal atau malamnya menggumpal

di kain. Celakanya, ketidaksempurnaan ini seringkali baru terlihat setelah proses pewarnaan.

Batik cap pun membutuhkan satu feeling dalam pengerjaannya. Hanya dengan komitmen untuk

Volume 2 Prosiding SNMPM Universitas Sebelas Maret 2013

106 Makalah Pendamping: Matematika 1

mendapatkan yang terbaiklah, tercipta karya batik cap yang berkualitas. Bentuk gambar/desain

motif pada batik cap selalu ada pengulangan yang jelas, sehingga gambar nampak berulang

dengan bentuk yang sama, dengan ukuran garis motif relatif lebih besar dibandingkan dengan

batik tulis.

Pengembangan desain motif batik cap, yang dari satu cap dapat menghasilkan beragam

corak, merupakan permasalahan yang diselesaikan dalam penelitian ini. Permasalahan ini

diselesaikan dengan menerapkan konsep grup simetri dan kristalografi berdimensi dua untuk

menghasilkan motif dan juga cap ajaib (magic stamp). Cap ini disebut ajaib (magic) karena

dengan satu cap yang didesain berdasarkan motif tersebut dapat menghasilkan beragam corak

batik cap melalui inovasi metode pengecapannya, yang didasarkan pada generator dalam grup

simetri (translasi, refleksi, rotasi, dan glide-refleksi).

Seperti yang telah diuraikan dalam latar belakang, para pengrajin batik cap menghadapi

kendala mahalnya harga sebuah cap, padahal satu cap biasanya hanya menghasilkan satu corak

batik cap, sedangkan harga jualnya lebih murah daripada batik tulis. Dalam kondisi seperti ini

maka sangat perlu dan urgen untuk mengembangkan desain motif dalam cap, yang dapat

menghasilkan banyak corak, artinya, dari satu desain motif dalam cap dapat menghasilkan lebih

dari satu corak batik cap. Pengembangan motif yang demikian akan dapat memperkecil modal

awal dan memberikan banyak pilihan corak batik bagi konsumen, sehingga akan meningkatkan

daya saing batik cap. Hal inilah yang merupakan fokus tujuan penelitian ini dilaksanakan.

Penelitian ini diharapkan dapat berkontribusi secara nyata dalam pengembangan ilmu

pengetahuan, teknologi dan seni (Kategori Penelitian I) yakni mengembangkan penerapan teori

grup simetri dan konsep kristalografi berdimensi dua untuk mendesain motif batik cap. Disisi

lain, pelaksanaan penelitian ini dimaksudkan dapat berkontribusi dalam pemecahan masalah

pembangunan dengan meningkatkan daya saing kain batik cap dan mendukung pengembangan

cluster unggulan potensi daerah, sekaligus meningkatkan kemampuan masyarakat (pengrajin/

produsen) dalam menerapkan teori tepat guna (Kategori Penelitian II). Dari sudut pandang

pengembangan kelembangaan (Kategori Penelitian III), penelitian ini dimaksudkan untuk

memperkuat Jurusan Matematika Fakultas Sains dan Matematika (FSM) Universitas

Diponegoro Semarang, khususnya Laboratorium Matematika Terapan (Bengkel Desain Motif

Simetris) dapat bermitra dengan fihak UMKM dalam rangka mengembangkan industri kreatif.

Metode pengecapan yang ditemukan dapat dimanfaatkan dalam pengembangan pembelajaran

matematika (grup simetri dan kristalografi) secara kreatif, inovatif dan produktif.

Penelitian ini dilakukan atas dorongan untuk dapat menciptakan (mengembangkan)

motif batik cap dan inovasi produk derivatifnya, dengan menerapkan teori grup simetri dan

kristalografi berdimensi dua dalam mendesain motifnya. Metode pengecapan motif dasar pada

selembar kain melalui formulasi-formulasi matematis menghasilkan banyak corak. Pengecapan

ini dilakukan tanpa adanya tumpang tindih yang satu dengan yang lain, dan secara berulang-



ulang menurut komposisi yang cocok dari rotasi, translasi dan refleksi. Hasil pengecapan yang

berdasarkan operasi rotasi, translasi atau refleksi dan komposisinya berasosiasi dengan sebuah

grup simetri.(Durbin, 1985).

Salah satu aplikasi grup simetri yang sangat menarik adalah dikenal sebagai

kristalografi berdimensi dua maupun tiga. Permasalahan tentang mengisi secara penuh suatu

bidang datar dengan poligon yang kongruen tanpa tumpang tindih kecuali pada sisi-sisinya

merupakan permasalahan yang dapat diselesaikan dengan teori kristalografi berdimensi dua.

Poligon-poligon kongruen yang mengisi penuh suatu bidang datar dengan mengoperasikan

gerakan (translasi, rotasi, refleksi atau glide-refleksi) dari satu poligon tersebut dikenal dengan

poligon fondamental. Hasil pengisian yang diperoleh berasosiasi dengan grup simetri dari

gambar yang dibentuk oleh sisi-sisi dari semua poligon tersebut. Hal ini merupakan fakta yang

mengaitkan antara teori grup dan kristalografi berdimensi dua, sehingga dinamakan grup

kristalografi berdimensi dua (Durbin, 1985).

Sekarang pandang bidang datar (kain mori) akan dipenuhi oleh poligon-poligon yang

berbentuk bujur sangkar yang memuat sebuah motif dasar yang tidak saling tumpang tindih

kecuali pada sisi-sisinya saling adjacent. Dengan menggerakkan poligon ini sesuai dengan

komposisi generator-generator rotasi, refleksi, translasi maupun refleksi-glide yang cocok akan

diperoleh suatu corak hasil pengecapan. Dengan memulai pada poligon dasar dan secara

periodik menggerakkan poligon dasar menurut generator yang dipilih maka keseluruhan

bidang datar (kain mori) akan terpenuhi oleh poligon-poligon dasar sehingga corak baru dapat

diperoleh.

Pengembangan motif batik cap yang didasarkan pada teori grup simetri, juga telah

digunakan untuk mengembangkan desain motif batik simetris. Pada tahun 1999-2000, Kartono

dkk pernah melakukan penelitian dengan judul ”Grup simetri untuk pengembangan desain

motif batik simetris” . Pengembangan desain motif batik simetris dengan menerapkan konsep

teori grup simetri dan periodesasi telah berhasil dari satu buah desain motif dasar dapat

menghasilkan 14 corak. (Kartono et al, 2000). Keempatbelas corak tersebut dihasilkan dengan

menggunakan bermacam-macam bentuk poligon seperti bujur sangkar, persegi panjang,

segitiga siku-siku, segitiga sama kaki, segitiga sama sisi bahkan segitiga dengan sudut-sudut

yang ditentukan sesuai dengan keinginan, sedangkan dalam pembuatan motif batik cap ini

hanya menggunakan poligon yang berbentuk bujur sangkar saja.

Kartono dkk (2011) menerapkan teori yang sama untuk menguak pola (motif) geometris

crop circle yang muncul di Berbah Sleman Daerah Istemewa Yogyakarta. Penelitian ini

menghasilkan motif lingkaran sebagai motif dasar, dan ternyata bentuk crop circle tersebut

dihasilkan melalui operasi translasi, rotasi, maupun glide-refleksi dari motif dasar lingkaran.

Penelitian itu berhasil menemukan pola geometrisnya yang tersusun dari 12 lingkaran utama, 2

lingkaran lain di luarnya dengan 11 titik pusat lingkaran (Kartono et al, 2011).



Pada awal tahun 2012, teori yang sama dipakai untuk mengembangkan pemanfaatan

limbah kayu sebagai bahan pembuat ukiran bergerak berbasis transformasi oleh Nurhilaliah

dan Ulfia Azmi dengan Kartono sebagai pembimbing, dalam rangka mengikuti Indonesian

Science Project Olympiad (ISPO) 2012.

Dari penelitian-penelitian ini dapat disimpulkan bahwa, motif yang dihasilkan dapat

dikategorikan ke dalam bentuk karya seni generatif. Dari sudut pandang seni generatif, selalu

dapat dihubungkan dengan keindahan yang selalu melekat pada karya seni itu. Penelitian-

penelitian ini semakin meyakinkan peneliti, bahwa motif dalam karpet maupun hiasan dinding

bordir yang dihasilkan juga mengandung unsur keindahan sebagai karya seni generatif.

Pada tahun 2012, Kartono dkk melaksanakan penelitian Riset Unggulan Daerah

(RUD) Balitbang Provinsi Jawa Tengah tahun 2012 dengan judul ”Pemberdayaan Ekonomi

Lokal melalui Pengembangan Inovasi Jenis Produk Bordir di Kabupaten Kudus”(Kartono et al,

2012). Inovasi jenis produk yang dimaksud adalah karpet dan hiasan dinding bordir. Pembuatan

desain motif dasarnya juga berbasis pada teori grup simetri dan kristalografi berdimensi dua.

Dari penelitian-penelitian ini dapat disimpulkan bahwa, baik desain motif batik simetris, crop

circle, ukiran kayu bergerak, maupun bordir tersebut dapat dikategorikan ke dalam bentuk

karya seni generatif, yang dapat dihubungkan dengan keindahan yang selalu melekat pada karya

seni itu. Unsur keindahan merupakan salah satu bagian penting dalam usaha pengembangan

industri kreatif.

METODE PENELITIAN

Jenis Penelitian

Penelitian ini merupakan penelitian eksperimental .

Waktu dan Tempat Penelitian

Jangka waktu penelitian ini selama sembilan bulan di Bengkel Desain Motif Simetris

Laboratorium Matematika Terapan, Laboratorium Komputasi Jurusan Matematika FMIPA

UNDIP, dan bekerjasama dengan Batik Adityan Laweyan Surakarta.

Target/Subjek Penelitian

Target penelitian iniadalah penemuan atau inovasi desain motif dalam cap dan

formulasi matematis pengecapannya, sehingga dari satu motif dalam cap tersebut dapat

menghasilkan banyak corak batik. Wujud hasil penelitian ini adalah cap ajaib (magic stamp),

prototipe kain batik cap yang siap diproduksi massal.

Prosedur

1. Membuat poligon dasar (poligon fondamental) berbentuk persegi ukuran 12 cm x 12

cm pada kertas gambar.



2. Mendesain motif dasar dengan mempertimbangkan nilai keindahannya dan generator-

generator pada teori grup simetri yang dipakai. Pada tahapan ini, telah dipilih satu

desain motif yang akan dibuatkan capnya.

3. Melakukan simulasi penataan motif.

4. Motif dasar ini kemudian discan, dan diperbaiki di studio gambar milik pengrajin batik

di Laweyan Surakarta. Perbaikan ini dilakukan untuk mendapatkan motif yang akurat

dan mencoba beberapa kombinasi warna. Hasil perbaikan inilah yang menjadi motif

yang dipakai untuk membuat cap, dan pemesanan cetakan/ cap ajaib (magic stamp)

dengan motif yang terpilih.

5. Membuat formulasi pergerakan/pergeseran poligon dasar ini berdasarkan kombinasi

generator pada grup simetri (rotasi, refleksi, translasi maupun refleksi-glide) dan

periodesasinya. Formulasi ini dibuat berdasarkan kombinasi yang diinginkan dan

kemudian dipilih formula yang menghasilkan corak hasil penyusunan yang indah.

Formulasi inilah yang kemudian dinamakan formula metode penataan motif dasar

simetris yang ditemukan itu.

6. Dengan menerapkan formula yang dipilih ini dan konsep periodesasi maka keseluruhan

poligon dasar akan terpenuhi oleh motif dasar tersebut. Dari sinilah keindahan dari

hasil penataan motif dasar simetris yang ditentukan itu akan dinilai.

7. Melakukan simulasi komputer dan pengecapan berdasarkan formulasi gerakan

pengecapan yang telah diperoleh pada langkah (5). Hasil pengecapan ini akan

menghasilkan corak-corak batik cap dari satu motif tersebut. Formulasi matematis yang

disimulasikan ini yang akan dipakai sebagai aturan gerakan pengecapan/ pembuatan

kain batik cap oleh pengrajin. Sampai pada penulisan laporan kemajuan ini, pembuatan

cap masih dilakukan, sehingga pembuatan kain batiknya belum dilaksanakan.

HASIL PENELITIAN DAN PEMBAHASAN

Hasil Penelitian

Penelitian ini berhasil membuat cap ajaib bermotif dengan tema Crop Circle dan 13

corak kain batik cap (Lampiran.1) berdasarkan teori grup symetri dan kristalografi berdimensi

dua. Ketigabelas corak kain batik cap yang berhasil dibuat ini merupakan penerapan dari 13

buah formulasi matematis gerakan pengecapan yang berhasil dirumuskan pada penelitian ini.

Inilah keunggulan dari hasil penelitian ini, dari satu cap dapat diciptakan beragam corak kain

batik cap, sehingga wajar kalau cap ini disebut cap ajaib (magic stamp).

Pembahasan

Formulasi pengecapan yang berhasil dirumuskan dalam penelitian ini dapat

menghasilkan 13 corak kain batik cap, yang variasi coraknya tidak sebanyak jika dibandingkan

dengan desain batik simetris (Kartono et al, 2000). Hal ini dikarenakan polygon bermotif dasar



yang digunakan dalam desain motif batik cap ini hanyalah berbentuk persegi tidak seperti pada

desain batik simetris yang menggunakan polygon persegi, persegi panjang, maupun segitiga.

Tema motif dasar pada cap (polygon persegi) yang dibuat terinspirasi oleh adanya

kemunculan crop circle di Berbah Sleman pada tahun 2011 (Kartono et al, 2011). Motif dasar

pada cap didesain terdiri dari lingkaran-lingkaran dengan beragam koordinat pusat dan jari-

jarinya. Bidang datar (selembar kain mori) diisi penuh oleh polygon-poligon kongruen (cap

bermotif dasar) melalui pengoperasian generator gerakan (translasi, refleksi, rotasi, atau glide-

refleksi), sehingga menghasilkan suatu corak batik cap. Dengan memulai pada polygon

fundamental dan mengulanginya secara berulang-ulang menurut gerakan yang diperintahkan

oleh generator gerakan maka keseluruhan bidang datar (selembar kain mori) dapat terisi penuh.

Menurut Durbin (1985), corak batik cap yang dihasilkan ini merupakan grup simetri dari

gambar yang dibentuk oleh sisi-sisi semua polygon (cap bermotif dasar) dan ketigabelas corak

batik cap yang dihasilkan ini merupakan kristalografi berdimensi dua.

Kain batik cap ini dapat dipandang sebagai sebuah obyek estetika berpola yang

memiliki tata aturan penggambaran pseudo-algoritmik yang dapat diperlakukan sebagai bentuk

seni generatif yang memiliki kegunaan memberikan inspirasi kepada peradaban umat manusia,

khususnya dalam bidang perkembangan seni generatif itu sendiri. Seni generatif pada batik cap

ini, selalu dapat dihubungkan dengan keindahan yang selalu melekat pada karya seni itu, yaitu

berbagai bentuk keselarasan (harmoni) dari berbagai cara pengecapan secara berulang tersebut.

Jadi sangat masuk akal kalau kain batik cap tersebut dikategorikan dalam suatu karya seni rupa

generatif karena pola tersebut merupakan pola iteratif (berulang) yang digenerateoleh motif

dasar. Ciri khas corak kain batik cap ini adalah pola iteratif yang terbentuk selalu mengawetkan

keterhubungan (konektifitas).

Dalam proses pembuatan kain batik cap ini, pengrajin mengeluh kesulitan dalam

melakukan pengecapan yang dapat mengawetkan keterhubungan tersebut. Ketigabelas corak

kain batik cap yang dihasilkan oleh pengrajin ini masih memperlihatkan adanya sambungan

yang tidak sempurna, walaupun dalam pengerjaannya telah dilakukan dengan sabar dan penuh

konsentrasi. Kesulitan lainnya adalah membuat seragam ketebalan tekstur kurvanya, namun

ketidaksempurnaan inilah yang akan menjadi pembeda dengan produk tekstil bermotif batik

(batik printing/ sablon).

Jelaslah bahwa pola berulang (iteratif) dari motif dasar yang membentuk beragram

corak akan menghasilkan bentuk fraktal sebagaimana pola berulang aritmatik sederhana dapat

menghasilkan pola chaos. Seiring dengan perkembangan teknologi komputasi, sebagaimana

dapat diterapkan untuk melihat pola aritmatika sederhana yang menghasilkan chaos dapat pula

diterapkan untuk melihat pola geometri sederhana (motif dasar) yang menghasilkan fraktal.

Upaya melihat fenomena fraktal pada corak batik cap yang dihasilkan ini akan memperluas

pula khazanah dan peluang apresiasi yang lebih baik pada produk ini.



Penerapan teori grup simetri dan kristalografi berdimensi dua pada pembuatan motif

dan kain batik cap ini juga dapat dipakai sebagai alat edukasi secara kreatif, inovatif, dan

produktif dalam mempelajari transformasi geometris bidang, atau teori grup simetri dan

kristalografi berdimensi dua. Titik atau bentuk obyek di bidang datar yang biasanya

ditransformasikan dengan generator translasi, rotasi, refleksi, atau glide-refleksi diganti dengan

motif batik. Pembelajaran matematika secara kreatif seperti ini akan sangat menyenangkan

karena disamping belajar, peserta didik akan tahu manfaat nyata dari proses pembelajaran.

Sambil bermain, juga belajar tentang transformasi bidang. bisa digunakan sebagai sarana

permainan kreatifitas seperti bermain puzzle. Karena sistem kerja pengecapan yang berulang-

ulang ini seperti menggunakan puzzle maka pembelajarannya lebih menyenangkan dan tidak

membosankan. Sifat inovatif dalam pembelajaran ini terlihat pada motif batik cap yang didesain

dengan melakukan inovasi dari satu motif dapat menghasilkan beragam corak. Pembelajaran ini

juga bersifat produktif karena hasil proses pembelajaran ini tidak berhenti di atas kertas tetapi

betul-betul diterapkan dan menghasilkan produk nyata. Proses pembelajaran seperti inilah yang

diharapkan mampu melahirkan teknoprenuer, seperti yang diinginkan oleh Kurikulum SMA

2013.

Diskusi dengan para pengrajin batik cap di Laweyan Surakarta menyarankan bahwa

hasil penelitian ini masih perlu penyempurnaan produk dan perencanaan produksi yang cermat

agar dapat menekan biaya produksi. Inovasi motif batik cap perlu dilakukan secara

berkelanjutan dalam rangka pengembangan keanekaragaman motif karya seni generatif. Upaya-

upaya inilah yang harus selalu dilakukan sebagai langkah nyata dalam memberdayakan

ekonomi lokal, mengembangkan potensi unggulan daerah dalam rangka meningkatkan

kesejahteraan masyarakat.

SIMPULAN DAN SARAN

Simpulan

Penerapan teori grup simetri dan kristalografi berdimensi dua, khususnya transformasi

geometris bidang datar (motif dasar bertema Crop Circle) dapat menghasilkan motif simetris

batik cap dan beragam coraknya melalui pengecapan yang berulang. Penelitian ini berhasil

membuat 13 formula pengecapan berulang yang menghasilkan 13 corak kain batik cap,

Keseluruhan proses pembuatan kain batik cap ini merupakan media edukasi yang kreatif,

inovatif dan produktif.

Hasil penelitian dapat diimplikasikan untuk mendukung pengembangan

keanekaragaman motif maupun metode pengecapan batik cap, dan potensi unggulan daerah,

yang diharapkan dapat menciptakan lapangan kerja baru sehingga dapat mendukung upaya

mempercepat pengentasan kemiskinan dan meningkatkan kesejahteraan masyarakat. Pelibatan



pengrajin dalam keseluruhan proses penelitian ini semakin memperkaya pengetahuan dan

keahliannya dalam menghasilkan produk kain batik cap.

Saran

Prototip kain batik cap yang dihasilkan pada penelitian ini (dibukukan dalam product knowledge

booklet) dapat ditindaklanjuti sebagai peningkatan daya saing dan perluasan pangsa pasar

produk kain batik cap dalam rangka pemberdayaan ekonomi lokal. Peningkatan keahlian

pengrajin dalam pengembangan moif, yang berbasis pada perkembangan ilmu pengetahuan,

teknologi dan seni ini dapat menjadi inspirator dalam upaya mengembangkan teknoprener-

teknoprener baru di industri kreatif batik cap atau merevitalisasi UMKM inovatif, yang

merupakan salah satu pilar utama dalam pengembangan SIDa (Sistem Inovasi Daerah).

DAFTAR PUSTAKA

1. Durbin, J.R, (1985), Modern Algebra : an Introduction, Second Edition, New

York:John Willey & Sons

2. Kartono, R. Heri Soelistyo Utomo, Harjito, (2000), Grup Simetri untuk Pengembangan

Desain Motif Batik Simetris, Laporan penelitian dosen muda dengan nomor:

015/P2IPT/DM/VI/1999.

3. Kartono, Priyono, Budi Warsito, (2011), Menguak Misteri Crop Circle di Indonesia,

Yogyakarta: Graha Ilmu, pp.41-53

4. Kartono, R.Heri Soelistyo Utomo, (2012),Pemberdayaan Ekonomi Lokal melalui

Pengembangan Inovasi Jenis Produk Bordir di Kabupaten Kudus, Laporan RUD

Balitbang Provinsi Jawa Tengah

5. Nurhilaliah, Ulfia Azmi, Kartono (Pembimbing), (2012), Pemanfaatan Limbah Kayu

Sebagai Bahan Pembuatan Ukiran Bergerak Berbasis Transformasi , Artikel Ilmiah

ISPO 2012

UCAPAN TERIMA KASIH

Artikel ini merupakan sebagian dari hasil penelitian Hibah Bersaing Desentralisasi DIKTI tahun

2013, oleh karena itulah penulis mengucapkan terima kasih atas kesempatan penelitian yang

diberikan. Ucapan terima kasih juga disampaikan kepada Batik Adityan Laweyan Surakarta

yang telah bekerjasama dengan baik untuk menyelesaikan proses pembuatan cap dan kain

batiknya.



LAMPIRAN: 10 CORAK KAIN BATIK CAP CROP CIRCLE



Eksistensi dan Karakterisasi Kontrol Optimal Vaksinasi Model Epidemi S I R

dengan Laju Insidensi Jenuh yang Termodifikasi

Rubono Setiawan

Prodi Pendidikan Matematika

Jurusan P.MIPA, F.KIP, Universitas Sebelas Maret

Gedung D Lantai 3 Komplek Gedung F.KIP Kampus Kentingan

Jalan Ir.Sutami No.36 A Kentingan Surakarta

e-mail : [email protected]

Abstrak

Dalam paper ini digunakan model epidemi S I R ( Susceptible Invected Recovered) dasar (

Kermack & Mc. Kendrick ) dengan laju insidensi jenuh termodifikasi dan dengan beberapa

asumsi tambahan lain. Strategi vaksinasi optimal dilakukan untuk meminimalkan jumlah

individu pada kelompok individu rentan dan terinfeksi untuk kemudian memaksimalkan

jumlah individu pada kelompok sembuh. Permasalahan optimasi yang dibentuk adalah

meminimalkan fungsional tujuan yang memuat variabel kontrol, serta sistem persamaan

diferensial yang dalam hal ini adalah model S I R sebagai kendala dalam permasalahan

optimasi tersebut. Hamiltonian disusun berdasarkan Lagrangian dari permasalahan

optimasi dan digunakan untuk membuktikan eksistensi serta menentukan kontrol yang

optimal dari permasalahan optimasi. Kriteria minimum Pontryagin digunakan sebagai alat

utama untuk menentukan kontrol yang optimal dan sistem yang optimal.

Kata Kunci : Kontrol Optimal, Model S I R , Vaksinasi Optimal, Hamiltonian, Pontryagin

1. PENDAHULUAN

Pembelajaran tentang dinamika penyakit menular merupakan bagian yang sangat penting dalam

bidang matematika epidemiologi. Dengan mengerti lebih dalam tentang karakteristik dari

penyebaran penyakit menular dalam suatu kelompok, daerah, masyarakat atau bahkan suatu

negara, maka dapat ditemukan cara cara yang lebih baik dan sesuai untuk menekan penyebaran

penyakit tertentu tersebut. Cara yang umum dikenal adalah dengan program vaksinasi yang

sesuai dan program proteksi atau karantina.

Model penyebaran penyakit telah banyak dipelajari oleh banyak penulis

1 , 2 , 3 , 5 , 6 . Cukup banyak diantaranya yang tertarik menggunakan bentuk laju

insidensi jenuh dalam formulasi modelnya, seperti 6 , 5 , 3 . Bentuk laju insidensi jenuh

dapat digolongkan menjadi bentuk laju insidensi nonlinear. Salah satu kelebihan dari bentuk

laju insidensi ini adalah adanya faktor jenuh yang ditentukan berdasarkan pengendalian

epidemi. Pengendalian epidemi yang dimaksud adalah berdasarkan ukuran pencegahan yang

sesuai terhadap penyakit atau pembawa ( vektor ) penyakit yang bersangkutan. Dalam hal ini

pencegahan ataupun pengendalian dapat dilakukan oleh dan atau terhadap individu dalam

kelompok individu rentan penyakit ataupun yang telah terjangkit penyakit. Bila hanya ada satu

ukuran pencegahan misalnya dilakukan oleh individu rentan penyakit maka digunakan bentuk

insidensi jenuh dengan satu faktor insidensi jenuh yang menunjukkan ukuran ukuran

pencegahan atau tindakan-tindakan prefentif yang sesuai dari individu sehat yang rentan

terkena penyakit , seperti yang telah digunakan dan dibahas oleh Zhang, dkk., 6 dan Setiawan,



R., 5 yaitu berbentuk 𝛽𝑆𝐼

1+𝛼1𝑆. Kemudian juga terdapat bentuk laju insidensi yang lain yaitu

𝛽𝑆𝐼

1+𝛼2𝐼, dalam bentuk insidensi ini menunjukkan bahwa jumlah kontak infektif antara individu

rentan dan individu terinfeksi dapat mengalami jenuh pada level infeksi yang tinggi karena

tingkat kepadatan individu yang tinggi dalam kelompok terinfeksi atau karena ukuran ukuran

proteksi yang dilakukan oleh kelompok individu rentan penyakit. Dalam paper ini akan

digunakan bentuk insidensi jenuh yang dimodifikasi yang berbentuk 𝛽𝑆 𝑡 𝐼 𝑡

1+𝛼1𝑆 𝑡 +𝛼2𝐼(𝑡). Dalam laju

insidensi tersebut memuat dua faktor insidensi jenuh yang tentunya mengakomodasi ukuran

ukuran tindakan pencegahan, proteksi dan kejenuhan yang terjadi karena tingkat kepadatan

penduduk yang tinggi.

Model dasar yang digunakan pada makalah ini nantinya adalah model S I R ( Susceptible

Invected Recovered ) dasar dengan beberapa asumsi- asumsi tambahan. Kemudian akan

dibentuk suatu permasalahan optimasi yang melibatkan model berbentuk sistem persamaan

diferensial sebagai kendala dari fungsi kontrol opimal vaksinasi yang merupakan fungsi tujuan (

biaya) dari permasalahan kontrol optimal tersebut. Dalam hal untuk menjabarkan permasalahan

tersebut maka makalah ini ditulis dalam beberapa bab yang dimulai dengan materi pendukung

tentang kontrol optimal sistem dinamik kontinu, fungsi biaya sebagai fungsi kontrol optimal

vaksinasi. Kemudian dilajutkan dengan bab hasil dan pembahasan yang berisi tentang eksistensi

kontrol optimal dan karakterisasi dari kontol optimal tersebut.

2. METODE PENELITIAN

Metode penelitian untuk mendapatkan hasil dalam makalah ini adalah metode literatur dengan

mengkaji makalah-makalah yang membahas penggunaan teori kontrol optimal pada model

penyebaran penyakit. Model dasar yang digunakan adalah model S I R yang digunakan oleh

Laarabi, dkk. 3 . Penelitian pengembangan dilakukan dengan menggunakan model yang

menggunakan angka kematian yang berbeda pada tiap subkelas populasi.

3. MATERI DAN TEORI PENDUKUNG

3.1. Bentuk Permasalahan Optimasi Kontol Optimal Sistem Dinamik Kontinu

Tanpa mengurangi keumuman, akan dijelaskan bentuk umum permasalahan optimasi sistem

dinamik kontinu untuk masalah minimasi fungsional kontrol. Misalkan diketahui 𝑥 adalah

keadaan (state) dari sistem dinamik kontinu bersyarat awal 𝑥0 dan dengan input kontrol u

sedemkian sehingga

𝑥 = 𝑓 𝑥, 𝑢 , 𝑥 0 = 𝑥0 , 𝑢 𝑡 ∈ 𝒰, 𝑡 ∈ 0, 𝑇 (3.1.1)

dengan 𝒰 adalah himpunan kontrol admissible, T adalah waktu final / akhir dari sistem. Dalam

hal ini kontrol 𝑢 ∈ 𝒰 haruslah dipilih untuk semua 𝑡 ∈ 0, 𝑇 untuk meminimalkan fungsional



tujuan J yang didefinisikan berdasarkan permasalahan nyata dalam aplikasi dan dapat

diabstraksikan sebagai

𝐽 = Ψ 𝑥 𝑇 + 𝐿 𝑥 𝑡 , 𝑥(𝑡) 𝑑𝑡 (3.1.2)

𝑇

0

dengan L adalah Lagrangian. Kemudian kendala dalam sistem dinamik dapat digabung dengan

Lagrangian L untuk mendapatkan vektor pengali Langrange 𝜆 yang sesuai dan nilainya berubah

terhadap waktu, dimana masing – masing anggota 𝜆 disebut sebagai keadaan bersama (costate)

dari sistem. Pengertian – pengertian tersebut sebagai dasar untuk mengkontruksi HamiltonianH

yang didefinisikan untuk setiap 𝑡 ∈ 0, 𝑇 sebagai

𝐻 𝜆 𝑡 , 𝑥 𝑡 , 𝑢 𝑡 , 𝑡 = 𝐿 𝑥 𝑡 , 𝑢(𝑡) + 𝜆𝑇𝑓 𝑥 𝑡 , 𝑢(𝑡) (3.1.3)

dengan 𝜆𝑇adalah transpose dari 𝜆. Selanjutnya Hamiltonian tersebut memengang peranan yang

sangat penting untuk membuktikan eksistensi adanya kontrol yang optimal dan menentukannya

dengan menggunakan prinsip minimum Pontryagin yang akan dijelaskan pada subbab

selanjutnya.

3.2. Permasalahan Optimasi Kontrol Optimal Model Penyebaran Penyakit

Dalam masalah penyebaran penyakit, hal yang pasti ingin diminimumkan adalah jumlah

individu rentan dan individu terinfeksi penyakit sehingga jumlah individu sembuh dapat

dimaksimumkan. Dalam usaha untuk mengendalikan penyebaran penyakit tersebut, salah satu

cara yang umum dilakukan adalah vaksinasi, yaitu vaksinasi terhadap individu rentan ( pasif )

dan atau individu terinfeksi penyakit ( aktif ). Vaksinasi tersebut dapat diasosiasikan dengan

suatu variabel kontrol u dan ditambahkan ke dalam model penyebaran penyakit yang

bersangkutan. Dalam hal membentuk permasalahan optimasi kontrol optimal, jumlah individu

rentan dan terinfeksi yang dikalikan dengan angka penyeimbang yang sesuai serta ditambah

dengan fungsi biaya yang dibutuhkan dalam kegiatan vaksinasi akan diformulasikan menjadi

fungsional tujuan yang akan diminimumkan, sedangkan model penyebaran penyakit yang

berbentuk sistem persamaan diferensial nonlinear yang memuat variabel kontrol akan menjadi

kendala ( constraint ) dalam permasalahan optimasi kontrol optimal tersebut.

3.3. Prinsip Minimum Pontryagin

Prinsip-prinsip minimum Pontryagin diturunkan dari aslinya yaitu prinsip- prinsip maksimum

Pontryagin. Prinsip tersebut ( baik maksimum maupun minimum) digunakan dalam teori

kontrol optimal untuk menentukan kemungkinan kontrol terbaik untuk sistem dinamik yang

telah ditentukan, dari keadaan satu ke keadaan yang lain, lebih khusus lagi apabila munculnya

kendala-kendala untuk keadaan atau input kontrolnya. Prinsip tersebut pertama kali



diperkenalkan pada tahun 1956 oleh matematikawan Rusia Lev Semenovic Pontryagin dan

murid-muridnya V.G. Boltyanskii, R.V. Gamkrelidze, 7 .Prinsip tersebut mempunyai bentuk

khusus persamaan Euler dan Lagrange dari kalkulus variasi.

Inti dari prinsip tersebut mengatakan bahwa Hamiltonian H yang dibentuk dari

permasalahan optimasi ( dalam hal ini tanpa mengurangi keumuman diambil kasus untuk

minimasi) kontrol optimal haruslah diminimumkan atas U, yaitu himpunan admissible control.

Jika 𝑢∗ ∈ 𝑈 adalah kontrol yang optimal dari permasalahan optimasi, maka prinsip minimum

Pontryagin mengatakan

𝐻 𝑥∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆∗ 𝑡 , 𝑡 ≤ 𝐻 𝑥∗ 𝑡 , 𝑢(𝑡), 𝜆∗ 𝑡 , 𝑡 , ∀𝑢 ∈ 𝑈, 𝑡 ∈ 𝑡0 , 𝑡𝑒𝑛𝑑 , (3.3.1)

dengan 𝑥∗ ∈ 𝐶1 𝑡0 , 𝑡𝑒𝑛𝑑 adalah trayektori keadaan (state) yang optimal, sedangkan 𝜆∗ ∈

𝐵𝑉 𝑡0 , 𝑡𝑒𝑛𝑑 ( Fungsi bervariasi terbatas pada 𝑡0 , 𝑡𝑒𝑛𝑑 ) adalah trayektori costate yang optimal.

Kemudian prinsip tersebut juga diturunkan untuk kondisi khusus dari Hamiltonian, yaitu apabila

waktu akhir 𝑡𝑒𝑛𝑑 ditentukan dan Hamiltonian tidak bergantung secara eksplisit terhadap waktu (

kondisi ekuilibrium terhadap waktu , 𝜕𝐻

𝜕𝑡≡ 0 ), maka prinsip minimum Pontryagin – nya adalah

𝐻 𝑥∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆∗ 𝑡 ≡ konstan, (3.3.2)

dan kemudian jika waktu akhir tidak ada maka

𝐻 𝑥∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆∗ 𝑡 ≡ 0. (3.3.3)

Selanjutnya akan dijelaskan syarat perlu untuk masalah minimasi kontrol optimal berdasar

prinsip minimum Pontryagin. Berdasarkan bentuk formal dari permasalahan minimasi kontrol

optimal (3.1.2) dengan kendala (3.1.1), maka prinsip minimum Pontryagin mengatakan bahwa

trayektori keadaan (state) optimal 𝑥∗, kontrol optimal 𝑢∗dan vektor pengali Lagrange 𝜆∗ yang

sesuai haruslah meminimalkan Hamiltonian H sedemikian sehingga

i. 𝐻 𝑥∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆∗ 𝑡 , 𝑡 ≤ 𝐻 𝑥∗ 𝑡 , 𝑢(𝑡), 𝜆∗ 𝑡 , 𝑡 , ∀𝑢 ∈ 𝑈, 𝑡 ∈ 𝑡0 , 𝑡𝑒𝑛𝑑 dan haruslah

memenuhi kondisi

ii. Ψ𝑇 𝑥 𝑇 + 𝐻 𝑇 = 0, dengan Ψ𝑇 𝑥 𝑇 = 𝜕Ψ 𝑥

𝜕𝑇 𝑥=𝑥 𝑇

,

sebagai tambahan persamaan keadaan bersama ( costate )

iii. −𝜆 𝑇 𝑡 = 𝐻𝑥 𝑥∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆∗ 𝑡 , 𝑡 = 𝜆𝑇 𝑡 𝑓𝑥 𝑥∗ 𝑡 , 𝑢∗ 𝑡 + 𝐿𝑥 𝑥∗ 𝑡 , 𝑢∗ 𝑡 harus

juga dipenuhi, dengan

𝐻𝑥 𝑥∗, 𝑢∗, 𝜆∗ = 𝜕𝐻

𝜕𝑥1 𝑥=𝑥∗,𝑢=𝑢∗,𝜆=𝜆∗

… 𝜕𝐻

𝜕𝑥𝑛 𝑥=𝑥∗,𝑢=𝑢∗,𝜆=𝜆∗

𝐿𝑥 𝑥∗, 𝑢∗ = 𝜕𝐿

𝜕𝑥1 𝑥=𝑥∗,𝑢=𝑢∗

… 𝜕𝐿

𝜕𝑥𝑛 𝑥=𝑥∗,𝑢=𝑢∗



𝑓𝑥 𝑥∗, 𝑢∗ =

𝜕𝑓1

𝜕𝑥1 𝑥=𝑥∗,𝑢=𝑢∗

… 𝜕𝑓1

𝜕𝑥𝑛 𝑥=𝑥∗,𝑢=𝑢∗

⋮ ⋱ ⋮

𝜕𝑓𝑛𝜕𝑥1

𝑥=𝑥∗,𝑢=𝑢∗

… 𝜕𝑓𝑛𝜕𝑥𝑛

𝑥=𝑥∗,𝑢=𝑢∗

Jika waktu akhir / final 𝑥(𝑇) tidak diketahui nilainya secara pasti (𝜕𝐻

𝜕𝑡≠ 0) maka haruslah

berlaku

iv. 𝜆𝑇 𝑇 = Ψ𝑥 𝑥 𝑇 .

Keempat kondisi di atas merupakan syarat perlu untuk adanya kontrol optimal, tetapi syarat ke

empat hanya digunakan ketika sistem tidak memiliki 𝑥 𝑇 . Jika 𝑥 𝑇 nilainya diketahui pasti

(fixed) maka kondisi ke empat bukanlah kondisi perlu untuk adanya kontrol optimal.

4. HASIL DAN PEMBAHASAN

4.1. Formulasi Model SIR dengan Laju Insidensi Jenuh Termodifikasi

Dalam subbab ini akan diformulasikan model SIR dengan beberapa asumsi tambahan baru,

dinama berdasarkan modelSIR tersebut akan dianalisa eksistensi dan karakterisasi kontrol

optimal tindakan vaksinasi. Model SIR yang digunakan adalah model SIR berdasarkan model

SIR yang ditulis oleh Laarabi, dkk. 3 , tetapi dengan modifikasi pada angka kematian alami

pada tiap kelas. Jika model SIR dalam 3 digunakan laju kematian alami yang pasti sama pada

tiap kelas, maka pada model di paper ini digunakan laju kematian alami yang memungkinkan

berbeda pada tiap kelas individu. Model SIR tersebut menggunakan laju insidensi jenuh yang

menggunakan dua faktor insidensi jenuh. Berikut ini model SIR selengkapnya yang disajikan

dalam sistem persamaan diferensial autonomos

𝑆 = 𝐴 −𝛽𝑆𝐼

1 + 𝛼1𝑆 + 𝛼2𝐼− 𝜇1𝑆

𝐼 =𝛽𝑆𝐼

1 + 𝛼1𝑆 + 𝛼2𝐼− 𝛿 + 𝜇2 + 𝛾 𝐼 (4.1.1)

𝑅 = 𝛾𝐼 − 𝜇3𝑅

𝑁 = 𝑆 + 𝐼 + 𝑅

dengan syarat awal 𝑆 0 = 𝑆0 ≥ 0, 𝐼 0 = 𝐼0 ≥ 0, 𝑅 0 = 𝑅0 ≥ 0. Dalam model SIR tersebut

di atas konstanta A adalah angka masukan (recruitment) populasi, 𝛽 adalah angka kontak

(transmisi), 𝜇1 , 𝜇2 , 𝜇3 masing – masing adalah angka kematian alami individu pada kelas rentan

(S), kelas terinfeksi (I) dan kelas sembuh (R), sedangkan 𝛿 adalah angka kematian akibat

pengaruh penyakit, kemudian yang terakhir adalah konstanta 𝛾 adalah angka kesembuhan dari

individu – individu yang terinfeksi.



4.2. Formulasi Model dengan Kontol Optimal Vaksinasi

Teknik kontrol optimal adalah cara yang banyak digunakan dalam hal mengembangkan strategi

untuk mengontrol berbagai jenis penyakit. Salah satu strategi tersebut adalah strategi vaksinasi

yang optimal. Tujuan utama dari strategi tersebut adalah untuk mengurangi jumlah individu

rentan dan individu terinfeksi penyakit serta meningkatkan jumlah individu yang sembuh.

Guna merumuskan permasalahan kontrol optimal maka akan dibutuhkan variabel kontrol

𝑢 𝑡 ∈ 𝑈𝑘𝑜𝑛𝑡𝑟𝑜𝑙 yang merupakan persentase dari individu – individu yang telah tervaksinasi per

satuan waktu. Kemudian 𝑈𝑘𝑜𝑛𝑡𝑟𝑜𝑙 didefinisikan dalam bentuk himpunan admissible control (

lihat 1 ) sebagai berikut :

𝑈𝑘𝑜𝑛𝑡𝑟𝑜𝑙 = 𝑢 𝑢 𝑡 terukur, 0 ≤ 𝑢 𝑡 ≤ 𝑢𝑚𝑎𝑥 < ∞, 𝑡 ∈ 0, 𝑡𝑒𝑛𝑑 (4.2.1)

Dalam tulisan ini diasumsikan adanya penyederhanaan pada variable kontrol yaitu 0 ≤ 𝑢(𝑡) ≤

𝑢𝑚𝑎𝑥 7 . Hal tersebut menurut Laarabi, dkk. 3 . Dikarenakan tidak mungkin untuk melakukan

vaksinasi untuk semua individu yang masuk kelas rentan penyakit dalam satu waktu. Kemudian

arti fisik dari variabel kontrol dalam masalah ini adalah jika jumlah individu rentan dan

terinfeksi mencapai level yang redah, maka jumlah individu sembuh akan meningkat.

Berdasarkan uraian tersebut di atas maka tujuan dari permasalahan optimasi yang akan dibentuk

adalah menimalkan jumlah individu rentan dan terinfeksi untuk meningkatkan jumlah individu

sembuh.

Setelah menentukan formulasi model SIR di atas, maka selanjutnya akan ditentukan

permasalahan optimasi dengan melibatkan model SIR dengan laju insidensi jenuh sebagai

kendala dan kontrol optimal vaksinasi sebagai fungsi tujuan untuk meminimalkan jumlah

individu terinfeksi dan juga individu rentan yang kemudian memaksimalkan jumlah individu

sembuh, yang dalam hal ini individu yang tervaksinasi akan langsung masuk ke dalam kelas

sembuh. Kontrol optimal yang digunakan dalam paper ini menggunakan kontrol optimal yang

digunakan oleh Laarabi, dkk. 3 . Berikut permasalahan optimasi selengkapnya.

Meminimalkan

𝐽 𝑢 = 𝐴1𝑆 𝑡 + 𝐴2𝐼 𝑡 +1

2𝜏𝑢2 𝑡

𝑡𝑒𝑛𝑑

0

𝑑𝑡 (4.2.2)

dengan kendala

𝑆(𝑡) = 𝐴 − 𝜇1 + 𝑢 𝑡 𝑆(𝑡) −𝛽𝑆 𝑡 𝐼(𝑡)

1 + 𝛼1𝑆(𝑡) + 𝛼2𝐼(𝑡)



𝐼(𝑡) =𝛽𝑆 𝑡 𝐼(𝑡)

1 + 𝛼1𝑆(𝑡) + 𝛼2𝐼(𝑡)− 𝛿 + 𝜇2 + 𝛾 𝐼(𝑡) (4.2.3)

𝑅(𝑡) = 𝛾𝐼 𝑡 − 𝜇3𝑅 𝑡 + 𝑢 𝑡 𝑆(𝑡)

dan dengan syarat awal 𝑆 0 = 𝑆0 ≥ 0, 𝐼 0 = 𝐼0 ≥ 0, 𝑅 0 = 𝑅0 ≥ 0. Dalam Persamaan

fungsi tujuan (4.2.2) suku 𝑆(𝑡) dan 𝐼 𝑡 merepresentasikan hasil capaian 𝑆(𝑡) dan 𝐼(𝑡) yang

ingin dikurangi, kemudian konstanta – konstanta positif 𝐴1 dan 𝐴2 masing – masing

dimaksudkan untuk menjaga keseimbangan besar 𝑆(𝑡) dan 𝐼 𝑡 . Dalam banyak kontrol optimal

yang terjadi membutuhkan biaya, tetapi dalam hal ini kita tidak mempunyai data yang cukup

untuk menentukan biaya secara pasti yang berhubungan dengan kontrol vaksinasi, oleh karena

itu dalam tulisan ini difokuskan dalam hal penggunaan “ biaya relatif ” (relative cost) untuk

kontrol. Dalam Persamaan (4.2.1) digunakan suku kuadrat 1

2𝜏𝑢2 , dimana konstanta 𝜏 adalah

angka beban yang berkaitan dengan kontrol 𝑢(𝑡) dan dalam hal ini kontrol kuadrat

mencerminkan tingkat keparahan efek samping dari vaksinasi (Joshi, 2 , dalam Laarabi, dkk.

3 .)

4.3. Eksistensi Penyelesaian

Dalam subbab ini akan dianalisa eksistensi penyelesaian dari Sistem (4.2.3). Pertama, Sistem

(4.2.3) akan ditulis dalam sistem nonlinear dengan koefisien terbatas adalah :

𝜙𝑡 = 𝐵𝜙 + 𝐹 𝜙 (4.3.1)

dengan 𝜙 = 𝑆 𝑡 𝐼 𝑡 𝑅(𝑡) 𝑇;

𝐵 =

− 𝜇1 + 𝑢 𝑡 0 0

0 − 𝛿 + 𝜇2 + 𝛾 0

𝑢 𝑡 𝛾 −𝜇3

, 𝐹 𝜙 =

𝐴 −

𝛽𝑆 𝑡 𝐼(𝑡)

1 + 𝛼1𝑆(𝑡) + 𝛼2𝐼(𝑡)

𝛽𝑆 𝑡 𝐼(𝑡)

1 + 𝛼1𝑆(𝑡) + 𝛼2𝐼(𝑡)0

dan 𝜙𝑡 adalah turunan dari 𝜙 terhadap waktu t . Kemudian dibentuk operator D dengan definisi

sebagai berikut

𝐷 𝜙 = 𝐵𝜙 + 𝐹 𝜙

Diambil sebarang 𝜙1 dan 𝜙2 anggota himpunan penyelesaian dari Sistem kemudian

𝐹 𝜙1 − 𝐹 𝜙2 = 2𝛽𝑆2𝐼2 1 + 𝛼1𝑆1 + 𝛼2𝐼1 − 𝑆1𝐼1 1 + 𝛼1𝑆2 + 𝛼2𝐼2

1 + 𝛼1𝑆1 + 𝛼2𝐼1 1 + 𝛼1𝑆2 + 𝛼2𝐼2

= 2𝛽 𝑆2𝐼2 1 + 𝛼1𝑆1 + 𝛼2𝐼1 − 𝑆1𝐼1 1 + 𝛼1𝑆2 + 𝛼2𝐼2

1 + 𝛼1𝑆1 + 𝛼2𝐼1 1 + 𝛼1𝑆2 + 𝛼2𝐼2



≤ 2𝛽 𝑆2𝐼2 1 + 𝛼1𝑆1 + 𝛼2𝐼1 − 𝑆1𝐼1 1 + 𝛼1𝑆2 + 𝛼2𝐼2

≤ 2𝛽 𝑆2𝐼2 + 𝛼1𝑆1𝑆2𝐼2 + 𝛼2𝐼1𝑆2𝐼2 − 𝑆1𝐼1 − 𝛼1𝑆2𝑆1𝐼1 − 𝑆1𝐼1𝛼2𝐼2

≤ 2𝛽 𝛼1𝑆1𝑆2 𝐼2 − 𝐼1 + 𝛼2𝐼1𝐼2 𝑆2 − 𝑆1 + 𝑆2𝐼2 − 𝑆1𝐼1

≤ 2𝛽 𝛼1𝑆1𝑆2 𝐼2 − 𝐼1 + 𝛼2𝐼1𝐼2 𝑆2 − 𝑆1 + 𝑆2 𝐼2 − 𝐼1 + 𝐼1 𝑆2 − 𝑆1

≤ 2𝛽 𝛼1𝑆1𝑆2 𝐼2 − 𝐼1 + 𝛼2𝐼1𝐼2 𝑆2 − 𝑆1 + 𝑆2 𝐼2 − 𝐼1 + 𝐼1 𝑆2 − 𝑆1 (∗)

≤ 2𝛽 𝛼1 𝐴

𝜇1

2

𝐼2 − 𝐼1 + 𝛼2 𝐴

𝜇1

2

𝑆2 − 𝑆1 + 𝐴

𝜇1 𝐼2 − 𝐼1

+ 𝐴

𝜇1 𝑆2 − 𝑆1 ∗∗

≤ 𝑀 𝑆2 − 𝑆1 + 𝐼2 − 𝐼1 (4.3.2)

dengan 𝑀 = 2𝛽max 𝛼1 𝐴

𝜇1

2+

𝐴

𝜇1 , 𝛼2

𝐴

𝜇1

2+

𝐴

𝜇1 .

Dalam pertidaksamaan (4.3.2), berdasarkan (*) apabila dicari penyelesaian untuk dinamika S

sebelum dikurangi dengan suku insidensi dan penyelesaian tersebut diambil untuk 𝑡 → ∞ maka

akan diperoleh kesimpulan bahwa jumlah individu S terbatas pada 𝐴

𝜇1, lebih lanjut jumlah

individu I juga pasti tidak akan lebih dari 𝐴

𝜇1. Berdasarkan Pertidaksamaan (4.3.2) akan

didapatkan hubungan :

𝐷 𝜙1 − 𝐷 𝜙2 ≤ 𝐾 𝜙1 − 𝜙2 (4.3.3)

dengan 𝐾 = max 𝑀, 𝐵 < ∞. Berdasarkan Pertidaksamaan (4.3.3) D adalah kontinu

Lipschitz seragam, lebih lanjut ditambah dengan definisi dari kontrol 𝑢(𝑡) serta pembatasan

pada 𝑆 𝑡 , 𝐼 𝑡 , 𝑅 𝑡 ≥ 0, maka dapat kita simpulkan bahwa penyelesaian dari Sistem (4.3.1)

ada.

4.4. Eksistensi Kontrol yang Optimal

Setelah memuktikan eksistensi penyelesaian dari Sistem (4.3.2), selanjutnya akan dibuktikan

eksistensi dari kontrol optimal. Sebelumnya akan ditentukan terlebih dahulu Lagrangian dan

Hamiltonian dari permasalahan optimasi (4.2.2) – (4.2.3). Langrangian dari permasalahan

optimasi tersebut adalah

𝐿 𝑆, 𝐼, 𝑢 = 𝐴1𝑆 𝑡 + 𝐴2𝐼 𝑡 +1

2𝜏𝑢2 𝑡 (4.4.1)



Selanjutnya untuk mencari nilai minimum dari Lagrangian (4.4.1) maka dibentuklah

Hamiltonian H untuk permasalahan kontrol optimal. Hamiltonial dari permasalahan optimasi

(4.2.2) – (4.2.3) adalah

𝐻 𝑥 𝑡 , 𝑢 𝑡 , 𝜆 𝑡 , 𝑡 = 𝑓 𝑥 𝑡 , 𝑢 𝑡 , 𝑡 + 𝜆 𝑡 𝑔 𝑥 𝑡 , 𝑢 𝑡 , 𝑡 (4.4.2)

dengan 𝑓 𝑡, 𝑥 𝑡 , 𝑢(𝑡) adalah integran fungsi tujuan, 𝜆(𝑡) adjoint dan 𝑔 𝑡, 𝑥 𝑡 , 𝑢 𝑡 adalah

ruas kanan dari sistem persamaan diferensial biasa yang sebagai model S I R. Bentuk (4.4.2)

apabila disesuaikan dengan model yang telah terformulasikan maka dapat ditulis sebagai

𝐻 𝑆, 𝐼, 𝑅, 𝑢, 𝜆1 , 𝜆2 , 𝜆3 , 𝑡 = 𝐿 𝑆, 𝐼, 𝑢 + 𝜆1

𝑑𝑆(𝑡)

𝑑𝑡+ 𝜆2

𝑑𝐼(𝑡)

𝑑𝑡+ 𝜆3

𝑑𝑅(𝑡)

𝑑𝑡 (4.4.3)

dalam hal ini 𝜆1 , 𝜆2 dan 𝜆3 adalah fungsi-fungsi adjoint yang sesuai.

Untuk penjaminan adanya kontrol optimal dari permasalahan optimasi (4.2.2) – (4.2.3),

akan dijelaskan lewat teorema berikut :

Teorema 4.4.1.Terdapat suatu kontrol optimal 𝑢∗ 𝑡 sedemikian sehingga

𝐽 𝑢∗ 𝑡 = 𝑚𝑖𝑛𝑢∈𝑈

𝐽 𝑢(𝑡)

dengan kendala Sistem (4.2.3) dengan syarat awal.

Bukti :

Variabel kontrol dan variabel keadaan (state variable) dari sistem semuanya bernilai tak negatif.

Kemudian suku 𝑢(𝑡) pada fungsional fungsi tujuan bersifat konvek yang merupakan syarat

perlu untuk masalah minimasi. Berdasarkan definisi dari ruang kontrol sendiri maka ruang

kontrol (4.2.1) juga konvek dan tertutup. Karena sistem optimal (4.2.3) terbatas maka juga

memenuhi sifat kekompakan yang diperlukan untuk eksistensi kontrol yang optimal. Selain itu

integran dalam fungsional (4.2.2) , 𝐴1𝑆 𝑡 + 𝐴2𝐼 𝑡 +1

2𝜏𝑢2 𝑡 juga konveks pada suku kontrol

𝑢(𝑡). Kemudian dapat dengan dibuktikan bahwa terdapat konstanta 𝜌 > 1, bilangan positif 𝜔1

dan 𝜔2 sedemikian sehingga

𝐽 𝑢(𝑡) ≥ 𝜔2 + 𝜔1 𝑢 2 𝜌

2 .

Berdasarkan uraian tersebut dapat disimpulkan bahwa terdapat kontrol optimal untuk

permasalahan optimasi (4.2.2) – (4.2.3). Q.E.D.

4.5. Karakterisasi dan Penentuan Kontrol yang Optimal

Eksistensi adanya kontrol yang optimal dari permasalahan optimasi (4.2.2) – (4.2.3) telah

dibuktikan pada subbab sebelumnya, kemudian untuk menentukan kontrol yang optimal



tersebut akan digunakan prinsip minimum Pontryagin pada Hamiltonian (4.4.2). Jika

𝑥∗ 𝑡 , 𝑢∗ 𝑡 adalah solusi optimal dari permasalahan optimasi kontrol optimal, maka terdapat

fungsi vektor nontrivial 𝜆 𝑡 = 𝜆1 𝑡 , 𝜆2 𝑡 , … , 𝜆𝑛 𝑡 𝑡 yang memenuhi persamaan –

persamaan berikut :

𝑥′ 𝑡 =𝜕𝐻 𝑥∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆 𝑡 , 𝑡

𝜕𝜆 4.5.1

0 =𝜕𝐻 𝑥∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆 𝑡 , 𝑡

𝜕𝑢 4.5.2

𝜆′ 𝑡 = −𝜕𝐻 𝑥∗ 𝑡 , 𝑢∗ 𝑡 , 𝜆 𝑡 , 𝑡

𝜕𝑥 (4.5.3)

Berdasarkan sifat dari ruang kontrol

𝑢∗ 𝑡 = 0, jika

𝜕𝐻

𝜕𝑢< 0

𝑢∗ 𝑡 ∈ 0, 𝑢𝑚𝑎𝑥 , jika𝜕𝐻

𝜕𝑢= 0

𝑢∗ 𝑡 = 𝑢𝑚𝑎𝑥 , jika𝜕𝐻

𝜕𝑢> 0

4.5.4

dan hasil dalam Persamaan (4.5.2) maka 𝑢∗ 𝑡 ∈ 0, 𝑢𝑚𝑎𝑥 .

Teorema 4.5.1.Jika 𝑆∗ 𝑡 , 𝐼∗ 𝑡 dan 𝑅∗(𝑡) adalah keadaan optimal yang berhubungan dengan

variabel kontrol yang optimal 𝑢∗ 𝑡 dari permasalahan optimasi (4.2.2) – (4.2.3), maka

terdapat variabel adjoint ( pengali Lagrange) 𝜆1 , 𝜆2 dan 𝜆3 yang sesuai dan memenuhi

𝑑𝜆1 𝑡

𝑑𝑡= −𝐴1 + 𝜆1 𝑡 𝜇1 + 𝑢 𝑡 + 𝜌1 − 𝜆2 𝑡 𝜌1 − 𝜆3 𝑡 𝑢 𝑡 ,

𝑑𝜆2

𝑑𝑡= −𝐴2 + 𝜆1 𝑡 𝜌2 − 𝜆2 𝑡 𝜌2 − 𝛿 + 𝜇2 + 𝛾 − 𝜆3 𝑡 𝛾,

𝑑𝜆3 𝑡

𝑑𝑡= 𝜆3 𝑡 𝜇3 ,

dengan

𝜌1 =𝛽𝐼 1 + 𝛼2𝐼

1 + 𝛼1𝑆 + 𝛼2𝐼 2, 𝜌2 =

𝛽𝑆 1 + 𝛼2𝑆

1 + 𝛼1𝑆 + 𝛼2𝐼 2 ,

dan kondisi transversal

𝜆𝑖 𝑡𝑒𝑛𝑑 = 0, 𝑖 = 1,2,3.

Lebih lanjut, kontrol optimal 𝑢∗ 𝑡 yang diberikan untuk



𝑢∗ 𝑡 = 𝑚𝑎𝑥 𝑚𝑖𝑛 𝜆1 𝑡 − 𝜆3 𝑆∗ 𝑡

𝜏, 𝑢𝑚𝑎𝑥 , 0 .

Bukti

Akan digunakan persamaan Hamiltonian (4.4.3) untuk membuktikan persamaan – persamaan

adjoint dan kondisi transversal. Jika diambil 𝑆 𝑡 = 𝑆∗ 𝑡 , 𝐼 𝑡 = 𝐼∗ 𝑡 ,

𝑅 𝑡 = 𝑅∗ 𝑡 dan kemudian melakukan diferensiasi terhadap Hamiltonian H terhadap S, I dan

R, serta berdasarkan syarat perlu ( syarat iii ) untuk prinsip minimum Pontryagin maka akan

didapat

𝑑𝜆1 𝑡

𝑑𝑡= −

𝜕𝐻

𝜕𝑆= −𝐴1 + 𝜆1 𝑡 𝜇1 + 𝑢 𝑡 + 𝜌1 − 𝜆2 𝑡 𝜌1 − 𝜆3 𝑡 𝑢 𝑡

𝑑𝜆2 𝑡

𝑑𝑡= −

𝜕𝐻

𝜕𝐼= −𝐴2 + 𝜆1 𝑡 𝜌2 − 𝜆2 𝑡 𝜌2 − 𝛿 + 𝜇2 + 𝛾 − 𝜆3 𝑡 𝛾

𝑑𝜆3 𝑡

𝑑𝑡= −

𝜕𝐻

𝜕𝑅= 𝜆3 𝑡 𝜇3

dengan

𝜌1 =𝛽𝐼 1 + 𝛼2𝐼

1 + 𝛼1𝑆 + 𝛼2𝐼 2, 𝜌2 =

𝛽𝑆 1 + 𝛼2𝑆

1 + 𝛼1𝑆 + 𝛼2𝐼 2

Selanjutnya dengan menggunakan kondisi optimal untuk Hamiltonian, maka akan didapat

hubungan

𝜕𝐻

𝜕𝑢= 0

⇔𝜕𝐻

𝜕𝑢= 𝜏𝑢∗ 𝑡 − 𝜆1 𝑡 𝑆∗ + 𝜆3 𝑡 𝑆∗ 𝑡 = 0, di 𝑢 = 𝑢∗ 𝑡 ,

dan dihasilkan

𝑢∗ 𝑡 = 𝜆1 𝑡 − 𝜆3 𝑆∗ 𝑡

𝜏.

Kemudian jika menggunakan sifat dari ruang kontrol, akan didapatkan hubungan

𝑢∗ 𝑡 = 0, jika

𝜆1 𝑡 − 𝜆3 𝑆∗ 𝑡

𝜏≤ 0

𝑢∗ 𝑡 = 𝜆1 𝑡 − 𝜆3 𝑆∗ 𝑡

𝜏, jika 0 <

𝜆1 𝑡 − 𝜆3 𝑆∗ 𝑡

𝜏< 𝑢𝑚𝑎𝑥

𝑢∗ 𝑡 = 𝑢𝑚𝑎𝑥 , jika 𝜆1 𝑡 − 𝜆3 𝑆∗ 𝑡

𝜏> 0

Jadi, kontrol yang optimal dari permasalahan optimasi (4.2.2) – (4.2.3) dapat dikarakterisasi

sebagai



𝑢∗ 𝑡 = 𝑚𝑎𝑥 𝑚𝑖𝑛 𝜆1 𝑡 − 𝜆3 𝑆∗ 𝑡

𝜏, 𝑢𝑚𝑎𝑥 , 0 .

Q.E.D.

Suatu sistem yang optimal dari permasalahan optimasi kontrol otpimal terdiri atas keadaan dari

sistem ( state sytem ) yang berpasangan dengan adjoint dari sistem ( vektor pengali Lagrange )

dengan kondisi awal dan kondisi transversal bersama beserta karakterisasi dari kontrol optimal

tersebut. Berdasarkan karakterisasi dari kontrol optimal yang telah dijelaskan dalam Teorema

(4.5.1) maka didapat sistem optimal dari permasalahan optimasi (4.2.2) – (4.2.3)

𝑆 ∗ = 𝐴 − 𝜇1 + 𝑢∗ 𝑆∗ −𝛽𝑆∗𝐼∗

1 + 𝛼1𝑆∗ + 𝛼2𝐼∗

𝐼 ∗ =𝛽𝑆∗𝐼∗

1 + 𝛼1𝑆∗ + 𝛼2𝐼∗− 𝛿 + 𝜇2 + 𝛾 𝐼∗

𝑅 ∗ = 𝛾𝐼∗ − 𝜇3𝑅∗ + 𝑢∗𝑆∗

𝜆1 = −𝐴1 + 𝜆1 𝜇1 + 𝑢∗ +

𝛽𝐼∗ 1 + 𝛼2𝐼∗

1 + 𝛼1𝑆∗ + 𝛼2𝐼∗ 2 − 𝜆2

𝛽𝐼∗ 1 + 𝛼2𝐼∗

1 + 𝛼1𝑆∗ + 𝛼2𝐼∗ 2− 𝜆3𝑢∗

𝜆2 = −𝐴2 + 𝜆1

𝛽𝑆∗ 1 + 𝛼2𝑆∗

1 + 𝛼1𝑆∗ + 𝛼2𝐼∗ 2− 𝜆2

𝛽𝑆∗ 1 + 𝛼2𝑆∗

1 + 𝛼1𝑆∗ + 𝛼2𝐼∗ 2− 𝛿 + 𝜇2 + 𝛾 − 𝜆3𝛾

𝜆3 = 𝜆3𝜇3

4.5.5

5. PENUTUP

Berdasarkan uraian dan penjelasan pada bab hasil dan pembahasan dapat diambil kesimpulan

terdapat suatu kontrol optimal untuk permasalahan optimasi (4.2.2) – (4.2.3) dan untuk

menentukannya digunakan prinsip-prinsip minimum Pontryagin pada Hamiltonian yang

terbentuk. Dengan ditemukannya kontrol optimal tersebut, maka juga ditemukan keadaan

sistem persamaan diferensial ( model S I R ) dan vektor pengali Langrange yang sesuai untuk

terpenuhinya fungsi tujuan yang minimum yaitu meminimumkan jumlah individu rentan dan

terifeksi sehingga otomatis akan memaksimumkan jumlah individu yang sembuh, selain itu

juga meminimukan biaya ( cost ) relatif dari tindakan vaksinasi, sehingga pada akhirnya akan

ditemukan sistem yang optimal dari permasalahan optimasi (4.2.2) – (4.2.3) yaitu Sistem

(4.5.5)

6.DAFTAR PUSTAKA

1 Chachuat, B., Optimal Control Lecture 17-18 : Problem Formulation, Department of

Chemical Engineering, McMaster University, (2009)., diakses pada 12 september 2013.

2 Joshi, H.R., “ Optimal Control of An HIV Immunology Model “, Optim. Control Appl.

Methods, 23, pp. 199 – 213, (2002).



3 Laarabi, H.,Labriji, E.H.,Rachik, M.,Kaddar, A.,”Optimal Control of An Epidemic Model

with A Saturated Incidence Rate”, Nonlinear Analysis : Modelling and Control, Vol.17,

No.4, pp. 448 – 459, (2012).

4 Luenberger, D.G., Optimization by Vector Space Methods, John Wiley and Sons, Inc.,

USA, (1969)

5 Setiawan, R., Widodo, Aryati, L.,” Stability Analysis of Delayed S I R Epidemic Model

With Saturated Incidence”, Presented on International Conference on Algebra (ICA)

UGM Yogyakarta,Yogyakarta, Indonesia, (2010).

6 Zhang, J-Z. ; Jin,Z. ; Liu, Q –X. ; dan Zhang, Z-Y., Analysis of a Delayed SIR Model with

Nonlinear Incidence , Discrete Dynamics in Nature and Society, Hindawi Publishing

Corporation , Vol. 2008, Article ID 636153, (2008).

7 -------, Pontryagin’s Minimum Principle, Wikipedia the free encyclopedia, diakses di

http://en.wikipedia.org/wiki/Pontryagin’s_minimum_principle 29 September 2013.

http://en.wikipedia.org/wiki/Pontryagin's_minimum_principle



ANALISIS KAPASITAS MAKSIMUM LINTASAN

DENGAN PENDEKATAN ALJABAR MAX-MIN

M. Andy Rudhito1)

1) Program Studi Pendidikan Matematika FKIP Universitas Sanata Dharma

Kampus III USD Paingan Maguwoharjo Yogyakarta,

e-mail: [email protected]

Abstract

Artikel ini membahas suatu metode analisis kapasitas maksimum lintasan dalam suatu

jaringan dengan menggunakan pendekatan aljabar max-min. Pembahasan merupakan hasil

kajian teoritis yang didasarkan literatur dan suatu perhitungan menggunakan program

MATLAB. Hasil pembahasan menunjukkan bahwa jaringan yang memuat kapasitas, dapat

dimodelkan sebagai graf berarah terbobot, di mana bobotnya adalah kapasitas dalam

jaringan. Graf berarah terbobot di atas dapat dinyatakan dalam matriks atas aljabar max-

min. Dengan menggunakan operasi perpangkatan max-min untuk matriks di atas, dapat

ditentukan kapasitas maksimum lintasan antara dua buah titik dalam jaringan. Selanjutnya

diberikan program MATLAB untuk menghitung perpangkatan matriks atas aljabar max-

min yang dapat digunakan untuk membantu menentukan kapasitas maksimum lintasan

dalam jaringan tersebut..

Keywords:aljabar max-min, matriks, lintasan, kapasitas maksimum.

PENDAHULUAN

Aljabar max-plus (himpunan R{}, dengan R adalah himpunan semua bilangan

real, yang dilengkapi dengan operasi maximum dan penjumlahan) telah digunakan untuk

memodelkan dan menganalisis sistem produksi sederhana, dengan fokus analisa pada masalah

input-output sistem (Baccelli et.al, 2001 dan Rudhito, 2003). Pemodelan dan analisis sifat-sifat

suatu jaringan antrian juga telah dilakukan dengan pendekatan aljabar max-plus, seperti dalam

Krivulin (2000) dan Rudhito (2011). Penerapan aljabar max-plus pada masalah analisis lintasan

kritis juga telah dibahas dalam Rudhito (2010). Pemodelan dan analisa suatu jaringan dengan

pendekatan aljabar max-plus ini dapat memberikan hasil analitis dan lebih mudah pada

komputasinya.

Selain aljabar max-plus, dalam Baccelli et.al. (2001), Gondran and Minoux (2008) dan

John and George (2010) telah disinggung beberapa varian aljabar yang serupa dengan aljabar

max-plus, seperti aljabar min-plus (dengan operasi minimum dan penjumlahan) dan aljabar

max-min (dengan operasi maximum dan minimum). Diberikan pula dalam referensi di atas,

beberapa gambaran singkat mengenai ilustrasi penerapannya yang terkait dengan masalah-

masalah dalam teori graf, seperti masalah lintasan terpendek dan masalah kapasitas maksimum

suatu lintasan dalam jaringan. Seperti halnya dalam aljabar max-plus, dengan pendekatan

aljabar yang serupa diharapkan masalah-masalah yang terkait dapat dimodelkan dan

perhitungan-perhitungan masalah-masalah yang terkait dapat dilakukan secara lebih analitis.

Makalah ini akan membahas analisis penentuan kapasitas maksimum suatu lintasan

dalam jaringan dengan menggunakan pendekatan aljabar max-min. Untuk memudahkan dalam

mailto:[email protected]



perhitungan numeriknya, akan disusun pula suatu program komputer dengan menggunakan

MATLAB. Dari hasil pembahasan makalah ini diharapkan sebagai langkah awal untuk ke

masalah berikutnya yang lebih kompleks, seperti menentukan aliran (flow) maksimum dalam

suatu jaringan.

ALJABAR MAX-MIN DAN MATRIKS

Dalam bagian ini dibahas konsep-konsep dasar aljabar max-min dan matriks atas aljabar

max-min. Pembahasan lebih lengkap dapat dilihat pada Rudhito (20011), Rudhito (2013a) dan

Rudhito (2013b).

Diberikan

R :=

R {} dengan

R adalah himpunan semua bilangan real

nonnegatip dan : = +. Pada

R didefinisikan operasi berikut:

a,b

R , ab := max(a, b) danab : = min(a, b) .

Dapat ditunjukkan bahwa (

R , , ) merupakan semiring idempoten komutatif dengan elemen

netral 0 = 0 dan elemen satuan = +. Kemudian (

R , , ) disebut dengan aljabar max-min,

yang selanjutnya cukup dituliskan dengan

R . Dalam hal urutan pengoperasian (jika tanda

kurang tidak dituliskan), operasimempunyai prioritas yang lebih tinggi dari pada operasi.

Karena (

R , ) merupakan semigrup komutatif idempoten, maka relasi“ ” yang

didefinisikan pada

R denganx yxy = y merupakan urutan parsial pada

R .Lebih lanjut

relasi ini merupakan urutan total pada

R . Karena

R merupakan semiring idempoten, maka

operasi dan konsisten terhadap urutan , yaitu a, b, c

R , jika a b , maka ac

bc, dan ac b c. Aljabar max-min

R tidak memuat pembagi nol yaitu x, y

R

berlaku: jika x y = min(x, y) = 0,maka x =0atau y = 0.

Operasi dan pada

R dapat diperluas untuk operasi-operasi matriks dalam nm

R

: = {A = (Aij)Aij

R , untuk i = 1, 2, ..., m dan j = 1, 2, ..., n}. Untuk

R , dan A, B

nm

R didefinisikan A, dengan (A)ij = Aij dan AB, dengan (AB)ij = AijBij untuk i

= 1, 2, ..., m dan j = 1, 2, ..., n. Untuk A pm

R , B np

R didefinisikan AB, dengan

(AB)ij = kjik

p

k

BA 1

. Matriks A, B nm

R dikatakan samajikaAij = Bijuntuk setiapidanj.

Didefinisikan matriks matriks O nm

R , di mana (O)ij := 0, untuk setiap i dan j, dan matriks

E nn

R , di mana (E )ij :=

ji

ji

jika,0

jika,. Dapat ditunjukkan bahwa ( nn

R , , )

merupakan semiring idempoten dengan elemen netral matriks O dan elemen satuan matriks E.

m

m

m m

m m



Sedangkan nm

R merupakan semimodul atas

R . Pangkat k darimatriks A nn

R dalam

aljabar max-plus didefinisikan dengan: 0A = En dan

kA

= A1k

A untuk k = 1, 2, ... .

Contoh 1.

i)

3

21

71

50=

731

5201

=

7 3,max1 ,max

5 2,max0 1,max

=

7

51

.

ii)

23

801

42

06

1

=

420312263

48001128601

=

2 0, ,1max2 3, ,max

4 0, 1,max2 0, ,1max

=

23

42.

ANALISIS KAPASITAS MAKSIMUM LINTASAN

Konsep-konsep dalam aljabar max-plus sangat terkait dengan konsep-konsep dalam

teori graf. Untuk itu dalam bagian ini akan diawali dengan meninjau kembali beberapa konsep

dalam teori graf.

Suatu graf berarah G didefinisikan sebagai suatu pasangan G = (V, A) dengan V adalah

suatu himpunan berhingga tak kosong yang anggotanya disebut titik dan A adalah suatu

himpunan pasangan terurut titik-titik. Anggota A disebut busur. Suatu lintasan dalam graf

berarah G adalah suatu barisan berhingga busur (i1, i2), (i2, i3), ... , (il1, il) dengan (ik, ik+1) A

untuk suatu l N(= himpunan semua bilangan asli) dank = 1, 2, ..., l 1. Suatu lintasan disebut

sirkuit jika titik awal dan titik akhirnya sama. Diberikan graf berarah G = (V, A) dengan V =

{1, 2, ... ,p}. Graf berarah G dikatakan berbobot jika setiap busur (j, i) A dikawankan

dengan suatu bilangan real Aij. Bilangan real Aij disebut bobot busur (j, i), dilambangkan dengan

w(j, i). Graf preseden dari matriks A nn

R adalahgraf berarah berbobot G(A) = (V, A)

denganV = {1, 2, ... ,n} dan A = {(j, i) | w(i, j) = Aij 0}. Sebaliknya untuk setiap graf

berarah berbobot G = (V, A) selalu dapat didefinisikan suatu matriks A nn

maxR dengan Aij =

. )( jika

)( jika )(

A,,

A,,,

ij

ijijw

, yang disebut matriks bobot graf G.

Dalam masalah lintasan kapasitas maksimum, untuk suatu graf berarah berbobot

dengan matriks bobotnya A nn

R , Aijadalah bilangan real nonnegatif dan merupakan

kapasitasbusur (j, i), yaitu aliran maksimum yang dapat melalui busur (j, i). Diberikan A

nn

R . Jika k = 0, 1, 2, 3, ..., maka unsur ke-st dari matriks k

A adalah



st

kA )( =

niii k 121 ,,1max

(min(1kisA , , ... ,

12 iiA ,,

tiA ,1

))

= niii k 121 ,,1

max

(min( tiA ,1,

12 iiA ,, ... ,

1kisA , )) , untuk setiap s, t.

Karena min( tiA ,1,

12 iiA ,, ... ,

1kisA , ) adalah kapasitas lintasan dengan panjang k dengan t

sebagai titik awal dan s sebagai titik akhirnya dalam G(A), maka st

kA )( adalah kapasitas

maksimumsemua lintasan dalam G(A) dengan panjang k, dengan t sebagai titik awal dan s

sebagai titik akhirnya. Jika tidak ada lintasan dengan panjang k dari t ke s, maka kapasitas bobot

maksimum didefinisikan sama dengan 0.

Teorema 1. DiberikanA nn

R . pn , p

Am EA ...

1nA .

Bukti: Karena banyak titik dalam G(A) adalah n maka semua lintasan dengan panjang pn

tersusun setidaknya oleh sebuah sirkuit, sehingga kapasitas maksimum sirkuit tersebut lebih

kecil atau sama dengan kapasitas maksimum lintasan yang panjangnya kurang dari n. Akibatnya

pA

m A ... 1n

A , p n. Karena untuk setiap A nn

R berlaku A m EA, maka

pA

m E A ... 1n

A , pn. ∎

Berdasarkan Teorema 1 di atas didefinisikan operasi bintang (*) berikut.

Definisi 1. DiberikanA nn

R . DidefinisikanA* : = E A ...

nA

1nA ... .

Mengingat Teorema 1 diperoleh bahwa A* : = E A ...

1nA . Berdasarkan

penjelasan tentang kapasitas dan pangkat matriks di atas dapat disimpukan bahwa unsur (A*)ij

merupakan kapasitas maksimum lintasan dengan ujung titik j dan pangkal titik i . Dari uraian di

atas diperoleh Teorema 2 berikut, dengan bukti seperti pada uraian di atas.

Teorema 2. Jika A nn

R merupakan matriks bobot suatu graf berarah berbobot, makaunsur

(A*)ij merupakan kapasitas maksimum lintasan dengan ujung titikj dan pangkal titik i .

Contoh 2. Diberikan suatu jaringan berkapasitas seperti pada Gambar 1 di bawah ini.

4

5

3 6

7 1

7

2

2

5

6

5 7

6

2

4

3

Gambar 1. Suatu Jaringan Berkapasitas

5



Matriks bobot graf berarah berbobot pada jaringan berkapasitas di atas adalah matriks A di

bawah ini. Dengan menggunakan program yang disusun dengan menggunakan MATLAB seperti

pada list program terlampir, dengan input matriks A tersebut, diperoleh output program matriks

A* sebagai berikut.

A =

0652000

0073000

0005200

0000540

0000006

0000007

0000000

, A*=

665545

075545

005545

000545

000006

000007

000000

.

Dari matriks A* nampak bahwa kapasitas maksimum lintasan dengan titik awal titik ke-j

nampak dalam unsur-unsur kolom ke-j matriks A*. Tabel berikut memberikan daftar lintasan

dan kapasitas maksimumnya dengan titik awal titik 1. Untuk titik awal yang lain dapat

dilakukan dengan cara yang sama.

Tabel 1. Kapasitas Maksimum Lintasan dari Titik 1

Titik Akhir Lintasan Kapasitas Maksimum

2 1 2 7

3 1 3 6

4 1 3 4 5

5 1 3 4 5 5

6 1 3 4 5 6 5

7 1 3 4 5 6 7 5

PENUTUP

Dari hasil pembahasan dapat disimpulkan bahwajaringan yang memuat kapasitas, dapat

dimodelkan sebagai graf berarah terbobot, di mana bobotnya adalah kapasitas dalam jaringan.

Graf berarah terbobot di atas dapat dinyatakan dalam matriks atas aljabar max-min. Dengan

menggunakan operasi perpangkatan max-min untuk matriks di atas, dapat ditentukan kapasitas

maksimum lintasan antara dua buah titik dalam jaringan. Dapat pula disusun suatu program

MATLAB untuk menghitung perpangkatan matriks atas aljabar max-min yang dapat digunakan

untuk membantu menentukan kapasitas maksimum lintasan dalam jaringan tersebut.

Hasil pembahasan makalah ini diharapkan dapat dikembangkan untuk masalah yang

lebih kompleks, seperti menentukan aliran (flow) maksimum dalam suatu jaringan, dengan

terlebih dahulu menentukan lintasan dengan kapasitas maksimal secara otomatis.

DAFTAR PUSTAKA



Baccelli, F., Cohen, G., Olsder, G.J. and Quadrat, J.P. 2001. Synchronization and Linearity.

New York: John Wiley & Sons.

John S. Baras and George Theodorakopoulos. 2010. Path Problems in Networks. Synthesis

Lectures on Communication Networks. Morgan & Claypool Publishers.

Gondran, M and Minoux, M. 2008. Graph, Dioids and Semirings. New York: Springer.

Krivulin, N.K., Algebraic Modelling and Performance Evaluation of Acyclic Fork-Join

Queueing Networks. Advances in Stochastic Simulation Methods, Statistics for Industry

and Technology. Birkhauser, Boston, 63-81, 2000

Rudhito MA, 2003, Sistem Linear Max-Plus Waktu-Invariant, Tesis: Program Pascasarjana

Universitas Gadjah Mada, Yogyakarta

Rudhito MA, Wahyuni S, Suparwanto A, dan Susilo F. 2010.Analisis Lintasan Kritis Jaringan

Proyek dengan Pendekatan Aljabar Max-Plus. Jurnal Matematika Vol 12 No. 3. pp. 128-

133

Rudhito, Andy. 2011. Aljabar Max-Plus Bilangan Kabur dan Penerapannya pada Masalah

Penjadwalan dan Jaringan Antrian Kabur. Disertasi: Program Pascasarjana Universitas

Gadjah Mada. Yogyakarta.

Rudhito, Andy. 2013a. Aljabar Max-Min Interval. Prosiding Seminar Nasional Penelitian,

Pendidikan , dan Penerapan MIPA, tanggal 18 Mei 2013, FMIPA Universitas Negeri

Yogyakarta: M-97 – M-102.

Rudhito, Andy. 2013b. Matriks atas Aljabar Max-Min Interval. Prosiding Seminar Nasional

Sains dan Pendidikan Sains dan Matematika, tanggal 15 Juni 2013, FSM Universitas

Kristen Satya Wacana, Salatiga: 115-121.

LAMPIRAN: List Program MATLAB untuk Menghitung A*

% Program Matlab untuk menghitung A* max-min % input: A = matriks persegi atas max-min % output: Matriks A* A1 = input(' Masukkan matriks Anxn = '); [m, n]= size(A1); % Menghitung A pangkat dan A+ G1=A1; A1_plus = A1; for s=1:n-1 s+1; for i = 1: n for j = 1: n F1(i, j) = -Inf; for p = 1: n F1(i, j) = max( F1(i, j) , min(A1(i, p), G1(p, j))); end; end; end; G1 = F1; A1_plus = max(A1_plus, F1);



end; disp(' Matriks A_plus '), disp(A1_plus); % Menghitung matriks E dan A* for i = 1 : n for j = 1 : n if i == j E(i,j) = Inf; end; end; end; A1_star= max(E, A1_plus) % Menampilkan hasil A* disp(' Matriks A_star '), disp(A1_star);



BILANGAN CLIQUE GRAF NON COMMUTING

DARI GRUP DIHEDRAL

Muflihatun Nafisah1)

, Abdussakir2)

1) Jurusan Matematika UIN Maulana Malik Ibrahim Malang

Jl. Sumbersari Gg. 3A 230 Malang, e-mail: [email protected]


Perum OMA View EF 01, Malang, e-mail: [email protected]

Abstrak. Misalkan 𝐺 grup tidak komutatif. Graf non commuting Γ𝐺 dari 𝐺

didefinisikan sebagai graf yang himpunan titiknya bukan anggota center dari 𝐺 dan dua

titik saling terhubung jika dan hanya jika tidak komutatif. Dari graf sederhana yang

didapatkan dari graf non commuting Γ𝐺 , orde terbesar subgraf komplit dari graf Γ𝐺

dinamakan dengan bilangan clique𝜔 Γ𝐺 . Pada makalah ini akan ditentukan bilangan

cliquegraf non commuting pada grup dihedral 𝐷2𝑛 . Metode yang digunakan adalah

kajian pustaka. Sedangkan analisis yang dilakukan adalah dengan melihat pola

berdasarkan beberapa contoh yang selanjutnya dinyatakan sebagai teorema.

Berdasarkan penelitian ini, diperoleh hasil bahwa bilangan cliquegraf non commuting

dari grup dihedral 𝐷2𝑛 untuk 𝑛 bilangan asli ganjil, dengan 𝑛 ≥ 3 adalah

𝜔 Γ𝐷2𝑛 = 𝑛 + 1

dan bilangan cliquegraf non commuting pada grup dihedral 𝐷2𝑛 untuk 𝑛 bilangan asli

genap, dengan 𝑛 ≥ 3 adalah

𝜔 Γ𝐷2𝑛 =

𝑛 + 2

2

Kata kunci:bilangan clique, graf non commuting, grup dihedral.

PENDAHULUAN

Graf𝐺 adalah pasangan himpunan (𝑉, 𝐸) dengan 𝑉 adalah himpunan tidak kosong dan

berhingga dari objek-objek yang disebut sebagai titik dan 𝐸 adalah himpunan (mungkin kosong)

pasangan tak berurutan dari titik-titik berbeda di 𝑉 yang disebut sebagai sisi. Banyak unsur di 𝑉

disebut orde dari 𝐺 dan dilambangkan dengan 𝑝(𝐺), dan banyak unsur di 𝐸 disebur ukuran dari

𝐺 dan dilambangkan dengan 𝑞(𝐺) (Chartrand dan Lesniak, 1986). Jika dimisalkan Γ merupakan

graf sederhana, ukuran maksimum dari subgraf komplit dari graf Γdisebut bilangan clique dari Γ

yang dinotasikan dengan ω(Γ)(Abdollahi, dkk.. 2010).

Beberapa penelitian mengenai bilangan clique suatu graf yang sudah dilakukan antara lain,

Vahidi dan Talebi (2010) membahas tentang bilangan bebas, bilangan clique dan bilangan cover

minimum dari graf commuting dari grup. Abdollahi, dkk. (2010) meneliti tentang bilangan

clique dari graf non commuting dari suatu grup. Chelvam, dkk. (2011) meneliti tentang bilangan

kromatik dan bilangan clique pada graf komuting yang diperoleh dari grup dihedral.

Perkembangan teori graf juga membahas tentang graf yang dibangun dari grup. Seperti

halnya yang dilakukan oleh Vahidi dan Talebi (2010) yang meneliti mengenai graf commuting

dari grup, perkembangan selanjutnya yaitu misalkan 𝐺 grup tidak komutatif dan 𝑍(𝐺) adalah

center dari 𝐺. Graf non commuting Γ𝐺adalah draf yang memiliki himpunan titik 𝐺\𝑍(𝐺) dan



dua titik 𝑥, 𝑦 ∈ 𝐺\𝑍(𝐺) akan terhubung langsung di Γ𝐺 jika 𝑥𝑦 ≠ 𝑦𝑥 ∈ 𝐺 (Abdollahi, dkk.

(2006) dan Abdollahi, dkk. (2010)).

Berdasarkan uraian di atas, meskipun Abdollahi, dkk. (2010), telah meneliti tentang

bilangan clique dari graf non commuting dari suatu grup, tetapi pada penelitian itu tidak

dilakukan pada grup dihedral, sehingga pada penelitian ini akan dikaji bilangan clique graf non

commuting dari grup dihedral.

TINJAUAN PUSTAKA

2.1 Graf

Graf𝐺 adalah pasangan himpunan (𝑉, 𝐸) dengan 𝑉 adalah himpunan tidak kosong dan

berhingga dari objek-objek yang disebut sebagai titik dan 𝐸 adalah himpunan (mungkin kosong)

pasangan tak berurutan dari titik-titik berbeda di 𝑉 yang disebut sebagai sisi. Banyak unsur di 𝑉

disebur orde dari 𝐺 dan dilambangkan dengan 𝑝(𝐺), dan banyak unsur di 𝐸 disebur ukuran dari

𝐺 dan dilambangkan dengan 𝑞(𝐺) (Chartrand dan Lesniak, 1986).

2.2 Grup Dihedral

Grup adalah suatu struktur aljabar yang dinyatakan sebagai (𝐺,∗) dengan 𝐺 himpunan tidak

kosong dan ∗ operasi biner di 𝐺 yang memenuhi sifat-sifat berikut:

a. 𝑎 ∗ 𝑏 ∗ 𝑐 = 𝑎 ∗ (𝑏 ∗ 𝑐), untuk semua 𝑎, 𝑏, 𝑐 ∈ 𝐺 (sifat assosiatif).

b. Ada suatu elemen 𝑒 di 𝐺 sehingga 𝑎 ∗ 𝑒 = 𝑒 ∗ 𝑎 = 𝑎, untuk semua 𝑎 ∈ 𝐺 (𝑒 disebut

dentitas di 𝐺).

c. Untuk setiap 𝑎 ∈ 𝐺 ada suatu elemen 𝑎−1 ∈ 𝐺sehingga 𝑎 ∗ 𝑎−1 = 𝑎−1 ∗ 𝑎 = 𝑒 (𝑎−1

disebut invers dari 𝑎).

Sebagai tambahan, grup(𝐺,∗) disebut abelian (grup komutatif) jika 𝑎 ∗ 𝑏 = 𝑏 ∗ 𝑎 untuk

semua 𝑎, 𝑏 ∈ 𝐺 (Raisinghania dan Aggarwal, 1980:31).

Grup dihedral adalah grup dari himpunan simetri-simetri dari segi- 𝑛 beraturan, dinotasikan

𝐷2𝑛 untuk setiap 𝑛 bilangan bulat positif dan 𝑛 ≥ 3. Dalam buku lain ada yang menuliskan grup

dihedral dengan 𝐷𝑛 . Operasi biner di 𝐷2𝑛 adalah operasi fungsi komposisi yang bersifat

assosiatif. Berikut ini beberapa notasi dan beberapa kaidah yang dapat menyederhanakan

perhitungan selanjutnya yaitu (Dummit dan Foote, 1991):

a. 1, 𝑟, 𝑟2 , … , 𝑟𝑛−1

b. |𝑠| = 2

c. 𝑠 ≠ 𝑟𝑖 untuk semua 𝑖

d. 𝑠𝑟𝑖 ≠ 𝑠𝑟𝑗 untuk semua 0 ≤ 𝑖, 𝑗 ≤ 𝑛 − 1 dengan 𝑖 ≠ 𝑗. Jadi

𝐷2𝑛 = {1, 𝑟, 𝑟2 , … , 𝑟𝑛−1 , 𝑠, 𝑠𝑟, 𝑠𝑟2 , … , 𝑠𝑟𝑛−1} yaitu setiap elemen dapat dituliskan

secara tunggal dalam bentuk 𝑠𝑘𝑟𝑖 untuk 𝑘 = 0 atau 𝑘 = 1 dan 0 ≤ 𝑖 ≤ 𝑛 − 1.

e. 𝑠𝑟 = 𝑟−1𝑠



f. 𝑠𝑟𝑖 = 𝑟−𝑖𝑠, untuk semua 0 ≤ 𝑖 ≤ 𝑛.

2.3 Graf Non Commuting

Misalkan 𝐺 grup tidak komutatif dan 𝑍(𝐺) adalah center dari 𝐺. Graf non commuting

Γ𝐺adalah draf yang memiliki himpunan titik 𝐺\𝑍(𝐺) dan dua titik 𝑥, 𝑦 ∈ 𝐺\𝑍(𝐺) akan

terhubung langsung di Γ𝐺 jika 𝑥𝑦 ≠ 𝑦𝑥 ∈ 𝐺 (Abdollahi, dkk.. 2006). Atau graf non commuting

dari 𝐺 didefinisikan sebagai graf yang himpunan titiknya adalah bukan anggota center dari 𝐺

dan dua titik saling terhubung jika dan hanya jika tidak komutatif (Abdollahi, dkk.. 2010).

Misalkan pada 𝐷6 diperoleh 𝑍 𝐷6 = {1}, sehingga graf noncommuting dari grup 𝐷6

memiliki himpunan titik-titik Γ𝐷6= {𝑟, 𝑟2 , 𝑠, 𝑠𝑟, 𝑠𝑟2}. Kemudian hasil di atas digambarkan ke

dalam bentuk graf non commuting sebagai berikut:

Gambar 2.1. Graf Non Commuting pada Grup 𝑫𝟔

2.4 Bilangan Clique

Misal Γ merupakan graf sederhana, ukuran maksimum dari subgraf komplit dari graf

Γdisebut bilangan clique dari Γ yang dinotasikan dengan ω(Γ)(Abdollahi, dkk.. 2010).

METODE PENELITIAN

Penelitian ini merupakan penelitian pustaka (library research), yang dimulai dengan

mengkaji topik berdasarkan bahan-bahan pustaka berupa buku, artikel, atau jurnal. Penelitian

selanjutnya dilakukan dengan mengkaji contoh-contoh khusus (induktif) untuk menemukan

suatu generalisasi yang dibuktikan secara deduktif. Adapun langkah-langkah penelitian ini

secara garis besar sebagai berikut:

a. Menentukan graf non commuting dari grup dihedral 𝐷2𝑛 dengan 𝑛 = 3,4,5,6,7,8.

b. Menetukan cliquegraf non commuting dari grup dihedral 𝐷2𝑛dengan 𝑛 = 3,4,5,6,7,8.

c. Menelaah pola bilangan cliquegraf non commuting pada grup dihedral 𝐷2𝑛dengan 𝑛 =

3,4,5,6,7,8 yang sudah ditemukan.

d. Membuat konjektur berdasarkan pola yang sudah ditemukan.

e. Merumuskan konjektur sebagai suatu teorema dan melengkapi dengan bukti secara

deduktif.



HASIL

Elemen-elemen dari grup dihedral 𝐷6 adalah {1, 𝑟, 𝑟2 , 𝑠, 𝑠𝑟, 𝑠𝑟2}. Adapun hasil operasi

komposisi pada setiap elemen grup dihedral 𝐷6 dalam bentuk tabel Cayley sebagai berikut:

Tabel 1. Tabel Cayley 𝑫𝟔

Dengan daerah warna kuning merupakan unsur-unsur yang tidak komutatif pada grup

dihedral 𝐷6. Sehingga unsur-unsur yang tidak komutatif pada grup dihedral 𝐷6 sebagai berikut:

𝑟 ∘ 𝑠 ≠ 𝑠 ∘ 𝑟 𝑟 2 ∘ 𝑠 ≠ 𝑠 ∘ 𝑟 2 𝑠 ∘ 𝑠𝑟 ≠ 𝑠𝑟 ∘ 𝑠

𝑟 ∘ 𝑠𝑟 ≠ 𝑠𝑟 ∘ 𝑟 𝑟 2 ∘ 𝑠𝑟 ≠ 𝑠𝑟 ∘ 𝑟 2 𝑠 ∘ 𝑠𝑟2 ≠ 𝑠𝑟2 ∘ 𝑠

𝑟 ∘ 𝑠𝑟2 ≠ 𝑠𝑟2 ∘ 𝑟 𝑟 2 ∘ 𝑠𝑟2 ≠ 𝑠𝑟2 ∘ 𝑟 2 𝑠𝑟 ∘ 𝑠𝑟2 ≠ 𝑠𝑟2 ∘ 𝑠𝑟

Dengan menghilangkan center dari grup 𝐷6 yaitu 𝑍 𝐷6 = {1}, sehingga graf

noncommuting dari grup 𝐷6 memiliki himpunan titik-titik Γ𝐷6= {𝑟, 𝑟2 , 𝑠, 𝑠𝑟, 𝑠𝑟2}. Kemudian

hasil di atas digambarkan ke dalam bentuk graf non commuting sebagai berikut:

Gambar 4.2. Graf Non Commuting pada Grup 𝑫𝟔

Dengan melihat gambar di atas, maka dapat ditentukan cliqueΓ𝐷6 sebagai berikut:



Gambar 4.3. clique 𝚪𝑫𝟔

Sehingga didapatkan cliqueΓ𝐷6 merupakan graf 𝐾4 dengan himpunan titik-titiknya adalah

{𝑟, 𝑠, 𝑠𝑟, 𝑠𝑟2}. Dengan demikian bilangan clique graf non commuting grup dihedral

𝐷6 𝜔 Γ𝐷6 = 4.

Berdasarkan pengamatan dengan langkah-langkah yang sama seperti di atas, ditemukan

pola untuk bilangan cliqueΓ𝐷2𝑛 dengan 𝑛 = 4,5,6,7,8 sebagai berikut:

Tabel 2. Pola Bilangan Clique Graf Non Commuting Grup D2n

No. Graf Non Commuting Bilangan Clique Graf NonCommuting

1. Graf noncommuting grup 𝐷6 𝜔(Γ𝐷6) = 4





6 Graf noncommuting grup𝐷16 𝜔(Γ𝐷16) = 5

Dengan demikian,diperoleh pola yang dapat dinyatakan sebagai teorema sebagai berikut:

Teorema 1:

Misalkan 𝐷2𝑛 adalah grup dihedral dengan order 2𝑛 dengan 𝑛 bilangan asli dan 𝑛 ≥ 3.

Bilangan clique Γ𝐷2𝑛 dengan 𝑛 ganjil diperoleh:

𝜔 Γ𝐷2𝑛 = 𝑛 + 1

sedangkan untuk 𝑛 genap diperoleh:

𝜔 Γ𝐷2𝑛 =

𝑛 + 2

2

Bukti:

Diketahui grup dihedral 𝐷2𝑛 = {1, 𝑟, 𝑟2 , ⋯ , 𝑟𝑛−1 , 𝑠, 𝑠𝑟, 𝑠𝑟2 , ⋯ , 𝑠𝑟𝑛−1}. Diperoleh bahwa

𝑍(𝐷2𝑛) = 1 untuk 𝑛 ganjil. Dengan demikian himpunan titik dari graf non commutingΓ𝐷2𝑛=



𝑟, 𝑟2 , ⋯ , 𝑟𝑛−1 , 𝑠, 𝑠𝑟, 𝑠𝑟2 , ⋯ , 𝑠𝑟𝑛−1 . Karena 𝑟𝑖 ∘ 𝑟𝑗 = 𝑟𝑗 ∘ 𝑟𝑖 , untuk semua 1 ≤ 𝑖, 𝑗 ≤ 𝑛 − 1

dengan 𝑖 ≠ 𝑗 maka titik-titik ini tidak terhubung langsung di Γ𝐷2𝑛. Dan karena 𝑛 ganjil, maka

𝑠 ∘ 𝑟𝑖 ≠ 𝑟𝑖 ∘ 𝑠, 𝑖 = 1,2, … , 𝑛 − 1, yang berarti bahwa 𝑠 dan 𝑟𝑖 saling terhubung langsung di

Γ𝐷2𝑛. Demikian juga karena 𝑛 ganjil, maka 𝑠𝑟𝑖 ∘ 𝑠𝑟𝑗 ≠ 𝑠𝑟𝑗 ∘ 𝑠𝑟𝑖 , 𝑗 = 0,1,2, ⋯ , 𝑛 − 1 dan

𝑖 = 0,1,2, ⋯ , 𝑛 − 1, dengan 𝑖 ≠ 𝑗 yang berarti 𝑠𝑟𝑖 dan 𝑠𝑟𝑗 saling terhubung langsung di Γ𝐷2𝑛.

Sehingga terdapat salah satu himpunan titik-titik yang membentuk clique graf non commuting

grup 𝐷2𝑛 dengan 𝑛 ganjil sebagai berikut:

Γ𝐷2∙𝑛: {𝑟, 𝑠, 𝑠𝑟, 𝑠𝑟2 , 𝑠𝑟3 , ⋯ , 𝑠𝑟𝑛−1}

11𝑛 − 1

Sehingga bilangan clique graf non commuting grup 𝐷2𝑛 dengan 𝑛 ganjil adalah 1 + 1 +

𝑛 − 1 = 𝑛 + 1.

Sementara itu, untuk 𝑛 genap diperoleh bahwa 𝑍(𝐷2𝑛) = 1, 𝑟𝑛

2 . Dengan demikian himpunan

titik dari graf non commutingΓ𝐷2𝑛= 𝑟, 𝑟2 , ⋯ , 𝑟

𝑛

2−1 , 𝑟

𝑛

2+1 , ⋯ , 𝑟𝑛−1 , 𝑠, 𝑠𝑟, 𝑠𝑟2, ⋯ , 𝑠𝑟𝑛−1 .

Karena 𝑟𝑖 ∘ 𝑟𝑗 = 𝑟𝑗 ∘ 𝑟𝑖 , untuk semua 1 ≤ 𝑖, 𝑗 ≤ 𝑛 − 1, dengan 𝑖 ≠ 𝑗 maka titik-titik ini tidak

terhubung langsung di Γ𝐷2𝑛. Dan karena 𝑛 genap, maka 𝑠 ∘ 𝑟𝑖 ≠ 𝑟𝑖 ∘ 𝑠, 𝑖 = 1,2, … , 𝑛 − 1 dan

𝑖 ≠𝑛

2 , yang berarti bahwa 𝑠 dan 𝑟𝑖 saling terhubung langsung di Γ𝐷2𝑛

. Demikian juga karena 𝑛

genap, maka 𝑠𝑟𝑖 ∘ 𝑠𝑟𝑗 ≠ 𝑠𝑟𝑗 ∘ 𝑠𝑟𝑖 , 𝑗 = 0,1,2, … , 𝑛 − 1 dan 𝑖 = 0,1,2, … , 𝑛 − 1, dengan 𝑖 ≠ 𝑗

dan jumlah dari 𝑖 dan 𝑗 bukan merupakan kelipatan dari 𝑛

2, yang berarti 𝑠𝑟𝑖 dan 𝑠𝑟𝑗 saling

terhubung langsung di Γ𝐷2𝑛. Maka salah satu himpunan titik-titik yang membentuk clique graf

non commuting grup 𝐷2𝑛 dengan 𝑛 genap sebagai berikut:

Γ𝐷2∙𝑛: {𝑟, 𝑠, 𝑠𝑟, 𝑠𝑟2 , ⋯ , 𝑠𝑟(

𝑛−2

2)}

11𝑛 − 2

2

Sehingga bilangan clique graf non commuting grup 𝐷2𝑛 dengan 𝑛 ganjil adalah 1 + 1 + 𝑛−2

2=

𝑛+2

2.

KESIMPULAN

Berdasarkan hasil penelitian kali ini, diperoleh bahwa bilangan cliquegraf non commuting

dari grup dihedral 𝐷2𝑛 untuk 𝑛 bilangan asli ganjil, dengan 𝑛 ≥ 3 adalah

𝜔 Γ𝐷2𝑛 = 𝑛 + 1



dan bilangan cliquegraf non commuting dari grup dihedral 𝐷2𝑛 untuk 𝑛 bilangan asli genap,

dengan 𝑛 ≥ 3 adalah

𝜔 Γ𝐷2𝑛 =

𝑛 + 2

2

SARAN

Penelitian selanjutnya disarankan untuk meneliti spektrum adjacency, spektrum laplace,

spektrum singles laplace, atau spektrum detour dari graf non commuting dari grup dihedral 𝐷2𝑛 .

DAFTAR PUSTAKA

Abdollahi, A., Akbari, S., dan Maimani, H.R.. (2006). Non-commuting Graph of a Group.

Journal of Algebra, Vol 298 Hal: 468-492.

Abdollahi, A., Azad, A., Hassanabadi, A.M., dan Zarrin, M.. (2010). On the Clique Numbers of

Non-commuting Graphs of Certain Groups. Algebra Colloquium, Vol 17 Hal: 611-620.

Chartrand, G. dan Lesniak, L.. (1986). Graph and Digraph 2nd

Edition. California: Wadsworth

Inc.

Chelvam, Tamizh, T., Selvakumar, K., dan Raja, S.. (2011). Commuting Graph on Dihegral

Group. The Journal of Mathematics and Computer Science. Vol 2, No 2, Hal: 402-406.

Dummit, D.S. Dan Foote, R.M.. (1991). Abstract Algebra. New Jersey: Prentice Hall, Inc.

Raisinghania, M.D., dan Aggarwal, R.S.. 1980. Modern Algebra. New Delhi: S. Chand &

Com[any LTD.

Vahidi, J., dan Taalebi, A.A.. (2010). The Commuting Graphs on Group 𝐷2𝑛 and 𝑄𝑛 . Journal

Mathematics and Computer Science. Vol 1, No 2, Hal: 123-127.



DIGRAF EKSENTRIK DARI GRAF MATAHARI

Sri Kuntari, Tri Atmojo Kusmayadi dan Nugroho Arif Sudibyo

Jurusan Matematika FMIPA UNS

Jl. Ir. Sutami 36A Surakarta

e-mail: [email protected],[email protected], [email protected]

Abstrak

Suatu graf G mempunyai himpunan vertex berhingga V(G) dan himpunan edge

E(G). Eksentrisitas vertexu dalam graf Gmerupakan jarak maksimum dari vertexu ke

sebarang vertex yang lain di G, dinotasikan e(u). Sedangkan jarak dari vertex u ke

vertexv di Gdidefinisikan sebagai adalah panjang dari pathterpendek dari vertex u ke

v dan dinotasikan d(u,v). Vertex vdisebut vertex eksentrik dari u jika d(u,v) e(u).

Digraf eksentrik dari graf G adalah suatu graf G’ dengan V(G’)= V(G), dan terdapat

suatu arc (edge berarah) yang menghubungkan vertexu ke vdenganvvertex eksentrik

dari u. Dalam makalah ini diselidiki digraf eksentrik pada graf matahari.

Kata kunci: eksentrisitas, digraf eksentrik, graf matahari.

PENDAHULUAN

Pengertian dan notasi yang berkaitan dalam makalah ini diambil dari Chartrand dan

Lesniak [2] serta Harris et al. [4]. Diketahui graf G dengan himpunan vertex V(G) dan

himpunan edge E(G). Jarak dua vertexu dan v dalam G, dinotasikan dengan d(u,v), merupakan

panjang path terpendek dari vertexu ke vertex v. Jika tidak ada path yang menghubungkan

kedua vertex, d(u,v) =.

Eksentrisitas dari vertex u dalam graf G didefinisikan sebagai jarak maksimum dari vertex u

ke sembarang vertex lainnya dalam G. Eksentrisitas vertex u dinotasikan sebagai e(u) dengan

e(u) = max{d(u,v)vV(G)}. Sedangkan vertex v merupakan vertex eksentrik dari vertex u jika

d(u,v)e(u). Digraf eksentik dari graf G yaitu ED(G) adalah graf yang mempunyai himpunan

vertex yang sama dengan G, V(ED(G)) = V(G) dan terdapat arc (edge berarah) yang

menghubungkan setiap vertex dalam G ke vertex eksentriknya. Suatu arc dalam digraf D

dikatakan arc simetri jika arc tersebut menghubungkan vertex u dan v, demikian juga

sebaliknya. Boland dan Miller [1] memberi saran untuk menemukan digraf eksentrik dari kelas-

kelas graf. Berkaitan dengan ini, diantaranya telah ditemukan digraf eksentrik dari graf (n,t)-

kite oleh Kusmayadi dkk. [7]. Huilgol et al. [5] mengkarakterisasi graf G dengan ED(G) = G.

Kemudian pada tahun 2012 Huilgol [6] mengadakan survey terhadap hasi-hasil yang berkaitan

dengan digraph eksentrik dan menyatakan masalah-masalah yang belum ada solusinya. Sebagai

contoh masalah tersebut adalah sifat-sifat dari suatu graf yang berkaitan dengan digraph

eksentrik.







HASIL DAN PEMBAHASAN

Graf matahariSnn3 adalah graf yang dibentuk dari cycleCn dengan cara menambahkan

sebuah vertex berderajat satu (pendant) pada setiap vertex di Cn. Definisi ini diambil dariWallis

[8]. Gambar 1 merupakan contoh dari graf matahari S3dan S4.

Gambar 1. Graf matahari S3(kiri) dan S4 (kanan)

Langkah-langkah dalam menentukan digraf eksentrik dari suatu graf ada tiga.

Pertama adalah menentukan jarak dari vertex u ke vertex v dalam graf G yang merupakan

panjang lintasan terpendek dari vertex u ke vertex v. Tetapi d(u,v) = , jika tidak ada lintasan

yang menghubungkan kedua vertex tersebut. Dalam menentukan jarak dari vertex u ke

sembarang vertex v dalam graf G digunakan algoritma Breadth First Search (BFS) Moore yang

mengacu dari Chartrand and Oellermann [3] yaitu

1. diambil salah satu vertex dalam graf G, misal u dan dilabeli 0 yang menyatakan jarak u

ke dirinya sendiri, sedangkan semua vertex u dilabeli ,

2. semua vertex berlabel yang adjacent dengan u dilabeli 1,

3. semua vertex berlabel yang adjacent dengan vertex berlabel 1 dilabeli 2, dan

seterusnya sampai vertex yang dimaksud misal v berjarak hingga. Label setiap vertex

menyatakan jarak dari vertex u.

Kedua menentukan vertex eksentrik dari vertex u, dinotasikan dengan e(u), yaitu vertex dalam

graf G yang memiliki jarak maksimum dari u. Vertex vadalah suatu vertex eksentrik dari u jika

d(u,v)e(u). Ketiga, menghubungkan vertex u dangan vertex eksentriknya dengan suatu arcd

diperoleh digraph eksentrik dari graf yang diberikan.

Diberikan graf matahariSnn3 dengan himpunan vertexV(Gn)={u1, u2, …, un, v1, v2, …,

vn} dan himpunan edgeE(Sn)={ui ui+1(mod n), uivi,i=1, 2, …, n}. Lema berikut merupakan dasar

untuk mengetahui besarnya eksentrisitas dari setiap vertex dalam graf matahari.

1u

2u

3u

1v

2v3v

2u1u

3u4u

1v 2v

3v4v



Lema 1.Diberikan graf matahariSnn3maka eksentrisitas dari vertex vi adalah 𝑛

2 +2 sedangkan

eksentrisitas vertex uiadalah 𝑛

2 +1, i=1, 2, …, n.

Bukti.

Menggunakan algoritma Breadth First Search (BFS) Moore, dapat dicari jarak setiap vertex ke

setiap vertex dalam graf matahari Sn. Untuk graf matahari, masalah mencari jarak antar vertex

dapat dibedakan menjadi dua yaitu untuk n ganjil dan n genap.

1. Untuk n ganjil

Tabel berikutmenyajikan jarak setiap vertex ke setiap vertex dalam Sn untuk n ganjil.

Tabel 1.Jarak dari Setiap Vertex ke Setiap Vertex dalam Graf Matahari nM untuk n Ganjil

Vertex 1u

2

1nu

2

1nu nu

1v

2

1nv

2

1nv nv

1u 0 2

1n

2

1n 1 1

2

1n

2

1n 2

2

1nu 2

1n 0 1

2

1n

2

1n 1 2

2

1n

2

1nu 2

1n 1 0

2

1n

2

1n 2 1

2

1n

nu 1 2

1n

2

1n 0 3

2

1n

2

1n 1

1v 1 2

1n

2

1n 3 0

2

3n 2

3n

2

1nv 2

1n 1 2

2

1n

2

3n 0 2 2

3n

2

1nv 2

1n 1 1

2

1n

2

3n 2 0 2

1n

nv 2 2

1n

2

1n 1 1

2

3n 2

1n 0

2. Untuk n genap

Tabel berikut menyajikan jarak setiap vertex ke setiap vertex dalam Sn untuk n genap



Tabel 2.Jarak dari Setiap Vertex ke Setiap Vertex dalam Graf Matahari nM untuk n Genap

Vertex 1u

2

nu nu

1v

2

nv nv

1u 0 2

n 1 1

2

2n 2

2

nu 2

n 0

2

2n

2

2n 1

2

n

nu 1 2

2n 0 2

2

n 1

1v 1 2

2n 2 0

2

4n 3

2

nv 2

4n 1

2

n

2

4n 0

2

2n

nv

2 2

n 1 3

2

2n 0

Dari Tabel 1 dan Tabel 2 diperoleh eksentrisitas dari vertex vi adalah 𝑛

2 +2 sedangkan

eksentrisitas vertex uiadalah 𝑛

2 +1, i=1, 2, …, n.∎

Untuk graf S3 dalam Gambar 1 dan menggunakan tabel jarak pada Tabel 1 diperoleh

eksentrisitas dari vertex𝑢𝑖 sebesar tiga dan eksentrisitas dari vertex𝑣𝑖 sebesar dua dengan i =

1, 2, 3.

Sedangkan untuk graf S4 dalam Gambar 1 dan menggunakan tabel jarak pada Tabel 2 diperoleh

eksentrisitas dari vertex𝑢𝑖 sebesar 4 dan eksentrisitas dari vertex𝑣𝑖 sebesar 3 dengan i = 1, 2, 3,

4.

Lema berikut ini digunakan untuk menentukan vertex eksentrik dari setiap vertex dalam graf

matahari.

Lema 2. Diberikan graf matahariSn, n3 maka vertex eksentrik dari 𝑢𝑖 , 𝑣𝑖 adalah 𝑣𝑛+𝑖

2𝑚𝑜𝑑 𝑛

dan

𝑣𝑛+𝑖+2

2𝑚𝑜𝑑 𝑛

untuk n ganjil, sedangkan untuk n genap, vertex eksentrik dari 𝑢𝑖 , 𝑣𝑖 adalah

𝑣𝑛+2𝑖

2𝑚𝑜𝑑 𝑛

.



Bukti.

Vertex eksentrik dari suatu vertex dalam graf matahari Sn, dapat dicari menggunakan Lema 1.

∎

Menggunakan Lema 2, vertex eksentrik dari setiap vertex dalam graf matahari S3 dan 𝑆4 dapat

dilihat pada Tabel 3.

Tabel 3. Vertex dan vertex eksentrik dari graf matahari S3 dan S4

Graf S3 Graf S4

vertex Vertex eksentrik vertex Vertex eksentrik

𝑢1 , 𝑣1 𝑣2 dan 𝑣3 𝑢1 , 𝑣1 𝑣3

𝑢2 , 𝑣2 𝑣3 dan 𝑣1 𝑢2 , 𝑣2 𝑣4

𝑢3 , 𝑣3 𝑣1dan 𝑣2 𝑢3 , 𝑣3 𝑣1

𝑢4 , 𝑣4 𝑣2

Selanjutnya diberikan teorema tentang digraf eksentrik dari graf matahari.

Teorema 3. Diberikan graf matahariSn, n3 maka maka digraf eksentrik dari graf matahari

adalah

1. digraf G yang mempunyai V(G)=V(Sn) dan mempunyai arc𝑣𝑖𝑣𝑗 dan 𝑢𝑖𝑣𝑗 dengan 𝑗 =

𝑛+𝑖

2 𝑚𝑜𝑑 𝑛, 𝑗 = 𝑛+𝑖+2

2 𝑚𝑜𝑑 𝑛 dan 𝑖 = 1, 𝑛 untuk n ganjil,

2. digraf G yang mempunyai V(G)=V(Sn) dan mempunyai arc𝑣𝑖𝑣𝑗 dan 𝑢𝑖𝑣𝑗 dengan 𝑗 =

𝑛+2𝑖

2 𝑚𝑜𝑑 𝑛 dan 𝑖 = 1, 𝑛 untuk n genap.

Bukti.

Dari Tabel 1, setiap vertex dihubungkan dengan vertex eksentriknya terbentuk arc. Arc yang

simetrik adalah 𝑣𝑖𝑣𝑗 dengan 𝑗 = 𝑛 +𝑖

2 𝑚𝑜𝑑 𝑛, 𝑗 = 𝑛+𝑖+2

2 𝑚𝑜𝑑 𝑛 dan 𝑖 = 1, 𝑛 .Arc yang tidak

simetrik adalah 𝑢𝑖𝑣𝑗 dengan 𝑗 = 𝑛 +𝑖

2 𝑚𝑜𝑑 𝑛, 𝑗 = 𝑛+𝑖+2

2 𝑚𝑜𝑑 𝑛 dan 𝑖 = 1, 𝑛 .

Selanjutnya diperoleh digraf eksentrik dari graf matahari Sn, n 3 untuk n ganjil adalah suatu

digraf G yang mempunyai V(G)=V(Sn) dan mempunyai arc𝑣𝑖𝑣𝑗 dan 𝑢𝑖𝑣𝑗 dengan 𝑗 =

𝑛+𝑖

2 𝑚𝑜𝑑 𝑛, 𝑗 = 𝑛 +𝑖+2


Sedangkan dari Tabel 2 dapat dibentuk arc dengan menghubungkan setiap vertex dengan vertex

eksentriknya. Arc yang simetrik adalah 𝑣𝑖𝑣𝑗 dengan 𝑗 = 𝑛+2𝑖

2 𝑚𝑜𝑑 𝑛 dan 𝑖 = 1, 𝑛 .Arc yang

tidak simetrik adalah 𝑢𝑖𝑣𝑗 dengan 𝑗 = 𝑛+2𝑖




Selanjutnya diperoleh digraf eksentrik dari graf matahari Sn, n 3 untuk n genapadalah suatu

digraf G yang mempunyai V(G)=V(Sn) dan mempunyai arc𝑣𝑖𝑣𝑗 dan 𝑢𝑖𝑣𝑗 dengan 𝑗 =

𝑛+2𝑖

2 𝑚𝑜𝑑 𝑛 dan 𝑖 = 1, 𝑛 . ∎

Digraf eksentrik dari graf matahari S3 dan S4 disajikan dalam Gambar 2.

Gambar 2. Digraf eksentrik dari graf matahari S3 (kiri) dan S4 (kanan)

PENUTUP

Penelitian ini dapat dikembangkan sesuai saran dari Boland dan Miller [1] untuk kelas-

kelas graf yang lain yang belum ditemukan digraph eksentriknya. Demikian juga penelitian

dapat dikembangkan mengikuti masalah yang diungkapkan oleh Huilgol [6].

UCAPAN TERIMA KASIH

Tim Peneliti mengucapkan terima kasih kepada Universitas Sebelas Maret atas

didanainya penelitian ini dalam hibah riset fundamental tahun anggaran 2013.

DAFTAR PUSTAKA

[1] Boland, J. and M. Miller. 2001. The Eccentric Digraph of a Digraph, Proceeding of

AWOCA’01, Lembang-Bandung, Indonesia.

[2] Chartrand, G. And L. Lesniak, 1996, Graphs and Digraphs 3rd

ed., Chapman and

Hall/RCR, New York.

[3] Chartrand, G. and O. R. Oellermann. 1993. Applied and AlGorithmic Graph Theory,

International Series in Pure and Applied Mathematics, McGraw-Hill Inc, California.

[4] Harris, J. M., J. L. Hirst and M. J. Mossinghoff, 2000, Combinatorics and Graph Theory

2nd

ed.. Springer, New York.

1u 2u

3u4u

1v 2v

3v

1u

2u 3u1v

2v3v

4v



[5] Huilgol, M. I., S.A. Ulla S. and Sunilchandra A.R., 2011, On Eccentric Digraphs of Graphs,

Applied Mathematics 2, pp:705-710.

[6] Huilgol, M.I., 2012, A Survey on Eccentric graph of a (Di)Graph, J. Math. Comput. Sci 2 no

4, pp:1144-1160.

[7] Kusmayadi, T. A., Nugroho, A. S. and S. Kuntari, 2013, Eccentric Digraph of (n, t)-

kiteGraph, Far East Journal of Mathematical Sciences, volume 74 nomer 2, pp 369-378.

[8] Wallis W.D., 2001, Magic Graph, Birkhauser, Boston, Basel, Berlin.



PEMBERIAN NOMOR VERTEX PADA JARINGAN GRAF MATAHARI𝑺𝒏

Dimas Ari Kurniawan Perdana dan Tri Atmojo Kusmayadi

Jurusan Matematika FMIPA UNS

Jl. Ir. Sutami 36A Surakarta

e-mail: [email protected],[email protected]

Abstrak

Minimum spanning tree padasuatu jaringan komunikasi menggunakan edge untuk

menghubungkan setiap vertexdalam lintasan yang bertujuan untuk menghasilkan jaringan

komunikasi yang efektif dan efisien. Jaringan komunikasi yang efektif dan efisien adalah

jaringan dengan rute terpendek yang dapat memberikan hasil yang maksimal dengan biaya

minimal. Misal G = (V;E) adalah jaringan komunikasi. Jarak adalah panjang lintasan

terpendek dari vertex u ke v dalam G, dinotasikan dengan d(u, v). Eksentrisitas dari vertex u

adalah jarak terjauh dari vertex u ke vertex lain, dinotasikan dengan e(u). Dalam paper ini,

akan diberikan penomoran vertexberdasarkan besar eksentrisitas tiap vertex pada jaringan

komunikasi yang berbentuk graf matahari 𝑆𝑛 .

Kata Kunci: minimum spanning tree, graf matahari, eksentrisitas, jarak

PENDAHULUAN

Di dalam suatu bentuk jaringan komunikasi, baik jaringan dengan kabel (wired) ataupun

tanpa kabel (wireless) yang menggunakan edge untuk menghubungkan setiap vertex pada suatu

jaringan bertujuan untuk menghasilkan jaringan komunikasi yang efektif dan efisien. Menurut

Kamalesh dan Srivatsa [3], tujuan dari bentuk jaringan komunikasi adalah untuk memberikan

hasil yang maksimal dengan biaya yang minimal. Dalam hal ini, posisi dan urutan dari tiap

vertex, banyaknya edge dan panjang tiap edge dalam menyalurkan data di dalam jaringan sangat

berpengaruh dalam mencapai hasil yang maksimal. Salah satu cara untuk membentuk jaringan

komunikasi yang efektif dan efisien adalah dengan memberi nomor pada setiap vertexdengan

menentukan bentuk minumum spanning treedarijaringan komunikasi tersebut. Dalam pemberian

nomor tiap vertex terlebih dahulu ditentukan jarak dan eksentrisitas setiap vertex pada lintasan

graf. Ketika vertex diberi nomor secara sistematik, spanning tree yang dihasilkan akan

mengalami perubahan bentuk yang relatif lebih kecil (minimum) dan akan menghasilkan

jaringan spanning tree yang efisien. Minimum spanning treeyang efisien adalah spanning tree

dari suatu jaringan yang melalui semua vertex yang ada dengan jarak paling minimum.

Dalam perkembangannya telah banyak penelitianterkait efisiensi jaringan melalui bentuk

minimum spanning tree. Kamalesh dan Srivatsa [3] dalam penelitiannya memberikan solusi

bentuk efisien jaringan komputer yang berbentuk graf tripartit menggunakan bentuk minimum

spanning tree dengan memberikan nomor pada tiap vertex berdasarkan jarak dan eksentrisitas

tiap vertex. Selanjutnya dalam paper ini, penulis tertarik untuk membahas penyelesaian masalah

pemberian nomor vertex dariminimum spanning tree pada jaringan graf matahari𝑆𝑛 .





Berikut ini diberikan beberapa definisi mengenai spanning tree, minimum spanning tree,

dan graf matahari 𝑆𝑛yang diambil dari Boland dan Miller [1], Chartrand dan Oellermann [3],

dan Wallis [4]

Definisi 1.MisalkanGadalah graf terhubung.Spanning tree dari G adalah spanning subgrafT

dari G jika T adalah sebuah tree dan T memuat semua vertex dari G.

Definisi 2. Misalkan G adalah graf terhubung berbobot. Spanning tree dimana total bobot

edgenya paling kecil disebut minimum spanning tree dari G.

Definisi 3. Graf matahari dinotasikan dengan 𝑆𝑛 , untuk n ≥ 3, adalah graf yang dibentuk dari

cycle dengan cara menambahkan sebuah vertex berderajat 1 (pendant) pada setiap vertex di

cycle Cn.

Dalam mencari bentuk spanning tree digunakan metode Breadth-First Search (BFS). BFS

adalah metode untuk mencari spanning tree dengan cara memproses semua vertex pada level

yang diberikan sebelum menuju ke level berikutnya.

Definisi 4. Jarak dari vertex u ke v di G adalah panjang lintasan terpendek dari vertex u ke v,

dinotasikan dengan d(u, v).

Jika tidak ada lintasan yang menghubungkan vertex u dan v, maka d(u,v) = 1. Selanjutnya

untuk menyelesaikan masalah lintasan terpendek dalam graf G, digunakan algoritma BFS

(Breadth First Search) Moore. Chartrand dan Oelermann [2] menyebutkan langkah-langkah

dalam algoritma BFS Moore adalah sebagai berikut.

1. Diambil salah satu vertex, misal u, dan dilabeli 0 yang menyatakan jarak dari u ke

dirinya sendiri, sedangkan semua vertex selain u dilabeli 1.

2. Semua vertex berlabel 1 yang adjacent dengan u dilabeli 1.

3. Semua vertex berlabel 1 yang adjacent dengan vertex berlabel 1 dilabeli 2 dan demikian

seterusnya sampai vertex yang dimaksud, misal v, sudah berlabel hingga ∞.

Definisi 5. Eksentrisitas (eccentricity) vertex u, dinotasikan e(u), dalam graf G adalah jarak

terjauh (lintasan terpendek maksimum) dari vertex u ke setiap vertex di G, dapat dituliskan

𝑒 𝑢 = max{𝑑(𝑢, 𝑣) 𝑣 ∈ 𝑉(𝐺)}.

Algoritma Kamalesh-Srivatsa

Dalam menentukan jaringan yang efektif dan efisien dilakukan pemberian nomor vertex

secara matematis. Menurut Kamalesh dan Srivatsa [4], langkah-langkah dalam pemberian

nomor vertex adalah sebagai berikut,

1) mengkonstruksikan suatu jaringan graf,

2) memberikan label pada tiap vertex menggunakan simbol {𝑣1 , 𝑣2 , … , 𝑣𝑛},

3) menentukan minimum spanning tree dari suatu jaringan graf,

4) menentukan eksentrisitas e(v) dari minimum spanning tree T,



5) memberikan nomor vertex pada jaringan berdasarkan nilai eksentrisitas secara

terurut. Vertex yang memiliki nilai eksentrisitas terkecil maka diberikan nomor

terkecil. Jika terdapat vertex yang memiliki nilai eksentrisitas sama maka dilihat

jarak vertex tersebut terhadap vertex awal. Vertex dengan d(vi, vawal) lebih kecil

diberikan nomor vertex lebih kecil. Jika terdapat vertex dengan d(vi, vawal) sama maka

vertex dengan indek lebih kecil diberikan penomoran vertex lebih kecil.

Pemberian nomor vertex pada jaringan graf matahari𝑆𝑛 dilakukan dalam beberapa tahap.

Sebelumnya diasumsikan bahwa bobot setiap edge adalah sama.

Langkah pertama mengkonstruksikan jaringan graf matahari𝑆𝑛 seperti Gambar 1.

Selanjutnya jaringan graf matahari𝑆𝑛 diberikan label vertex dengan himpunan vertexnya V =

{𝑣1 , 𝑣2 , … , 𝑣𝑛 , 𝑢1 , 𝑢2 , … , 𝑢𝑛}

Gambar 2. Graf Matahari 𝑆𝑛 dengan label

Minimum Spanning Tree Graf Matahari 𝑺𝒏′

Jaringan graf matahari yang sudah diberi label kemudian ditentukan bentuk minimum

spanning treenya. Minimum spanning tree dapat ditentukan dengan menggunakan algoritma

BFS sehingga diperoleh minimum spanning tree graf matahari𝑆𝑛′ seperti pada Gambar 3.

v1

v2 u1v3

u2u3

v4 u4 u5 v5

un-2 un-1

vn-2 unvn-1

vn

vn

Gambar 1. Graf Matahari 𝑆𝑛 tanpa label



v1

u1

u2 u3

v2

v3

u4 u5

v4

v5

un-1un

vn-1vn

v1

u1

u2 u3

v2 v3

u4 u5

v4

un-2 un-1 v5

vn-2 unvn-1

vn

(a) (b)

Gambar 3. Minimum spanning tree 𝑆𝑛′ dari jaringan graf matahari 𝑆𝑛 (a) untuk n ganjil n

≥ 3 dan (b) untuk n genap n ≥ 4.

Dari minimum spanning tree yang sudah diperoleh, selanjutnya dicari nilai

eksentrisitasnya. Nilai eksetrisitas setiap vertex diperoleh dengan mencari lintasan terpendek

maksimum. Dalam mencari lintasan terpendek dari vertex ke setiap vertex dalam 𝑆𝑛′ digunakan

algoritma BFS Moore.

Eksentrisitas dari Graf Matahari 𝑺𝒏′

Misal 𝑆𝑛′ adalah bentuk miminum spanning tree dari graf matahari yang diperoleh dengan

algoritma BFS, dimana label vertex diberikan seperti pada Gambar 2, maka eksentrisitas dari

minimum spanning tree graf matahari 𝑆𝑛′ untuk n ganjil n> 3 adalah

𝑒 𝑢𝑖 =

𝑛 + 𝑖

2, 𝑖 = 1, 3, … , 𝑛,

𝑛 + 1 + 𝑖

2, 𝑖 = 2, 4, … , 𝑛 − 1, (1)

dan

𝑒 𝑣𝑗 =

𝑛 + 2 + 𝑗

2, 𝑗 = 1, 3, … , 𝑛,

𝑛 + 3 + 𝑗

2, 𝑗 = 2, 4, … , 𝑛 − 1. (2)

Sedangkan eksentrisitas dari minimum spanning tree graf matahari 𝑆𝑛′ untuk n genap, n> 4

adalah,



𝑒 𝑢𝑖 =

𝑛

2+ 1 , 𝑖 = 1

𝑛 + 2 + 𝑖

2, 𝑖 = 2, 4, … , 𝑛 − 2

𝑖 − 1 + 𝑛

2. 𝑖 = 3, 5, … , 𝑛 − 1

𝑛 . 𝑖 = 𝑛 , (3)

dan

𝑒 𝑣𝑗 =

𝑛 + 4

2, 𝑗 = 1

𝑛 + 4 + 𝑗

2, 𝑗 = 2, 4, … , 𝑛 − 2

𝑛 + 1 + 𝑗

2. 𝑗 = 3, 5, … , 𝑛 − 1

𝑛 + 1 . 𝑗 = 𝑛 . (4)

Penomoran vertex pada Graf Matahari 𝑺𝒏′

Setelah ditentukan eksentrisitas dari bentuk minimum spanning tree graf matahari 𝑆𝑛′ ,

selanjutnya diberikan nomor vertex pada jaringan berdasarkan nilai eksentrisitas secara terurut.

Vertex yang memiliki nilai eksentrisitas terkecil maka diberikan nomor terkecil.

Misal 𝑆𝑛′ merupakan bentuk minimum spanning tree dari graf matahari 𝑆𝑛 , maka urutan

penomoran vertex dari minimum spanning tree graf matahari𝑆𝑛′ dapat dinotasikan dengan λ(𝑆𝑛

′ )

Teorema 1. Misal 𝑆𝑛′ merupakan bentuk minimum spanning tree dari graf matahari dengan n

ganjil n ≥ 3, maka λ(𝑆𝑛′ ) nya adalah

𝜆 𝑢𝑖 = 1 , 𝑖 = 1 2𝑖 − 1 , 𝑖 = 2, 4, … , 𝑛 − 12𝑖 − 2 , 𝑖 = 3, 5, … , 𝑛,

dan

𝜆 𝑣𝑗 =

2 , 𝑗 = 1 2𝑗 + 1 , 𝑗 = 2, 4, … , 𝑛 − 12𝑗 , 𝑗 = 3, 5, … , 𝑛.

Bukti.

Penomoran vertex dari setiap vertex pada minimum spanning tree graf matahari 𝑆𝑛′ untuk n

ganjil n> 3, diperoleh dari urutan nilai eksentrisitas setiap vertex. Jika nilai eksentrisitas vertex

kecil maka diberi nomor urut kecil, semakin besar nilai eksentrisitas vertex maka semakin besar

pula nomor urut vertex tersebut. Berdasarkan eksentrisitasdari minimum spanning tree graf

matahari𝑆𝑛′ dengan n ganjil n> 3 pada persamaan (1),maka didapatkan urutan penomoran vertex

untuk setiap vertex 𝑢𝑖adalah 1 untuk i = 1, dan 2i -1 untuk setiap 𝑖 = 2, 4, … , 𝑛 − 1, serta 2i – 2

untuk setiap 𝑖 = 3, 5, … , 𝑛, sehingga urutan penomoran vertex dari eksentrisitas vertex ui, λ(ui)



adalah 1 untuk i = 1, dan 2i -1 untuk setiap 𝑖 = 2, 4, … , 𝑛 − 1, serta 2i – 2 untuk setiap 𝑖 =

3, 5, … , 𝑛. Demikian juga urutan penomoran vertex untuk vertex vj,berdasarkan eksentrisitas

pada persamaan (2), didapatkan urutan penomoran vertex untuk setiap vertex vjadalah 2 untuk j

= 1, dan 2j + 1 untuk setiap 𝑗 = 2, 4, … , 𝑛 − 1, serta 2j untuk setiap 𝑖 = 3, 5, … , 𝑛, sehingga

urutan penomoran vertex dari eksentrisitas vertex vj, λ(vj) adalah 2 untuk j = 1, dan 2j + 1 untuk

setiap 𝑗 = 2, 4, … , 𝑛 − 1, serta 2j untuk setiap 𝑖 = 3, 5, … , 𝑛.

Teorema 2. Misal 𝑆𝑛′ merupakan bentuk minimum spanning tree graf matahari dengan n genap

n ≥ 4, maka λ(𝑆𝑛′ ) nya adalah

𝜆 𝑢𝑖 =

1 , 𝑖 = 1 2𝑖 , 𝑖 = 2, 4, … , 𝑛 − 22𝑖 − 4 , 𝑖 = 3, 5, … , 𝑛 − 12𝑖 − 2 , 𝑖 = 𝑛 ,

dan

𝜆 𝑣𝑗 =

3 , 𝑗 = 1 2𝑗 + 3 , 𝑗 = 2, 4, … , 𝑛 − 22𝑗 − 1 , 𝑗 = 3, 5, … , 𝑛 − 12𝑗 , 𝑗 = 𝑛.

Bukti.

Penomoran vertex dari setiap vertex pada minimum spanning tree graf matahari 𝑆𝑛′

untuk n genap n ≥ 4, diperoleh dari urutan nilai eksentrisitas setiap vertex. Jika nilai

eksentrisitas vertex kecil maka diberi nomor urut kecil, semakin besar nilai eksentrisitas vertex

maka semakin besar pula nomor urut vertex tersebut. Berdasarkan eksentrisitasdari minimum

spanning tree graf matahari𝑆𝑛′ dengan n genap n> 4 pada persamaan (3), maka didapatkan

urutan penomoran vertex untuk setiap vertex 𝑢𝑖adalah 1 untuk i = 1, dan 2i untuk setiap

𝑖 = 2, 4, … , 𝑛 − 2, lalu 2i – 4 untuk setiap 𝑖 = 3, 5, … , 𝑛 − 1, serta 2i -2 untuk 𝑖 = 𝑛, sehingga

urutan penomoran vertex dari eksentrisitas vertex ui, λ(ui) adalah 1 untuk i = 1, dan 2i untuk

setiap 𝑖 = 2, 4, … , 𝑛 − 2, lalu 2i – 4 untuk setiap 𝑖 = 3, 5, … , 𝑛 − 1, serta 2i – 2 untuk 𝑖 = 𝑛.

Demikian juga urutan penomoran vertex untuk vertex vjberdasarkan eksentrisitas pada

persamaan (4), didapatkan urutan penomoran vertex untuk setiap vertex vjadalah 3 untuk j = 1,

dan 2j + 3untuk setiap 𝑗 = 2, 4, … , 𝑛 − 2, lalu 2j – 1 untuk setiap 𝑗 = 3, 5, … , 𝑛 − 1, serta 2j

untuk 𝑗 = 𝑛, sehingga urutan penomoran vertex dari eksentrisitas vertex vj, λ(vj) adalah 3 untuk j

= 1, dan 2j + 3untuk setiap 𝑗 = 2, 4, … , 𝑛 − 2, lalu 2j – 1 untuk setiap 𝑗 = 3, 5, … , 𝑛 − 1, serta 2j

untuk 𝑗 = 𝑛.

SIMPULAN DAN SARAN

Berdasarkan pembahasan dapat diambil kesimpulan bahwa pemberian

nomorvertexdapat diterapkan untuk berbagai jaringan yang mempunyai karakteristik sama



sepertikelas - kelas dalamjaringan graf matahari 𝑆𝑛 dengan himpunan vertex V =

{𝑣1 , 𝑣2 , … , 𝑣𝑛 , 𝑢1 , 𝑢2 , … , 𝑢𝑛},diperoleh pemberian nomor vertex untuk jaringan graf matahari 𝑆𝑛′

dengan n ganjil, n ≥ 3seperti pada Teorema 1. dan untuk jaringan graf matahari 𝑆𝑛′ dengan n

genap, n ≥ 4seperti pada Teorema 2.

DAFTAR PUSTAKA

[1] Boland, J. and Miller, M. (2001). The eccentric digraph of a digraph. Proceeding of

AWOCA'01. Lembang-Bandung. Indonesia.

[2] Chartrand, G. and O. R. Oellermann. (1993). Applied and Algorithmic Graph Theory.

McGraw Hill Inc., New York.

[3] Kamalesh, V. N. and S. K, Srivatsa. (2009). Node numbering in topological structure of

interconnection network. Indian Journal of Science and Technology. 2 no. 11, 37 – 40.

[4] Wallis, W. D. (2001). Magic Graphs. Birkhauser. Boston.



SPEKTRUM ADJACENCY GRAF NON COMMUTING

DARI GRUP DIHEDRAL (𝑫𝟐𝒏)

Rivatul Ridho Elvierayani

1), Abdussakir, M.Si

2)


Jl. Sumbersari Gg.3B 158 Malang, e-mail: [email protected]


Perum OMA View EF 01 Malang,e-mail: [email protected]

Abstrak

Graf dapat dinyatakan dalam bentuk matriks, misalnya matriks adjacency. Ketika graf

sudah dinyatakan dalam bentuk matriks, maka dapat didekati secara aljabar linier untuk

mencari nilai eigen dan vektor eigennya. Matriks baru yang memuat semua nilai eigen pada

baris pertama dan banyaknya vektor eigen yang besesuaian pada baris kedua disebut

spektrum. Spektrum yang diperoleh dari matriks A(G) disebut spektrum adjacency. Kajian

mengenai grup dalam aljabar abstrak membawa pada konsep baru dalam teori graf yang

disebut graf noncommuting. Pada artikel ini ditentukan spektrum adjacency graf non

commuting pada grup dihedral (𝐷2𝑛) dengan n adalahbilangan asli diperoleh spektrum

adjacency nya:

𝑠𝑝𝑒𝑐 𝛤𝐷2𝑛 =

𝑛 − 1

2+ 𝑛 − 1 𝑛 +

𝑛 − 1

2

2

0 −1𝑛 − 1

2− 𝑛 − 1 𝑛 +

𝑛 − 1

2

2

1 𝑛 − 2 𝑛 − 1 1

∀𝑛

≥ 3 danganjil

spec (𝛤𝐷2𝑛)=

𝑛−2

2+

5𝑛2−12𝑛+4

40 −2

𝑛−2

2−

5𝑛2−12𝑛+4

4

1𝑛−2

2

3𝑛−6

21

∀𝑛 ≥ 6 dangenap

Kata Kunci:Graf, matriks adjacency, nilai eigen, vektor eigen, spektrum, grup dihedral,

graf non commuting.

PENDAHULUAN

Graf Gadalah pasangan (V(G),E(G)) dengan V(G) adalah himpunan tidak kosong dan

berhingga dari objek-objek yang disebut titik, dan E(G) adalah himpunan (mungkin kosong)

pasangan tak berurutan dari titik-titik berbeda di V(G) yang disebut sisi. Banyaknya unsur di

V(G) disebut order dari G dan dilambangkan dengan n(G), dan banyaknya unsur di E(G)

disebut ukuran dari G dan dilambangkan dengan m(G) (Chartrand & Lesniak, 1996).

Sisi e=(u, v) dikatakan menghubungkan titik u dan v. Jika e=(u, v) adalah sisi di graf G,

maka u dan v disebut terhubung langsung(adjacent),v dan e serta u dan e disebut

terkaitlangsung (incident), dan titik u dan v disebut ujung dari e. Dua sisi berbeda e1 dan e2

disebut terhubung langsung (adjacent), jika terkait langsung pada satu titik yang sama, sisi e =

(u, v) akan ditulis e = uv (Chartrand & Lesniak, 1996).

Misalkan G graf dengan order 𝑛 𝑛 ≥ 1 dan ukuran q serta himpunan titik V(G) = {v1, v2,

…, vn}.Matriks keterhubungan titik (matriks Adjacency) dari graf G, dinotasikan dengan A(G),

adalah matriks (n n). Dengan kata lain,matriks adjacencydapat ditulisA(G) = [aij], 1 i, jp,

dengan 𝑎𝑖𝑗 = 1 jika 𝑣𝑖𝑣𝑗 ∈ 𝐸(𝐺) dan 𝑣𝑖𝑣𝑗𝐸(𝐺). Matriks adjacency suatu graf G adalah

matriks simetri dengan unsur 0 dan 1 dan memuat nilai 0 pada diagonal utamanya (Chartrand &

Lesniak, 1996).




Jika A adalah matriks 𝑛 × 𝑛, maka vektor tak nol 𝑥 di dalam 𝑅𝑛 dinamakan vektor eigen

(eigenvector) dari A jika 𝐴𝑥 adalah kelipatan skalar dari 𝑥, yakni 𝐴𝑥 = 𝜆𝑥 untuk skalar 𝜆.

Skalar 𝜆 dinamakan nilai eigen (eigenvalue) dari 𝐴 dan 𝑥 dikatakan vektor eigen yang

bersesuaian dengan 𝜆.

Karena matriks adjacency adalah matriks simetri dan real sehingga eigenvalue i, i = 1, 2, 3, …,

p nonnegatif real numbers dan dapat ditulisan dengan 12 p= 0. If 𝜇𝑖1≥ 𝜇𝑖2

≥ ⋯ ≥ 𝜇𝑖𝑔

adalah nilai eigen yang berbeda, maka spektrum dari A(G) dapat dituliskan dengan:

spec (G) = 𝜇𝑖1

𝜇𝑖2…

𝑚1 𝑚2 …

𝜇𝑖𝑔

𝑚𝑔

𝑚𝑔 melambangkan multiplisitas nilai eigen 𝜇𝑖𝑗 (Yin, 2008). m1 + m2 + … + mg = p (Ayyaswamy

& Balachandran, 2010). Multiplisitas dari 𝜇𝑖𝑗 sebagai akar persamaan karakteristik dari

det(𝜇𝑖𝑗 𝐼 − 𝐴(𝐺)) = 0 sama dengan dimensi ruang vektor eigen yang bersesuaian dengan 𝜇𝑖𝑗

(Bigg, 1974).

Sebuah sistem aljabar (G,*) dengan G bukan himpunan ∅ dan satu operasi biner *

dikatakan sebagai grup jika memenuhi postulat:

(i) Operasi * memenuhi hukum assosiatif

𝑎 ∗ 𝑏 ∗ 𝑐 = 𝑎 ∗ 𝑏 ∗ 𝑐 … . . ∀𝑎, 𝑏, 𝑐 ∈ 𝐺

(ii) Setiap elemen G mempunyai identitas terhadap operasi *, misal e adalah identitas di G

𝑒 ∗ 𝑎 = 𝑎 ∗ 𝑒 = 𝑎 … . ∀𝑎 ∈ 𝐺

(iii) Setiap elemen G mempunyai invers terhadap operasi *

𝑎−1 ∗ 𝑎 = 𝑎 ∗ 𝑎−1 = 𝑒, dimana e adalah ∈ 𝐺(Raisinghania dan Aggarwal, 1980).

Jika (𝐺,∗) adalah grup dan 𝑎 ∗ 𝑏 = 𝑏 ∗ 𝑎, ∀𝑎, 𝑏 ∈ 𝐺, maka G dikatakan grup abelian atau

grup komutatif. Grup dihedral adalah grup dari himpunan simetri-simetri dari segi-n beraturan,

dinotasikan 𝐷2𝑛 , untuk setiap n bilangan bulat positif dan𝑛 ≥ 3. Dalam buku lain ada yang

menuliskan grup dihedral dengan 𝐷𝑛 (Dummit dan Foote, 1991). Karena grup dihedral akan

digunakan secara ektensif, maka perlu beberapa notasi dan beberapa hitungan yang dapat

menyederhanakan perhitungan selanjutnya dan membantu mengamati 𝐷2𝑛 sebagai grup

abstrak, yaitu:

(1) 1, r, 2r , . . .,

1nr

(2) 2s ,

(3) irs untuk semua i.

(4) untuk semua 0 ≤ 𝑖, 𝑗 ≤ 𝑛 − 1 dengan 𝑖 ≠ 𝑗. Jadi

𝐷2𝑛 = 1, 𝑟, 𝑟2 , … , 𝑟𝑛−1 , 𝑠, 𝑠𝑟2 , … , 𝑠𝑟𝑛−1 yaitu setiap elemen dapat dituliskan secara

tunggal dalam bentuk ik rs untuk k = 0 atau 1 dan 0 ≤ 𝑖 ≤ 𝑛 − 1.



(5) srsr 1 .

(6) srsr ii , untuk semua 0 ≤ 𝑖 ≤ 𝑛 (Dummit dan Foote, 1991).

Misal G grup, center dari grup G, dituliskan 𝑍(𝐺) sebagai berikut:

𝑍(𝐺) = 𝑧 ∈ 𝐺 ∶ 𝑧𝑥 = 𝑥𝑧, ∀𝑥 ∈ 𝐺

Jadi jika 𝑍(𝐺) adalah himpunan anggota G yang komutatif terhadap semua anggota 𝑍(𝐺).

Misal G grup non abelian dan Z(G) adalah center dari G. Graf non commutingΓGadalah

sebuah graf yang mana titik-titiknya merupakan himpunan dari 𝐺\𝑍(𝐺) dan dua titik x dan y

terhubung langsung jika dan hanya jika 𝑥𝑦 ≠ 𝑦𝑥(Abdollahi, A, 2006, Journal of Algebra).

𝛤𝐺adalah sebuah graf yang titiknya adalah bukan elemen-elemen center dari sebuah graf G,

titik-titik dari 𝛤𝐺 adalah G\Z(G) merupakan pengambilan atau penghapusan elemen center pada

graf G.

Beberapa penelitian lain mengenai spektrum suatu graf sudah pernah dilakukan. Shuhua

Yin (2006) meneliti spektrum Adjacency dan spektrum Laplace pada graf Gl yang diperoleh

dari graf komplit Kl dengan menambahkan pohon isomorfik berakar untuk masing-masing titik

di Kl. Abdussakir, dkk (2009) meneliti spektrum adjacency pada graf komplit (Kn), graf star

(Sn), graf bipartisi komplit (Km,n), dan graf lintasan (Pn). Ayyaswamy & Balachandran (2010)

meneliti spektrum Detour pada beberapa graf yang meliputi graf K(n, n), graf Korona G dan K1,

graf perkalian Kartesius G dengan K2, graf perkalian leksikografik G dengan K2, dan perluasan

dobel kover dari graf beraturan. Abdussakir, dkk (2012) meneliti spektrum Adjacency, Laplace,

Singless Laplace, dan Detour graf multipartisi komplit K(𝛼1 , 𝛼2 , 𝛼3 , … , 𝛼𝑛). Dalam penelitian

mengenai graf commuting dan non commuting, Abdollahi, dkk (2006&2010) meneliti tentang

grup finite pada dua grup yang non abelian dan bilangan clique. Abdussakir, dkk (2013)

meneliti tentang spektrum graf commuting suatu grup. Berdasarkan uraian di atas, belum ada

yang mengkaji mengenai spektrum graf non commuting sehingga peneliti bermaksud untuk

mengkaji spektrum adjacency graf non commuting dari grup dihedral (𝐷2𝑛).

METODE PENELITIAN

Dalam penulisan artikel ini, peneliti menggunakan metode studi literatur, adapun

langkah-langkah peneliti diantaranya:

1. Membuat tabel cayle dengan operasi komposisi (∘) pada grup dihedral 𝐷2𝑛 .

2. Menentukan himpunan titik-titik graf non commuting dari grup dihedral 𝐷2𝑛 dari tabel

cayle.

3. Menggambar graf non commuting dari grup dihedral 𝐷2𝑛 .

4. Menentukan matriks adjacency dari graf non commuting dari grup dihedral 𝐷2𝑛 .

5. Mencari nilai eigen (eigenvalue) dari matriks adjacency graf non commuting grup dihedral

𝐷2𝑛 .



6. Mencari multiplisitas setiap nilai eigen dari matriks adjacency graf non commuting grup

dihedral 𝐷2𝑛 .

7. Mencari spektrum adjacency dari grup dihedral 𝐷2𝑛 .

8. Mencari pola dan dirumuskan menjadi suatu lemma dan teorema serta dibuktikan

kebenarannya secara umum.


Pada pembahasan ini, grup dihedral yang digunakan adalah𝐷6 , 𝐷8, 𝐷10 , … , 𝐷2𝑛 .

Pembahasan yang disajikan dalam bentuk contoh selanjutnya dijadikan sebuah teorema dan

disertai bukti.

Dihedral 𝐷6dibangun dari elemen-elemen {1, 𝑟, 𝑟2 , 𝑠, 𝑠𝑟, 𝑠𝑟2}, hasil operasi komposisi pada

setiap elemen grup dihedral berbentuk tabel Cayley yang menunjukkan unsur-unsur yang tidak

komutatif pada 𝐷6sebagai berikut:

Tabel 1. Tabel Cayley D6

° 1 r r2

s Sr sr2

1 1 r r2 s Sr sr

2

r r r2 1 sr

2 S

sr

r2 r

2 1 r sr sr

2 s

s s sr sr2 1 R r

2

sr sr sr2 s

r

2 1 r

sr2 sr

2 s sr r

r

2 1

Dari tabel 1, diperoleh center 𝐷6 atau 𝑍 𝐷6 yaitu {1} yang ditunjukkan pada tabel

dengan warna hitam, dan elemen-elemen pada D6 yang tidak komutatif ditunjukkan pada tabel

dengan warna abu-abu. Sehingga graf non kommuting dari grup 𝐷6 memiliki himpunan titik-

titiknya ΓD6= {𝑟, 𝑟2 , 𝑠, 𝑠𝑟, 𝑠𝑟2}. Dari hasil tersebut akan digambarkan ke dalam bentuk graf

non commuting sebagai berikut:

Gambar 1. Graf non D6

Graf non commuting grup 𝐷6 diatas menghasilkan matriks adjacency sebagai berikut:



𝑟 𝑟2 𝑠 𝑠𝑟 𝑠𝑟2

𝐴 ΓD6 =

𝑟𝑟2

𝑠𝑠𝑟𝑠𝑟2

0 0 1 1 10 0 1 1 11 1 0 1 11 1 1 0 11 1 1 1 0

Setelah mendapatkan bentuk matriks Adjacency maka akan dicari nilai eigen dan vektor eigen

dari matriks tersebut dengan cara mengolah persamaan de𝑡 𝐴 ΓD6 − 𝐼 =0.

Dengan mereduksi matriks menggunakan metode Gaussian Elimination yang ada pada software

Maple 12, maka akan diperoleh:

Karena det 𝐴 ΓD6 − 𝐼 adalah hasil perkalian semua unsur diagonal utama matriks segitiga

atas berikut, maka diperoleh polinomial karakteristiknya yaitu:

det 𝐴 ΓD6 − 𝐼 = (1)(𝜆) 1 + 𝜆 2 6 + 2𝜆 − 𝜆2

karena det 𝐴 ΓD6 − 𝐼 =0, maka

det 𝐴 ΓD6 − 𝐼 = (1)(𝜆) 1 + 𝜆 2 6 + 2𝜆 − 𝜆2 = 0

dan diperoleh nilai eigennya

𝜆1 = 1 + 7, 𝜆2 = 0, 𝜆3 = −1, 𝜆4 = 1 − 7 ,

Selanjutnya akan ditentukan basis untuk ruang vektor eigen, basis merupakan baris nol pada

matriks. Untuk semua 𝜆 yang diperoleh subtitusikan kedalam det 𝐴 ΓD6 − 𝐼 =0 dengan

metode gauss Jordan dalam software Maple 12 akan diperoleh 𝜆1 = 1 + 7 multiplisitas nilai

eigennya 1, 𝜆2 = 0 multiplisitas nilai eigennya 1, 𝜆3 = −1 multiplisitas nilai eigennya 2,

𝜆4 = 1 − 7 multiplisitas nilai eigennya 1. Sehingga diperoleh spektrum adjacency graf non

commuting dari 𝐷6 adalah:

𝑠𝑝𝑒𝑐(Γ𝐷6) = 1 + 7 0 −1 1 − 7

1 1 2 1

Dengan cara yang sama akan diperoleh

𝑠𝑝𝑒𝑐 Γ𝐷8 =

4 0 −21 3 2

;

𝑠𝑝𝑒𝑐(Γ𝐷10) = 2 + 2 6 0 −1 2 − 2 6

1 3 4 1 ;

spec ΓD12 = 2 + 2 7 0 −2 2 − 2 7

1 6 2 1 ;

spec ΓD14 = 3 + 51 0 −1 3 − 51

1 5 6 1 ;



spec ΓD16 = 3 + 57 0 −2 3 − 57

1 9 3 1

dan

spec ΓD20 = 4 + 4 6 0 −2 4 − 4 6

1 12 4 1

Dari percobaan yang dilakukan oleh peneliti, didapatkan beberapa lemma dan teorema

diantaranya:

Lemma 1:

Misalkan Γ𝐷2𝑛 adalah graf non commuting dari grup dihedral𝐷2𝑛 dengan n ganjil, maka

polinomial karakteristik matriks adjacency 𝐴 Γ𝐷2𝑛 adalah:

𝑝 𝜆 = 1 𝜆 𝑛 1 + 𝜆 𝑛−1 −𝜆 + 𝑛 − 1 𝜆 + 𝑛 𝑛 − 1

Bukti:

Diketahui grup dihedral 𝐷2𝑛 = {1, r, r2, …, r

n-1, s, sr, sr

2, …, sr

n-1}. Diperoleh bahwa

Z(𝐷2𝑛) = {1}untuk n ganjil. Dengan demikian graf non commuting 𝐷2𝑛mempunyai himpunan

titik { r, r2, …, r

n-1, s, sr, sr

2, …, sr

n-1}. Karena n ganjil, maka 𝑠𝑟𝑖 ≠ 𝑟𝑖𝑠, 𝑖 = 1, 2, … , 𝑛 − 1,

artinya s dan 𝑟𝑖 saling terhubung langsung di graf non commuting 𝐷2𝑛 . Demikian juga, karena n

ganjil, maka 𝑠𝑟𝑖𝑠𝑟𝑗 ≠ 𝑠𝑟𝑗 𝑠𝑟𝑖 , j=1, 2,..., n-1 dan 𝑖 = 1, 2, … , 𝑛 − 1, dengan 𝑖 ≠ 𝑗, yang berarti

𝑠𝑟𝑖 dan 𝑠𝑟𝑗 saling terhubung langsung di graf non commuting maka diperoleh matriks

keterhubungan titik:

𝑟 𝑟2 ⋯ 𝑟𝑛−1 𝑠 𝑠𝑟 𝑠𝑟2 ⋯ 𝑠𝑟𝑛−1

𝐴 ΓD2𝑛 =

𝑟𝑟2

⋮𝑟𝑛−1


⋮𝑠𝑟𝑛−1

0 0 … 0 1 1 1 ⋯ 10 0 … 0 1 1 1 ⋯ 1⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋯ ⋮0 0 ⋯ 0 1 1 1 ⋯ 11 1 ⋯ 1 0 1 1 ⋯ 11 1 ⋯ 1 1 0 1 ⋯ 11 1 ⋯ 1 1 1 0 ⋯ 1⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮1 1 ⋯ 1 1 1 1 ⋯ 0

Setelah mendapatkan bentuk matriks adjacency maka akan dicari nilai eigen dan vektor eigen

dari matriks tersebut dengan menyelesaikan persamaan de𝑡 𝐴 ΓD2n − 𝐼 =0


de𝑡 𝐴 ΓD2n − 𝐼 =

𝑟𝑟2

⋮𝑟𝑛−1


⋮𝑠𝑟𝑛−1

−𝜆 0 … 0 1 1 1 ⋯ 10 −𝜆 … 0 1 1 1 ⋯ 1⋮ ⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋯ ⋮0 0 ⋯ −𝜆 1 1 1 ⋯ 11 1 ⋯ 1 −𝜆 1 1 ⋯ 11 1 ⋯ 1 1 −𝜆 1 ⋯ 11 1 ⋯ 1 1 1 −𝜆 ⋯ 1⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮1 1 ⋯ 1 1 1 1 ⋯ −𝜆

Diperoleh matriks segitiga atas dari 𝐴 ΓD2𝑛 − λI sebagai berikut:




𝑟𝑟2

⋮𝑟𝑛−1


⋮𝑠𝑟𝑛−1

1 1 … 1 −𝜆 1 1 ⋯ 10 𝜆 … 𝜆 1 − 𝜆2 1 + 𝜆 1 + 𝜆 ⋯ 1 + 𝜆0 0 ⋱ 𝜆 ⋮ ⋮ ⋮ ⋯ ⋮0 0 ⋯ 𝜆 (𝑛 − 2) − 𝜆2 (𝑛 − 2) + 𝜆 (𝑛 − 2) + 𝜆 ⋯ (𝑛 − 2) + 𝜆0 0 ⋯ 0 1 + 𝜆 −𝜆 − 1 0 ⋯ 00 0 ⋯ 0 0 1 + 𝜆 −𝜆 − 1 ⋯ 00 0 ⋯ 0 0 0 1 + 𝜆 ⋱ 0⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ −𝜆 − 10 0 ⋯ 0 0 0 1 ⋯ −𝜆 + 𝑛 − 1 𝜆 + 𝑛 𝑛 − 1

Polinomial karakteristik dari 𝐴 ΓD2𝑛 − λI adalah det 𝐴 ΓD2𝑛

− λI , merupakan hasil

perkalian semua unsur diagonal utama matriks segitiga atas tersebut, sehingga diperoleh:

𝑝 𝜆 = 1 𝜆 𝑛 1 + 𝜆 𝑛−1 −𝜆 + 𝑛 − 1 𝜆 + 𝑛 𝑛 − 1

Teorema 1:

Spektrum Γ𝐷2𝑛dengan n ganjil diperoleh:


𝑛−1

2+ 𝑛 − 1 𝑛 +

𝑛−1

2

20 −1

𝑛−1

2− 𝑛 − 1 𝑛 +

𝑛−1

2

2

1 𝑛 − 2 𝑛 − 1 1

Bukti:

Dari lemma 1, diperoleh bahwa

𝑝 𝜆 = 1 𝜆 𝑛 1 + 𝜆 𝑛−1 −𝜆 + 𝑛 − 1 𝜆 + 𝑛 𝑛 − 1

Sehingga diperoleh nilai eigen

𝜆1 =𝑛 − 1

2+ 𝑛 − 1 𝑛 +

𝑛 − 1

2

2

, 𝜆2 = 0, 𝜆3 = −1,

𝜆4 =𝑛 − 1

2− 𝑛 − 1 𝑛 +

𝑛 − 1

2

2

Selanjutnya akan ditentukan multiplisitas dari setiap nilai eigen. Karena multiplisitas itu

sama dengan basis ruang vektor eigen yang besesuaian dengan i, i = 1, 2, 3, 4 dan basis

merupakan baris nol pada matriks, subtitusikan i ke 𝐴(ΓD2n) − 𝑖𝐼 dan dengan mereduksi

matriks menggunakan meode Gauss Jordan akan diperoleh matriks eselon baris tereduksi.

Dengan melihat basis pada matriks tersebut diperoleh:

untuk 𝜆1 =𝑛−1

2+ 𝑛 − 1 𝑛 +

𝑛−1

2

2 setelah dieliminasi ke 𝐴(ΓD2n

) − 1𝐼, diperoleh matriks

eselon baris dengan 1 baris yang nol. Jadi untuk 𝜆1 =𝑛−1

2+ 𝑛 − 1 𝑛 +

𝑛−1

2

2 memiliki

multiplisitas sebanyak 1. Untuk 𝜆2 = 0 setelah dieliminasi ke 𝐴(ΓD2n) − 2𝐼, diperoleh matriks

eselon baris dengan n – 2 baris yang nol. Jadi untuk 𝜆2 = 0 memiliki multiplisitas sebanyak n –

2. Untuk 𝜆3 = −1 setelah dieliminasi ke 𝐴(ΓD2n) − 3𝐼, diperoleh matriks eselon baris dengan



n – 1 baris yang nol. Jadi untuk 𝜆3 = −1 memiliki multiplisitas sebanyak n – 1. Untuk

𝜆4 =𝑛−1

2− 𝑛 − 1 𝑛 +

𝑛−1

2


) − 4𝐼, diperoleh matriks

eselon baris denga 1 baris yang nol. Jadi untuk 𝜆4 =𝑛−1

2+ 𝑛 − 1 𝑛 +

𝑛−1

2

2 memiliki

multiplisitas sebanyak 1.

Sehingga diperoleh:


𝑛−1

2+ 𝑛 − 1 𝑛 +

𝑛−1

2

20 −1

𝑛−1

2− 𝑛 − 1 𝑛 +

𝑛−1

2

2

1 𝑛 − 2 𝑛 − 1 1

Lemma 2:

Misalkan Γ𝐷2𝑛 graf non commuting dari grup dihedral𝐷2𝑛 dengan n genap dan 𝑛 ≥ 6, maka

polinomial karakteristik matriks adjacency 𝐴 Γ𝐷2𝑛 adalah:

p(𝜆)= 1 𝜆 𝑛−2 −1 𝑛−2

2 −2𝜆 − 𝜆2 𝑛−4

2 2𝑛 − 4 𝜆 +

𝑛2 − 2𝑛 1

2𝑛−4.𝜆 −𝑛 2𝑛2−4𝑛 − 𝑛−2 (𝑛+2) 𝜆− 𝑛−4 𝜆2+𝜆3

𝑛

2+𝜆

Bukti:

Diketahui grup dihedral 𝐷2𝑛 = {1, r, r2, …, r

n-1, s, sr, sr

2, …, sr

n-1}. Diperoleh bahwa

Z(𝐷2𝑛) = {1, 𝑟𝑛

2 }untuk n ganjil. Dengan demikian graf non commuting 𝐷2𝑛mempunyai

himpunan titik {r, r2, …, r

n-1, s, sr, sr

2, 𝑠𝑟

𝑛

2 , 𝑠𝑟𝑛

2+1 , …, 𝑠𝑟𝑛−2, sr

n-1}. Jumlah himpunan titiknya

adalah 2𝑛 − 2 dari grup dihedral 𝐷2𝑛 . Karena n genap, maka 𝑠𝑟𝑖 ≠ 𝑟𝑖𝑠, 𝑖 = 1, 2, … , 𝑛 − 1,

artinya s dan 𝑟𝑖 saling terhubung langsung di graf non commuting 𝐷2𝑛 .Demikian juga, karena n

genap, maka 𝑠𝑟𝑖𝑠𝑟𝑗 ≠ 𝑠𝑟𝑗 𝑠𝑟𝑖 , j=1, 2,..., n-1 dan 𝑖 = 1, 2, … , 𝑛 − 1, dengan 𝑖 ≠ 𝑗, yang berarti

𝑠𝑟𝑖 dan 𝑠𝑟𝑗 saling terhubung langsung di graf non commuting D2𝑛kecualijika 𝑠𝑟𝑖𝑠𝑟𝑗 = 𝑟𝑛

2

yang berarti 𝑠𝑟𝑖 dan 𝑠𝑟𝑗 tidak saling terhubung langsung di graf non commuting D2𝑛maka

diperoleh matriks keterhubungan titik:

𝑟 𝑟2 ⋯ 𝑟𝑛−1𝑠 𝑠𝑟 𝑠𝑟2 ⋯ 𝑠𝑟𝑛

2−1𝑠𝑟

𝑛

2 𝑠𝑟𝑛

2+1 ⋯ 𝑠𝑟𝑛−2 𝑠𝑟𝑛−1

𝐴 ΓD2𝑛 =

𝑟𝑟2

⋮𝑟𝑛−1


⋮

𝑠𝑟𝑛

2−1

𝑠𝑟𝑛

2

𝑠𝑟𝑛

2+1

⋮𝑠𝑟𝑛−2

𝑠𝑟𝑛−1 0 0 … 0 1 1 1 ⋯ 1 1 1 ⋯ 1 10 0 … 0 1 1 1 ⋯ 1 1 1 ⋯ 1 1⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮0 0 ⋯ 0 1 1 1 ⋯ 1 1 1 ⋯ 1 11 1 ⋯ 1 0 1 1 ⋯ 1 0 1 ⋯ 1 11 1 ⋯ 1 1 0 1 ⋯ 1 1 0 ⋱ 1 11 1 ⋯ 1 1 1 0 ⋱ 1 1 1 ⋱ 0 1⋮ ⋮ ⋯ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋯ ⋱1 1 ⋯ 1 1 1 1 ⋱ 0 1 1 ⋱ 1 01 1 ⋯ 1 0 1 1 ⋱ 1 0 1 ⋱ 1 11 1 ⋯ 1 1 0 1 ⋱ 1 1 0 ⋱ 1 1⋮ ⋮ ⋯ ⋮ ⋱ ⋱ ⋱ ⋮ ⋱ ⋱ ⋱ ⋱ ⋮ ⋮1 1 ⋯ 1 1 1 1 ⋱ 1 1 1 ⋯ 0 11 1 ⋯ 1 1 1 1 ⋱ 0 1 1 ⋯ 1 0



Setelah mendapatkan bentuk matriks adjacency maka akan dicari nilai eigen dan vektor eigen

dari matriks tersebut dengan menyelesaikan persamaan de𝑡 𝐴 ΓD2n − 𝐼 =0:

𝑟 𝑟2 ⋯ 𝑟𝑛−1 𝑠 𝑠𝑟 𝑠𝑟2 ⋯ 𝑠𝑟𝑛

2−1 𝑠𝑟

𝑛

2 𝑠𝑟𝑛

2+1 ⋯ 𝑠𝑟𝑛−2 𝑠𝑟𝑛−1

de𝑡 𝐴 ΓD2n − 𝐼 =

𝑟𝑟2

⋮𝑟𝑛−1


⋮

𝑠𝑟𝑛

2−1

𝑠𝑟𝑛

2

𝑠𝑟𝑛

2+1

⋮𝑠𝑟𝑛−2

𝑠𝑟𝑛−1 −𝜆 0 … 0 1 1 1 ⋯ 1 1 1 ⋯ 1 10 −𝜆 … 0 1 1 1 ⋯ 1 1 1 ⋯ 1 1⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮0 0 ⋯ −𝜆 1 1 1 ⋯ 1 1 1 ⋯ 1 11 1 ⋯ 1 −𝜆 1 1 ⋯ 1 0 1 ⋯ 1 11 1 ⋯ 1 1 −𝜆 1 ⋯ 1 1 0 ⋱ 1 11 1 ⋯ 1 1 1 −𝜆 ⋱ 1 1 1 ⋱ 0 1⋮ ⋮ ⋯ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋯ ⋱1 1 ⋯ 1 1 1 1 ⋱ −𝜆 1 1 ⋱ 1 01 1 ⋯ 1 0 1 1 ⋱ 1 −𝜆 1 ⋱ 1 11 1 ⋯ 1 1 0 1 ⋱ 1 1 −𝜆 ⋱ 1 1⋮ ⋮ ⋯ ⋮ ⋱ ⋱ ⋱ ⋮ ⋱ ⋱ ⋱ ⋱ ⋮ ⋮1 1 ⋯ 1 1 1 1 ⋱ 1 1 1 ⋯ −𝜆 11 1 ⋯ 1 1 1 1 ⋱ 0 1 1 ⋯ 1 −𝜆

Diperoleh matriks segitiga atas dari 𝐴 ΓD2𝑛 − λI sebagai berikut:

𝒓 𝒓𝟐 ⋯ 𝒓𝒏−𝟏 𝒔 𝒔𝒓 𝒔𝒓𝟐 ⋯ 𝒔𝒓𝒏

𝟐−𝟏 𝒔𝒓

𝒏

𝟐 𝒔𝒓𝒏

𝟐+𝟏 ⋯ 𝒔𝒓𝒏−𝟐 𝒔𝒓𝒏−𝟏

𝒓𝒓𝟐

⋮𝒓𝒏−𝟏

𝒔𝒔𝒓𝒔𝒓𝟐

⋮

𝒔𝒓𝒏

𝟐−𝟏

𝒔𝒓𝒏

𝟐

𝒔𝒓𝒏

𝟐+𝟏

⋮𝒔𝒓𝒏−𝟐

𝒔𝒓𝒏−𝟏

1 1 … 1 −𝜆 1 1 ⋯ 1 0 1 ⋯ 1 10 𝜆 … 𝜆 1 − 𝜆2 1 + 𝜆2 1 + 𝜆2 ⋯ 1 + 𝜆2 1 1 + 𝜆2 ⋯ 1 + 𝜆2 1 + 𝜆2

⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮0 0 ⋯ 𝜆 𝑛 − 3 − 𝜆2 𝑛 − 3 + 𝜆2 𝑛 − 3 + 𝜆2 ⋯ 𝑛 − 3 + 𝜆2 𝑛 − 3 𝑛 − 3 + 𝜆2 ⋯ 𝑛 − 3 + 𝜆2 𝑛 − 3 + 𝜆2

0 0 ⋯ 0 𝜆 0 0 ⋯ 0 −𝜆 0 ⋯ 0 00 0 ⋯ 0 0 −1 0 ⋯ 0 2 + 𝜆 −𝜆 − 1 ⋱ 0 00 0 ⋯ 0 0 0 −1 ⋱ 0 2 + 𝜆 0 ⋱ 0 0⋮ ⋮ ⋯ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ ⋮ ⋮ −𝜆 − 1 ⋱0 0 ⋯ 0 0 0 0 ⋯ −1 2 + 𝜆 0 ⋱ 0 −𝜆 − 10 0 ⋯ 0 0 0 0 ⋱ 0 −2𝜆 − 𝜆2 2𝜆 + 𝜆2 ⋱ 0 00 0 ⋯ 0 0 0 0 ⋱ 0 0 −2𝜆 − 𝜆2 ⋱ 0 0⋮ ⋮ ⋯ ⋮ ⋱ ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋮0 0 ⋯ 0 0 0 0 0 0 0 0 ⋯ 2𝑛 − 4 𝜆 + 𝑛2 − 2𝑛 − 𝑛 − 2 𝜆 − 𝜆2

0 0 ⋯ 0 0 0 0 0 0 0 0 ⋯ 01

2𝑛 − 4.𝜆 −𝑛 2𝑛2 − 4𝑛 − 𝑛 − 2 (𝑛 + 2) 𝜆 − 𝑛 − 4 𝜆2 + 𝜆3

𝑛

2+ 𝜆

Polinomial karakteristik dari 𝐴 ΓD2𝑛 − λI adalah det 𝐴 ΓD2𝑛

− λI , merupakan hasil

perkalian semua unsur diagonal utama matriks segitiga atas tersebut, sehingga diperoleh:

p(𝜆)= 1 𝜆 𝑛−2 −1 𝑛−2

2 −2𝜆 − 𝜆2 𝑛−4

2 2𝑛 − 4 𝜆 +

𝑛2 − 2𝑛 1

2𝑛−4.𝜆 −𝑛 2𝑛2−4𝑛 − 𝑛−2 𝑛+2 𝜆− 𝑛−4 𝜆2+𝜆3

𝑛

2+𝜆

Teorema 2:

Spektrum D2n dengan n genap dan 𝑛 ≥ 6 diperoleh:

Specc (𝛤𝐷2𝑛)=

𝑛−2

2+

5𝑛2−12𝑛+4

40 −2

𝑛−2

2−

5𝑛2−12𝑛+4

4

1𝑛−2

2

3𝑛−6

21

Bukti:

Dari lemma 2, diperoleh bahwa



p(𝜆)= 1 𝜆 𝑛−2 −1 𝑛−2

2 −2𝜆 − 𝜆2 𝑛−4

2 2𝑛 − 4 𝜆 +

𝑛2 − 2𝑛 1

2𝑛−4.𝜆 −𝑛 2𝑛2−4𝑛 − 𝑛−2 𝑛+2 𝜆− 𝑛−4 𝜆2+𝜆3

𝑛

2+𝜆

Sehingga diperoleh nilai eigen

𝜆1 =𝑛 − 2

2+

5𝑛2 − 12𝑛 + 4

4, 𝜆2 = 0, 𝜆3 = −2, 𝜆4 =

𝑛 − 2

2−

5𝑛2 − 12𝑛 + 4

4

Selanjutnya akan ditentukan multiplisitas dari setiap nilai eigen. Karena multiplisitas itu

sama dengan basis ruang vektor eigen yang besesuaian dengan i, i = 1, 2, 3, 4 dan basis

merupakan baris nol pada matriks, subtitusikan i ke 𝐴(ΓD2n) − 𝑖𝐼 dan dengan mereduksi

matriks menggunakan meode Gauss Jordan akan diperoleh matriks eselon baris kita tereduksi.

Dengan melihat basis pada matriks tereduksi tersebut diperoleh:

untuk 𝜆1 =𝑛−2

2+

5𝑛2−12𝑛+4


) − 1𝐼, diperoleh matriks eselon

baris dengan 1 baris nol. Jadi untuk 𝜆1 =𝑛−2

2+

5𝑛2−12𝑛+4

4 memiliki multiplisitas sebanyak 1.

Untuk 𝜆2 = 0 setelah dieliminasi ke 𝐴(ΓD2n) − 2𝐼, diperoleh matriks eselon baris dengan

𝑛−2

2baris nol. Jadi untuk 𝜆2 = 0 memiliki multiplisitas sebanyak

𝑛−2

2. Untuk 𝜆3 = −2 setelah

dieliminasi ke 𝐴(ΓD2n) − 3𝐼, diperoleh matriks eselon baris dengan

3𝑛−6

2baris nol. Jadi untuk

𝜆3 = −2 memiliki multiplisitas sebanyak 3𝑛−6

2.

Untuk 𝜆4 =𝑛−2

2−

5𝑛2−12𝑛+4


) − 4𝐼, kita temukan diperoleh

matriks eselon baris denga 1 baris nol. Jadi untuk 𝜆4 =𝑛−2

2−

5𝑛2−12𝑛+4

4 memiliki

multiplisitas sebanyak 1.

Sehingga diperoleh:


𝑛−2

2+

5𝑛2−12𝑛+4

40 −2

𝑛−2

2−

5𝑛2−12𝑛+4

4

1𝑛−2

2

3𝑛−6

21

KESIMPULAN DAN SARAN

Berdasarkan pembahasan dapat disimpulkan bahwa spektrum Adjacency graf non

commuting pada grup dihedral (𝐷2𝑛) dengan n adalahbilangan asli ganjil diperoleh spektrum

Adjacency nya:



𝑠𝑝𝑒𝑐𝑐 𝛤𝐷2𝑛

= 𝑛 − 1

2+ 𝑛 − 1 𝑛 +

𝑛 − 1

2

2

0 −1𝑛 − 1

2− 𝑛 − 1 𝑛 +

𝑛 − 1

2

2

1 𝑛 − 2 𝑛 − 1 1

∀ 𝑛

≥ 3 danganjil


𝑛−2

2+

5𝑛2−12𝑛+4

40 −2

𝑛−2

2−

5𝑛2−12𝑛+4

4

1𝑛−2

2

3𝑛−6

21

∀ 𝑛 ≥ 6 dangenap

Berbagai macam spektrum dapat diperoleh dari suatu matriks, sehingga disarankan bagi

pembaca untuk mencari rumus spektrum yang lain dari grup dihedral (𝐷2𝑛).

DAFTAR PUSTAKA

Abdollahi, A., Akbari, S., & Maimani, H. 2006. Non-commuting Graph of a Group. Journal Of

Algebra, vol 298 pp: 468-492.

Abdussakir, Ikawati, DSE, and Sari, FKN.. 2012. Spektrum Adjacensy, Spektrum Laplace,

Spektrum Signless-Laplace, dan Spektrum Detour Graf Multipatisi Komplit. Malang: UIN

Maliki Malang

Ayyaswamy, S.K. and Balachandran, S.. 2010. On Detour Spectra of Some Graph.

International Journal of Computational and Mathematical Sciences, vol 4 pp:250-252.

Biggs, Norman. 1974. Algebraic Graph Theory. Cambride: Cambride University Press.

Biyikoglu, T., Leydold, J., & Stadler, P. F. 2007. Laplacian Eigenvectors of Graphs. Berlin:

Springer.

Chartrand, G., & Lesniak, L. 1996. Graph and Digraph Third Edition. Calfornia: Wadsworth

Inc.

Raisinghania, M.D., Aggarwal, R. S.. 1980. Modern Algebra. New delhi: S. Chand & Company

Ltd.

Yin, S.. 2008. Investigation os Spectrum of the Adjacency and Laplacian Matrixx of Graph Gl.

WSEAS TRANSACTION on SYSTEM, vol 7 pp: 362-372.



OPTIMASI HASIL PANEN PADI MENGGUNAKAN SINGULAR VALUE

DECOMPOSITION (SVD) DANANT COLONY OPTIMIZATION (ACO)

Vina Puspita Dewi

1), Hanna Arini Parhusip

2), Lilik Linawati

3)

1) Mahasiswa Program Studi Matematika FSM UKSW 2), 3)

Dosen Program Studi Matematika FSM UKSW

Fakultas Sains dan Matematika, Universitas Kristen Satya Wacana

Jl. Diponegoro 52-60 Salatiga 50711

E-mail: [email protected])

, [email protected])

,

[email protected])

Abstrak

Hasil panen padi di Kota Surakarta pada tahun 1992-2012 akan ditentukan periode tanam

yang optimal. Untuk mendapatkan periode tanam yang optimal maka perlu menyusun

fungsi tujuan. Fungsi tujuan yang dipilih adalah berbentuk kuadratik yang parameter-

parameternya ditentukan menggunakan Singular Value Decomposition (SVD). Ant Colony

Optimization (ACO) ACO merupakan algoritma optimasi yang menggunakan perilaku

semut. ACO menghasilkan periode III (September – Desember) sebagai periode yang

optimal. Hasil gabah per hektar yang diperoleh adalah 43.8 ton

Kata Kunci:Ant Colony Optimization (ACO), Singuler Value Decomposition (SVD)

PENDAHULUAN

Kajian optimasi hasil panen padi di kota Surakarta berdasarkan data BPS Surakarta

untuk mencari periode tanam optimal (maksimal) pernah dilakukan menggunakan pemrograman

kuadratik. Ada tiga periode tanam dalam satu tahun yaitu periode I (Januari-April), periode II

(Mei-Agustus), dan periode III (September-Desember). Kajian didasarkan pada data hasil panen

padi tahun 1992-2012. Analisis dilakukan untuk setiap periode tanam, sehingga pada masing-

masing periode tanam dibuat fungsi tujuan yang berbentuk kuadratik. Parameter-parameter

fungsi tujuan ditentukan menggunakan metode kuadrat terkecil dan diperoleh periode tanam

yang optimal (maksimal) adalah periode tanam III. Jadi hampir setiap tahun periode yang

optimal adalah pada periode III (Dewi, dkk, 2013).

Terdapat beberapa metode optimasi non linear modern diantaranya Simulated

Annealing, algoritma genetik, Ant colony optimization (ACO), dan Particle Swarm Optimization

(PSO). Pada penelitian ini akan digunakan ACO untuk menentukan periode tanam optimal dan

diharapkan akan memberikan hasil yang sama dengan hasil penelitian menggunakan

pemrograman kuadratik. ACO dibuat berdasarkan perilaku kooperatif dari koloni semut di alam

yang dapat menemukan lintasan terpendek dari sarang semut ke suatu sumber makanan. Metode

ini dikembangkan oleh Dorigo pada awal 1990-an (Rao, 2009). Untuk fungsi tujuan disusun

menggunakan Singuler Value Decomposition (SDV) dan diharapkan nilai error terhadap

parameter-parameter fungsi tujuan yang diperoleh lebih kecil.

Penelitian mengenai Ant Colony Optimiation (ACO) sudah pernah dilakukan oleh

beberapa peneliti diantaranya untuk menyelesaikan permasalahan penjadwalan mesin pararel

(Chang, dkk, 2008), menyelesaikan permasalahan job shop dengan menggunakan ACO (Seo






&Kim, 2008), dan untuk mengoptimalkan reduksi warna pada sirup stevioside (Parhusip &

Martono, 2012).

DASAR TEORI

Ant Colony Optimization (ACO)

Menurut Rao (2009) ACO dapat dijelaskan dengan menampilkan masalah optimasi

dalam grafik multilayer sebagaimana ditunjukkan pada Gambar 1 dengan banyaknya variabel

sama dengan banyaknya layer. Sedangkan banyaknya titik/node pada tiap layer sama dengan

banyaknya titik diskrit yang diijinkan berkaitan dengan variabel keputusan.

Layer 1(x1) x11 x12 x13 x14 x15

Layer 2 (x2) x21 x22 x23 x24 x25

Layer 3 (x3) x31 x32 x33 x34 x35

Layer 4 (x4) x41 x42 x43 x44 x45

Tujuan

(makanan)

rumah



Gambar 1. Grafik multilayer untuk Ant Colony Optimization (ACO)

𝑥𝑖= variabel ke-i. i=1,2,...,n

𝑥𝑖𝑗 = lintasan pada node ke-i dan posisi ke-j. j=1,2,...,m

Berikut ini model cara semut berjalan dari rumah/sarang menuju ke node tujuan dan kembali

lagi ke rumah/ sarangnya:

1. Sifat Perilaku Semut dalam Perjalanan Menuju Tujuan

Seekor semut berjalan dari titik awal yaitu rumah menuju ke layer pertama sampai

ke layer terakhir dan akan berhenti sampai ke node tujuan (makanan).

Semut ke-k pada lokasi node i untuk menuju posisi ke-j sebagai posisi selanjutnya

menggunakan jejak feromon ij pada probabilitas

𝜌𝑖𝑗(𝑘)

=

𝜏𝑖𝑗𝛼

𝜏𝑖𝑗𝛼

𝑗∈𝑁𝑖(𝑘)

, jika𝑗 ∈ 𝑁𝑖(𝑘)

0 , jika𝑗 ∉ 𝑁𝑖(𝑘)

(1)

dimana menyatakan derajat kepentingan dari feromon dan 𝑁𝑖(𝑘)

menyatakan

himpunan node-node pada persekitaran semut ke-k pada posisi i, kecuali node

predesesor ( yaitu node terakhir yang dikunjungi sebelum i). Hal ini akan menjaga

semut ke-k kembali ke node yang sama.

2. Lintasan Kembali dan Memperbaharui Feromon

Sebelum ke node rumah (arah mundur), semut ke-kmenyimpan )(k feromon

pada lintasan yang telah dikunjungi. Nilai feromon ij pada lintasan (i,j) diperbarui

dengan

𝜏𝑖𝑗 ← 𝜏𝑖𝑗 + ∆𝜏(𝑘) (2)

Karena ada peningkatan pada feromon , probabilitas lintasan tersebut akan dipilih semut

lain juga akan semakin meningkat.

3. Penguapan Jejak Feromon

Ketika seekor semut ke-kbergerak ke node berikutnya, feromon yang dapat

dinyatakan sebagai

𝜏𝑖𝑗 ← 1 − 𝜌 𝜏𝑖𝑗 ; ∀ 𝑖, 𝑗 𝜖𝐴 (3)

dimana 𝜌 ]1,0( adalah laju penguapan (yang dikenal juga sebagai faktor penurunan

feromon) dan A menyatakan segmen atau lintasan yang dilalui oleh semut ke-k dari

rumah ke tujuan. Penurunan intensitas feromon menyebabkan eksplorasi pada lintasan

yang berbeda-beda selama proses pencarian. Hal ini menyebabkan adanya eliminasi

dari pemilihan lintasan yang buruk sehingga jejak feromon dapat menghasilkan nilai



yang maksimum.Suatu iterasi dikatakan lengkap jika meliputi pergerakan semut,

penguapan feromon dan penyimpanan feromon.

Setelah semua semut ke-k kembali ke titik sarang (rumah) , informasi feromon

diperbaharui berdasarkan hubungan

𝜏𝑖𝑗 = 1 − 𝜌 𝜏𝑖𝑗 + ∆𝜏𝑖𝑗(k)𝑁

𝑘=1 (4)

dimana )(k

ij adalah banyaknya feromon yang disimpan pada lintasan ij oleh semut ke-

k. Tujuan feromon diperbaharui adalah untuk meningkatkan nilai feromon yang

berkaitan dengan baik atau tidaknya lintasan. Feromon disimpan pada lintasan ij terbaik

dalam bentuk

∆𝜏𝑖𝑗(k) =

𝑄

𝐿𝑘 (5)

dimana Q menyatakan suatu konstan dan kL adalah panjang lintasan yang dilalui oleh

semut ke-k (seperti dari 1 kota ke kota lain). Persamaan (5) dapat diimplementasikan

sebagai

∆𝜏𝑖𝑗(𝑘)

=

𝜍𝑓𝑡𝑒𝑟𝑏𝑎𝑖𝑘

𝑓𝑡𝑒𝑟𝑏𝑢𝑟𝑢𝑘; jika 𝑖, 𝑗 ∈ perjalanan global terbaik

0; untuk yang lain

(6)

fterbaik= nilai terbaik fungsi tujuan

fterburuk= nilai terburuk fungsi tujuan

= parameter yang digunakan untuk mengkontrol pembaharuan feromon

Fungsi Tujuan ACO Menggunakan Singular Value Decomposition (SVD)

Pada penelitian ini digunakan fungsi tujuan kuadratik dengan parameter-parameternya

dicari menggunakan Singuler Value Decomposition (SDV). Parameter-parameter fungsi tujuan

yang akan dicari adalah

𝑆𝑖 = 𝛼1𝑥𝑖2 + 𝛼2𝑦𝑖

2 + 𝛼3𝑥𝑖𝑦𝑖 + 𝛼4𝑥𝑖 + 𝛼5𝑦𝑖 + 𝛼6 (7)

Persamaan (7) dalam bentuk matriks dapat ditulis:

𝐴𝑣 𝛼 = 𝑆 (8)

dimana

A=

𝑥1

2 𝑦12 𝑥1𝑦1

𝑥22 𝑦2

2 𝑥2𝑦2

𝑥1 𝑦1 1𝑥2 𝑦2 1

⋮ ⋮ ⋮𝑥𝑛

2 𝑦𝑛2 𝑥𝑛𝑦𝑛

⋮ ⋮ ⋮𝑥𝑛 𝑦𝑛 1

(8a)

𝑣 𝛼 = 𝛼1𝛼2𝛼3𝛼4𝛼5𝛼6

ix = data ke- i variabel 1

iy = data ke- i variabel 2

𝑆 =iS = data ke- i variabel 3 i = 1,2,...,n; n= banyaknya data



𝛼𝑗 = parameter fungsi tujuan j = 1,2,...,6

𝐴 = 𝑈𝛴𝑉𝑇 (9)

Menurut Watkins (1991) pada persamaan (9) jika matriks Aϵ Rnxm

mempunyai rankr,

maka terdapat matriks dengan kolom-kolom dari nilai eigen 𝐴𝐴𝑇U ϵ Rnxn

, Σ adalah matriks

diagonal dari akar nilai eigen 𝐴𝐴𝑇Σ ϵ Rnxm

, dan V adalah matriks dengan kolom-kolom dari

vektor eigen 𝐴𝐴𝑇V ϵ Rmxm

.

Dari persamaan (8) dan (9) diperoleh:

𝑈𝛴𝑉𝑇𝑣 𝛼 = 𝑆 atau 𝛴𝑉𝑇𝑣 𝛼 = 𝑈𝑇𝑆 (10)

Misal 𝑐 = 𝑈𝑇𝑆 dan 𝑦 = 𝑉𝑇𝑣 𝛼 , maka 𝛴𝑦 = 𝑐 sehingga 𝑦 = 𝛴𝑇𝑐

Persamaan (8) diselesaikan dengan:

𝑣 𝛼 = 𝑉𝑦 (11)

Untuk error :

Error= E = 𝑆 𝑝𝑒𝑛𝑑𝑒𝑘𝑎𝑡𝑎𝑛 −𝑆 𝑑𝑎𝑡𝑎

𝑆 𝑑𝑎𝑡𝑎 . 100%

Selain itu dengan menghitung Conditional Number:

κ 𝐴 ≡ 𝐴−1 𝐴 jika 𝐴 nonsinguler

∞jika 𝐴 singuler

Menurut Anderson, dkk, (1999) jika Conditional Number dibawah 67108864 maka errorinvers

dinyatakan baik. Sebaliknya dikatakan tidak baik (ill condition)

Setelah mendapatkan fungsi tujuan, agar fungsi tujuan menjadi tidak berkendala maka perlu

disusun fungsi Lagrange untuk menyelesaikannya dengan ACO yaitu

m

i

ii xgxfxL1

)()(),(

untuk Cx

dan 0

(12)

Kondisi Karush Kuhn Tucker (KKT) pada persamaan (13) dapat digunakan untuk menemukan

titik kritis dengan menyelesaikan sistem persamaan yang diperoleh dari 0

L . Artinya

mencari pemaksimal *x

dan parameter optimal *

yang memenuhi

(1).𝜆 𝑖∗ ≥ 0

(2). 𝜆 𝑖∗ 0*)( xg i

untuk i = 1,2,…,m.

(13)

(3).

m

i

ii xgxf1

0*)(**)(

Fungsi tujuan mempunyai titik pemaksimal jika bersifat concave (cekung). Menurut Perresini,

dkk, (1998) ada beberapa cara untuk menunjukkan fungsi tujuan yang diperoleh concave:



1. Jika matriks Hessian fungsi tujuan negative semi definite (setiap nilai eigen ≤ 0) maka

𝑥 ∗ merupakan pemaksimal.

2. Sebuah fungsi 𝑓(𝑥 ) adalah cembung pada sebuah selang (berhingga atau tak

berhingga). Jika untuk setiap dua titik 𝑥 dan𝑦 didalam dimana 𝑥 dan𝑦 ϵ Rndan untuk

semua 0 ≤ 𝜆 ≤ 1berlaku

𝑓 𝜆𝑥 + 1 − 𝜆 𝑦 ≤ 𝜆𝑓 𝑥 + 1 − 𝜆 𝑓(𝑦 ) (14)

Jika pernyataan diatas berlaku dengan tanda pertidaksamaan yang terbalik, maka𝑓(𝑥 )

adalah cekung .

METODE PENELITIAN

Tahap 1. Penelitian ini didasarkan pada data sekunder yang diperoleh dari BPS kota Surakarta

untuk data hasil panen padi tahun 1992-2012.

Tahap 2. Data hasil panen padi akan dioptimalkan dengan menggunakan algoritma ACO,

dengan parameter fungsi tujuan ditentukan dengan menggunakan SVD.

Tahap 3. Menyusun dan menyelesaikan model

a. Menyusun fungsi tujuan dengan menggunakan SVD

b. Menyusun fungsi Lagrange seperti persamaan (12).

c. Mengoptimalkan fungsi Lagrange sesuai dengan algoritma ACO.

Tahap 4. Menganalisis hasil dan pembahasan

Tahap 5. Membuat kesimpulan.


Penyusunan fungsi tujuan dengan menggunakan SVD menghasilkan fungsi tujuan

untuk masing-masing periode tanam sebagai berikut:

𝑆𝐼 = 0.8362𝑥2 − 0.0282 − 0.4457𝑥𝑦 − 0.681𝑥 + 0.4676𝑦 + 0.8401 (15)

𝑆𝐼𝐼 = −0.2253𝑥2 − 3.1680𝑦2 + 4.6619𝑥𝑦 − 2.9688𝑥 + 2.5897𝑦 + 0.3584 (16)

𝑆𝐼𝐼𝐼 = 1.1955𝑥2 + 0.7538𝑦2 − 0.1339𝑥𝑦 − 1.6698𝑥 − 0.6658𝑦 − 1.3404 (17)

Pada Gambar 1 disajikan data aktual yang dibandingkan dengan data pendekatan untuk setiap

periode tanam. Nilai error dari parameter setiap fungsi tujuan menggunakan metode kuadrat

terkecil maupun dengan SVD diperlihatkan pada Tabel 1.



Periode I Periode II Periode III

Gambar 2. Grafik hasil panen padi menurut data aktual dan hasil pendekatan fungsi kuadratik

pada setiap periode tanam.

Tabel 1.Nilai error berdasarkan metode kuadrat terkecil dan SVD serta nilai Conditional

Number.

Metode yang

digunakan


Error Kuadrat terkecil 9.4% 13.8342% 18.5405%

SVD 7.27% 11.89% 8.43%

Conditional

number

Kuadrat terkecil 23568 37013 22201

SVD 162.86 221.188 160.35

Metode SVD memberikan nilai error dan Conditional Number yang lebih kecil jika

dibandingkan dengan metode kuadrat terkecil. Begitu juga dengan Conditional Number yang

diperoleh. Hal ini dapat disimpulkan bahwa parameter-parameter fungsi tujuan yang diperoleh

menggunakan SVD lebih baik jika dibandingkan dengan metode kuadrat terkecil.

Perlu dibuat persamaan Lagrange seperti persamaan (12) dengan kendala yaitu 𝑥

≤𝑥𝑚𝑎𝑘𝑠 dan 𝑦 ≤ 𝑥. Sehingga persamaan (15) sampai (17) menjadi:

𝐿 𝑥 , 𝜆 = 0.8362𝑥2 − 0.0282𝑦2 − 0.4457𝑥𝑦 − 0.681𝑥 + 0.4676𝑦 + 0.8401 +

𝜆1 𝑥 − 1 + 𝜆2 𝑦 − 𝑥 − 𝜆3𝑥 − 𝜆4𝑦 (18)

𝐿 𝑥 , 𝜆 = −0.2253𝑥2 − 3.1680𝑦2 + 4.6619𝑥𝑦 − 2.9688𝑥 + 2.5897𝑦 + 0.3584 +

𝜆1 𝑥 − 1 + 𝜆2(𝑦 − 𝑥) − 𝜆3𝑥 − 𝜆4𝑦 (19)

𝐿 𝑥 , 𝜆 = 1.1955𝑥2 + 0.7538𝑦2 − 0.1339𝑥𝑦 − 1.6698𝑥 − 0.6658𝑦 − 1.3404 +

𝜆1 𝑥 − 1 + 𝜆2(𝑦 − 𝑥) − 𝜆3𝑥 − 𝜆4𝑦 (20)

Masing-masing fungsi tujuan diselesaikan berdasarkan algoritma ACO, dan diperoleh

penyelesaian seperti pada Tabel 2.

0 5 10 15 20 250.75

0.8

0.85

0.9

0.95

1

indeks

fungsi tuju

an

hasil

pendekatan

0 5 10 15 20 250.4

0.5

0.6

0.7

0.8

0.9

1

indeks

fungsi tu

juan

hasil

pendekatan

0 5 10 15 20 250.55

0.6

0.65

0.7

0.75

0.8

0.85

0.9

0.95

1

indeks

fungsi tu

juan

hasil

pendekatan



Tabel 2.Penyelesaian optimal berdasarkan ACO untuk ketiga periode tanam.


x*

0.7434 0.7160 0.8087

y*

0.6759 0.6662 0.5663

S*

0.453 0.4396 0.5262

𝜆1 0.62 0.0770 0.3434

𝜆2 0.4832 0.9032 0.6415

𝜆3 0.1436 0.2022 0.8831

𝜆4 0.1831 0.0134 0.2934

Tabel 3. Kondisi KKT untuk setiap periode tanam.


Kondisi I Terpenuhi Terpenuhi Terpenuhi

Kondisi II -0.1591

-0.0326

-0.1068

-0.1225

-0.0219

-0.045

-0.1448

-0.0089

-0.0657

-0.1555

-0.7142

-0.1662

Kondisi III 0.3845

0.6007

-0.4157

-0.1001

-0.8502

-0.7984

-1.3547

1.5464

-0.4088

-0.0536

-1.3627

-0.8009

-0.5233

-1.1220

-0.2920

-0.3256

-1.3275

-1.0664

Kondisi KKT pada Tabel 3 tidak terpenuhi sehingga 𝑥 ∗ bukan merupakan pemaksimal

dan parameter 𝜆 ∗tidak optimal. Selain itu dengan mencari niai eigen dari matriks Hessian fungsi

Lagrange. Diperoleh nilai eigen untuk setiap periode tanam yaitu:

Periode I: [-1.47; -1.01; 0; 0; 1.14; 2.95]

Periode II: [-9.24; -0.65; 0; 0; 0.29; 2.81]

Periode III: [-0.98; -0.48; 0; 0; 2.27; 4.61]

Dari ketiga periode tanam diatas nilai eigen untuk masing-masing periode tanam tidak ada yang

bersifat negative semi definite, sehingga 𝑥 ∗ bukan merupakan pemaksimal.

Cara selanjutnya yaitu menguji persamaan (14), dari Gambar 3 dapat disimpulkan bahwa untuk

setiap periode tidak terlihat secara signifikan bersifat convex atau concave.




Gambar 3. Fungsi tujuan convex atau concave.

Tabel 4.Penyelesaian optimal untuk ketiga periode tanam dalam bentuk data berdimensi.

Metode yang digunakan Periode I Periode II Periode III

Luas Tanam

Akhir (ha)

Pemrograman Kuadratik 132.9505 54.6966 120.4908

ACO 118.944 109.55 142.33

Luas Panen (ha) Pemrograman Kuadratik 120.4864 105.2448 76.1586

ACO 98 103.9 63.99

Hasil gabah

(ton)

Pemrograman Kuadratik 61.7237 55.8306 60.4087

ACO 29.18 34.31 43.8

Dapat dijelaskan dari Tabel 4 bahwa periode tanam yang optimal adalah periode III,

dimana hasil gabah yang didapat dalam satu hektar sawah adalah 43.8 ton. Pada penelitian yang

pernah dilakukan menggunakan pemrograman kuadratik periode optimal adalah periode III.

Secara informal (dari data) periode III merupakan periode yang maksimal hampir di setiap

tahunnya. Pada dasarnya ACO tidak baik karena 0

L tidak terpenuhi, untuk itu

menggunakan fungsi tujuan seperti persamaan (18) sampai (20) diselesaikan dengan

pemrograman kuadratik menurut dewi,dkk, (2013). Hasil untuk pemrograman kuadratik

diperoleh pada Tabel 5.

Tabel 5. Penyelesaian fungsi tujuan SVD dengan pemrograman kuadratik


Luas Tanam Akhir 47.12 41.922 127.8992

Luas Panen 42.7025 95.2068 57.2006

Hasil gabah 35.8976 56.6334 59.2967

1 2 3 4 5 6 7 8 9 100.78

0.79

0.8

0.81

0.82

0.83

0.84

0.85

0.86

ruas kiri

ruas kanan

1 2 3 4 5 6 7 8 9 100.35

0.4

0.45

0.5

ruas kiri

ruas kanan

1 2 3 4 5 6 7 8 9 10-1.5

-1.48

-1.46

-1.44

-1.42

-1.4

-1.38

-1.36

-1.34

ruas kiri

ruas kanan



Menggunakan pemrograman kuadratik diperoleh hasil yang lebih optimal dibandingkan

dengan ACO. Hasil optimasinya juga menunjukkan periode III merupakan periode optimal.

SIMPULAN DAN SARAN

Analisis hasil panen padi berdasarkan ACO yang parameternya ditentukan

menggunakan SVD memberikan hasil bahwa periode III merupakan periode optimal. Hal ini

mendukung hasil penelitian pada data yang sama dengan analisis menggunakan pemrograman

kuadratik dan parameter ditentukan berdasarkan metode kuadrat terkecil bahwa periode III

merupakan periode optimal. Menggunakan fungsi tujuan yang diperoleh dari SVD dan

mengoptimasi dengan pemrograman kuadratik periode III merupakan periode yang optimal.

Hasil ACO jika dibandingkan dengan pemrograman kuadratik lebih optimal pemrograman

kuadratik.

DAFTAR PUSTAKA

Anderson, E. dkk.(1999). LAPACK User's Guide Third Edition, SIAM, Philadelphia.

(http://www.netlib.org/lapack/lug/lapack_lug.html)

Chang, P.T. dkk. (2008). Ant colony optimization system for a multi-quantitative and

qualitative objective job-shop parallel-machine-scheduling problem. International

Journal of Production Research,Vol. 46, No. 20, 15 October 2008, 5719–5759.

Dewi, V.P. Parhusip, H.A. & Linawati, L. (2013). Analisis hasil panen padi menggunakan

pemodelan kuadratik. Prosiding (dalam proses), Seminar Nasional Matematika VII

yang diselenggarakan oleh jurusan Matematika FMIPA dan Prodi Pendidikan

Matematika Program Pasca Sarjana UNNES tanggal 26 Oktober 2013.Semarang:

Universitas Negeri Semarang.

Parhusip, H.A. &Martono, Y.(2012). Optimization Of Colour Reduction For Producing

Stevioside Syrup Using Ant Colony Algorithm Of Logistic Function, proceeding of The

Fifth International Symposium on Computational Science,ISSN:2252-7761,Vol1, pp91-

101, GMU.

Peressini, A.L. Sullivan, F.E. & Uhl, J. (1998). The Mathematics of Nonlinear Programing,

Springer Verlag, New York,Inc.

Rao, S.S. (2009). Engineering Optimization, Theory and Practice, John Wiley & Sons, Inc.,

Hoboken, New Jersey.

Seo, M. & Kim, D. (2010). Ant colony optimisation with parameterised search space for the job

shop scheduling problem. International Journal of Production Research.Vol. 48, No. 4,

15 February 2010, 1143–1154

Watkins, D.S. (1991). Fundamentals of Matrix Computations, John Wiley & Sons, New York.

http://www.netlib.org/lapack/lug/lapack_lug.html

kristalografi bidang datar batik capmath.fkip.uns.ac.id/wp-content/uploads/2014/06/ruang-7.pdf ·...

Documents