BAB I

PENDAHULUAN

A.  Latar Belakang

Apakah suatu formula untuk jumlah dari n bilangan bulat positif ganjil pertama? Jumlah dari n bilangan bulat ganjil positif pertama untuk n = 1, 2, 3, 4, 5 adalah

1 = 1,

1 + 3 = 4,

1 + 3 + 5 = 9,

1 + 3 + 5 + 7 = 16,

1 + 3 + 5 + 7 + 9 = 25.

Dari nilai-nilai ini layak untuk membawa jumlah dari n bilangan bulat ganjil positif pertama adalah n2. Kita perlu suatu metode untuk membuktikan bahwa perkiraan itu benar.

Induksi matematis adalah suatu teknik pembuktian penting secara ekstrem dapat digunakan untuk membuktikan pernyataan tegas tipe ini. Seperti yang kita lihat dalam bagian ini dan dalam bab berikutnya, induksi matematis digunakan secara ekstensif untuk membuktikan hasil tentang berbagai objek diskret luas. Misalnya, induksi matematis digunakan untuk membuktikan hasil tentang kompleksitas algoritma, pembetulan tipe program komputer tertentu, teorema tentang graf dan pohon, dan juga suatu range luas dari identitas dan pertidaksamaan.

Dalam bagian ini kita akan menggambarkan bagaimana induksi matematis dapat digunakan dan mengapa induksi matematis merupakan suatu teknik pembuktian valid. Ini secara ekstrim penting dengan mencatat bahwa induksi matematis hanya dapat digunakan untuk membuktikan hasil yang diperoleh suatu cara lain. Ini bukan merupakan alat untuk menemukan formula atau teorema.

B.  Rumusan Masalah

1.      Pengenalan Induksi Matematika

2.      Tahapan induksi matematika dan contoh-contohnya.

BAB II

PEMBAHASAN

A.      Pengenalan Induksi Matematika

Induksi matematika ditemukan pertama kali oleh seorang metematikawan asal prancis yang bernama Blaise Pascal (1623-1662). Induksi matematika merupakan teknik yang dikembangkan untuk membuktikan pernyataan dan merupakan pembuktian deduktif, meski namanya induksi. Induksi matematika atau disebut juga induksi lengkap sering dipergunakan untuk pernyataan-pernyataan yang menyangkut bilangan-bilangan asli.

Pengertian lain yaitu suatu cara standar dalam membuktikan bahwa sebuah pernyataan tertentu berlaku untuk setiap bilangan asli. Pembuktian cara induksi matematika ingin membuktikan bahwa teori atau sifat itu benar untuk semua bilangan asli atau semua bilangan dalam himpunan bagiannya.

B.       Tahapan Induksi Matematika

Ø  Basis Step             : Tunjukkan bahwa S(1) benar

Ø  Inductive Step      : Asumsikan S(k) benar, Akan dibuktikan  S(k) ® S(k+1) benar

Ønbsp; Conclusion            : S(n) adalah benar untuk setiap n bilangan integer   Positif

Langkah-langkah pembuktian :

1. Pembuktian rumus atau teorema untuk suatu nilai bilangan bulat positif n, biasanya nilai yang terkecil .
2. Bukti bahwa jika rumus atau teorema yang dimaksud adalah benar untuk n=k, dimana k adalah suatu bilanganbulat positif, maka rumus tersebut juga benar untuk n=k+1.
3. Kesimpulan bahwa rumus yang dimaksud adalah benar untuk semua nilai n yang lebih besar daripada bilangan bulat yang telah dibuktikan kebenaranya dilangkah pertama.

Misalkan akan dibuktikan suatu pernyataan bahwa jumlah n bilangan asli
pertama, yaitu 1+2+:::+n, adalah sama dengan       .Untuk membuktikan
bahwa pernyataan itu berlaku untuk setiap bilangan asli, langkah-langkah
yang dilakukan adalah sebagai berikut:

1.      Cara Biasa / Basis

Menunjukkan bahwa pernyataan tersebut benar untuk n = 1. Jelas sekali bahwa jumlah 1 bilangan asli pertama adalah  = 1. Jadi pernyataan tersebut adalah benar untuk n = 1.

Untuk n =1, Ruas kiri                 = 1

Sedangkan Ruas kanan               =   = 1

Kerena ruas kiri = ruas kanan, maka persamaan benar untuk n=1.

2.      Menunjukkan bahwa jika pernyataan tersebut benar untuk n = k, maka
pernyataan tersebut juga benar untuk n = k+1.

3.      Dengan induksi matematika dapat disimpulkan bahwa pernyataan tersebut berlaku untuk setiap bilangan asli n

C.       Contoh-Contoh Soal

Contoh 1:

Gunakan induksi matematika untuk membuktikan bahwa 5ⁿ− 1 dapat dibagi 4 untuk setiap n = 1, 2,....

1.           Akan ditunjukkan bahwa 5ⁿ − 1 habis dibagi 4 untuk n = 1

 5¹− 1 = 5− 1 = 4 è habis dibagi 4.

2.      Asumsikan bahwa 5ⁿ− 1 habis dibagi 4 untuk n = k, juga untuk n= k+ 1,

(5)^k+1− 1 = 5.5^k− 1

= (1 + 4).5^k− 1

= 5^k +4.5^k−1

= (5^k− 1) + 4.5^k

(n=1) = (5¹-1)+4.5¹ = (5-1)+4.5 = 4+20 =24 è kelipatan 4 èbernilai 6

(n=2) = (5²-1)+4.5² = (25-1)+4.25= 24+100=124 è bernilai 31

Contoh 2:

Gunakan induksi matematika untuk membuktikan bahwa n³+2n adalah kelipatan 3, untuk semua bilangan asli

1.      Akan ditunjukkan bahwa n³+2n  adalah kelipatan 3 untuk n = 1.

1³+2.1=1+2=3 è kelipatan 3 è bernilai 1

2.      Asumsikan bahwa n³+2n adalah kelipatan 3 untuk n = k  juga untuk n= k+ 1

n³ +2n = (k+1)³+2(k+1)

= (k³+3k²+3k+1)+ 2k+2

= k³+3k²+5k+3

(n=1) = 1³+3.1²+5.1+3 = 12 è adalah kelipatan 3 è bernilai 4

(n=2)= 2³+3.2²+5.2+3 = 8+12+10+3 = 33 è kelipatan 3 è 10

Contoh 3 :

Gunakan induksi matematis untuk membuktikan bahwa n³ – n dapat dibagi dengan 3 apabila n adalah suatu bilangan bulat positif.

Solusi: Untuk mengonstruksi bukti, misalkan P(n) menyatakan proposisi: “n³ – n dapat dibagi dengan oleh 3.”

Langkah Dasar: P(1) benar, karena 1³ – 1 = 0 dapat dibagi dengan 3.

Langkah Induktif: Asumsikan bahwa P(n) benar; yaitu, n³ – n dapat dibagi dengan 3. Kita harus menunjukkan bahwa (n + 1)³ – (n + 1) dapat dibagi dengan 3. Ingat bahwa

(n + 1)³ – (n + 1) = (n³ + 3n² + 3n + 1) – (n + 1)

= (n³ – n) + 3(n² + n).

Karena kedua suku dalam jumlah ini dapat dibagi dengan 3 (pertama dengan asumsi dari langkah induktif, dan kedua karena jumlah itu merupakan 3 kali suatu bilangan bulat), selanjutnya (n + 1)³ – (n + 1) juga dapat dibagi dengan 3. Ini melengkapi langkah induktif. Sehingga, dengan prinsip induksi matematis, n³ – n dapat dibagi oleh 3 apabila n adalah suatu bilangan bulat positif.

Contoh 4 :

Buktikan 1+3+5+...+(2n-1)= n²

1.      Rumusnya benar untuk n=1 karena 1=1²

2.      Asumsikan bahwa rumus tersebut benar untuk n=k ; yaitu kita misalkan bahwa

1+3+5 +...+(2k-1)=k²

maka rumus tersebut benar untuk n=k+1 (Catatan bahwa bilangan bulat positif ganjil ke-n adalah (2k – 1), karena bilangan bulat ini diperoleh dengan menambahkan 2 suatu total dari k – 1 kali dengan 1.); yaitu bahwa

1+3+5+...+(2k-1)+(2k+1)=(k+1)²

Dengan menambahkan (2k+1) pada kedua ruas, Sehingga mengasumsikan bahwa P(k) benar, ini mengikuti

1+3 + 5 +…+(2k – 1) + (2k + 1) = 1 + 3 +…+ (2k – 1) + (2k + 1)

=  k² + (2k + 1)

=  k² + 2k + 1

=  (k + 1)².

Ini menunjukkan bahwa P(n + 1) mengikuti dari P(n). Catatan bahwa kita menggunakan hipotesis induktif P(n) dalam kesamaan kedua dengan menempatkan kembali jumlah dari n bilangan bulat positif ganjil pertama dengan n2.

Karena P(1) benar dan implikasi P(n) P(n +1) benar untuk semua bilangan bulat positif n, prinsip induksi matematis menunjukkan bahwa P(n) benar untuk semua bilangan bulat positif n.

Contoh 5 :

Gunakan induksi matematis untuk menunjukkan bahwa

1 + 2 + 2² + … + 2ⁿ = 2^{n + 1} – 1

untuk semua bilangan bulat nonnegatif n. Solusi: Misalkan P(n) adalah proposisi bahwa formula ini tepat untuk bilangan bulat n.

Langkah Dasar: P(0) benar karena 2⁰ = 1 = 2¹ – 1.

Langkah Induktif: Asumsikan bahwa P(n) benar. Untuk menyelesaikan langkah induktif dengan menggunakan asumsi ini, harus ditunjukkan bahwa P(n + 1) benar, yaitu,

1 + 2 + 2² + … + 2ⁿ + 2^{n +1} = 2^{(n + 1)+1} – 1 = 2^{n + 2} – 1.

Dengan menggunakan hipotesis induktif P(n), diperoleh

1 + 2 + 2² + … + 2ⁿ + 2^{n +1} = (1 + 2 + 2² + … + 2ⁿ) + 2^{n +1}

= (2^{n + 1} – 1) + 2^{n + 1}

= 2. 2^{n + 1} – 1

= 2^{n + 2} – 1.

Langkah induktif terakhir ini, yang melengkapi bukti itu.

Contoh  6:

Gunakan induksi matematis untuk membuktikan pertidaksamaan n < 2ⁿ untuk semua bilangan bulat positif n.

Solusi: Misalkan P(n) adalah proposisi “n < 2ⁿ”.

Langkah Dasar: P(1) benar, karena 1< 2¹ = 2.

Langkah Induktif: Asumsikan bahwa P(n) benar untuk bilangan bulat positif n. Yakni, asumsikan bahwa k < 2^k. Kita perlu menunjukkan bahwa P(k + 1) benar. Yakni, kita perlu untuk menunjukkan bahwa k +1< 2^{k + 1}. Dengan menambahkan 1 untuk kedua sisi dari k < 2^k, dan kemudian mencatat bahwa 1< 2^k, memberikan

k + 1< 2^k + 1≤ 2^k + 2^k = 2^{k + 1}

Kita telah menunjukkan bahwa P(k +1) benar, yaitu, k + 1< 2^{k + 1}, didasarkan pada asumsi bahwa P(n) benar. Langkah induktif lengkap.

Jadi, dengan prinsip induksi matematis, telah ditunjukkan bahwa k<2^k benar untuk semua bilangan bulat positif.

Contoh 7 :

Gunakan induksi matematika untuk membuktikan bahwa

n!≥ 2ⁿ⁻¹

untuk setiap n= 1,2,....

1.         Akan ditunjukkan bahwa n!≥ 2ⁿ⁻¹  benar untuk n = 1. Jelas sekali

bahwa  1!  2¹⁻¹

 1   2⁰

 1  1

2.         Asumsikan bahwa n! ≥ 2ⁿ⁻¹ adalah benar untuk n=k. Akan ditunjukkan bahwa n!≥ 2ⁿ⁻¹ juga benar untuk n=k + 1, yaitu (k + 1) ≥ 2^(k+1)−1.

(k+1)!  = (k+1)(k!)

≥(k + 1)(2^k−1)

 ( 2^k-1)(2^k-1)

≥2.2^k−1

= 2^1+(k−1)

= 2^(k+1)−1

Terbukti bahwa (k+1) ≥ 2^(k+1)−1.

Karena Langkah Dasar dan Langkah  Induktif terbukti, maka dapat disimpulkan bahwa

n!≥ 2ⁿ⁻¹

untuk setiap n = 1, 2,....

Contoh 8:

Buktikan n²  2n +1 untuk  3

Karena 3² = 9  2(3) +1=7, maka formula tersebut benar untuk n=3

Asumsikan n² 2n+1 maka:

(n+1)²=n²+2n+1 2n+1+2n+1=2n+2+2n 2n+2+1=2(n+1)+1

Sehingga formula tersebut benar untuk n+1. Menurut prinsip P induksi, formula tersebut berlaku untuk n 3

Contoh 9:

Buktikan 2ⁿ  n² untuk n 4

Karena 2⁴=16=4², maka  formula tersebut benar n=4. Asumsikan 2ⁿ  n² dan juga n²  2n+1 di dapat:

2ⁿ⁺¹ = 2(2ⁿ) 2(n²) = n² +n²  n² +2n +1=(n+1)²

                 Formula tersebut benar untuk n+1. Menurut prinsip induksi, formula tersebut bermakna untuk n 4.

Latihan soal induksi matematika

Contoh 1 :

Buktikan bahwa :

1 + 2 + 3 + … + n = ½ n(n+1)

untuk setiap n bilangan integer positif

Jawab :

q Basis : Untuk n = 1 akan diperoleh :

1 = ½ 1 . (1+1) ->1 = 1

q Induksi : misalkan untuk n = k asumsikan 1 + 2 + 3 + …+ k = ½ k (k+1)

q adib. Untuk n = k+1 berlaku

1 + 2 + 3 + …+ (k+1) = ½ (k+1) (k+2)

Jawab :

q 1 + 2 + 3 + …+ (k+1) = (k+1) (k+2) / 2

1 + 2 + 3 + …+ k + (k+1) = (k+1) (k+2) / 2

k (k+1) / 2 + (k+1) = (k+1) (k+2) / 2

(k+1) [ k/2 +1 ] = (k+1) (k+2) / 2

(k+1) ½ (k+2) = (k+1) (k+2) / 2

(k+1) (k+2) / 2 = (k+1) (k+2) / 2

q Kesimpulan : 1 + 2 + 3 + …+ n = ½ n (n +1)

Untuk setiap bilanga bulat positif n

Contoh 2 :

Buktikan bahwa :

1 + 3 + 5 + … + n = (2n – 1) = n²

untuk setiap n bilangan bulat positif

Jawab :

q Basis : Untuk n = 1 akan diperoleh :

1 = 1² -> 1 = 1

q Induksi : misalkan untuk n = k asumsikan 1 + 3 + 5 + …+ (2k – 1) = k²

q adib. Untuk n = k + 1 berlaku

1 + 3 + 5 + …+ (2 (k + 1) – 1) = (k + 1)²

1 + 3 + 5 + …+ (2k + 1) = (k + 1)²

1 + 3 + 5 + …+ ((2k + 1) – 2) + (2k + 1) = (k + 1)²

1 + 3 + 5 + …+ (2k – 1) + (2k + 1 ) = (k + 1)²

k ² + (2K + 1) = (k + 1)²

k ² + 2K + 1 = k ² + 2K + 1

Kesimpulan : 1 + 3 + 5 + … + n = (2n – 1) = n²

Untuk setiap bilangan bulat positif n

Contoh 3 :

Buktikan bahwa :

N ³ + 2n adalah kelipatan 3

untuk setiap n bilangan bulat positif

Jawab :

q Basis : Untuk n = 1 akan diperoleh :

1 = 1³ + 2(1) -> 1 = 3 , kelipatan 3

q Induksi : misalkan untuk n = k asumsikan k ³ + 2k = 3x

q adib. Untuk n = k + 1 berlaku

(k + 1)³ + 2(k + 1) adalah kelipatan 3

(k ³ + 3k ² + 3 k+1) + 2k + 2

(k ³ + 2k) + (3k ² + 3k + 3)

(k ³ + 2k) + 3 (k ² + k + 1)

Induksi

3x + 3 (k ² + k + 1)

3 (x + k ² + k + 1)

Kesimpulan : N ³ + 2n adalah kelipatan 3

Untuk setiap bilangan bulat positif n

Transfer file

Masih menggunakan cara lama dalam melakukan file sharing? Secara umum fitur file sharing bawaan Windows memang mudah namun sering kali dibuat repot dengan berbagai macam masalah yang kerap muncul, seperti munculnya permintaan untuk memasukkan username dan password, sistem lain sering tidak muncul di daftar jaringan dan berbagai masalah yang sering membuat kesal, padahal settingnya sudah diset secara default. Metode baru telah hadir dalam kegiatan file sharing yaitu dengan memanfaatkan protokol HTTP, menggunakan aplikasi yang bernama HTTP File Server yang dibuat oleh Massimo Melina (Rejetto).

HTTP File Server atau yang disingkat menjadi HFS adalah sebuah program khusus untuk file sharing antar komputer yang memanfaatkan jalur HTTP. HFS dirilis dengan lisensi GRATIS dan tidak perlu instalasi alias portabel. Jadi hanya dengan dua-kali klik mouse, HFS sudah berjalan dan bisa langsung dikonfigurasi dengan cepat tanpa perlu setting yang rumit. Dalam waktu kurang dari 5 menit pengguna langsung bisa membagi file-filenya melalui jaringan LAN maupun W-LAN.

Cara mengakses file-file yang di-sharing melalui HFS pun sangat mudah, tinggalkan cara kuno yang dimana masih menyamakan nama Workgroup antar sistem. Cukup buka web browser apa aja (Mozilla Firefox atau Windows Internet Explorer) lalu ketik alamat IP yang disediakan oleh HFS dan secara instant daftar file yang di-sharing langsung tampil dilayar. Untuk mengambil file yang di-sharing pun menggunakan proses download yang biasanya digunakan untuk download file dari website, hanya saja disini kecepatan download luar bisa kencang karena koneksi yang digunakan adalah jaringan lokal dengan kemampuan stream kabel LAN dan W-LAN. Jadi jangan kaget kalau kecepatan download bisa mencapai angka 5.500 KB/s [5,5 MB/s] (LAN) atau 1.500 KB/s [1,5 MB/s] (W-LAN) tergantung dari kestabilan dari masing-masing hardware.

Adakah cara untuk memberi file ke sistem server? Tentu saja bisa, di HFS semuanya bisa. Disini HFS menyediakan opsi untuk upload dari client, tentukan folder untuk lokasi upload lalu centang opsi upload di menu klik kanan dan pilih Anyone. Pengguna bisa membuat account tersendiri bagi yang mau meng-akses ke HFS, jadi layaknya sebuah situs file sharing. Pembatasan kecepatan download maupun upload dapat dilimitasi pada HFS, biasanya hal ini untuk menghindari overload pada kapasitas bandwidth yang digunakan. Apalagi kalau membagi file-file film kelas HD yang ukurannya ratusan MB.

Dengan HFS pun bisa saja membangung sebuah portal video streaming dengan kualitas HD tanpa koneksi internet. Namun dengan syarat, player client harus ada fitur seperti “Open Location”, jadi nantinya alamat URL file video dari HFS dimasukkan ke dalam video player tersebut. Media Player Classic dengan paket codec K-Lite bisa melakukan streaming dengan lancar.

 

HFS pun mendapat penghargaan 5 bintang dari softpedia berkat kemudahan dan penggunaan yang sangat praktis tanpa embel-embel. Menurut saya HFS adalah sebuah “tool” file sharing terbaik yang pernah ada. Hanya dengan beberapa langkah, pengguna bisa langsung membagi filenya ke dalam jaringan lokal miliknya dan tidak perlu lagi yang namanya setting IP dan workgroup. Saya juluki sebagai “instant file sharing tool”.

DOWNLOAD (install) / DOWNLOAD (portabel)

Lintasan dan sirkuit Hamilton

• Lintasan Hamilton ialah lintasan yang melalui tiap simpul didalam graf tepat satu kali

• Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul didalam graf tepat satu kali, kecuali simpul awal (juga mrpk simpul akhir) dilalui 2 kali
• Graf yang memiliki sirkuit Hamilton disebut graf Hamilton , sedangkan graf yang memiliki lintasan Hamilton disebut graf semi Hamilton

Contoh :

Graf Di samping memiliki lintasan Hamilton dengan lintasan :

b,c,d,e,f,g,a,b

dan Graf di samping juga memiliki sirkuit Hamilton karena di awali di simpul b dan berakhir di simpul b








Graf disamping memiliki lintasan Hamilton dengan lintasan :

a,b,c,d,e,i,f,g,h

Tapii graf disamping tidak memiliki sirkuit Hamilton.











Teorema Untuk Lintasan dan Sirkuit Hamilton

• Syarat cukup (bukan syarat perlu) supaya graf sederhana G dengan n buah simpul (n>=3) adalah graf Hamilton ialah jika derajad tiap simpul paling sedikit n/2
• Setiap graf lengkap adalah graf Hamilton
• Dalam graf l engkap dengan n buah simpul (n>=3) terdapat (n-1)! /2 buah sirkuit Hamilton
• Dalam graf lengkap G dengan jumlah simpul n>=3 dan n ganjil , terdapat (n-1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika n genap dan n>=4 , maka dalam G terdapat (n-2)/2 buah sirkuit Hamilton

Lintasan dan Sirkuit Euler

• Lintasan Euler ialah lintasan yang melalui tiap sisi dalam graf tepat sekali
• Sirkuit Euler ialah sirkuit yang melalui tiap sisi dalam graf tepat satu kali
• Graf yang mempunyai sirkuit Euler disebut graf Euler, sedang graf yang mempunyai lintasan Euler disebut semi Euler

Contoh
a. Apakah Ada Lintasan Euler ?
b. Apakah ada sirkuit Euler ?

Jawab
a. ADA lintasan euler dengan lintasan :
a,b,c,d,e,f,g,b,d,f,a,g

b. Tidak ADA sirkuit Euler.








a. Apakah ada lintasan Euler ?
b. Apakah ada Sirkuit Euler ?

Jawab
a. ADA lintasan Euler dengan lintasan :
a,b,c,d,e,c,h,b,f,h,e,f,g,a
b. Ada sirkuit euler karena berawal dari simpul a dan berakhir di simpul a

Teorema Untuk Lintasan dan sirkuit euler

• Graf tak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan mempunyai 2 buah simpul berderajat ganjil atau tidak ada simpul berderajad ganjil samasekali

• Graf tak berarah G adalah graf Euler jika hanya jika setiap simpul berderajad genap

• Graf berarah G memiliki sirkuit Euler jika hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama kecuali 2 simpul, yang pertama memiliki derajad keluar satu lebih besar dari derajad masuk, dan yang kedua memiliki derajad masuk satu lebih besar dari derajad keluar

GRAF

2.1.1 Definisi Graf

Secara matematis, graf didefiniskan sebagai berikut :

Definisi. Graf G didefinisikan sebagai pasangan himpunan (V, E) ditulis dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tidak-kosong dari simpul-simpul (vertices atau node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul (vertices).

Definisi di atas menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu.

2.1.2 Jenis-Jenis Graf

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis :

1. Graf sederhana ( simple graph ).

Graf yang tidak memiliki gelang maupun sisi-ganda.

2. Graf tak-sederhana ( unsimple-graph ).

Graf yang memiliki gelang maupun sisi-ganda. Ada dua macam graf tak-sederhana, yaitu graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda adalah graf yang memiliki sisi ganda, sedangkan graf semu adalah graf yang memiliki gelang.

 

Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:

1. Graf berhingga ( limited graph ).

2. Graf tak-berhingga ( unlimited graph ).

Berdasarkan orientasi arah pada sisi maka secara umum graf dapat digolongkan menjadi dua jenis:

1. Graf berarah ( directed graph ).

Graf yang setiap sisinya diberikan orientasi arah. Pada graf berarah, ( v_j, v_k ) dan ( v_{k ,} v_j ) menyatakan dua busur yang berbeda, dengan kata lain

( v_j ,v_k ) ≠ ( v_k ,v_j )

Untuk busur ( v_j ,v_k ), simpul v_j disebut simpul asal ( initial vertex ) dan untuk simpul vk disebut simpul terminal

( terminal vertex ).

2. Graf tak-berarah ( undirected graph ).

Graf yang sisinya tidak memiliki orientasi arah. Pada graf tek-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan, dengan kata lain:

( v_j ,v_k ) = ( v_k ,v_j ).

 

 

 

2.1.3 Terminologi Dasar

Terdapat beberapa istilah penting yang berkaitan dengan graf. Berikut ini didefinisikan beberapa terminologi yang sering digunakan:

1. Bertetangga ( Adjacent )

Dua bua simpul pada graf tak-berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain, v_j bertetangga dengan v_k jika (v_j , v_k ) adalah sebuah sisi pada graf G.

2. Bersisian ( Incident )

Untuk sembarang sisi e = (v_j , v_k ), sisi e dikatakan bersisian dengan simpul v_j dan simpul v_k .

3. Simpul Terpencil ( Isolated Vertex )

Simpul yang tidak mempunyai sisi yang bersisian dengannya. Atau, dapat juga dinyatakan bahwa simpul terpencil adalah simpul yang tidak satupun bertetangga dengan simpul-simpul lainnya.

 

4. Graf Kosong ( Null atau Empty Graph )

Graf yang himpunan sisinya merupakan himpunan kosong, ditulis sebagai N_n, yang dalam hal ini n adalah jumlah simpul.

5. Derajat ( Degree )

Derajat suatu simpul pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul tersebut.

Pada graf berarah, derajat simpul v dinyatakan dengan d_in(v) dan d_out(v), yang dalam hal ini:

d_in(v) = derajat masuk (in-degree)

= jumlah simpul yang masuk ke simpul v

 

d_out(v) = derajat masuk (in-degree)

= jumlah simpul yang keluar dari simpul v

dan

d(v) = d_in(v) + d_out(v).

Notasi: d(v) menyatakan derajat simpul.

 

6. Lintasan ( Path )

Lintasan yang panjangnya n dari simpul awal v₀ ke simpul tujuan v_n di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v₀ , e₁ , v₁ , e₂ , v₂ ,…,v_n-1 ,e_n ,v_n sedemikian sehingga e₁ = ( v₀ , v₁ ) ,

e₂ = ( v₁ , v₂ ) , … , e_n = ( v_n-1 , v_n ) adalah sisi-sisi dari graf G.

 

7. Siklus ( Cycle ) atau Sirkuit ( Circuit )

Lintasan yang berawal dan berakhir pada simpul yang sama.

8. Terhubung (connected)

Graf tak-berarah G disebut graf terhubung ( connected graph ) jika untuk setiap pasang simpul v_i dan v_j di dalam himpunan V terdapat lintasan dari v_i ke v_j ( yang juga harus berarti ada lintasan dari v_i ke v_j ). Jika tidak, maka G disebut graf tak-terhubung (disconnected graph ). Sedangkan graf berarah G dikatakan terhubung jika graf tak-berarahnya terhubung (graf tak-berarah dari G diperoleh dengan menghilangkan arahnya).

9. Upagraf ( Subgraph )

Misalkan G = (V,E) adalah sebuah graf. G₁ = (V₁ , E₁) adalah upagraf dari G jika V₁ C V dan E₁ C E

 

10. Komplemen Upagraf

Komplemen dari upagaraf G₁ terhadap graf G adalah graf G₂ = (V₂ , E₂) sedemikian sehingga E₂ = E – E₁ dan V₂ adalah himpunan simpul yang anggota – anggota E₂ bersisian dengannya.

11. Upagraf Merentang (Spanning Subgraph )

Upagraf G₁ = (V₁ , E₁) dari G = (V, E) dikatakan upagraf merentang jika V₁ = V ( yaitu G₁ mengandung semua simpul dari G ).

 

12. Cut-set

Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen terhubung.

13. Graf Berbobot ( Weighted Graph )

Graf yang setiap sisinya diberi harga (bobot).

 

 

2.1.4 Beberapa Graf Sederhana Khusus

Ada beberapa graf sederhana khusus yang dijumpai pada banyak aplikasi. Beberapa di antaranya adalah seperti yang didefinisikan di bawah ini :

1. Graf Lengkap ( Complete Graph )

Graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya. Graf lengkap dengan n buah simpil dilambangkan dengan K_n. Setiap simpul pada K_n berderajat n-1. Jumlah sisi pada graf lengkap yang terdiri dari n buah simpul adalah n(n - 1)/2.

2. Graf Lingkaran

Graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan C_n.

3. Graf Teratur ( Regular Graphs )

Graf yang setiap simpulnya mempunyai derajat yang sama. Apabila derajat setiap simpunya adalah r, maka graf tersebut disebut juga graf teratur derajat r.

4. Graf Bipartit ( Bipartite Graph )

Graf G yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V₁ dan V₂, sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V₁ ke sebuah simpul di V₂. Dapat juga dinyatakan sebagai G(V1,V2).

5. Graf Isomorfik ( Isomorphic Graph )

Dua bua graf, G₁ dan G₂ dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduanya sedemikian sehingga jika sisi e bersisian dengan simpul u dan v di G₁ , maka sisi e’ yang berkorespon di G₂ juga harus bersisian dengan simpul u’ dan v’ di G₂.

Syarat-syarat dua buah graf dapat dikatakan isomorfik :

• Mempunyai jumlah simpul yang sama
  
• Mempunyai jumlah sisi yang sama
  
• Mempunyai jumlah simpul yang sama berderajat tertentu
  

6. Graf Planar (Planar Graph)

Graf G yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong (bersilangan). Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan dinamakan graf bidang (plane graph).

7. Pohon (tree)

Graf tak-berarah terhubung yang tidak mengandung sirkuit.

 

2.2 LINTASAN TERPENDEK (SHORTEST PATH)

Menurut teori Graf, persoalan lintasan terpendek (The Shortest Path Problem) adalah merupakan suatu persoalan untuk mencari lintasan antara dua buah simpul pada graf berbobot yang memiliki gabungan nilai jumlah bobot pada sisi graf yang dilalui dengan jumlah yang paling minimum atau dapat dinyatakan juga sebagai berikut :

• Diberikan sebuah graf berbobot (dengan himpunan simpul V, himpunan sisi E, dan fungsi bobot bernilai bilangan riil yang dapat ditulis dengan f : E → R ), dan diberikan elamen v dari V , sehingga dapat dicari sebuah lintasan P dari v ke setiap v‘ dari V, sehingga
  

  
  

  Adalah nilai minimal dari semua lintasan yang menghubungkan v ke v’.
  

Persoalan lintasan terpendek merupakan salah satu persoalan optimasi yang menggunakan graf berbobot, dimana bobot pada setiap sisi graf tersebut dapat kita gunakan untuk menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya.

Lintasan terpendek adalah jalur yang dilalui dari suatu node ke node lain dengan besar atau nilai pada sisi yang jumlah akhirnya dari node awal ke node akhir paling kecil.

Lintasan terpendek adalah lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat lain. Lintasan minimum yang dimaksud dapat dicari dengan menggunakan graf. Graf yang digunakan adalah graf yang berbobot, yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot.

 

2.2.1 Jenis Persoalan Rute Terpendek (Shortest Path Problem)

Ada beberapa macam persoalan lintasan terpendek, antara lain:

a. Lintasan terpendek antara dua buah simpul tertentu (a pair shortets path).

b. Lintasan terpendek antara semua pasangan simpul (all pairs shortest path).

c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain (single-source shoertest path).

d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path)

2.3 ALGORITMA DJIKSTRA

2.3.1 Definisi Algoritma Djikstra

Edsger Wybe Dijkstra, menemukan suatu algoritma untuk mencari lintasan terpendek pada suatu graf. Algoritma Dijkstra pada awalnya diterapkan pada graf berarah, tetapi ternyata algoritma ini juga benar untuk algoritma graf tak-berarah. Algoritma ini menggunakan prinsip greedy yang digunakan untuk menyatakan bahwa pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukannya ke dalam himpunan solusi. Akan tetapi bobot dari graf tersebut harus bernilai bilangan positif (bobot >=0).

Pada dasarnya, algoritma ini merupakan salah satu bentuk algoritma greedy. Algoritma ini termasuk algoritma pencarian graf yang digunakan untuk menyelesaikan masalah lintasan terpendek dengan satu sumber pada sebuah graf yang tidak memiliki cost sisi negatif, dan menghasilkan sebuah pohon lintasan terpendek. Algoritma ini sering digunakan pada routing

2.3.2 Mekanisme Algoritma Djikstra

Algoritma dijkstra mencari lintasan terpendek dalam sejumlah langkah. Algoritma ini menggunakan strategi greedy sebagai berikut :

Untuk setiap simpul sumber (source) dalam graf, algoritma ini akan mencari jalur dengna cost minimum antara simpul tersebut dengan simpul lainnya. Algoritma ini juga dapat digunakan untuk mencari total biaya (cost) dari lintasan terpendek yang dibentuk dari sebuah simpul ke sebuah simpul tujuan. Sebagai contoh, bila simpul pada graf merepresentasikan kota dan bobot sisi merepresentasikan jarak antara 2 kota yang mengapitnya, maka algoritma dijkstra dapat digunakan untuk mencari rute terpendek antara sebuah kota dengan kota lainnya.

Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G.

Algoritma dijkstra dimulai dari sebuah simpul asal dan dalam setiap iterasinya menambahkan sebuah verteks lain ke lintasan terpendek pohon merentang. Verteks ini merupakan titik terdekat ke akar namun masih diluar bagian pohon.

Properti Algoritma Djikstra :

1. Matriks Ketetanggan M[mij]

mij = bobot sisi (i,j) ; pada graf tak berarah mij = mji

mii = 0

mij = ∞ , jika tidak ada sisi dari simpul i ke simpul j

2. Larik S = [si] yang dalam hal ini,

si = 1, jika simpul i termasuk ke dalam lintasan terpendek

si = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek

3. Larik/tabel D = [di] yang dalam hal ini,

di = panjang lintasan dari simpul awal s ke simpul i

Algoritma Lintasan Terpendek Dijkstra :

(Mencari lintasan terpendek dari simpul a ke semua simpul lain}

Langkah 0 (inisialisasi):

- inisialisasi s_i = 0 dan d_i = m_ai untuk i = 1, 2, …, n

 

Langkah 1:

- isi s_a dengan 1 (karena simpul a adalah simpul asal lintasan terpendek, jadi sudah pasti terpilih)

- isi d_a dengan ∞ (tidak ada lintasan terpendek dari simpul a ke a)

 

Langkah 2, 3, … , n-1:

- cari j sedemikian sehingga s_j = 0 dan d_j = min{d₁, d₂, …, d_n}

- isi s_j dengan 1

- perbarui d_i, untuk i = 1, 2, 3, …, n dengan:

d_i (baru) = min{d_i (lama), d_j + m_ji }.

 

Algoritma Djikstra dalam psedo-code :

procedure Dijkstra (input m: matriks, a:simpul awal)

{mencari lintasan terpendek dari simpul awal a ke semua simpul lainya

Masukan : matriks ketetanggaa (m) dari graf berbobot G dan simpul awal a

Keluaran: lintasan terpendek dari a ke semua simpul lainnya}

Deklarasi

s1,s2,…,sn : interger {larik interger}

d1,d2,…,dn : interger {larik interger}

i : interger

Algoritma

{Langkah 0 (inisialisasi) : }

for i ← 1 to n do

s_i ← 0

d_i ← m_ai

endfor

{Langkah 1: }

s_a ← 1 {karena simpul a adalah simpul asal lintasan terpendek, jadi terpilih dalam lintasan terpendek}

d_a ← ∞{tidak ada lintasan terpendek dari simpul a ke a}

{Langkah 2,3,…,n1:}

for i ← 2 to n-1 do

Cari j sedemikian sehingga s_j = 0 dan d_j = min {d₁,d₂,…,d_n}

S_j ← 1 {simpul j sudah terpilih ke dalam lintasan terpendek}

perbarui d_i, untuk i = 1,2,3,…,n

dengan : d_i (baru) = min {d_i(lama),d_j + m_ji}

endfor.