ERD

APA ITU ERD???

Diagram Hubungan Entitas atau entity relationship diagram merupakan model data berupa notasi grafis dalam pemodelan data konseptual yang menggambarkan hubungan antara penyimpan. Model data sendiri merupakan sekumpulan cara, peralatan untuk mendeskripsikan data-data yang hubungannya satu sama lain, semantiknya, serta batasan konsistensi. Model data terdiri dari model hubungan entitas dan model relasional. Diagram hubungan entitas ditemukan oleh Peter Chen dalam buku Entity Relational Model-Toward a Unified of Data. Chen mencoba merumuskan dasar-dasar model dan setelah itu dikembangkan dan dimodifikai oleh Chen dan banyak pakar lainnya. Pada saat itu diagram hubungan entitas dibuat sebagai bagian dari perangkat lunak yang juga merupakan modifikasi khusus, karena tidak ada bentuk tunggal dan standar dari diagram hubungan entitas.

Kegunaan

Diagram hubungan entitas digunakan untuk mengkonstruksikan model data konseptual, memodelkan struktur data dan hubungan antar data dan mengimplementasikan basis data secara logika maupun secara fisik dengan DBMS (Database Management system). Dengan diagram hubungan entitas ini kita dapat menguji model dengan mengabaikan proses yang harus dilakukan. Diagram hubungan entitas dapat membantu dalam menjawab persoalan tentang data yang diperlukan dan bagaimana data tersebut saling berhubungan..

Symbol

1. Persegi panjang, menyatakan himpunan entitas.

2. Oval, menyatakan atribut (atribut key digaris bawahi).

3. Belah ketupat, menyatakan himpunan relasi.

4. Garis, menyatakan penghubung antara himpunan relasi dengan himpunan entitas dan himpunan entitas dengan atributnya.

Entitas

Entitas adalah suatu objek yang dapat didefinisikan dalam lingkungan pemakai, sesuatu yang penting bagi pemakai dalam konteks sistem yang akan dibuat. Sebagai contoh pelanggan, pegawai dll. Seandainya A adalah seorang pegawai maka A adalah isi dari pegawai, sedangkan jika B adalah seorang pelanggan maka B adalah isi dari pelanggan. Karena itu harus dibedakan entitas sebagai bentuk umum dari deskripsi tertentu dan isi entitas seperti A dan B dalam contoh di atas.

Fisik Entitas

Entitas yang bersifat fisik. Contoh : pegawai, guru, dan karyawan.

Konsep Entitas

Entitas yang tidak bersifat konsep. Contoh: gaji,sekolah

Macam-Macam Atribut

Atribut terdiri dari atribut sederhana atau atormis, atribut komposit, atribut berharga tunggal. atribut null-value, atribut kunci, atribut bernilai banyak dan atribut turunan. Masing-masing atribut memiliki ciri tersendiri. Atribut atormis tidak dapat dibagi-bagi menjadi atribut yang sederhana. Atribut komposit adalah atribut yang dapat dipecah menjadi atribut lain, misalnya atribut alamat dapat dipecah menjadi atribut jalan, kecamatan, kelurahan,kota serta kode pos. atribut komposit digunakan pada database untuk kemudahan menjawab pertanyaan-pertanyaan tertentu dalam database atribut berharga tunggal mempunyai satu harga untuk entitas tertentu, atribut null-value tidak mempunyai nilai, atribut kunci merupakan atribut unik dari suatu entitas dan nilai dari atribut kunci akan berbeda untuk masing-masing entitas.atribut bernilai banyak adalah atribut yang entitasnya lebih dari satu, misalnya adalah atribut hobi. Atribut hobi ini bisa terdiri dari atribut berenang, atribut voli dan atribut berbelanja.atribut turunan merupakan atribut yang didapat dari atribut lainnya.Pada entitas pegawai terdapat atribu nomor induk yang biasanya terkandung nilai tahun masuk, misalnya NIP =5195025, berarti Pegawai yang bersangkutan masuk pada tahun 1995), maka jika kita tambahkan atribut Lama_Kerja pada entitas Pegawai, atribut Lama_Kerja dapat kita hitung dengan cara mengurangkan tahun dimana perhitungan dilakukan (katakanlah 2005) dengan tahun mahasiswa yang bersangkutan masuk ke Instansi (Hasilnya 10 tahun).

Hubungan Relasi

Relasi adalah hubungan antara suatu himpunan dengan himpunan entitas yang lainnya. Pada penggambaram diagram hubungan entitas, relasi adalah perekat yang menghubungkan suatu entitas dengan entitas lainnya. Relasi merupakan hubungan yang berarti antara suattu entitas dengan entitas lainnya. Frasa ini berimplikasi bahwa relasi mengijinkan untuk menjawab pertanyaan-pertanyaan yang berkaitan dengan hubungan suatu entits dengan lainya. Hubungan dibedakan antar bentuk hubungan antar entitas dengan isinya masing-masing. Misalnya kasus hubungan antara entitas pegawai dan entitas bagian adalah jam kerja, sedangkan isi hubungannya dapat berupa total jam kerja, gaji lembur. Relasi digambarkan dalam bentuk intan. Pada model data relasi hubungan antar data dihubungkan dengan kunci relasi. Tipe hubungan di antara beberapa buah tipe entitas adalah kumpulan dari relasi di antara entitas-entitas dari tipe entitas tersebut.

Notasi ERD

Ada sejumlah konvensi mengenai Notasi  ERD. Notasi klasik sering digunakan untuk model konseptual. Berbagai notasi lain juga digunakan untuk menggambarkan secara logis dan fisik dari suatu basis data, salah satunya adalah IDEF1X.

Gambar Erd1

Model ERD

Notasi-notasi simbolik yang digunakan dalam Entity Relationship Diagram adalah sebagai berikut :

Entitas, Adalah segala sesuatu yang dapat digambarkan oleh data. Entitas juga dapat diartikan sebagai individu yang mewakili sesuatu yang nyata (eksistensinya) dan dapat dibedakan dari sesuatu yang lain (Fathansyah, 1999). Ada dua macam entitas yaitu entitas kuat dan entitas lemah. Entitas kuat merupakan entitas yang tidak memiliki ketergantungan dengan entitas lainnya. Contohnya entitas anggota. Sedangkan entitas lemah merupakan entitas yang kemunculannya tergantung pada keberadaaan entitas lain dalam suatu relasi.

Atribut, Atribut merupakan pendeskripsian karakteristik dari entitas. Atribut digambarkan dalam bentuk lingkaran atau elips. Atribut yang menjadi kunci entitas atau key diberi garis bawah.

Relasi atau Hubungan, Relasi menunjukkan adanya hubungan diantara sejumlah entitas yang berasal dari himpunan entitas yang berbeda.

Penghubung antara himpunan relasi dengan himpunan entitas dan himpunan entitas dengan atribut dinyatakan dalam bentuk garis.

Gambar erd2

Contoh ERD

Derajat relasi atau kardinalitas

Menunjukkan jumlah maksimum entitas yang dapat berelasi dengan entitas pada himpunan entitas yang lain. Macam-macam kardinalitas adalah:

Satu ke satu (one to one), Setiap anggota entitas A hanya boleh berhubungan dengan satu anggota entitas B, begitu pula sebaliknya.

Satu ke banyak (one to many), Setiap anggota entitas A dapat berhubungan dengan lebih dari satu anggota entitas B tetapi tidak sebaliknya.

Banyak ke banyak (many to many), Setiap entitas A dapat berhubungan dengan banyak entitas himpunan entitas B dan demikian pula sebaliknya.

Tahap ERD

Tahap pertama pada desain sistem informasi menggunakan model ER adalah menggambarkan kebutuhan informasi atau jenis informasi yang akan disimpan dalam database. Teknik pemodelan data dapat digunakan untuk menggambarkan setiap ontologi (yaitu gambaran dan klasifikasi dari istilah yang digunakan dan hubungan anatar informasi) untuk wilayah tertentu.

Tahap berikutnya disebut  desain logis, dimana data dipetakan ke model data yang logis, seperti model relasional.  Model data yang loguis ini kemudian dipetakan menjadi model fisik , sehingga kadang-kadang, Tahap kedua ini disebut sebagai “desain fisik”.

Secara umum metodologi ERD sebagai berikut:

Erd 3

Metodologi ERD

Contoh Kasus:

Sebuah perusahaan mempunyai beberapa bagian. Masing-masing bagian mempunyai pengawas dan setidaknya satu pegawai. Pegawai ditugaskan paling tidak di satu bagian (dapat pula dibeberapa bagian). Paling tidak satu pegawai mendapat tugas di satu proyek. Tetapi seorang pegawai dapat libur dan tidak dapat tugas di proyek.

Menentukan entitas

Entitasnya : pengawas, bagian, pegawai, proyek

FLOWCHART

Apa itu Flowchart?

Flowchart atau diagram alir merupakan sebuah diagram dengan simbol-simbol grafis yang menyatakan aliran algoritma atau proses yang menampilkan langkah-langkah yang disimbolkan dalam bentuk kotak, beserta urutannya dengan menghubungkan masing masing langkah tersebut menggunakan tanda panah. Diagram ini biasa digunakan untuk mencari penyelesaian suatu masalah dengan menjelaskan apa yang seharusnya dilakukan. Sistem flowchart memberi solusi selangkah demi selangkah untuk penyelesaian masalah yang ada di dalam proses atau algoritma tersebut. Flowchart membuat urutan proses menjadi jelas dan sangat logis sehingga bisa memudahkan kita dalam merancang sebuah program.

Flowchart berfungsi :

»   untuk memudahkan perancangan alur urutan logika suatu program, 

»   memudahkan pelacakkan sumber kesalahan program, 

»   untuk menerangkan logika program. 

»   menolong analis dan programmer untuk memecahkan masalah kedalam segmen-segmen yang lebih kecil 

»   menolong dalam menganalisis alternatif-alternatif lain dalam pengoperasian.

Contoh, penyelesaian lampu yang tidak berfungsi dengan memaparkan langkah-langkah yang harus dilakukan :

Diagram alir

Simbol-simbol Flowchart

Dalam menerapkan/menggunakan flowchart, kita harus mengerti fungsi-fungsi dari berbagai simbol yang tersedia di flowchart agar memudahkan kita untuk memahami langkah-langkah yang kita paparkan di flowchart.

Gambar berikut adalah simbol flowchart yang umum digunakan.

Macam-macam Flowchart

ada 4 jenis diagram alir secara umum: 

·         Diagram Alir Dokumen, menunjukkan kontrol dari sebuah sistem aliran dokumen.

·         Diagram Alir Data, menunjukkan kontrol dari sebuah sistem aliran data.

·         Diagram Alir Sistem, menunjukkan kontrol dari sebuah sistem aliran secara fisik.

·         Diagram Alir Program, menunjukkan kontrol dari sebuah program dalam sebuah sistem.

FLOWCHART DOKUMEN

Diagram Alir Dokumen
Flowchart Paperwork menelusuri alur dari data yang ditulis melalui sistem.
Flowchart Paperwork sering disebut juga dengan Flowchart Dokumen.
Kegunaan utamanya adalah untuk menelusuri alur form dan laporan
sistem dari satu bagian ke bagian lain baik bagaimana alur form dan
laporan diproses, dicatat dan disimpan.

FLOWCHART SISTEM

Diagram Alir Sistem

Flowchart Sistem merupakan bagan yang menunjukkan alur kerja atau apa yang sedang dikerjakan di dalam sistem secara keseluruhan dan menjelaskan urutan dari prosedur-prosedur yang ada di dalam sistem.

Dengan kata lain, flowchart ini merupakan deskripsi secara grafik dari urutan prosedur-prosedur yang terkombinasi yang membentuk suatu sistem.

Flowchart Sistem terdiri dari data yang mengalir melalui sistem dan proses yang mentransformasikan data itu. Data dan proses dalam flowchart sistem dapat digambarkan secara  online (dihubungkan langsung dengan komputer) atau offline (tidak dihubungkan langsung dengan  komputer, misalnya mesin tik, cash register atau kalkulator).

FLOWCHART PROGRAM

Diagram Alir Program

Flowchart Program dihasilkan dari Flowchart Sistem. Flowchart Program merupakan  keterangan yang lebih rinci tentang bagaimana setiap langkah program atau prosedur sesungguhnya dilaksanakan. Flowchart ini menunjukkan setiap langkah program atau prosedur dalam urutan yang  cepat saat terjadi. Programmer menggunakan flowchart program untuk menggambarkan urutan  instruksi dari program komputer. Analis Sistem menggunakan flowchart program untuk  menggambarkan urutan tugas-tugas pekerjaan dalam suatu prosedur atau operasi. 

Langkah-langkah Membuat Flowchart

Beberapa hal yang harus diperhatikan dalam pembuatan sebuah flowchart :

a.  Flowchart digambarkan dari halaman atas ke bawah dan dari kiri ke
     kanan.
b.  Aktivitas yang digambarkan harus didefinisikan secara hati-hati dan
     definisi ini harus dapat dimengerti oleh pembacanya.
c.  Tentukan awal dan akhir secara jelas dan teranalisis.
d.  Setiap langkah dari aktivitas harus diuraikan dengan menggunakan
     deskripsi kata kerja, misalkan “menghitung luas lingkaran”.
e.  Setiap langkah dari aktivitas harus berada pada urutan yang benar.
f.  Lingkup dan range dari aktifitas yang sedang digambarkan harus
    ditelusuri dengan hati-hati. Percabangan-percabangan yang memotong
    aktivitas yang sedang digambarkan tidak perlu digambarkan pada
    flowchart yang sama. Simbol konektor harus digunakan dan
    percabangannya diletakan pada halaman yang terpisah atau hilangkan
    seluruhnya bila percabangannya tidak berkaitan dengan sistem.
g. Gunakan simbol-simbol flowchart yang standar.

Apa itu teori tree ??

TEORI TREE DAN PENERAPANNYA

Dalam matematika, dan lebih khusus dalam teori graf, pohon merupakan graf tak berarah di mana setiap dua simpul dihubungkan dengan tepat satu jalan sederhana. Dengan kata lain, setiap grafik terhubung tanpa siklus sederhana adalah pohon. Hutan adalah suatu kesatuan menguraikan pohon.

Berbagai macam struktur data disebut sebagai pohon dalam ilmu komputer yang setara sebagai grafik diarahkan dengan pohon dalam teori graf, meskipun struktur data tersebut umumnya berakar pohon, sehingga pada kenyataannya diarahkan grafik, dan mungkin juga memiliki memesan tambahan cabang.

           

Pohon (tree) merupakan salah satu bentuk khusus dari struktur suatu graf. Misalkan A merupakan sebuah himpunan berhingga simpul (vertex) pada suatu graf G yang terhubung. Untuk setiap pasangan simpul di A dapat ditentukan suatu lintasan yang menghubungkan pasangan simpul tersebut. Suatu graf terhubung yang setiap pasangan simpulnya hanya dapat dihubungkan oleh suatu lintasan tertentu, maka graf tersebut dinamakan pohon (tree). Dengan kata lain, pohon (tree) merupakan graf tak-berarah yang terhubung dan tidak memiliki sirkuit. 

Berikut adalah beberapa sifat pohon : 

• Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi. Jika G tidak mempunyai sirkuit maka G merupakan pohon. 

• Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi. 

• Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal. 

• Misalkan G adalah graf sederhana dengan jumlah simpul n, jika G tidak mengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuat satu sirkuit. 

 Pohon keputusan dibangun untuk membuat aturan klasifikasi dari beberapa atribut yang diasosiasikan ke dua kelas atau lebih melalui perhitungan entropy dan information gain, serta perhitungan seleksi atribut lainnya.

    

     Sebuah pohon keputusan dg konsep membeli komputer, mengindikasikan apakah pelanggan di AllElectronics membeli komputer atau tidak. Setiap node internal mewakili pengujian pada atribut . Setiap node daun (terminal) mewakili kelas (buys computer = yes atau buys computer = no)

Dari pohon keputusan di atas maka didapatkan aturan klasifikasi sebagai berikut :
R1: IF age = youth AND student = no THEN buys computer = no
R2: IF age = youth AND student = yes THEN buys computer = yes
R3: IF age = middle aged THEN buys computer = yes
R4: IF age = senior AND credit rating = excellent THEN buys computer = yes
R5: IF age = senior AND credit rating = fair THEN buys computer = no

Pohon Berakar 

       Pada suatu pohon, yang sisi-sisinya diberi arah sehingga menyerupai graf berarah, maka simpul yang terhubung dengan semua simpul pada pohon tersebut dinamakan akar. Suatu pohon yang satu buah simpulnya diperlakukan sebagai akar maka pohon tersebut dinamakan pohon berakar (rooted tree). Simpul yang berlaku sebagai akar mempunyai derajat masuk sama dengan nol. Sementara itu, simpul yang lain pada pohon itu memiliki derajat masuk sama dengan satu. Pada suatu pohon berakar, Simpul yang memiliki derajat keluar sama dengan nol dinamakan daun. 

1. Anak (child atau children) dan Orangtua (parent) b, c, dan d adalah anak-anak simpul a, a adalah orangtua dari anak-anak itu 
2. Lintasan (path) Lintasan dari a ke h adalah a, b, e, h. dengan pnjang lintasannya adalah 3. f adalah saudara kandung e, tetapi, g bukan saudara kandung e, karena orangtua mereka berbeda. 
3. Subtree 
4. Derajat (degree) 

Derajat sebuah simpul adalah jumlah anak pada simpul tersebut. 
Contoh : 
Simpul yang berderajat 0 adalah simpul c, f, h, I, j, l, dan m. 
Simpul yang berderajat 1 adalah simpul d dan g. 
Simpul yang berderajat 2 adalah simpul b dan k. 
Simpul yang berderajat 3 adalah simpul a dan e. abkgjfcdmlieh abkgjfcdmlieh 

       Pohon keputusan merupakan himpunan aturan IF…THEN. Setiap path dalam tree dihubungkan dengan sebuah aturan, di mana premis terdiri atas sekumpulan node-node yang ditemui, dan kesimpulan dari aturam terdiri atas kelas yang terhubung dengan leaf dari path.

Gambar: Konsep Dasar Pohon Keputusan

Bagian awal dari pohon keputusan ini adalah titik akar (root), sedangkan setiap cabang dari pohon keputusan merupakan pembagian berdasarkan hasil uji, dan titik akhir (leaf) merupakan pembagian kelas yang dihasilkan.

Pohon keputusan mempunyai 3 tipe simpul yaitu:

1. Simpul akar, dimana tidak memiliki cabang yang masuk dan memiliki cabang lebih dari satu, terkadang tidak memiliki cabang sama sekali. Simpul ini biasanya berupa atribut yang paling memiliki pengaruh terbesar pada suatu kelas tertentu.
2. Simpul internal, dimana hanya memiliki 1 cabang yang masuk, dan memiliki lebih dari 1 cabang yang keluar.
3. Simpul daun, atau simpul akhir dimana hanya memiliki 1 cabang yang masuk, dan tidak memiliki cabang sama sekali dan menandai bahwa simpul tersebut merupakan label kelas.

Tahap awal dilakukan pengujian simpul akar, jika pada pengujian simpul akar menghasilkan sesuatu maka proses pengujian juga dilakukan pada setiap cabang berdasarkan hasil dari pengujian. Hal ini berlaku juga untuk simpul internal dimana suatu kondisi pengujian baru akan diterapkan pada simpul daun. Pada umumnya proses dari sistem pohon keputusan adalah mengadopsi strategi pencarian top-down untuk solusi ruang pencariannya. Pada proses mengklasifikasikan sampel yang tidak diketahui, nilai atribut akan diuji pada pohon keputusan dengan cara melacak jalur dari titik akar sampai titik akhir, kemudian akan diprediksikan kelas yang ditempati sampel baru tersebut.
Pohon keputusan banyak digunakan dalam proses data mining karena memiliki beberapa kelebihan, yaitu:
1. Tidak memerlukan biaya yang mahal saat membangun algoritma.
2. Mudah untuk diinterpetasikan.
3. Mudah mengintegrasikan dengan sistem basis data.
4. Memiliki nilai ketelitian yang lebih baik.
5. Dapat menemukan hubungan tak terduga dan suatu data.
6. Dapat menggunakan data pasti/mutlak atau data kontinu.
7. Mengakomodasi data yang hilang.

Berikut contoh penerapan pohon keputusan studi kasus mengenai uji kelayakan kredit:

Gambar: Contoh Pohon Keputusan dalam Identifikasi Kelayakan Kredit

Dari pohon tersebut diketahui bahwa pemohon yang layak menerima kredit adalah pemohon yang penghasilannya sama dengan 2- 3x angsuran dan kepemilikan rumahnya adalah milik sendiri.

Kesimpulan

Penggunaan teori graf dan pohon pada suatu kegiatan pengambilan keputusan memang berguna untuk beberapa kondisi. Seperti yang sudah dijelaskan sebelumnya bahwa teori pohon ini mempunyai beberapa keuntungan diantara lainnya adalah mudah untuk diinterpetasikan, mudah mengintegrasikan dengan sistem basis data, memiliki nilai ketelitian yang lebih baik, dapat menemukan hubungan tak terduga dan suatu data, dan keuntungan lainnya.

Dengan menyajikan pohon keputusan untuk memilih sesuatu, kita dapat tahu skema langkah yang harus diambil dan yang tidak perlu diambil sehingga keputusan yang ktia ambil tidak asal melainkan berdasarkan analisis yang sudah kita lakukan dan kita sajikan dalam pohon keputusan. Maka itu pentingnya kita untuk mempelajari teori pohon ini.

Apa itu graf???

TEORI GRAF

Pada ilmu matematika dan ilmu komputer, teori graf adalah cabang kajian yang mempelajari sifat-sifat graf. Secara informal, suatu graf adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) ataubusur (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan busur). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan gelang (loop).

Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan pada Facebook bisa direpresentasikan dengan graf, yakni simpul-simpulnya adalah para pengguna Facebook dan ada sisi antar pengguna jika dan hanya jika mereka berteman.

Pengertian GRAF dalam matematika

“Dalam matematika dan ilmu komputer, sebuah graf adalah objek dasar pelajaran dalam teori graf. Dalam bahasa sehari-hari, sebuah graf adalah himpunan dari objek-objek yang dinamakan titik, simpul, atau sudut dihubungkan oleh penghubung yang dinamakan garis atau sisi. Dalam graf yang memenuhi syarat, dimana biasanya tidak berarah, sebuah garis dari titik A ke titik B dianggap sama dengan garis dari titik B ke titik A. Dalam graf berarah, garis tersebut memiliki arah. Pada dasarnya, sebuah graf digambarkan dengan bentuk diagram sebagai himpunan dari titik-titik (sudut atau simpul) yang digabungkan dengan kurva (garis atau sisi).”

Mudahnya untuk memahami graf, Graf adalah himpunan/kumpulan  titik - titik yang memiliki bobot yang dan saling dihubungkan. Titik dalam graf diknal juga dengan simpul/vertex. Sebuah graf memiliki simpul2 yang dihubungkan oleh garis (busur). Pada kehidupan sehari-hari, secara tidak langsung kita menerapkan teori graf untuk mencari jalan pulang dengan rute terpendek. Atau contoh lainnya dapat kita temukan pada langkah-langkah di permainan catur dan halma.

Graf juga banyak dipakai untuk membantu menyelesaikan masalah-masalah yang berhubungan dengan Kecerdasan Buatan (Artificial Intelligence), seperti dalam contoh, yang merupakan suatu teka-teki yang banyak dipakai sebagai ilustrasi. Dalam hal ini, graf digunakan untuk menyatakan hubungan-hubungan yang terjadi di antara objek-objek. Dengan cara itu, deduksi ke kesimpulan akan lebih mudah dibuat.

Contoh
Ada sebuah pulau yang penghuninya hanya terdiri dari 2 macam yaitu : pemakan orang (cannibal) dan pemakan sayuran (vegetarian). Pada mulanya, ada 2 orang pemakan orang dan 2 orang pemakan sayuran di sisi barat sungai. Di sisi barat itu pula terdapat sebuah perahu kecil yang hanya dapat menampung paling banyak 2 orang. Masalahnya adalah bagaimana cara mengangkut keempat orang tersebut ke sisi timur sungai. Syaratnya adalah : jumlah pemakan manusia pada suatu sisi sungai tidak boleh lebih banyak dari jumlah pemakan sayuran di sisi yang sama, karena hal itu akan menyebabkan pemakan manusia akan memakan pemakan sayuran.

Penyelesaian:

Suatu cara penyelesaian yang sistematis adalah dengan menggambarkan semua kemungkinan keadaan, dan kemudian menghilangkan bagian-bagian yang tidak mungkin terjadi karena tidak memenuhi kendala yang diisyaratkan.

Misalkan simbol “v” menyatakan pemakan sayuran, “c” menyatakan pemakan orang, “B” menyatakan perahu dan simbol "/" menyatakan sungai. Dengan menggunakan simbol tersebut maka vvcB/c berarti suatu keadaan di mana di sisi barat sungai (di sebelah kiri simbol /) ada 2 orang pemakan sayuran dan satu orang pemakan orang, sedangkan di sisi timur sungai ada seorang pemakan orang. Perahu ada di sisi barat sungai.

Semua kemungkinan keadaan di sungai tersebut dapat digambarkan pada Gambar 6 (sumbu mendatar menyatakan jumlah pemakan sayur di timur sungai dan sumbu tegak menyatakan jumlah pemakan orang di timur sungai). Pada suatu titik tertentu, ada 2 kemungkinan posisi perahu (B), yaitu di kiri sungai atau di kanan sungai.

  

Selanjutnya, dihilangkan keadaan-keadaan yang tidak mungkin terjadi:
a. Karena jumlah pemakan orang (o) di suatu sisi sungai tidak boleh lebih banyak dari jumlah pemakan sayurnya (s), maka titik-titik : v/Bvcc, vB/vcc, vcc/Bv, vccB/v harus dihilangkan
b. Perahu harus berada pada sisi sungai yang ada orangnya. Jika tidak demikian, maka tidak ada orang yang dapat menyeberang. Oleh karena itu, harus dihilangkan titik-titik   vvcc/B dan B/vvcc

Dengan adanya beberapa titik yang dihilangkan tersebut, maka didapatkan keadaan yang dinyatakan pada Gambar berikut

Dari titik-titik yang tersisa, dibuat garis-garisnya. Suatu garis menghubungkan 2 buah titik yang dapat dicapai satu dari yang lainnya. Sebagai contoh, titik ssoP/o dapat dihubungkan dengan titik c/Bvvc karena dari titik vvcB/c, perahu dapat mengangkut 2 orang pemakan sayur (s) ke sisi kanan sungai, sehingga didapatkan titik c/Bvvc. Kondisi ini juga berlaku sebaliknya. Dari titik c/Bvvc, perahu dapat mengangkut 2 orang pemakan sayur ke kiri sungai sehingga didapatkan titik vvcB/c. Dengan penambahan semua garis yang mungkin dibuat, maka didapatkan graf yang dinyatakan pada Gambar berikut.

Untuk menyelesaikan masalah tersebut, berarti harus dicari jalur (garis) yang menghubungkan titik vvccB/ (perahu dan semua orang yang terlibat berada di barat sungai) dengan titik /Bvvcc (perahu dan semua orang yang terlibat berada di timur sungai)

Dari Gambar 3 didapatkan 2 kemungkinan jalur yaitu :
vvccB/ ® vv/Bcc ® vvcB/c ® c/Bvvc ® ccB/vv ® /Bvvcc
atau:
vvccB/ ® vc/Bvc ® vvcB/c ® c/Bvvc ® ccB/vv ® /Bvvcc

Definisi 2
Graf Sederhana (Simple Graph) adalah graf yang tidak mempunyai loop ataupun garis paralel.

PENERAPAN GRAF PADA PERMAINAN CATUR

Untuk penjelasan kali ini, saya memilih permainan catur sebagai media penerapan teori graf. Knight’s Tour dimana ini merupakan suatu aplikasi dari teori graf pada permainan catur papan. Suatu Knight’s Tour pada papan catur adalah rangkaian perjalanan kuda catur pada papan catur sehingga seluruh kotak terlewati kuda tepat satu kali.

Aturan langkah kuda pada permainan catur adalah sebagai

berikut :

•        Melangkah dua persegi ke arah horisontal kemudian satu persegi ke arah vertikal, atau

•        Melangkah dua persegi ke arah vertikal kemudian satu persegi ke arah horisontal, atau

•        Melangkah dua persegi ke arah vertikal kemudian satu persegi ke arah horisontal, atau

•        Melangkah satu persegi ke arah vertikal kemudian dua persegi ke arah horisontal.

Jika dalam Knight’s Tour setiap persegi dari papan catur dapat dilewati tepat satu kali dan kuda kembali pada persegi semula maka disebut langkah kuda tertutup

(Closed Knight’s Tour). Namun, jika semua persegi telah dilewati dan kuda tidak dapat kembali ke posisi semula maka disebut langkah kuda yang terbuka (Open Knight’s

Tour)

Contoh Closed Knight’s Tour

Di atas adalah contoh dari Knight’s Tour. Angka 1-64 menandakan urutan kotak yang dilewati oleh kuda catur tersebut. Langkah yang diambil oleh kuda urut dari 1

sampai dengan 64.

1. ALGORITMA RUNUT BALIK (BACKTRACK)

Algoritma runut-balik (backtracking algorithm) adalah algoritma yang berbasis pada DFS untuk mencari solusi persoalan secara lebih mangkus. Runut-balik, yang merupakan perbaikan dari algoritma bruteforce, secara sistematis mencari solusi persoalan di antara  semua kemungkinan solusi yang ada. Dengan metode ini, kita tidak perlu memeriksa semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang selalu dipertimbangkan. Akibatnya, waktu pencarian dapat dihemat. Runut-balik lebih alami dinyatakan dalam algoritma rekursif. Kadang-kadang disebutkan pula bahwa

runut-balik merupakan bentuk tipikal dari algoritma rekursif. Istilah runut-balik pertama kali diperkenalkan oleh D.H. Lehmer pada tahun 1950. Selanjutnya, R. J. Walker, Golomb, dan Baumert menyajikan uraian umum tentang runut-balik dan penerapannya pada berbagai persoalan.

2. APLIKASI ALGORITMA RUNUT-BALIK PADA KNIGHT’S TOUR

Algoritma runut-balik (backtracking algorithm) dapat dipakai untuk menyelesaikan permasalahan dari Knight’s Tour. Ide dasar dari algoritma runut balik adalah dengan membangun solusi-solusi parsial dari masalah (dalam hal ini jalan selangkah pada papan) lalu mencoba memperluas solusi tersebut. Jika solusi yang telah dikembangkan gagal (langkah selanjutnya tidak menuju solusi) maka akan dilakukan runut-balik dan mencoba solusi parsial lainnya.

Algoritma runut-balik yang dipakai adalah:

1. Dari kotak tempat kuda tersebut berada, dibangkitkan langkah-langkah berikutnya yang memungkinkan dilalui oleh kuda tersebut.

2.    Salah satu langkah (kotak) dipilih untuk diperluas.

3.    Kuda melangkah ke kotak yang dipilih tersebut.

4.    Kembali ke langkah satu sampai langkah yang diperluas tidak dapat mencapai  solusi (kuda tidak dapat melangkah lagi).

5.  Pencarian langkah dilakukan dengan melakukan runut balik ke langkah yang telah dilalui terdekat dan kuda melangkah balik ke kotak tersebut dan kembali ke langkah satu.

6. Pencarian langkah dihentikan bila telah melakukan solusi atau tidak ada  langkah yang memungkinkan lagi bagi kuda catur tersebut.

Kesimpulan

Teori graf adalah cabang kajian yang mempelajari sifat-sifat graf. Secara informal, suatu graf adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) ataubusur (arc). Dalam matematika dan ilmu komputer, sebuah graf adalah objek dasar pelajaran dalam teori graf. Dalam bahasa sehari-hari, sebuah graf adalah himpunan dari objek-objek yang dinamakan titik, simpul, atau sudut dihubungkan oleh penghubung yang dinamakan garis atau sisi. Pada intinya penggunaan graf pada kehidupan sehari-hari sudah sering kita temukan. Misalnya ketika kita memilih rute jalan pulang yang tercepat dengan mempertimbangkan segala alternatif yang ada untuk tiba di rumah dengan cepat. Contoh lain yaitu ketika hendak memutuskan suatu perkara dengan terlebih dahulu mengidentifikasikan masalah apa saja yang harus diselesaikan dan hal apa yang akan terjadi jika kita melakukan tibdakan tersebut.