Partisi Maksimum pada Poligon

Partisi Maksimum pada Poligon Muhammad Nassirudin - 13511044 Program Studi Teknik Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, Indonesia [email protected]

Abstrak—Poligon (segibanyak) merupakan sebuah bangun datar yang dibentuk dari sejumlah titik. Titik-titik tersebut kemudian dihubungkan satu dengan yang lain sehingga terbentuklah suatu daerah/lintasan tertutup. Poligon tersebut juga dapat dibagi-bagi lagi menjadi daerah-daerah yang lebih kecil dengan menghubungkan setiap dua titik pada poligon dengan sebuah garis lurus. Pembuatan makalah ini didasarkan pada kasus tersebut. Penelitian akan dilakukan untuk menjawab pertanyaan berapa paling banyak pembagian daerah/partisi yang dapat diperoleh dengan cara membagibagi poligon seperti cara yang telah disebutkan di atas. Dalam penelitian ini, poligon dengan buah titik akan dilambangkan dengan sementara banyak pembagian daerah maksimumnya dilambangkan dengan notasi . Banyaknya partisi/pembagian daerah maksimum akan disajikan sebagai suatu fungsi dari banyaknya titik, , dari poligon. Metode dasar yang digunakan adalah mencacah (counting), pembuktian dengan induksi matematika, dan perhitungan kombinasi. Pada akhir dari penelitian ini, didapatkan hasil bahwa banyaknya daerah maksimum dapat diperoleh hanya dengan mengetahui banyaknya titik pada poligon. Selain itu, didapatkan juga suatu rumus dalam bentuk yang eksplisit yang dapat digunakan untuk menghitungnya. Kata Kunci—Garis, Partisi Maksimum, Poligon, Rumus Eksplisit, Titik.

Pada makalah ini, penelitian tidak hanya dilakukan ketika banyaknya titik , tetapi juga untuk sebarang bilangan bulat positif . Dengan demikian, permasalahan yang dapat diselesaikan dengan hasil dari penelitian ini lebih luas. Banyaknya partisi/pembagian daerah maksimum, , dapat dinyatakan sebagai suatu fungsi dari banyaknya titik, , pada poligon. Selain itu, fungsi ini pada akhirnya dapat dinyatakan sebagai suatu rumus dalam bentuk eksplisit, yaitu hanya melibatkan variabel . Hal ini sangat memudahkan perhitungan — perhitungan cukup dilakukan sekali dan langsung didapatkan hasilnya. Penentuan rumus dilakukan dalam beberapa tahap. Pertama, akan diteliti untuk kasus-kasus trivia-mudah, yaitu ketika nilai , dengan cara mencacah satu per satu. Tahap kedua adalah melihat apakah ada pola dalam perhitungannya yang mungkin akan memberikan petunjuk menuju hasil akhir. Dalam tahap ini, akan diambil sebagai langkah awal. Tahap yang terakhir adalah melakukan perhitungan yang analog dengan kasus namun kasus yang dibahas lebih umum, yaitu untuk sebarang nilai . Selain itu, langkah-langkah induksi dan perhitungan kombinatorik juga akan dilakukan dalam beberapa identitas yang digunakan dalam perhitungan.

I. PENDAHULUAN Suatu hari, Pak Zeta membuat sebuah papan dengan 7 buah paku yang ditancapkan. Pak Zeta memberikan papan tersebut kepada adik dan adik melingkarkan karet pada setiap 3 paku pada papan tersebut sehingga papan tersebut terbagi-bagi menjadi daerah-daerah yang lebih kecil. Dari semua kemungkinan peletakan paku-paku, berapakah paling banyak daerah yang dapat diperoleh adik? Apakah syarat cukup dan syarat perlu untuk peletakan paku sehingga pembagian daerah maksimum didapat? Sekiranya itulah gambaran persoalan yang dapat dijawab dengan hasil yang diperoleh dari penelitian ini. Paku-paku pada papan tersebut dapat dianggap sebagai titik-titik dari poligon . Karet-karet yang dilingkarkan pada setiap 3 paku membuat setiap paku/titik pada papan terhubung oleh sebuah garis lurus. Segmen-segmen karet yang menumpuk pada sepasang paku/titik dianggap sebagai satu garis. Dengan demikian, persoalan menjadi mencari banyaknya partisi maksimum yang dapat diperoleh dari poligon .

Makalah IF2091 Struktur Diskrit – Sem. I Tahun 2011/2012

II. DASAR TEORI A. Poligon Poligon (dapat juga disebut sebagai segibanyak) merupakan suatu bangun datar (2D) yang memiliki banyak sisi. Yang manjadi ciri khas dari poligon adalah semua sisinya terhubung membentuk suatu lintasan tertutup. Dalam makalah ini, digunakan notasi untuk menyatakan poligon dengan titik. Poligon yang sering kita temui dalam kehidupan sehari-hari, misalnya, adalah segitiga (trigon/ ), segiempat (tetragon/ ), segilima (pentagon/ ), dan segidelapan (oktagon/ ). Perhatikan bahwa poligon hanya kita definisikan untuk . Beberapa istilah dan sifat dari poligon yang akan sering digunakan dalam makalah ini adalah sebagai berikut. 1. Poligon sederhana, yaitu poligon yang tidak memiliki sisi-sisi yang bersilangan. 2. Poligon kompleks, yaitu poligon yang memiliki sisisisi yang bersilangan. 3. Konveks, yaitu poligon yang semua sudut dalamnya

kurang dari . Konkaf, yaitu poligon yang memiliki sudut dalam lebih dari . Sebagai kesepakatan, akan digunakan kaidah-kaidah berikut dalam meneliti poligon pada makalah ini. i. Pemberian nama setiap titik dilakukan dengan memilih satu titik sebagai titik awal dan diberi nama . Dari dipilih titik yang terhubung dengannya dengan arah yang berlawanan dengan arah gerak jarum jam. Titik tersebut kemudian dinamakan . Proses ini terus dilakukan hingga mencapai . Didefinisikan . ii. Jika titik dan terhubung, sisi yang dibentuk dari kedua titik itu dilambangkan dengan . Hal yang sama juga berlaku untuk setiap garis (partisi) yang menghubungkan titik dan . Garis tersebut akan dilambangkan dengan . Dalam makalah ini, . iii. Tidak ada sudut dalam dari yang bernilai . Dengan kata lain, tidak ada 3 titik pada yang terletak pada satu garis lurus (kolinear). iv. Partisi/pembagian daerah yang dioperasikan terhadap poligon dilakukan dengan cara menghubungkan setiap 2 titik pada dengan sebuah garis lurus. Daerah yang dihitung hanya daerah dalam dari . Untuk mempermudah dalam memahami kesepakatan ini, pada gambar 2-1 diberikan parameter-parameter pada poligon . Batas-batas/lintasan poligon diberikan oleh garis merah sementara garis-garis partisi diberikan oleh warna hitam. 4.



langkah 2, dengan asumsi benar akan dibuktikan bahwa juga benar dengan .

C. Kombinatorik Kombinatorik merupakan salah satu cabang ilmu dari matematika yang mempelajari struktur benda yang berhingga atau diskrit. Beberapa aturan dasar dalam kombinatorik adalah aturan penjumlahan (rule of sum) dan aturan perkalian (rule of product). Salah satu alat dari cabang ilmu ini yang digunakan dalam penelitian ini adalah perhitungan kombinasi. Kombinasi biasa dilambangkan dengan

atau

dengan

bilangan bulat nonnegatif. Per definisi, kombinasi berarti banyak cara mengambil objek dari n buah objek tanpa memerhatikan urutannya. Secara matematis, kombinasi dapat ditulis sebagai

dengan menyatakan bilangan faktorial dari dan kasus khusus . Salah satu identitas pada operasi kombinasi yang digunakan dalam penelitian adalah

D. Deret Aritmatika Deret Aritmatika merupakan suatu deret yang selisih dari dua suku yang berurutannya selalu konstan. Perhitungan suku ke- dapat dilakukan dengan rumus sementara jumlah dari

suku pertamanya diberikan oleh

dengan merupakan bilangan real yang menjadi suku pertamanya dan adalah konstanta yang merupakan selisih dari dua suku yang berurutan (beda).

III. PEMBUKTIAN BEBERAPA IDENTITAS Gambar 2-1 Parameter-parameter pada poligon

B. Induksi Matematika Induksi matematika merupakan salah satu metode yang dapat digunakan dalam membuktikan suatu pernyataan. Biasanya pernyataan yang dibuktikan berhubungan dengan bilangan bulat positif. Induksi matematika merupakan suatu metode pembuktian yang baku dan berterima di kalangan penelitian ilmiah. Secara singkat, proses pembuktiannya dilakukan dalam beberapa langkah seperti berikut. Misalkan merupakan pernyataan yang ingin dibuktikan dengan adalah suatu bilangan bulat. Jika ingin dibuktikan bahwa juga berlaku/benar untuk semua bilangan bulat ,  langkah 1, membuktikan bahwa benar, Makalah IF2091 Struktur Diskrit – Sem. I Tahun 2011/2012

Pada pengerjaan makalah ini, dipakai setidaknya tiga identitas matematika dasar dalam perhitungannya. Pembuktian yang dilakukan pada identitas pertama akan memanfaatkan prinsip induksi matematika. Tentu saja dengan mencari terlebih dahulu rumusan hipotesisnya. Cara ini memang tidak alami, namun ini merupakan cara yang baku dan valid. Selain itu, agar tidak monoton, pada pembuktian identitas kedua dan ketiga akan dipakai pendekatan yang berbeda namun tetap sah. Metode yang dipakai sengaja dibedakan satu dengan yang lainnya agar terlihat perbedaan, kelebihan, kekurangan dan ciri khas dari masing-masing metode. Pada setiap pembuktian identitas, kita gunakan dan sebagai bilangan bulat positif.

A. Identitas Pertama

banyaknya cara memilih

buah objek adalah

. Dengan demikian, lemma kita telah terbukti. Untuk , pembuktiannya diberikan pada tabel 3-1 dengan cara mencacah biasa. Sekarang, akan dibuktikan dengan induksi pada bahwa identitas tersebut benar untuk sebarang bilangan bulat positif .

Lemma 2.

Misalkan untuk

Bukti. Kita akan memulai dengan memanfaatkan fakta

benar bahwa

, akan

dibuktikan bahwa pernyataan juga benar untuk . Perhatikan bahwa

bahwa

. Untuk

, kita dapatkan

benar. Asumsikan pernyataan benar untuk untuk

Dengan demikian, bukti selesai dan pernyataan benar untuk semua bilangan bulat positif . Sekilas memang cara ini sangat mudah, namun letak kesulitan sebetulnya terletak dari mana didapatkan rumusan hipotesis . Kadang seseorang dapat langsung menemukannya, kadang butuh usaha dan coba-coba. Sebagai perbandingan, metode yang dipakai pada pembuktian identitas kedua jauh lebih alami namun agak tricky. Tabel 3-1 Pembuktian

, maka

dengan memanfaatkan lemma 1. Berdasarkan prinsip induksi matematika, lemma 2 telah terbukti dengan sah. Sekarang, kita siap membuktikan identitas kedua ini. Pertama kita akan nyatakan sebagai suatu hasil operasi dari kombinasi. Perhatikan bahwa

memiliki koefisien

pada penjabarannya (dan seperti itu pula untuk bilangan lebih dari 3), sehingga pastilah hanya dipengaruhi oleh

,

, dan sebuah konstanta. Kita

tulis 1 2 3

1 3 6

1 3 6

Dengan menjabarkan kombinasi dan mengelompokkan suku-suku sejenis, dengan mudah kita dapatkan , , dan . Jadi,

B. Identitas Kedua Dari sini, kita dapatkan Pada pembuktian identitas kedua ini akan digunakan pendekatan yang berbeda. Kita akan menggunakan pendekatan kombinatorik. Untuk itu, akan dibuktikan dua buah lemma berikut ini terlebih dahulu. Lemma 1.

Bukti. Kita tahu bahwa

dapat diinterpretasikan

sebagai banyaknya cara mengambil buah objek dari buah objek. Selain itu, pengambilan buah objek itu dapat juga dilakukan seperti berikut. Kita pisahkan satu buah objek sehingga sekarang tersisa objek. Jika kita inginkan objek yang dipisahkan tadi tidak termasuk objek yang dipilih, kita harus memilih buah objek dari objek yang ada. Banyaknya cara untuk itu adalah . Jika kita ingin objek yang dipisahkan itu harus menjadi objek yang terpilih, kita tinggal memilih objek lagi dari objek yang ada. Banyaknya cara untuk melakukannya adalah

. Dengan demikian,


Dengan demikian, identitas kedua telah kita buktikan. Meskipun cara yang dipakai tidak semudah cara yang dipakai pada pembuktian identitas pertama, cara kedua ini jauh lebih alami dan ilmiah—tidak perlu coba-coba. Perhatikan juga bahwa pada perhitungan ini kita mengambil

ketika

IV. PEMBAHASAN

.

C. Identitas Ketiga

Dengan cara ketiga ini, kita akan memanfaatkan hasil yang telah didapatkan sebelumnya, yaitu identitas pertama dan kedua. Kita mulai dari penjabaran polinomial berpangkat 4 berikut.

Andaikan kita punya

Dengan demikian, semua identitas yang diperlukan telah dibuktikan.

, maka

Di sisi lain, kita juga punya

Untuk sekarang dan seterusnya, kita akan gunakan sebagai sebuah bilangan bulat positif yang menunjukkan banyaknya titik pada poligon dan adalah bilangan bulat positif dengan . Selain itu, kita ambil batas bawah karena poligon hanya terdefinisi dalam daerah tersebut. Sebagai permulaan, kita akan ambil dan sebagai kasus pembuka. Perlu diingat kembali bahwa banyaknya pembagian daerah/partisi maksimum pada poligon dinotasikan dengan . Dengan mudah dapat kita lihat pada gambar 4-1 (a) dan (b) bahwa dan . Untuk kasus , pada gambar hanya diberikan kasus ketika sederhana dan konveks, sementara kasus ketika kompleks atau konkaf belum ditangani. Alih-alih kita membahas hanya untuk , kita akan tunjukkan secara umum bahwa partisi maksimum akan didapatkan hanya jika sederhana dan konveks.

(b) Gambar 4-1 Partisi pada Poligon ketika

Dengan menggabungkan hasil di atas dengan hasil yang sebelumnya, didapatkan

Andaikan kita punya kompleks serta dan adalah sisi-sisi yang bersilangan dengan . Misalkan juga kedua sisi tersebut berpotongan pada titik , maka kita dapatkan daerah (segitiga) dan bukan merupakan daerah dalam dari poligon. Padahal jika sisi-sisi yang bersilangan ini kita hilangkan dengan mengambil dan sebagai sisi alihalih dan , kita dapatkan daerah dan sebagai daerah dalam poligon. Tentu saja dengan demikian daerah partisi poligon menjadi lebih banyak. Proses pengalihan sisi ini membuat poligon tidak memiliki sisi-sisi yang bersilangan. Dengan kata lain, haruslah merupakan poligon sederhana. Misalkan menyatakan bahwa dapat dipartisi maksimum, maka secara matematis dapat ditulis yang ekivalen dengan kontraposisinya

Jadi, yaitu Makalah IF2091 Struktur Diskrit – Sem. I Tahun 2011/2012

harus sederhana (karena lawannya poligon

kompleks adalah poligon sederhana). Selanjutnya, andaikan sekarang konkaf dan misalkan adalah titik pada poligon dengan sudut dalam lebih dari . Kita punya daerah berada di luar poligon . Padahal dengan menggeser titik sedemikian sehingga sudut dalam kurang dari , kita dapatkan daerah berada di dalam poligon . Tentu saja hal ini menambah daerah partisi sehingga partisi maksimum dapat dicapai. Namun, konsekuensi dari proses ini adalah membuat tidak memiliki sudut dalam yang lebih dari . Dengan kata lain, haruslah konveks. Secara matematis, dapat ditulis yang ekivalen dengan yaitu, konveks (lawannya konkaf). Dari dua pembahasan di atas kita dapatkan bahwa sederhana dan konveks adalah syarat perlu partisi maksimum tercapai. Dari sini, poligon yang akan kita bahas seterusnya pasti sederhana dan konveks. Satu garis yang melintasi suatu daerah pasti akan membagi dua daerah tersebut. Dengan fakta/aksioma ini, kita akan mencari nilai . Sebelumnya, perhatikan bahwa tiga buah garis yang saling tidak sejajar dapat berpotongan pada satu titik. Keadaan ini disebut dengan konkuren. Begitu juga tiga buah titik yang saling berbeda bisa saja berada pada satu garis lurus. Keadaan ini disebut sebagai kolinear. Berdasarkan kesepakatan yang telah dibahas sebelumnya, kondisi kolinear tidak mungkin terjadi. Misalkan kita punya poligon yang memiliki 3 garis yang konkuren dengan banyaknya pembagian daerah adalah . Kita dapat menggeser salah satu titik sedemikian sehingga ketiga garis tidak konkuren lagi. Ketika hal tersebut dilakukan, kita dapatkan sebuah daerah baru (berupa segitiga) yang dibatasi oleh ketiga garis tersebut. Perhatikan bahwa daerah ini sebelumnya merupakan sebuah titik dan belum dihitung. Jadi, konfigurasi yang baru ini memiliki buah partisi daerah—lebih banyak dari yang sebelumnya. Perlu ditinjau juga bahwa dalam kasus poligon kita ini, dua buah garis yang berpotongan di dalam poligon tidak dapat kita buat menjadi tidak berpotongan. Begitu juga sebaliknya. Sebagai contoh, jika kita ambil sebagai salah satu garis, setiap garis dengan dan pasti akan berpotongan dengan . Sebaliknya, jika atau , kedua garis tersebut tidak akan berpotongan. Dengan begitu, selain kekonkurenan, tidak ada lagi kondisi yang dapat kita kendalikan di dalam poligon. Jadi, dapat kita simpulkan bahwa partisi maksimum akan diperoleh ketika tidak ada 3 garis yang konkuren di dalam . Misalkan menyatakan terdapat tiga garis pada poligon yang konkuren di dalam poligon, maka secara matematis kondisi di atas dapat ditulis Selain itu, dari pembahasan di atas juga dapat ditarik kesimpulan jika terdapat 3 garis yang konkuren di dalam , partisi maksimum tidak akan diperoleh. Secara Makalah IF2091 Struktur Diskrit – Sem. I Tahun 2011/2012

matematis, ditulis yang ekivalen dengan Dari dua hasil terakhir yang kita dapat ini, dapat ditarik kesimpulan Dengan kata lain, tidak terjadinya konkuren (di dalam ) merupakan syarat cukup sekaligus syarat perlu agar partisi maksimum tercapai. Sekarang, kita akan coba melihat pola perhitungan pada . Pertama, kita hubungkan sisi-sisinya hingga menjadi sebuah poligon konveks sederhana. Kemudian, dari titik kita tarik garis partisi menuju dan . Sekarang, terdapat 3 daerah partisi pada . Setelah itu, kita pindah ke titik dan tarik garis menuju (menambah 2 daerah) dan (menambah 3 daerah). Sekarang, kita dapatkan tambahan daerah sebanyak daerah. Terakhir, dari kita tarik garis menuju . Proses ini menambah daerah partisi sebanyak 3 daerah. Jadi, . Proses ini dapat dilihat pada gambar 4-2 (a)-(d).

1 1

(a)

1

3

6 7

4 5

(b)

1

2

3

2

2

3

6 8

7

4 5

8 10

11

9

(c) (d) Gambar 4-2 Partisi Maksimum pada Dalam perhitungan di atas, ada dua kaidah penting yang digunakan. Pertama, penarikan garis dilakukan dengan terurut dari sampai dan, untuk setiap nilai , nilai terurut dari sampai . Kedua, jika suatu daerah dibagi dua oleh sebuah garis, daerah yang lama kita ambil sebagai daerah yang lebih kiri-atas; daerah baru adalah daerah yang lebih kanan-bawah. Pada gambar 4-2 setiap daerah telah dinomori sesuai dengan kedua kaidah ini. Sekarang, kita akan beranjak ke kasus yang lebih umum. Misalkan adalah poligon sederhana dan

konveks. Dari , kita tarik garis ke titik hingga sehingga poligon terbagi menjadi daerah. Ketika kita tarik sebuah garis melewati sebuah daerah akan terbentuk sebuah daerah baru. Jadi, jika terdapat buah daerah yang dilintasi, akan terbentuk buah daerah baru. Dengan aksioma tersebut, jika kita tarik garis dari menuju , akan terbentuk 2 daerah baru disebabkan garis memotong dua buah daerah. Hal yang sama juga berlaku jika kita buat garis , akan terbentuk 3 daerah baru. Sekilas bisa kita terka bahwa angka-angka ini akan membentuk sebuah deret aritmatika dengan beda 1. Jadi, ketika titik dan dihubungkan, akan terbentuk daerah baru. Perhatikan bahwa adalah suku kekarena suku pertamanya adalah . Bagaimanapun, hal tersebut belum valid karena belum ada bukti kecuali terkaan. Sekarang, kita akan menyelidiki dari mana angka-angka tersebut berasal. Suatu daerah pasti dibatasi oleh sebuah garis. Ketika ada garis yang memotong daerah tersebut, garis tersebut pasti akan memotong garis pembatas daerah itu sehingga terjadi perpotongan. Selain itu, sebuah daerah baru pasti akan terbentuk ketika sebuah perpotongan terjadi. Misalnya, jika kita tarik garis dari menuju pada contoh sebelumnya, pasti garis tersebut akan memotong garis , , dan sehingga akan terbentuk 3 buah daerah baru. Namun, daerah baru juga akan terbentuk ketika garis tersebut mencapai titik yang menyebabkan kita harus menambahkan hasilnya dengan 1.

Gambar 4-3 Proses Partisi pada Poligon Lebih jauh lagi, mencari banyaknya penambahan daerah baru kemudian berubah menjadi mencari banyaknya perpotongan garis yang terjadi ketika garis dibentuk. Pada kasus penarikan garis dari , dengan jelas kita lihat bahwa setiap titik hanya terhubung dengan sehingga pastilah garis yang terhubung dari setiap titik hanya 1. Konsekuensinya, banyaknya perpotongan yang terjadi akan sama dengan banyaknya titik pada lintasan antara dengan . Dengan demikian pada penarikan garis , akan terbentuk daerah. Hal ini sesuai dengan terkaan kita sebelumnya sehingga terkaan kita terbukti benar. Dari sini, kita dapatkan jika semua garis telah terhubung akan terdapat


daerah baru. Selanjutnya, kita akan membahas kasus yang lebih umum lagi. Pandang garis adalah garis yang ingin kita buat. Disebabkan setiap titik , , telah dihubungkan ke setiap titik , , ketika kita ingin menghubungkan garis dari titik , telah terdapat tepat garis yang terhubung ke setiap titik . Karena terdapat buah titik pada lintasan antara dengan , kita dapatkan banyaknya perpotongan yang terjadi adalah perpotongan. Hal ini berlaku untuk kasus . Dengan demikian, banyakya daerah baru yang terbentuk adalah daerah dan jika semua nilai telah dimasukkan, akan terbentuk

daerah baru. Lebih jauh lagi, karena nilai berjalan dari sampai , kita dapatkan daerah yang terbentuk sebanyak

buah. Ditambah dengan kasus ketika adalah total partisi maksimum dari , yaitu

, hasilnya

Beberapa perhitungan dengan rumus yang kita dapat ini untuk kasus s.d. diberikan oleh tabel 4-1. Tabel 4-1 Nilai dengan Rumus yang Didapat 3 4 5 6 7 8 9 1 4 11 25 50 91 154

V. LEBIH JAUH TENTANG PARTISI MAKSIMUM Dari pembahasan yang telah dipaparkan pada bab sebelumnya, kita akan meninjau ulang cara yang dipakai untuk mencari dan menggunakan pendekatan lain yang lebih elegan. Coba diingat kembali bahwa pada penarikan garis , , , banyaknya daerah baru yang terbentuk sama dengan banyaknya perpotongan garis ditambah 1. Jika semua garis telah dibuat, total perpotongan-perpotongan garis ini akan sama dengan total perpotongan garis yang ada di dalam poligon . Selain itu, angka 1 akan dijumlah terusmenerus sebanyak

6 kali. Namun, kita belum menangani kasus ketika =1,

Dengan memasukkan rumus eksplisit untuk , dan , kita dapatkan

,

jadi hasilnya harus ditambah dengan . Sekarang, kita tinggal mencari banyaknya perpotongan garis di dalam poligon . Sebuah perpotongan garis (dalam kasus kita ini) hanya akan terjadi jika dua buah garis saling berpotongan. Jadi, untuk sebarang dua garis berbeda yang kita ambil, pasti terjadi tepat sebuah perpotongan. Namun, kita tidak tahu apakah perpotongan terjadi di dalam atau di luar poligon. Untuk menangani masalah ini, kita ingat kembali bahwa keadaan yang kita punya adalah konveks. Jika kita mengambil sebuah bangun datar, alih-alih garis, perpotongan diagonalnya pasti terjadi di dalam bangun tersebut. Kedua diagonal ini menyatakan dua garis yang kita tinjau. Karena bangun datar ini memiliki tepat dua buah diagonal, pastilah bangun datar yang cocok adalah segiempat (tetragon/ ). Sebuah segiempat dibentuk dari tepat 4 buah titik yang berbeda, sehingga pada

akan ada

buah segiempat

yang berbeda. Perlu diperhatikan bahwa pada sebuah segiempat titik perpotongan diagonalnya unik. Sebuah titik pada poligon juga pasti adalah perpotongan sepasang Makalah IF2091 Struktur Diskrit – Sem. I Tahun 2011/2012

garis yang unik. Sepasang garis yang unik akan berujung, masing-masing, pada 2 titik yang unik sehingga terdapat 4 buah titik yang unik yang akan membentuk sebuah segiempat yang unik. Dengan demikian, banyaknya perpotongan garis di dalam poligon akan sama dengan banyaknya segiempat yang dapat dibentuk dari poligon, yaitu

perpotongan.

Jadi, dengan menggabungkan hasil yang baru kita dapat ini dengan hasil yang sebelumnya, kita dapatkan

atau dengan menyatakan pembagian daerah/partisi maksimum yang dapat diperoleh pada . Tidak adanya 3 (atau lebih) garis yang konkuren di dalam poligon merupakan syarat cukup dan syarat perlu agar partisi maksimum tercapai. Poligon berupa poligon sederhana dan konveks merupakan syarat perlu agar partisi maksimum tercapai.

DAFTAR PUSTAKA [1]

dengan bantuan lemma 1 pada bab III. Jika dihitung untuk s.d. , hasil yang diperoleh sama seperti data pada tabel 4-1. Memang, dengan sedikit usaha, namun tidak sulit, didapatkan

Jika

diperhatikan

kemunculan bentuk

dengan

seksama,

dapat diinterpretasikan

[4]

PERNYATAAN Dengan ini saya menyatakan bahwa makalah yang saya tulis ini adalah tulisan saya sendiri, bukan saduran, atau terjemahan dari makalah orang lain, dan bukan plagiasi. Bandung, 16 Desember 2012

.

Pencarian rumus dengan pendekatan ini memang jauh lebih elegan dan tidak rumit jika dibandingkan dengan pendekatan yang dipakai sebelumnya. Selain itu, metode ini tidak melibatkan perhitungan panjang yang rentan dengan ketidaktelitian dan kesalahan hitung, sehingga kemungkinannya kecil untuk terjadi kesalahan perhitungan. Meskipun begitu, cara ini dapat dibilang agak karena membutuhkan pemahaman konsep yang baik tentang kombinatorik, sementara cara sebelumnya lebih straight forward ‘langsung’ dan hanya membutuhkan kemampuan menghitung yang baik. Setelah mendapatkan hasil ini, sekarang dapat kita jawab persoalan dari studi kasus yang dipaparkan pada Bab Pendahuluan, yaitu .

VI. KESIMPULAN Misalkan

[3]

sebetulnya

dengan maksud mengambil buah titik dari titik untuk membentuk sebuah garis. Keterkaitannya dengan kasus kita adalah pada penambahan 1 pada setiap perhitungan partisi daerah yang disebabkan oleh dibuatnya garis . Dengan alasan ini, dapat kita katakan setiap pembuatan sebuah garis menyebabkan bertambahnya satu buah daerah baru (yang belum diwakilkan oleh perpotongan garis), namun hal ini tidak berlaku untuk setiap garis yang terhubung ke titik (karena ). Sehingga, sisa titik yang perlu kita tinjau tinggal dan banyaknya garis yang dapat dibuat adalah

[2]

Munir, Rinaldi, Diktat Kuliah IF2091 – Struktur Diskrit. Bandung: Program Studi Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung, 2008. Larson, Loren C., Problem-Solving Through Problems. New York: Springer-Verlag, 1983. http://www.mathsisfun.com/geometry/polygons.html, 6 Desember 2012, 12:40:59 GMT. http://mathworld.wolfram.com/ArithmeticSeries.html, 4 Desember 2012 13:51:32 GMT.

adalah suatu poligon dengan

titik, maka


Muhammad Nassirudin NIM. 13511044

Partisi Maksimum pada Poligon

Recommend Documents