teori graf (materi)

Upload: nugroho-indrawan

Post on 10-Feb-2018

249 views

Category:

Documents


0 download

TRANSCRIPT

  • 7/22/2019 Teori Graf (Materi)

    1/95

    Pertemuan ke-1

    Teori Dasar Graf

    Kelahiran Teori Graf

    Teori Graf mulai dikenal pada saat seorang matematikawan bangsa Swiss, bernama

    Leonhard Euler, berhasil mengungkapkan Misteri Jembatan Konigsberg pada tahun

    1736. Di Kota Konigsberg (sekarang bernama Kalilingrad, di Uni Soviet) mengalir

    sebuah sungai bernama sungai Pregel. Di tengah sungai tersebut terdapat dua buah

    pulau. Dari kedua pulau tersebut terdapat jembatan yang menghubungi ke tepian

    sungai dan diantara kedua pulau. Jumlah jembatan tersebut adalah 7 buah sepertigambar berikut :

    Konon kabarnya, penduduk kota Konigsberg sering berjalan-jalan ke tempat tersebut

    pada hari-hari libur. Kemudian muncul suatu keinginan untuk dapat menikmati daerah

    tersebut dengan melalui ketujuh jambatan tepat satu kali, yakni bermula dari satu

    tempat (A, B, C atau D) dan kembali ke tempat semula. Mereka berusaha untuk

    memperoleh rute yang sesuai dengan keinginan tersebut, dengan selalu mencoba

    Sungai Pregel

    di Kalilingrad(Uni Soviet)

    A

    B

    CD

  • 7/22/2019 Teori Graf (Materi)

    2/95

    menjalaninya. Setelah mencoba berkali-kali dan karena sudah cukup lama tidak

    diperoleh rutenya, akhirnya penduduk tersebut mengirim surat kepada Euler. Euler

    dapat memecahkan masalah tersebut, yakni bahwa perjalanan / rute yang diinginkan

    (yakni berawal dari suatu tempat, melalui ketujuh jembatan tepat satu kali, dan kembali

    ke tempat semula) tidak mungkin dicapai.

    Secara singkat, dalam tulisannya, Euler menyajikan keadaan jembatan Konigsberg

    tersebut seperti gambar berikut :

    Dalam masalah di atas, daratan (tepian A dan B, serta pulau C dan D) disajikan

    sebagai titik dan jembatan disajikan sebagai ruas garis. Euler mengemukakan

    teoremanya yang mengatakan bahwa perjalanan yang diinginkan di atas (yang

    kemudian dikenal sebagai perjalanan Euler) akan ada apabila graf terhubung dan

    banyaknya garis yang datang pada setiap titik (derajat simpul) adalah genap.

    Problema & Model Graf

    Secara umum, langkah-langkah yang perlu dilalui dalam penyelesaian suatu masalahdengan bantuan komputer adalah sebagai berikut :

    Problema Model Yang Tepat Algoritma Program Komputer

    A

    C D

    B

  • 7/22/2019 Teori Graf (Materi)

    3/95

    Contoh problema graf :

    1. Petugas kantor telepon yang ingin mengumpulkan koin-koin dari telepon umum.

    Berangkat dari kantor & kembali ke kantornya lagi.

    Yang diharapkan suatu rute perjalanan dengan waktu minimal.

    Masalah di atas dikenal sebagai Travelling Salesman Problem

    Sebagai contoh :

    Untuk menyelesaikan masalah di atas dapat dipakai Algoritma Tetangga Terdekat

    (yakni menggunakan Metode Greedy)

    = Kantor

    8

    117

    12 9

    11 9

    11 10

    8

    1

    34

    2

    5

    * waktu dalam menit

    1

  • 7/22/2019 Teori Graf (Materi)

    4/95

    2. Perancangan Lampu Lalu Lintas.

    Yang diharapkan pola lampu lalu lintas dengan jumlah fase minimal.

    Sebagai contoh :

    Untuk menyelesaikan masalah di atas dapat dipakai Algoritma Pewarnaan Graf (juga

    dikenal sebagai Graph Coloring, yakni menggunakan Metode Greedy)

    Graf Secara FormalSebuah Graf G mengandung 2 himpunan :

    (1). Himp. V, yang elemennya disebut simpul

    Vertex / point / titik / node

    (2). Himp. E, yang merupakan pasangan tak terurut dari simpul-simpul, disebut ruas

    C D

    B E

    A

    F

    A

    A

    B

    B

    A

    D

    D

    FB

    F

    FC

    E

    C

    E

    C

    E

    B

    C

    E

  • 7/22/2019 Teori Graf (Materi)

    5/95

    Edge / rusuk / sisi

    Sehingga sebuah graf dinotasikan sebagai G ( V, E )

    Contoh :

    G ( V, E )

    V = { A, B, C, D }

    E = { ( A, B ), ( B, C ), ( C, D ), ( D, A ), ( B, D ) }

    Secara Geometri :

    Tidak ada ketentuan khusus dalam penyajian graf secara geometri, seperti dimana dan

    bagaimana menyajikan simpul dan ruas. Berikut contoh penyajian Graf yang sama,

    tetapi disajikan berbeda.

    e2

    e3e1 e5

    e4CD

    A

    B

    terdiri dari 4 simpul dan 5 ruas

    C

    A

    D

    A

    A

    B

    D B

    C

    DB

    C

  • 7/22/2019 Teori Graf (Materi)

    6/95

    Beberapa istilah lain dalam graf :

    Berdampingan

    simpul U dan V disebut berdampingan bila terdapat ruas (U,V)

    Order

    banyaknya simpul

    Size

    banyaknya ruas

    Self-loop (loop) / Gelung

    ruas yang menghubungkan simpul yang sama ( sebuah simpul )

    Ruas sejajar / berganda

    ruas-ruas yang menghubungkan 2 simpul yang sama

    Sebuah graf dikatakan multigraf bila graf tersebut mengandung ruas sejajar atau

    gelung. Sedangkan graf yang tidak mengandung ruas sejajar atau gelung dikenal

    sebagai graf sederhana, atau yang disebut graf. Adapun contoh multigraf adalah

    sebagai berikut.

    Subgraf

    G(V, E) adalah Subgraf dari G (V, E) bila : V V dan E E

    Apabila E mengandung semua ruas di E yang kedua ujungnya di V , maka

    G adalah Subgraf yang dibentuk oleh V (Spanning Subgraph)

    A

    AA

    e2

    A e3

    e4e1

    e5

    e6

    Multigraf

  • 7/22/2019 Teori Graf (Materi)

    7/95

    Contoh :

    Graf berlabel

    Graf berlabel/ berbobot adalah graf yang setiap ruasnya mempunyai nilai/bobot berupabilangan non negatif.

    Contoh :

    e2

    e3e1 e5

    e4CD

    AB

    G :

    e5e1

    A B

    D

    G :

    G subgraf dari G

    e2

    e5e1

    A B

    D

    G :

    G spanning subgrapf dari G

    B D F

    C GE

    HA

    3

    19

    8

    13

    3

    3

    4

    222

    12

    6

    3

  • 7/22/2019 Teori Graf (Materi)

    8/95

    Isomorfisma

    G (V,E) dan G* (V*,E*) adalah 2 buah Graf.

    f : V V * suatu fungsi satu-satu dan pada, sedemikian sehingga (u,v) adalah ruas

    dari G jika dan hanya jika (f (u),f(v)) adalah ruas dari G *

    Maka f disebut fungsi yang isomorfisma dan G & G * adalah graf-graf yang isomorfis

    Contoh :

    Graf yang berbentuk huruf A & R, X & K, F & T, dan V & Z, di bawah ini adalah

    isomorfis.

    Homomorfis

    Jika G* dan G** diperoleh dari G dengan membagi beberapa ruas dari G oleh

    penambahan beberapa simpul pada ruas tersebut, maka kedua graf G* dan G**

    disebut homomorfis

  • 7/22/2019 Teori Graf (Materi)

    9/95

    Contoh :

    Operasi pada Graf

    Berdasarkan definisi graf (yang terdiri dari 2 himpunan) dan operasi pada himpunan,maka pada graf juga dapat dilakukan operasi-operasi. Bila diketahui 2 buah graf :

    G1(V1,E1) dan G2(V2,E2), maka :

    1. Gabungan G1G2 adalah graf dengan himpunan V nya = V1V2dan himpunan Enya = E1E2

    2. Irisan G1G2adalah graf dengan himpunan V nya = V1V2dan himpunan E nya =E1E2

    3. Selisih G1- G2 adalah graf dengan himpunan V nya = V1dan himpunan E nya = E1-

    E2

    Sedangkan Selisih G2 G1 adalah graf dengan himpunan V nya = V2dan himpunan

    E nya = E2 E1

    4. Penjumlahan Ring G1G2 adalah graf yang dihasilkan dari

    (G1G2) (G1G2) atau (G1- G2)(G2- G1)

    G G* G**

  • 7/22/2019 Teori Graf (Materi)

    10/95

    Contoh :

    CD

    BA

    E

    e2e4

    e1

    e3

    e6e5

    e7e8

    A

    F

    D

    e1 B

    C

    e4 e2

    e10

    e3

    e9

    D

    A e1 B

    C

    e4 e2

    e3CD

    BA

    E

    e2e4

    e1

    e3

    e6e5

    e7e8

    e10 e9

    CD

    BA

    E

    e6e5

    e7e8

    CD

    e10 e9

    CD

    BA

    E

    e6e5

    e7e8

    e10 e9

    G1 G2

    G1G2G1G2

    G1G2

    G1 - G2 G2 G1

  • 7/22/2019 Teori Graf (Materi)

    11/95

    Graf Null / Hampa

    Ada beberapa pengertian tentang graf null/hampa. Di sini akan dipakai pengertian

    bahwa suatu graf dikatakan graf null/hampa bila graf tersebut tidak mengandung ruas.

    Contoh :

    Suatu graf G dikatakan dikomposisikan menjadi K dan L bila G = K L dan K L = Contoh :

    Penghapusan / Deletion

    Penghapusan dapat dilakukan pada simpul ataupun ruas.

    1) Penghapusan Simpul .

    GL

    K

    D

    A

    A

    A

    B

    B

    B

    C

    C

    CD

    G :

    V1

    V3

    V2

    V danE =

  • 7/22/2019 Teori Graf (Materi)

    12/95

    Notasinya : G {V}

    Contoh :

    Penghapusan Simpul V2

    2) Penghapusan Ruas .

    Notasinya : G {e}

    Contoh :

    Penghapusan Ruas e3

    Pemendekan / Shorting

    Pemendekan/Shorting adalah menghapus simpul yang dihubungkan oleh 2 ruas

    (simpul berderajat 2), lalu menghubungkan titik-titik ujung yang lain dari kedua ruas

    tersebut.

    Contoh :

    VV1 V2

    V3V4

    V5

    V6V7V7 V6

    V5

    V4 V3

    e1 e1

    e2 e2e3 e4 e4

    e5 e5

  • 7/22/2019 Teori Graf (Materi)

    13/95

    pemendekan terhadap simpul A dan C

    Derajat Graf

    Derajat graf adalah jumlah dari derajat simpul-simpulnya. Sedangkan derajat simpul

    adalah banyaknya ruas yang incidence (terhubung) ke simpul tersebut.

    Contoh :

    d (A) = 2

    d (B) = 5

    d (C) = 3

    d (D) = 3d (E) = 1

    d (F) = 0

    +

    = 14 = 2 x Size

    B

    C

    F

    ED

    A

    A

    DD C

    B B

  • 7/22/2019 Teori Graf (Materi)

    14/95

    Berdasarkan derajat simpul, sebuah simpul dapat disebut :

    Simpul Ganjil, bila derajat simpulnya merupakan bilangan ganjil

    Simpul Genap, bila derajat simpulnya merupakan bilangan genap

    Simpul Bergantung / Akhir, bila derajat simpulnya adalah 1

    Simpul Terpencil, bila derajat simpulnya adalah 0

    Keterhubungan

    Dalam keterhubungan sebuah graf, akan dikenal beberapa istilah-istilah berikut :

    1. Walk : barisan simpul dan ruas

    2. Trail : Walk dengan ruas yang berbeda

    3. Path / Jalur : Walk dengan simpul yang berbeda

    4. Cycle / Sirkuit : Trail tertutup dengan derajat setiap simpul = 2

    Contoh :

    1) A, B, C, D, E, F, C, A, B, D, C Walk

    2) A, B, C, D, E, F, C, A Trail

    3) A, B, C, A Cycle

    4) A, B, D, C, B, D, E Walk5) A, B, C, D, E, C, F Trail

    6) A, B, D, C, E, D Trail

    7) A, B, D, E, F, C, A Cycle

    8) C, E, F Path

    ED

    A

    B

    FC

    b

    d

    h

    e

    gc k

    f

    a

  • 7/22/2019 Teori Graf (Materi)

    15/95

    9) B, D, C, B Cycle

    10) C, A, B, C, D, E, C, F, E Trail

    11) A, B, C, E, F, C, A Trail

    Graf yang tidak mengandung cycle disebut dengan Acyclic

    Contoh :

    Suatu graf G disebut terhubung jika untuk setiap 2 simpul dari graf terdapat jalur yang

    menghubungkan kedua simpul tersebut.

    Subgraf terhubung suatu graf disebut komponen dari G bila subgraf tersebut tidak

    terkandung dalam subgraf terhubung lain yang lebih besar.Jarak antara 2 simpul dalam graf G adalah panjang jalur terpendek antara ke-2 simpul

    tersebut.

    Diameter suatu graf terhubung G adalah maksimum jarak antara simpul-simpul G.

    Ada Subgraf S dari graf terhubung G, yang bila kita ambil / pindahkan dari G, akan

    menyebabkan G tidak terhubung.

    Kalau tidak ada Subgraf sejati R dari S, yang pemindahannya juga menyebabkan G

    tidak terhubung, maka Sdisebut Cut-Setdari G.

    Graf Regular

    Sebuah graf dikatakan graf regular bila derajat setiap simpulnya sama.

  • 7/22/2019 Teori Graf (Materi)

    16/95

    Contoh :

  • 7/22/2019 Teori Graf (Materi)

    17/95

    Pertemuan ke-2

    Teori Dasar Graf (Lanjutan)

    Matriks dan Graf

    Untuk menyelesaikan suatu permasalahan model graf dengan bantuan komputer, maka

    graf tersebut disajikan dalam bentuk matriks. Matriks-matriks yang dapat menyajikan

    model graf tersebut antara lain :

    Matriks Ruas

    Matriks Adjacency

    Matriks IncidenceSebagai contoh, untuk graf seperti di bawah ini :

    Maka,

    Matriks Ruas :

    V4V5

    V2 V3

    V1

    e6

    e5

    e4

    e3

    e2

    e1

    e8

    e7

    1 2

    1 31 4

    1 5

    2 3

    3 4

    3 5

    4 5

    n x 2

  • 7/22/2019 Teori Graf (Materi)

    18/95

    Atau :

    Matriks Adjacency :

    Matriks Incidence :

    Graf PlanarSebuah graf dikatakan graf planar bila graf tersebut dapat disajikan (secara geometri)

    tanpa adanya ruas yang berpotongan. Sebuah graf yang disajikan tanpa adanya ruas

    yang berpotongan disebut dengan penyajian planar/map/peta.

    Contoh :

    1 1 1 1 2 3 3 4

    2 3 4 5 3 4 5 5

    2 x n

    V1 V2 V3 V4 V5

    V1 0 1 1 1 1

    V2 1 0 1 0 0

    V3 1 1 0 1 1

    V4 1 0 1 0 1

    V5 1 0 1 1 0

    e1 e2 e3 e4 e5 e6 e7 e8

    V1 1 1 0 1 1 0 0 0

    V2 1 0 1 0 0 0 0 0

    V3 0 1 1 0 0 1 1 0

    V4 0 0 0 1 0 1 0 1

    V5 0 0 0 0 1 0 1 1

    Graf Planar

    K4

    Penyajian Planar

  • 7/22/2019 Teori Graf (Materi)

    19/95

    Graf yang termasuk planar antara lain :

    Tree / Pohon

    Kubus

    Bidang Empat

    Bidang Delapan Beraturan

    Tree / Pohon

    Kubus

    BidangEmpat

    BidangDelapan

    Beraturan

  • 7/22/2019 Teori Graf (Materi)

    20/95

    Pada penyajian planar/map, dikenal istilah region. Derajat dari suatu region adalah

    panjang walk batas region tersebut

    Contoh :

    d ( r1 ) = 3

    d ( r2 ) = 3

    d ( r3 ) = 5

    d ( r4 ) = 4

    d ( r5 ) = 3+

    = 18 = 2 x SIZE

    Region dengan batasnya gelung, maka d (r) = 1

    Region dengan batasnya ruas sejajar, maka d (r) = 2

    Formula Euler untuk Graf Planar

    Untuk Graf Planar berlaku Formula Euler berikut :

    V E + R = 2

    Dimana p = jumlah simpul dan q = jumlah ruas

    r1

    r4

    r5

    r2

    r3

    AB

    C

    D

    FE

  • 7/22/2019 Teori Graf (Materi)

    21/95

    Graf Non-Planar

    Sebuah graf yang tidak dapat disajikan (secara geometri) tanpa adanya ruas yang

    berpotongan dikenal sebagai graf non planar.

    Contoh :

    K3,3

    Utility Graph K5= Bintang

    Teorema Kuratowski ( 1930 )

    Suatu graf adalah Non-Planar jika dan hanya jika mengandung subgraf yang

    Homomorfis ke K3,3atau ke K5

    Pewarnaan Graf

    Pewarnaan graf adalah pemberian warna terhadap simpul-simpul graf dimana 2 buah

    simpul yang berdampingan tidak boleh mempunyai warna yang sama.

    G berwarna n artinya graf tersebut menggunakan n warna.

    Bilangan kromatis dari G = K(G) adalah jumlah minimum warna yang dibutuhkan.

    Algoritma yang dapat digunakan untuk mendapatkan bilangan kromatis dari sebuah

    graf adalah Algoritma Welch-Powell.

    Adapun langkah-langkahnya adalah :

    1. Urutkan simpul-simpul berdasarkan derajatnya.

    Dari besar ke kecil.

    2. Warnai.

  • 7/22/2019 Teori Graf (Materi)

    22/95

    Contoh :

    Langkah 1 :

    urutan simpulnya dari besar ke kecil adalah : E, C, G, A, B, D, F, H

    Langkah 2 :

    mewarnai :

    warna Merah : E, A

    warna Putih : C, D, H

    warna Biru : G, B, F

    Sehingga bilangan kromatis graf di atas adalah 3.

    Teorema :

    Pernyataan berikut adalah ekivalen :

    (1) G berwarna 2

    (2) G adalah bipartisi

    (3) Setiap sirkuit dalam G mempunyai panjang genap

    Graf Lengkap k dengan n simpul membutuhkan n warna

    G

    A B C

    D

    EF

    H

  • 7/22/2019 Teori Graf (Materi)

    23/95

    Teorema :

    Suatu graf planar G adalah berwarna 5

    Pewarnaan Region

    Pewarnaan region dapat dilakukan (seperti pemberian warna pada wilayah-wilayah di

    peta) dengan cara membuat dual dari map tersebut. Gambarkan sebuah simpul baru

    pada masing-masing region suatu map M, kemudian buat sebuah ruas yang

    menghubungkan simpul pada 2 buah region yang berdampingan bila terdapat ruas

    sebagai batas / persekutuan kedua region tersebut. Buatlah tanpa adanya ruas baru

    yang berpotongan, maka akan terbentuk suatu map M*, yang disebut dual dari map M.

    Setelah Dualnya terbentuk, dapar dilakukan pewarnaan terhadap simpul-simpulnya.

    Simpul-simpul tersebut mewakili region sebelumnya, sehingga warna yang digunakan

    untuk suatu simpul berarti warna yang dapat digunakan untuk pewarnaan region yang

    diwakilinya.

    Teorema : suatu map M adalah berwarna 5

    Setiap graf planar adalah berwarna (simpul) 4

    Dibuktikan oleh Apple & Haken (1976) 2000 Graf, jutaan kasus.

  • 7/22/2019 Teori Graf (Materi)

    24/95

    Pertemuan ke-3

    Pohon (Tree)

    Pohon

    Tree atau pohon adalah graf terhubung yang tidak mengandung sirkuit.

    Untuk itu perlu diingat kebali bahwa :

    Suatu Graf G disebut terhubung apabila untuk setiap dua simpul dari graf G

    selalu terdapat jalur yang menghubungkan kedua simpul tersebut.

    Sirkuit atau cycle adalah suatu lintasan tertutup dengan derajat setiap simpul

    dua.

    Contoh :

    Sifat :

  • 7/22/2019 Teori Graf (Materi)

    25/95

    Suatu Graf G adalah Pohon jika dan hanya jika terdapat satu dan hanya satu jalur

    diantara setiap pasang simpul dari Graf G.

    Teorema :

    Suatu Graf G dengan n buah simpul adalah Pohon jika :

    (1) G terhubung dan tak mengandung sirkuit, atau

    (2) G tidak mengandung sirkuit dan mempunyai n-1 buah ruas, atau

    (3) G mempunyai n-1 buah ruas dan terhubung

    Pohon Rentangan

    Suatu spanning tree atau pohon rentangan adalah suatu subgraf dari graf G yang

    mengandung semua simpul dari G, dan merupakan suatu pohon.

    Contoh :

    Contoh :

    GRAF G SPANNING TREE

    n simpul n simpul

    m ruas n 1 ruas

    m ( n 1)

    BRANCH

    (CABANG)

    CHORD

    Keterangan

    BranchChord

  • 7/22/2019 Teori Graf (Materi)

    26/95

    Graf G :

    Pohon Rentangan dari Graf G :

  • 7/22/2019 Teori Graf (Materi)

    27/95

    Pohon Rentangan Minimal

    Apabila G suatu Graf berbobot (Suatu Network); maka pohon rentangan minimal dari

    graf adalah pohon rentangan dengan jumlah bobot terkecil.

    Minimal spanning tree

    Contoh :

    Untuk mendapatkan pohon rentangan minimal dapat digunakan Algoritma berikut :

    Solin

    Kruskal

    Prims

    SOLIN

    1. Urutkan ruas dari G menurut bobotnya; dari besar ke kecil.

    2. Lakukan penghapusan ruas berdasarkan urutan yang sudah dilakukan; dengan

    ketentuan bahwa penghapusan ruas tersebut tidak menyebabkan graf menjadi

    tidak terhubung.

    .

    . .

    .

    .

    .

    . . .

    11

    19

    10

    13

    1615

    918

    14

    12

    8 17

  • 7/22/2019 Teori Graf (Materi)

    28/95

    KRUSKAL

    1. Urutkan ruas dari G menurut bobotnya; dari kecil ke besar.

    2. Lakukan penambahan ruas berdasarkan urutan yang sudah dilakukan; dengan

    ketentuan bahwa penambahan ruas tersebut tidak menyebabkan adanya sirkuit.

    PRIMS

    = Kruskal + menjaga graf tetap terhubung

    Untuk mencari pohon rentangan maksimal, dapat dilakukan dengan dengan cara

    merubah bobot tiap ruas menjadi (bobot yang lama)

    Definisi :

    Hutan atau foresi adalah graf yang tidak mengandung sirkuit.

    Pohon adalah hutan yang terhubung

    Contoh :

    Pertemuan ke-4

  • 7/22/2019 Teori Graf (Materi)

    29/95

    Berbagai Jenis Pohon (Tree)

    Pohon Berakar

    Suatu pohon berakar R adalah suatu pohon bersama dengan suatu simpul r yang

    dirancang/ditunjuk sebagai akar (root) dari R. Seperti diketahui bahwa hanya terdapat

    satu jalur antara r dengan simpul lain v pada pohon pohon tersebut. Panjang jalur

    antara r dengan simpul v disebut level atau kedalaman simpul v. Simpul bukan akar,

    yang berderajat satu disebut daun. Jalur antara suatu simpul dengan suatu daun

    disebut cabang (branch).

    Berikut ini contoh pohon berakar.

    Contoh :

    Suatu pohon dapat dijadikan suatu pohon berakar cukup dengan mengangkat salah

    satu simpul sebagai akar. Dengan adanya akar, setiap ruas dari pohon seolah-olah

    mempunyai arah, yang bermula dari akar tersebut. Simpul u dikatakan mendahului

    simpul v jika jalur dari akar r ke v melalui u. Dikatakan u mendahului langsung v bila u

    mendahului v serta simpul u dan v berdampingan. Pada contoh di atas, a mendahului d,

    mendahului e, dan mendahului h.

    R

    b c

    d e f g

    a

    hi j

  • 7/22/2019 Teori Graf (Materi)

    30/95

    Suatu pohon berakar dapat digunakan untuk menelusurisemua kemungkinan dari

    kejadian, dengan masing-masing kejadian dapat muncul dalam sejumlah hingga cara.

    Bebarapa contoh lain yang penting dari pohon berakar adalah pohon binar (binary tree)

    dan pohon sintaks (syntax tree) atau pohon derivasi (derivation tree).

    Pohon Binar

    Dalam struktur data, pohon memegang peranan yang cukup penting. Struktur ini

    biasanya digunakan terutama untuk menyajikan data yang mengandung hubungan

    hirarkikal antara elemen-elemen mereka.

    Bentuk pohon khusus yang lebih mudah dikelola dalam komputer adalah pohon binary.

    Bentuk ini merupakan bentuk pohon yang umum. Sebuah pohon binar T didefinisikan

    terdiri dari sebuah himpunan hingga elemen yang disebut simpul (node), sedemikian

    sehingga :

    a. T adalah hampa (disebut pohon null) atau

    b. T mengandung simpul R yang dipilih (dibedakan dari yang lain), disebut

    akar (root) dari T, dan simpul sisanya membentuk 2 pohon binar (subpohonkiri dan subpohon kanan dari R) T1 dan T2 yang saling lepas.

    Perhatikan bahwa pendefinisian pohon binar di atas adalah rekursif. Jika T1 tidak

    hampa, maka simpul akarnya disebut suksesor kiri dari R. Hal serupa untuk akar dari

    T2 (tidak hampa) disebut suksesor kanan dari R.

    Untuk menyajikan pohon binar, simpul akar adalah simpul yang digambar pada bagian

    paling atas. Sedangkan suksesor kiri digambarkan sebagai garis ke kiri bawah dan

    suksesor kanan sebagai garis ke kanan bawah.

    Contoh :

  • 7/22/2019 Teori Graf (Materi)

    31/95

    Pohon Sintaks

    Untuk menjelaskan mengenai bahasa secara teoritis dan formal, kita lihat terlebih

    dahulu sebuah kalimat sehari-hari dalam bahasa Indonesia, yaitu :

    SI KUCING KECIL MENENDANG BOLA BESAR

    Gambar penguraian kalimat di atas membentuk struktur pohon, yang disebut pohon

    sintaks dari kalimat. Disini kalimat dibagi-bagi berdasar jenis dan fungsi kata. Dari

    pelajaran bahasa Indonesia kita tahu bahwa kalimat di atas telah benar susunannya,

    atau telah benar tata bahasanya.Pohon sintaks dari kalimat di atas dapat dilihat sebagai berikut :

    A

    C

    GD E F

    I

    B

    H

    J K

  • 7/22/2019 Teori Graf (Materi)

    32/95

    KALIMAT

    Besar

    PredikatSubyek

    BolaMenendangKecilSi Kucing

    Obyek

    Kata

    Keadaan

    Kata

    Benda

    Kata

    Kerja

    Kata

    Keadaan

    Kata

    Sandang

    Kata

    Benda

  • 7/22/2019 Teori Graf (Materi)

    33/95

    Pertemuan ke-5

    Graf Berarah

    Graf Berarah

    Di dalam situasi yang dinamis, seperti pada komputer digital ataupun pada sistem aliran

    (flow system), konsep graf berarah lebih sering digunakan dibandingkan dengan

    konsep graf tak berarah.

    Suatu graf berarah (Directed Graph, yang dikenal sebagai Digraf) D terdiri dari 2

    himpunan :

    (1). Himp. V, yang elemennya disebut simpul

    Vertex / point / titik / node

    (2). Himp. A, yang merupakan pasangan terurut dari simpul-simpul, disebut ruas

    berarah

    Arc / arkus

    Sehingga sebuah digraf dinotasikan sebagai D ( V, A )

    Contoh :

    Sebuah graf berarah D(V,A), dengan :

    1. V = { 1, 2, 3, 4 }

    2. A = { (1,4), (2,1), (2,1), (4,2), (4,3), (2,3), (2,2) }

    Arc (2,2) disebut gelung (self-loop), sedangkan arc (2,2) muncul 2 kali, disebut arc

    sejajar atau arc berganda.

    4

    3

    2

    1

  • 7/22/2019 Teori Graf (Materi)

    34/95

    Apabila arc suatu graf berarah mempunyai suatu bobot, graf berarah tersebut

    dinamakan suatu jaringan atau network.

    Beberapa Pengertian dalam graf berarah :

    Derajat ke luar (out degree) suatu simpul adalah banyaknya arc yang mulai /

    keluar dari simpul tersebut.

    Derajat ke dalam (in degree) suatu simpul adalah banyaknya arc yang berakhir /

    masuk ke simpul tersebut.

    Simpul berderajat ke dalam = 0 disebut sumber (source), sedangkan simpul

    berderajat ke luar = 0 disebut muara (sink).

    Pengertian Walk, Trail, Path (Jalur) dan Sirkuit (Cycle) berlaku pula pada graf

    berarah, dimana harus sesuai dengan arah arc. Kalau tidak sesuai dengan arah

    arc-nya, maka disebut sebagai semi walk, semi path atau semi trail.

    Pada graf berarah terdapat 3 pengertian keterhubungan, yakni :

    Terhubung lemah, jika terdapat suatu semi path antara setiap 2 simpul dari D.

    Terhubung unilateral, jika antara setiap 2 simpul u dan v dari D, terdapat jalur dari

    u ke v atau dari v ke u.

    Terhubung kuat, jika antara setiap 2 simpul u dan v dari D, terdapat jalur dari u kev dan dari v ke u.

    Contoh :

    A B

    C

    A B

    C

    A B

    C

    Terhubung Lemah Terhubung Unilateral Terhubung Kuat

  • 7/22/2019 Teori Graf (Materi)

    35/95

    Relasi dan Matriks

    Pandang D(V,A) suatu graf berarah tanpa arc sejajar, maka A adalah himpunan bagian

    dari V x V (produk Cartesis himpunan), jadi merupakan Relasi pada V. Sebaliknya bila

    R adalah Relasi pada suatu himpunan V, maka D(V,R) merupakan graf berarah tanpa

    arc sejajar. Jadi konsep Relasi dan konsep graf berarah tanpa arc sejajar adalah satu

    dan sama.

    Misalkan D(V,A) suatu graf berarah dengan simpul v1, v2, , vm. Matriks M berukuran

    (mxm) merupakan matriks (matriks adjacency) dari D, dengan mendefinisikan sebagai

    berikut :

    M = (Mij), dengan mijbanyaknya arc yang mulai di vidan berakhir di vj

    Bila D tidak mengandung arc berganda, maka elemen M adalah 0 dan 1. Kalau Graf

    berarah mengandung arc berganda, elemen M merupakan bilangan bulat non negatif.

    Jadi suatu matriks berukuran (mxm) yang elemennya bilangan bulat non negatif

    menyatakan secara tunggal suatu graf berarah dengan m simpul.

    Contoh :

    Teorema :

    M adalah Matriks dari sutau graf berarah D, maka elemen baris ke i kolom ke j dari

    Matriks Mnmenyatakan banyaknya walk dengan panjang n dari simpul vike simpul vj.

    V2

    V4

    V3

    V1 1 0 0 0

    1 0 0 0

    0 2 0 1

    0 0 1 0

    D(V,A) :

    Matriks M

  • 7/22/2019 Teori Graf (Materi)

    36/95

    Algoritma Jalur Terpendek

    Pandang D suatu graf berarah yang hingga dengan tiap-taip arc mempunyai bobot. Jadi

    D merupakan suatu network. Kita hendak menentukan Jalur Terpendek antara 2 simpul

    u dan v.

    Gambar berikut merupakan suatu network. Kita ingin menghitung jalur terpendek dari

    simpul u ke simpul v.

    Untuk dapat menentukan jalur terpendeknya, kita gunakan cara berikut :

    Buat table jarak, dengan tiap kolom mewakili simpul yang ada, dan kita isikan

    data jarak dari satu simpul ke simpul lainnya sesuai dengan kolom yang ada.

    Usahakan diurut dari yang kecil ke besar.

    Kita mulai dengan simpul u sebagai simpul awal. Beri harga = 0. Ambil simpul

    dengan jarak terdekat dari u, dalam hal ini z (uz =2), kemudian tandai uz. Semua

    arc lain, yang berakhir di z kita hapus. Beri harga = 2 pada kolom z. Kemudian

    u x y z a b c v

    uz = 2

    ux = 4

    uy = 6

    xy = 3

    xa = 4

    yc = 1

    yb = 2

    zy = 2

    zc = 5

    ab = 2

    av = 3

    bv = 3 cv = 3

    u

    x a

    y b v

    cz

    4

    22

    3

    6

    1

    5

    2

    2

    3

    3

    3

    4

    SumberMuara

  • 7/22/2019 Teori Graf (Materi)

    37/95

    pada judul kolom yang telah diberi harga, kita tandai *. Hasil langkah tersebut

    dapat dilihat pada tabel berikut ini :

    Dari simpul u dan z (yang telah ditandai *), dicari simpul lain yang jaraknya

    terdekat dihitung dari u. Jadi harus diperhitungkan harga yang tertulis di judul

    kolom. Disini ux =4 merupakan nilai terkecil, sehingga kita beri harga pada kolom

    x = 4, kemudian kita hapus data yang berakhir dengan x dan kita beri tanda *

    pada judul kolom x. Hasil langkah tersebut dapat dilihat pada tabel berikut ini :

    Demikian proses dilanjutkan berturut-turut sebagai berikut :

    u* (0) x y z* (2) a b c v

    uz = 2ux = 4

    uy = 6

    xy = 3xa = 4

    yc = 1yb = 2

    zy = 2zc = 5

    ab = 2av = 3

    bv = 3 cv = 3

    u* (0) x* (4) y z* (2) a b c v

    uz = 2

    ux = 4

    uy = 6

    xy = 3

    xa = 4

    yc = 1

    yb = 2

    zy = 2

    zc = 5

    ab = 2

    av = 3

    bv = 3 cv = 3

    u* (0) x* (4) y* (4) z* (2) a b c v

    uz = 2

    ux = 4

    uy = 6

    xy = 3

    xa = 4

    yc = 1

    yb = 2

    zy = 2

    zc = 5

    ab = 2

    av = 3

    bv = 3 cv = 3

    u* (0) x* (4) y* (4) z* (2) a b c* (5) v

    uz = 2

    ux = 4

    uy = 6

    xy = 3

    xa = 4

    yc = 1

    yb = 2

    zy = 2

    zc = 5

    ab = 2

    av = 3

    bv = 3 cv = 3

  • 7/22/2019 Teori Graf (Materi)

    38/95

    Dari tabel terakhir, data yang kita gunakan adalah data yang ditandai kotak. Terlihat

    dari judul kolom masing-masing simpul, harga yang merupakan jarak terpendek dari

    simpul awal (dalam hal ini simpul u) ke simpul tersebut. Sebagai contoh, jarak

    terpendek dari u ke v adalah 8. Sedangkan dari u ke c adalah 5, dan seterusnya.

    Jalur terpendek dari u ke v dapat ditentukan dengan cara mundur, yakni dari data yang

    ada yang berakhir dengan v adalah cv, kemudian yang berakhir dengan c adalah yc,

    yang berakhir dengan y adalah zy dan yang berakhir dengan z adalah u. Sehingga jalur

    yang dimaksud adalah : u z y c v

    Penggambaran dari solusi tersebut adalah sebagai berikut :

    u* (0) x* (4) y* (4) z* (2) a b* (6) c* (5) v

    uz = 2

    ux = 4

    uy = 6

    xy = 3

    xa = 4

    yc = 1

    yb = 2

    zy = 2

    zc = 5

    ab = 2

    av = 3

    bv = 3 cv = 3

    u* (0) x* (4) y* (4) z* (2) a* (8) b* (6) c* (5) v

    uz = 2

    ux = 4

    uy = 6

    xy = 3

    xa = 4

    yc = 1

    yb = 2

    zy = 2

    zc = 5

    ab = 2

    av = 3

    bv = 3 cv = 3

    u* (0) x* (4) y* (4) z* (2) a* (8) b* (6) c* (5) v* (8)

    uz = 2

    ux = 4

    uy = 6

    xy = 3

    xa = 4

    yc = 1

    yb = 2

    zy = 2

    zc = 5

    ab = 2

    av = 3

    bv = 3 cv = 3

  • 7/22/2019 Teori Graf (Materi)

    39/95

    Problema Aliran Maksimal

    Tujuan dari problema aliran maksimal adalah mengatur jadwal pengiriman barang agar

    jumlah barang yang dikirimkan dari suatu simpul ke simpul lain (yang tertentu) adalah

    maksimum. Simpul yang mengirimkan (simpul awal) disebut sumber (source) dan

    simpul yang menerima kiriman disebut muara (sink). Antara sumber dan muaraterdapat pula simpul lain yang disebut simpul perantara. Dalam hal ini ditetapkan bahwa

    simpul perantara tidak dapat menyimpan barang.

    Contoh :

    u

    x a

    y b v

    cz

    4

    22

    3

    6

    1

    5

    2

    2

    3

    3

    3

    4

    SumberMuara

    a b

    c

    dsumber muara

    8410

    04

    5

    5

    100

    0

    07

  • 7/22/2019 Teori Graf (Materi)

    40/95

    Untuk menyelesaikan problema aliran maksimal ini dapat digunakan beberapa cara,

    antara lain dengan menelusuri satu persatu jalur yang dapat dilalui ataupun dengan

    memanfaatkan max flow min cut. Adapun aliran maksimal dari contoh ini adalah 22.

  • 7/22/2019 Teori Graf (Materi)

    41/95

    Pertemuan ke-6

    Graf Berarah (Lanjutan)

    Mesin State Hingga

    Mesin State Hingga merupakan suatu struktur abstrak yang didefinisikan terdiri atas :

    (1) Himpunan hingga A, berisi simbol input

    (2) Himpunan hingga S, berisi internal state

    (3) Himpunan hingga Z, berisi simbol output

    (4) Sebuah fungsi f : S x A S, disebut fungsi next-state(5) Seubuah fungsi g : S x A Z disebut fungsi output

    M ( A, S, Z, f, g)

    M (A, S, Z, q0, f, g)

    Contoh : M ( A, S, Z, f, g) dengan :

    (1) A = (a,b)(2) S = (q0, q1, q2)

    (3) Z = ( x, y, z)

    (4) f : S x A S, yang didefinisikan sebagai :

    f (qo, a) = q1 f (q0, b) = q2

    f (q1, a) = q2 f (q1, b) = q1

    f (q2, a) = qo f (q2, b) = q1

    (5) g : S x A Z, yang didefinisikan sebagai :

    g (q0, a) = x g (q0, b) = y

    g (q1, a) = x g (q1, b) = z

    g (q2, a) = z g (q2, b) = y

    INPUT : Untai

    OUTPUT : Untai

  • 7/22/2019 Teori Graf (Materi)

    42/95

    Automata Hingga

    Automata Hingga merupakan suatu struktur abstrak yang didefinisikan terdiri atas :(1) Himpunan hingga A, berisi simbul input

    (2) Himpunan hingga S, berisi internal state

    (3) Himpunan T (dimana T S), elemennya disebut state penerima

    (4) State awal (biasanya q0), anggota S

    (5) Fungsi next-state f : S x A S

    M (A, S, T, qo, f)

    Contoh : M (A, S, T, qo, f) dengan :

    (1) A = {a, b }

    (2) S = {q0, q1, q2 }

    (3) T = {qo, q1 }

    (4) State awal = q0

    (5) Fungsi next-state f : S x A S, yang didefinisikan sebagai tabel berikut :

    f a b

    q0

    q1

    q2

    q0

    q0

    q2

    q1

    q2

    q2

    INPUT : Untai

    OUTPUT : Diterima

    atau ditolak

  • 7/22/2019 Teori Graf (Materi)

    43/95

    Pertemuan ke-7

    Algor itma

    Algoritma

    Istilah algoritma pertama kali diperkenalkan oleh seorang ahli matematika yaitu Abu

    Jafar Muhammad Ibnu Musa Al Khawarizmi.

    Yang dimaksud dengan algoritma adalah :

    Urutan dari barisan instruksi untuk menyelesaikan suatu masalah

    Adapun algoritma dapat dinyatakan dalam bentuk : flow chart, diagram alur,

    bahasa semu

    Sedangkan secara bahasa, algoritma berarti suatu metode khusus untuk

    menyelesaikan suatu masalah yang nyata (dari Webster Dictionary).

    Dari suatu permasalahan yang akan diselesaikan, bisa terjadi terdapat lebih dari satu

    algoritma. Dalam memilih algoritma yang terbaik yang dapat digunakan, harus

    diperhatikan beberapa kriteria. Kriteria tersebut antara lain :

    Efektif dan efisien

    Jumlah langkahnya berhingga

    Berakhir

    Ada output

    Terstruktur

    Adapun langkah-langkah yang dilakukan dalam proses penyelesaian masalah dengan

    bantuan komputer adalah sebagai berikut :

  • 7/22/2019 Teori Graf (Materi)

    44/95

    MASALAH ?

    MODEL

    PROGRAM

    ALGORITMA

    HASIL SOLUSI

    EKSEKUSI

    DATA

    Studi Tentang Algor itmaHal-hal yang akan dipelajari mengenai studi algoritma yaitu :

    1. Bagaimana Merencanakannya

    2. Bagaimana Menyatakannya

    3. Bagaimana Validitasnya

    4. Bagaimana Menganalisisnya

    5. Bagaimana Menguji suatu program

    Merencanakan algoritma : Merupakan suatu studi tentang teknik variasi design (model)

    Menyatakan algoritma : Menyatakannya dengan singkat, dibuat dalam bahasa

    pemrograman yang terstruktur, misalnya Pascal, C

  • 7/22/2019 Teori Graf (Materi)

    45/95

    Validitas algoritma : Memenuhi kebutuhan yang diinginkan, dan

    perhitungannya/solusinya selalu benar untuk semua kemungkinan input yang

    legal

    Menganalisis algoritma : Perbandingan dari waktu perhitungan dan banyaknya

    storage/memori yang digunakan (efisiensi)

    Menguji suatu program : Pengujian suatu program yang dilakukan dalam dua fase,

    yakni :

    Fase Debugging :

    proses dari eksekusi program yang mengkoreksi kesalahan dalam bahasa

    pemrograman (logic & syntax)

    Fase Profiling :

    program sudah benar

    melihat/mengukur waktu tempuh & storage

    Analisis Algoritma

    Sebagaimana studi tentang algoritma, maka faktor yang sangat diperhitungkan adalah

    faktor efisiensi, yang meliputi :

    a. Waktu tempuh (running time)

    banyaknya langkah

    besar dan jenis input data

    jenis operasi

    jenis komputer dan kompilator

    b. Jumlah memori yang dipakai

    Dalam hal menganalisis algoritma, dikenal istilah kompleksitas.Kompleksitas adalah :

    Sebuah fungsi F(N) yang diberikan untuk waktu tempuh dan / atau kebutuhan

    storage dengan ukuran N input data

    Kompleksitas ini dapat berupa kompleksitas waktu & memori

  • 7/22/2019 Teori Graf (Materi)

    46/95

    Beberapa definisi kompleksitas:

    1. f(n) = (g(n)) dua konstanta positif c dan n0

    f(n)cg(n)n n0

    2. f(n) = (g(n)) konstanta positif c dan n0

    f(n)cg(n)n n0

    3. f(n) = (g(n)) konstanta positif c1, c2 dan n0

    c1g(n)f(n)c2g(n)n n0

    4. f(n) (g(n)) sebuah konstanta positif n0

    lim ( ) / ( )n

    f n g n

    1, n n0

    Dari keempat definisi di atas, yang paling banyak digunakan untuk menganalisis

    algoritma adalah definisi 1 (Big Oh).

    Teorema :

    Jika f(n) = amnm+ am-1n

    m-1 + . . .+ a1n+ a0 adalah polinomial tingkat m,

    maka f(n) = (nm)

    Sebagai contoh :

    f(n) = 3n5+ 4n4+ 10n2+ 56 = (n5)

    f(n) = 9n7+ 5n6+ 36 = (n7)

    f(n) = 8n9 = (n9)

    f(n) = n6

    + 19 = (n6

    )f(n) = 25 = (n0) = (1)

    Berikut ini adalah urutan dari Big Oh - Big Oh :

    (1) (log n) (n) (n log n) (n2) (n3) (2n)

  • 7/22/2019 Teori Graf (Materi)

    47/95

    Berikut ini beberapa contoh analisis terhadap algoritma

    Contoh 1 :

    (i) c a + b

    (ii) for i 1 to n do

    c a + b

    repeat

    (iii) for i 1 to n do

    for j 1 to n do

    c a + b

    repeat

    repeat

    Analisisnya :

    banyaknya

    operasi +

    f(n) Big Oh

    (i) 1 kali f(n) = 1 (1)

    (ii) n kali f(n) = n (n)

    (iii) n2kali f(n) = n2 (n2)

    Contoh 2 :

    Penjumlahan 2 buah matriks berorde (m X n) dan elemennya real

    1. Set A[i,j], B[i,j], C[i,j] real

    2. Untuk i 1 s/d m kerjakan

    3. untuk j 1 s/d n kerjakan

    4. C[i,j] A[i,j] + B[i,j]

    5. akhir j

    6. akhir i

  • 7/22/2019 Teori Graf (Materi)

    48/95

    Analisisnya :

    jumlah operasi + = mn kali

    jumlah memori = 3 mn x 4 = 12 mn

    (asumsi : 1 elemen memerlukan 4 satuan memori/byte)

    total = 13 mn

    Keadaan Dari Kompleksitas Waktu Algori tma

    Keadaan dari kompleksitas waktu algoritma meliputi :

    a. WORST Case nilai maksimum dari f(n) input yang mungkin

    b. BEST Case nilai minimum dari f(n) input yang mungkin

    c. AVERAGE Case nilai ekspektasi dari f(n)

    Contoh 3 :

    Menentukan lokasi suatu elemen pada array data secara linier

    1. Set k:= 1 ; loc := 0

    2. Repeat langkah 3 dan 4 While loc := 0 dan k n3. If Item := Data(k) then set loc := k

    4. Set k := k + 1

    5. If loc := 0 then

    Write Elemen tidak ada pada array data

    Else Write loc adalah lokasi darielemen

    6. Exit

    Bila elemen (item) yang dicari merupakan elemen terakhir dari array tersebut atau tidak

    terdapat dalam array :

    WORST CASE

    F(n) = (n)

  • 7/22/2019 Teori Graf (Materi)

    49/95

    Bila elemen (item) yang dicari merupakan elemen pertama dari array tersebut :

    BEST CASE

    F(n) = (1)

    Bila elemen (item) yang dicari berada diantara elemen pertama dan elemen terakhir

    dari array tersebut :

    AVERAGE CASE

    Banyaknya elemen dalam array tersebut adalah n, maka probabilitas masing-masing

    elemen adalah 1/n

    F(n) = 1 . 1/n + 2 . 1/n + 3 . 1/n + . . . + n . 1/n

    = ( 1 + 2 + 3 + . . . + n ) . 1/n

    = (n + 1) . n/2 . 1/n

    = (n + 1)/2

    = 1/2 n + 1/2

    = (n)

  • 7/22/2019 Teori Graf (Materi)

    50/95

    Pertemuan ke-8

    Teknik Iteratif & Rekursi f

    Teknik Iteratif

    Teknik Iteratif merupakan suatu teknik pembuatan algoritma dengan pemanggilan

    procedure beberapa kali atau hingga suatu kondisi tertentu terpenuhi

    Contoh :

    Teknik Iteratif pada algoritma untuk menghitung faktorial dari bilangan bulat positif n,

    adalah sebagai berikut :

    Function FAK (n : integer) : integer

    FAK=1

    For i = 1 TO n

    FAK = FAK * i

    NEXT i

    END FAK

    Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :

    Misal n = 5, maka :

    FAK=1, kemudian

    i FAK

    1 1 * 1 = 1

    2 1 * 2 = 2

    3 2 * 3 = 6

    4 6 * 4 = 24

    5 24 * 5 = 120

    Contoh :

    BARISAN BILANGAN FIBBONACI

  • 7/22/2019 Teori Graf (Materi)

    51/95

    1, 1, 2, 3, 5, 8, 13, 21, . . .

    Teknik Iteratif pada algoritma untuk menentukan suku ke-n dari barisan bilangan

    Fibbonaci, adalah sebagai berikut :

    1. Set x, y, n, i, f : integer

    2. x 1 ; y 1

    3. If n 2 then

    begin

    4. for i 3 to n do

    begin

    5. F x + y

    6. x y

    7. y F

    end

    else

    8. F x

    9. Write(F)

    End

    Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :

    Misal n = 5, maka :

    x=1, y=1, kemudian

    i F x y

    3 1 + 1 = 2 1 2

    4 1 + 2 = 3 2 3

    5 2 + 3 = 5 3 5

    Teknik Rekursi f

  • 7/22/2019 Teori Graf (Materi)

    52/95

    Teknik Rekursif merupakan salah satu cara pembuatan algoritma dengan pemanggilan

    procedureatau functionyang sama

    Contoh :

    Teknik Rekursif pada algoritma untuk menghitung faktorial dari bilangan bulat positif n,

    adalah sebagai berikut :

    Function FAK (n : integer) : integer

    1. If n := 0 then FAK := 1

    2. Else FAK := n * FAK(n-1)

    Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :

    Misal n = 5, maka :

    FAK(5) = 5 * FAK(4)

    FAK(4) = 4 * FAK(3)

    FAK(3) = 3 * FAK(2)

    FAK(2) = 2 * FAK(1)

    FAK(1) = 1 * FAK(0)

    1

    Contoh :

    BARISAN BILANGAN FIBBONACI

  • 7/22/2019 Teori Graf (Materi)

    53/95

    1, 1, 2, 3, 5, 8, 13, 21, . . .

    Teknik Rekursif pada algoritma untuk menentukan suku ke-n dari barisan bilangan

    Fibbonaci, adalah sebagai berikut :

    Procedure F(n : integer) : integer

    1. If n 2 then F(n) = 1

    else F(n) = F(n-1) + F(n-2)

    Endif

    End

    Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :

    Misal n = 5, maka :

    F(2)

    F(3)

    F(4)

    F(5)

    F(1)

    F(1)

    F(2)

    F(3)

    F(2)

    1

    1

    1

    11

    PERBEDAAN ANTARA TEKNIK ITERATIF DAN REKURSIF :

  • 7/22/2019 Teori Graf (Materi)

    54/95

    ITERATIF REKURSIF

    Tidak ada variabel lokal baru Ada variabel lokal baru

    Program tidak sederhana Program menjadi lebih sederhana

    Permainan Menara Hanoi

    Contoh paling umum dari penggunaan teknik rekursif adalah pada permainan menara

    Hanoi. Berdasarkan legenda, pertama kali dimainkan secara manual oleh seorang

    pendeta Budha di Hanoi, sehingga permainan ini disebut Menara Hanoi. Dalam

    permainan ini, akan dipindahkan sejumlah piringan yang tidak sama besarnya dari satutonggak ke tonggak lainnya, dengan diperbolehkan menggunakan (melewati) sebuah

    tonggak bantuan. Aturan permainannya adalah semua piringan pada tonggak A akan

    dipindahkan ke tonggak C (dapat dengan melewati tonggak bantuan B), dengan

    ketentuan bahwa pemindahan piringan dilakukan satu per satu dan piringan yang lebih

    besar tidak boleh diletakan di atas piringan yang lebih kecil. Untuk jelasnya lihat gambar

    berikut :

    Menurut legenda tersebut dikatakan bahwa jika anda selesai memindahkan seluruh 64

    piringan, pada saat itu juga dunia kiamat. Ini menurut legenda, yang mungkin juga

    benar. Secara umum, untuk menyelesaikan n buah piringan diperlukan pemindahan

    Tonggak Asal (A) Tonggak Bantu (B) Tonggak Tujuan (C)

  • 7/22/2019 Teori Graf (Materi)

    55/95

    sebanyak 2n1 kali. Bayangkan jika untuk setiap pemindahan memerlukan waktu 1

    detik, maka berapa waktu yang diperlukan untuk menyelesaikan 64 buah piringan.

  • 7/22/2019 Teori Graf (Materi)

    56/95

    Pertemuan ke-9

    Teknik Backtracking

    Teknik Backtracking merupakan salah satu teknik dalam penyelesaian masalah secara

    umum (General Problem Solving). Adapun dasar dari teknik ini adalah suatu teknik

    pencarian (Teknik Searching). Teknik pencarian ini digunakan dalam rangka

    mendapatkan himpunan penyelesaian yang mungkin. Dari himpunan penyelesaian

    yang mungkin ini akan diperoleh solusi optimal atau memuaskan.

    Teknik Backtracking ini diperkenalkan pertama kali oleh : D.H. Lehmer (1950),Penulisan algoritmanya oleh : R.J. Walker (1960), dan

    Variasi aplikasinya dikembangkan oleh : Golomb & Baumert (1960)

    Berikut ini disajikan algoritma backtracking secara umum, yang menggunakan teknik

    iteratif :

    PROCEDURE BACKTRACK(n)

    INTEGER k,n; LOCAL x(1:n)

    k 1

    WHILE k > 0 DO

    IF ada x(k) yang belum dicoba sedemikian sehingga

    x(k) T(x(1), , x(k-1)) AND Bk(x(1), , x(k)) = TRUE

    THEN

    IF (x(1), , x(k)) adalah sebuah jalur (path) yang merupakan solusi

    THEN PRINT (x(1), , x(k)) ENDIF

    k k + 1

    ELSE k k 1

    ENDIF

    REPEAT

  • 7/22/2019 Teori Graf (Materi)

    57/95

    END BACKTRACK

    Sedangkan bentuk rekursifnya adalah sebagai berikut :

    PROCEDURE RBACKTRACK(k)

    GLOBAL n, x(1:n)

    FOR setiap x(k) sedemikian sehingga

    x(k) T(x(1), , x(k-1)) AND Bk(x(1), , x(k)) = TRUE

    IF (x(1), , x(k)) adalah sebuah jalur (path) yang merupakan solusi

    THEN PRINT (x(1), , x(k)) ENDIF

    CALL RBACKTRACK(k + 1)

    END RBACKTRACK

    Contoh Pemakaian Teknik Backtracking :

    The 8 - Queens Problem

    The 4 - Queens Problem

    Sum of Subsets

    Graph Coloring

    Hamilton Cycles Knapsack Problem

    Tic - Tac - Toe Game

    The Travelling Salesman Problem

    Sum of Subsets

    Masalah utama dari Sum of Subsets adalah jika terdapat n bilangan real dan ingindihitung semua kombinasi yang mungkin dari himpunan bilangan tersebut. Kombinasi

    yang diinginkan yaitu kombinasi yang jumlah seluruh elemennya sama dengan M

    (tertentu).

  • 7/22/2019 Teori Graf (Materi)

    58/95

    Sebelum kita selesaikan masalah tersebut dengan menggunakan teknik backtracking,

    perhatikan terlebih dahulu penyajian permasalahan dan penyelesaiannya dalam bentuk

    pohon.

    Misalkan banyaknya bilangan real tersebut adalah 4 (n=4). Terdapat 2 jenis pohon

    pencarian, yakni Breadth First Search (BFS) yang menggunakan queue dan Depth First

    Search (DFS) yang menggunakan stack. Berikut penggambaran kedua jenis pohon

    tersebut.

    1

    2 3 4 5

    6 7 8 11

    12 13 14 15

    16

    9 10

    Breadth First Search (BFS)

  • 7/22/2019 Teori Graf (Materi)

    59/95

    Kedua bentuk penyajian pohon dari persoalan sum of subsets, merupakan tahapan

    pertama dalam proses mendapatkan solusi sesungguhnya (solusi optimal). Untuk

    mendapatkan solusi yang optimal dari ruang penyelesaian digunakan suatu algoritmalain. Algoritma tersebut menggunakan teknik backtracking, yang selanjutnya disebut

    dengan algoritma SUMOFSUB.

    PROCEDURE SUMOFSUB(s,k,r)

    GLOBAL INTEGER M,n

    GLOBAL REAL W(1:n)

    GLOBAL BOOLEAN X(1:n)

    REAL r,s; INTEGER k,j

    X(k) = 1

    IF s + W(k) = M THEN PRINT (X(j), j 1 TO k)

    ELSE

    IF s + W(k) + W(k+1) M THEN

    2 3

    18 19

    6 7

    8

    21 12 132026

    30 910

    Depth First Search (DFS)

    1

    31 24

    4 5

    28 16 17 1129 2225

    27

    23 14 15

  • 7/22/2019 Teori Graf (Materi)

    60/95

    CALL SUMOFSUB(s+W(k), k+1, r-W(k))

    ENDIF

    ENDIF

    IF s + r - W(k) M AND s + W(k) M THEN

    X(k) 0

    CALL SUMOFSUB(s, k+1, r-W(k))

    ENDIF

    END SUMOFSUB

    Contoh :

    Suatu himpunan terdiri dari 6 bilangan, yakni {5, 10, 12, 13, 15, 18} yang disusun

    secara tidak turun. Akan ditentukan himpunan-himpunan bagiannya, yang jumlah

    seluruh elemennya adalah 30.

    15,3,58 5,3,58 10,3,58 0,3,58

    0,4,4612,4,4610,4,465,4,4617,4,4615,4,4627,4,46

    0,5,3313,5,3312,5,3310,5,335,5,3315,5,33

    0,1,73

    20,6,18

    5,2,68 0,2,68

    12,6,18 13,6,18A

    C

    B

    Bagian dari state space tree dengan SUMOFSUB

  • 7/22/2019 Teori Graf (Materi)

    61/95

    Perhatikan simpul A, B dan C yang merupakan outputnya dalam bentuk tuple

    (1,1,0,0,1), (1,0,1,1) dan (0,0,1,0,0,1).

  • 7/22/2019 Teori Graf (Materi)

    62/95

    Pertemuan ke-10

    Metode Devide And Conquer (DANDC) - Searching

    Di dalam metode ini, kita mempunyai suatu fungsi untuk menghitung input. Kemudian n

    input tersebut dipartisi menjadi k subset input yang berbeda (1< k n) k subproblem

    k subproblem k subsolusi solusi

    Bentuk Umum dari Proses Metode DANDC :

    Jika subproblem masih relatif cukup besar, maka metode DANDC dapat digunakan lagi

    untuk keadaan tersebut. Pemakaian ulang DANDC dinyatakan dengan teknik rekursif.

    Pemecahan menjadi k subproblem ini menunjukkan bahwa ia mempunyai sifat yang

    sama dengan problem aslinya (awalnya).

    Algoritmanya secara umum :

    n input

    Subsolusi 1

    Subproblem 1

    Input 1

    Solusi Optimal

    Subsolusi 2

    Subproblem 2

    Input 2

    Subsolusi 3

    Subproblem 3

    Input 3

    Subsolusi k

    Subproblem k

    Input k. . .

    . . .

    . . .

  • 7/22/2019 Teori Graf (Materi)

    63/95

    PROCEDURE DANDC(p,q)

    GLOBAL n,A(1:n); INTEGER m.p.q

    IF SMALL(p,q) THEN G(p,q)

    ELSE

    M DIVIDE(p,q)

    COMBINE(DANDC(p,m),DANDC(m+1,q))

    ENDIF

    END DANDC

    SMALL(p,q) adlah fungsi yang bernilai boole yang menentukan apakah input q-p+1

    berukuran cukup kecil solusi dapat dihitung tanpa pemecahan. Jika demikian halnya,

    maka fungsi G(p,q) yang dipanggil.

    Pada keadaan lain fungsi DIVIDE(p,q) yang dipanggil.

    Fungsi DIVIDE(p,q) menghasilkan integer yang menguraikan input menjadi 2 bagian.

    Misal m = DIVIDE(p,q), maka input dipecah A(p:m) dan A(m+1,q)

    Metode DANDC biasa dipakai pada searching dan sorting.

    Searching

    Menentukan Bilangan Max dan Min

    Sebelum kita lihat penggunaan metode DANDC-nya, maka kita lihat terlebih dahulu

    algoritmanya secara iteratif sebagai berikut :

    PROCEDURE STRAITMAXMIN

    INTEGER i,n

    max min A(1)

    For i 2 TO n DO

    IF A(i) > max THEN max A(i) bagian perbandingan

    ELSE IF A(i) < min THEN min A(i) bagian perbandingan

  • 7/22/2019 Teori Graf (Materi)

    64/95

    ENDIF

    ENDIF

    REPEAT

    END STRAITMAXMIN

    Procedure STRAITMAXMIN tersebut akan menghasilkan 3 keadaan, yakni:

    1. Best Case, bila datanya tersusun menaik, dengan banyak perbandingan adalah n-1

    2. Worst Case, bila datanya tersusun menurun, dengan banyak perbandingan adalah

    2(n-1)

    3. Average Case, bila datanya tidak tersusun menaik ataupun menurun, dengan

    banyak perbandingan adalah 3(n-1)/2

    Bila pada procedure STRAITMAXMIN tersebut, bagian perbandingannya diubah

    menjadi :

    IF A(i) > max THEN max A(i) ENDIF

    IF A(i) < min THEN min A(i) ENDIF

    Maka Best Case = Worst Case = Average Case = 2(n-1)

    Algoritmanya secara rekursif (dengan metode DANDC)

    PROCEDURE MAXMIN(i,j,fmax,fmin)

    INTEGER i,j; GLOBAL n,A(1:n)

    CASE

    : i=j ; fmax fmin A(i)

    : i=j-1 ; IF A(i) < A(j) THEN fmax A(j); fmin A(i)

    ELSE fmax A(i); fmin A(j)

    ENDIF

    : ELSE

    mid (i+j)/2

    CALL MAXMIN(i,mid,gmax,gmin)

    CALL MAXMIN(mid+1,j,hmax,hmin)

  • 7/22/2019 Teori Graf (Materi)

    65/95

    fmax MAX(gmax,hmax)

    fmin MIN(gmin,hmin)

    ENDCASE

    END MAXMIN

    Contoh :

    A = { 22, 13, -5, -8, 15, 60, 17, 31, 47 }

    Maka simulasi dari procedure MAXMIN tersebut adalah :

    Jadi outputnya adalah max = 60 dan min = -8

    Jumlah perbandingan elemennya, yang direpresentasikan oleh T(n) adalah :

    T( n/2 ) +T( n/2 ) + 2 ; n > 2

    T(n) { 1 ; n = 2

    7

    1 9 60 -8

    6 9 60 171 5 22 -8

    8 9 47 316 7 60 174 5 15 -81 3 22 -5

    3 3 -5 -51 2 22 13

    2

    9

    5 8

    3 64

    1

  • 7/22/2019 Teori Graf (Materi)

    66/95

    0 ; n = 1

    untuk n power value dari 2 = 2kdan k integer positif, maka :

    T(n) = 2 T(n/2) + 2

    = 2 (2 T(n/4) + 2) + 2

    = 4 T(n/4) + 4 + 2 = 22T(n/2

    2) + 2

    2+ 2

    = 23T(n/23) + 23+ 22+ 2

    .

    .

    .

    = 2k-1T(2) + 2k-1+ 2k-2+ + 23+ 22+ 2

    = 2k-1+2k- 2

    = 3n/2 - 2

    Jadi T(n) = (n)

  • 7/22/2019 Teori Graf (Materi)

    67/95

    Pertemuan ke-11

    Metode Devide And Conquer (DANDC) - Sorting

    Sorting

    Untuk mengurutkan barisan n input elemen yang ditempatkan dalam suatu array.

    Urutan yang diinginkan adalah urutan yang tidak turun (non decreasing).

    Contoh barisan dengan urutan :

    1. Menaik : 5, 8, 10, 12, 15, 16

    2. Menurun : 20, 17, 15, 14, 12, 103. Tidak turun : 5, 9, 10, 12, 12, 15, 16

    4. Tidak naik : 16, 15, 15, 12, 10, 8

    Dari Metode Sorting yang ada, akan dibahas metode merge sort dan quick sort.

    Merge Sort

    Algoritma dari Merge Sort terdiri dari dua prosedur, yakni prosedur MERGESORT dan

    prosedur MERGE. Kedua prosedur tersebut tidak dapat dipisahkan satu dengan yang

    lainnya (terintegrasi).

    PROCEDURE MERGESORT(low,high)

    INTEGER low,high

    IF low < high THEN

    mid (low + high) / 2

    CALL MERGESORT(low,mid)

    CALL MERGESORT(mid+1,high)

    CALL MERGE(low,mid,high)

    ENDIF

    END MERGESORT

  • 7/22/2019 Teori Graf (Materi)

    68/95

    PROCEDURE MERGE(low,mid,high)

    INTEGER h,I,j,k,low,mid,high

    GLOBAL A(low:high); LOCAL B(low:high)

    h low; j mid + 1; i low

    WHILE h mid AND j high DO

    IF A(h) A(j) THEN B(i) A(h); h h+1

    ELSE B(i) A(j); j j+1

    ENDIF

    i i+1

    REPEAT

    IF h > mid THEN FOR k j TO high DO

    B(i) A(k); i i+1

    REPEAT

    ELSE FOR k h TO mid DO

    B(i) A(k); i i+1

    REPEAT

    ENDIF

    FOR k low TO high DO

    B(k) A(k)

    REPEAT

    END MERGE

    Contoh :

    A(1:10) yakni :

    A = { 310, 285, 179, 652, 351, 423, 861, 254, 450, 520 }

  • 7/22/2019 Teori Graf (Materi)

    69/95

    Representasi di dalam tree dari CALL MERGESORT sbb :

    Representasi di dalam tree dari CALL MERGE sbb :

    T(n) = (n 2log n)

    1,10

    10,10

    1,3

    9,98,86,75,54,43,31,2

    2,21,1

    6,84,5 9,10

    7,76,6

    1,5 6,10

    1,1,2

    1,2,3 4,4,5

    1,3,5

    6,7,8 9,9,10

    6,6,7

    6,8,10

    1,5,10

  • 7/22/2019 Teori Graf (Materi)

    70/95

    Quick Sort

    Algoritma Quick Sort terdiri dari dua prosedur, yaitu prosedur PARTITION dan prosedur

    QUICKSORT.

    PROCEDURE QUICKSORT(p,q)

    IF p < q THEN

    j q+1

    CALL PARTITION(p,j)

    CALL QUICKSORT(p,j-1)

    CALL QUICKSORT(j+1,q)

    ENDIF

    END QUICKSORT

    PROCEDURE PARTITION(m,p)

    INTEGER m,p,i; GLOBAL A(m-1,p)

    V A(m); i m

    LOOP

    LOOP i i+1 UNTIL A(i) V REPEAT

    LOOP p p-1 UNTIL A(p) V REPEATIF i < p THEN CALL INTERCHANGE(A(i),A(p))

    ELSE EXIT

    REPEAT

    A(m) A(p); A(p) V

    END PARTITION

    Contoh :

    Suatu array A berisi elemen-elemen :

    65 70 75 80 85 60 55 50 45

    1 2 3 4 5 6 7 8 9

  • 7/22/2019 Teori Graf (Materi)

    71/95

    Hasil tracenya adalah sebagai berikut :

    i p 1 2 3 4 5 6 7 8 9 10

    65 70 75 80 85 60 55 50 45+

    2 9 65 45 75 80 85 60 55 50 70 +

    3 8 65 45 50 80 85 60 55 75 70 +

    4 7 65 45 50 55 85 60 80 75 70 +

    5 6 65 45 50 55 60 85 80 75 70 +

    6 5 60 45 50 55 65 85 80 75 70 +

    5 4 55 45 50 60 65 85 80 75 70 +

    4 3 50 45 55 60 65 85 80 75 70 +

    3 2 45 50 55 60 65 85 80 75 70 +

    10 9 55 45 50 60 65 70 80 75 85 +

    9 8 50 45 55 60 65 70 75 80 85 +

    8 7 45 50 55 60 65 70 75 80 85 +

    Analisisnya :

    Worst Case = (n2)

    Average Case = (n log n)

  • 7/22/2019 Teori Graf (Materi)

    72/95

    Pertemuan ke-12

    Metode Greedy

    Masalah Knapsack

    Kita diberikan sebuah knapsack (ransel) yang dapat menampung berat

    maksimum M dan sehimpunan benda A = {a0,a1,...,an-1} yang berbobot W =

    {w0,w1,...,wn-1}. Setiap benda tersebut diberikan nilai profit yang dinotasikan dengan P

    = {p0,p1,...,pn-1}. Jika kita diperbolehkan memasukkan zi bagian dari benda ai yang

    ada ke dalam knapsack dimana 0 zi 1 , maka kita dapatkan profit sebesar zi pi

    untuk benda ai tersebut.

    Yang dimaksud dengan masalah knapsack adalah :

    Bagaimana kita memilih atau menentukan ziuntuk masing-masing benda aidari

    keadaan di atas dengan tujuan mendapatkan total profit yang maksimal, dan

    dengan kendala bahwa total bobot dari benda-benda yang dimasukkan ke dalam

    knapsack tidak melebihi M.

    Secara matematis, masalah knapsack tersebut dapat ditulis sebagai berikut :

    maksimumkan Q z pi ii=0

    n-1

    =

    dengan kendala zii

    n

    iw W=

    0

    1

    dan 0 zi1 , pi0 , wi0 , 0 i n-1

    Sebuah solusi yang optimal adalah himpunan Z = {z0,z1,...,zn-1} yang memaksimalkan

    nilai Q dan memenuhi kendala-kendala yang ada.

  • 7/22/2019 Teori Graf (Materi)

    73/95

    Contoh :

    Kita diberikan sebuah knapsack (ransel) yang dapat menampung berat

    maksimum 15 Kg dan sehimpunan benda A = {a0,a1,a2,a3} yang berbobot

    (dalam Kg) W = {5,9,2,4}. Setiap benda tersebut diberikan nilai profit P =

    {100,135,26,20}. Jika kita diperbolehkan memasukkan zi bagian dari benda ai

    yang ada ke dalam knapsack dimana 0 zi 1 , maka tentukanlah Z =

    {z0,z1,z2,z3} agar diperoleh total profit yang maksimal !

    Algori tma Sekuensial Knapsack Metode Greedy

    Salah satu cara untuk menyelesaikan masalah knapsack secara sekuensial

    adalah dengan pemakaian metode Greedy. Procedure tersebut disebut procedureGREEDY_KNAPSACK.

    Sebelum procedure tersebut digunakan, benda-benda harus diurutkan rasio pi/wi-nya

    tidak menaik. Dengan kata lain :

    p0/ w0 p1 / w1 ... pn-1 / wn-1

    Adapun procedure GREEDY_KNAPSACK adalah sebagai berikut :

    procedure GREEDY_KNAPSACK(P,W,M,Z,n)

    real P(0:n-1),W(0:n-1),Z(0:n-1),cu; {n = banyak benda}

    integeri,n;

    Z 0 { Z(0), Z(1), . . . , Z(n-1) = 0}

    cu M

    fori 0 to n-1 do

    if W(i) cuthen exit endif

    Z(i) 1

    cu cu - W(i)

    repeat

    if i n-1 thenZ(i) cu/W(i) endif

    end GREEDY_KNAPSACK

  • 7/22/2019 Teori Graf (Materi)

    74/95

    Jika algoritma ini digunakan untuk menyelesaikan masalah seperti pada contoh yang

    lalu, dimana n = 4; M = 15; W = { 5,9,2,4 }; P = { 100,135,26,20 }, maka akan terlihat

    hasil tracenya sebagai berikut :

    Z 0

    cu 15

    i = 0

    karena W(0) cu yaitu : 5 15 berarti : Z(0) 1

    cu 15 - 5 = 10

    i = 1

    karena W(1) cu yaitu : 9 10 berarti : Z(1) 1

    cu 10 - 9 = 1

    i = 2

    karena W(2) cu yaitu : 2 1 berarti : keluar dari loop (exit)

    Karena 2 3 maka Z(2) cu/W(2) = 1/2 = 0,5

    Jadi optimisasi masalah knapsack diperoleh bila Z = { 1; 1; 0,5; 0 }

    Sehingga Q = 1 x 100 + 1 x 135 + 0,5 x 26 + 0 x 20

    = 100 + 135 + 13 + 0

    = 248

    Analisis :

    Kompleksitas waktu dari algoritma Greedy_Knapsack ini adalah O(n). Tetapi jikadata yang digunakan belum terurut rasio pi/wi -nya tidak menaik, maka

    diperlukan kompleksitas waktu sebesar O(n log n) untuk mengurutkan

    sebelumnya. Sehingga untuk masalah optimisasi knapsack, kompleksitas waktu

    dari algoritma ini akan lebih besar pada waktu proses pengurutannya.

  • 7/22/2019 Teori Graf (Materi)

    75/95

    Latihan :

    Diketahui 3 buah benda dan sebuah knapsack dengan kapasitas maksimum 20. Berat

    dan profit dari masing-masing benda tersebut adalah (18, 15, 10) dan (25, 24, 15).

    Tentukanlah Z agar diperoleh total profit yang maksimal !

    Jawab :

    Pertama, kita periksa apakah rasio pi/wi-nya tidak menaik.

    p0/w0 = 25/18

    p1/w1 = 24/15

    p2/w2= 15/10

    Terlihat bahwa syarat rasio pi/wi -nya tidak menaik belum terpenuhi. Jadi

    susunan (urutan) -nya untuk sementara kita ubah, agarsyarat rasio pi/wi-nya

    tidak menaik terpenuhi dan kita dapat menyelesaikan masalah tersebut

    dengan procedure GREEDY_KNAPSACK.

    Untuk itu, kita ubah sementara urutan benda-bendanya (setelah diperoleh

    jawaban sementara, kita kembalikan urutan ke susunan semula). Perubahan

    yang kita lakukan adalah sebagai berikut :

    urutan ke-

    (yang lama)

    urutan ke-

    (yang baru)

    0 2

    1 0

    2 1

    sehingga syaratnya terpenuhi ;

    24/15 15/10 25/18 rasio pi/wi-nya tidak menaik

  • 7/22/2019 Teori Graf (Materi)

    76/95

    Sekarang kita sudah dapat menggunakan procedure GREEDY_KNAPSACK

    untuk menyelesaikan masalah tersebut. Adapun hasil trace-nya adalah sebagai

    berikut :

    Z 0

    cu 20

    i = 0

    karena W(0) cu yaitu : 15 20 berarti : Z(0) 1

    cu 20 - 15 = 5

    i = 1

    karena W(2) cu yaitu : 10 5 berarti : keluar dari loop (exit)

    Karena 1 2 maka Z(1) cu/W(1) = 5/10 = 0,5

    Jadi diperoleh : Z(0) = 1 ; Z(1) = 0,5 ; Z(2) = 0

    Sekarang urutannya kita kembalikan seperti semula, yakni :

    urutan ke-

    (yang saat ini)

    urutan ke-

    (yang

    semula)

    Z(i)

    2 0 0

    0 1 1

    1 2 0,5

    Jadi optimisasi masalah knapsack diperoleh bila Z = { 0; 1; 0,5 }

    Sehingga Q = 0 x 25 + 1 x 24 + 0,5 x 15

    = 0 + 24 + 7,5

    = 31,5

  • 7/22/2019 Teori Graf (Materi)

    77/95

    Pertemuan ke-13

    Metode Greedy (Lanjutan)

    Masalah Pohon Rentangan Minimal

    Permasalahan umum dari pohon rentangan minimal adalah mencari minimum biaya

    (cost) pohon rentangan dari setiap ruas suatu graf yang membentuk pohon.

    Setiap graf tidak dapat ditentukan pohon rentangan minimalnya. Adapun graf yang

    dapat kita tentukan pohon rentangan minimalnya adalah graf yang memenuhi ketiga

    syarat berikut :1. graf tersebut harus terhubung

    2. setiap ruas dari graf tersebut harus mempunyai nilai atau bobot (graf

    berlabel)

    3. graf teresbut tidak berarah

    Algoritma yang dapat digunakan untuk menyelesaikan masalah pohon rentangan

    minimal cukup banyak. Dalam pembahasan ini, algoritma yang akan dipakai adalah

    algoritma PRIMS.

    Berikut ini akan disajikan langkah-langkah penyelesaian masalah pohon rentangan

    minimal dengan menggunakan algoritma PRIMS.

    PROCEDURE PRIM(E,COST,n,T,mincost)

    REAL COST(n,n),mincost

    INTEGER NEAR(n),n,i,j,k,l,T(1:n-1,2)

    (k,l) ruas dengan biaya atau bobot yang minimum

    mincost COST(k,l)

    (T(1,1),T(1,2)) (k,l)

    FOR i 1 TO n DO

    IF COST (i,l) < COST(i,k) THEN NEAR (i) l

  • 7/22/2019 Teori Graf (Materi)

    78/95

    ELSE NEAR(i) k ENDIF

    REPEAT i

    NEAR(k) NEAR(l) 0

    FOR i 2 TO n-1 DO

    Pilih j (sebuah index) sedemikian sehingga NEAR(j) 0 AND COST(j,NEAR(j)) adalah

    minimum

    (T(i,1),T(i,2)) (j,NEAR(j))

    mincost mincost + COST(j,NEAR(j))

    NEAR(j) 0

    FOR k 1 TO n DO

    IF NEAR(k) 0 AND COST(k,NEAR(k)) > COST(k,j)

    THEN NEAR(k) j

    ENDIF

    REPEAT k

    REPEAT i

    IF mincost ~ THEN PRINT bukan pohon rentangan ENDIF

    END PRIM

    Contoh :

    Perhatikan graf berikut ini :

    Tentukanlah nilai pohon rentangan minimalnya, serta pohon yang membentuk pohon

    rentangan minimal tersebut.

    1

    6

    3

    4 5

    210

    25

    45

    20

    4035

    55

    30

    15

    50

  • 7/22/2019 Teori Graf (Materi)

    79/95

    Penyelesaian :

    Dengan menggunakan algoritma PRIMS, prosesnya adalah sebagai berikut :

    (k,l) (1,2)

    mincost COST(1,2) = 10

    (T(1,1),T(1,2)) (1,2)

    i=1

    COST (1,2) < COST(1,1) ?

    10 < ~ TRUE : NEAR (1) 2

    i=2

    COST (2,2) < COST(2,1) ?

    ~ < 10 FALSE : NEAR (2) 1

    i=3

    COST (3,2) < COST(3,1) ?

    50 < ~ TRUE : NEAR (3) 2

    i=4

    COST (4,2) < COST(4,1) ?

    ~ < 30 FALSE : NEAR (4) 1

    i=5

    COST (5,2) < COST(5,1) ?

    40 < 45 TRUE : NEAR (5) 2

    i=6

    COST (6,2) < COST(6,1) ?

    25 < ~ TRUE : NEAR (6) 2

    NEAR(1) NEAR(2) 0

    i = 2

    Pilih j = 6 karena NEAR(6) 0 dan COST(6,NEAR(6)) adalah minimum

    (T(2,1),T(2,2)) (6,2)

    mincost 10 + COST(6,2) = 10 + 25 = 35

  • 7/22/2019 Teori Graf (Materi)

    80/95

    NEAR(6) 0

    k = 1

    NEAR(1) 0 dan COST(1,NEAR(1)) > COST(1,6) ?

    0 0 dan ~ > ~ FALSE dan FALSE FALSE

    k = 2

    NEAR(2) 0 dan COST(2,NEAR(2)) > COST(2,6) ?

    0 0 dan ~ > 25 FALSE dan TRUE FALSE

    k = 3

    NEAR(3) 0 dan COST(3,NEAR(3)) > COST(3,6) ?

    2 0 dan 50 > 15 TRUE dan TRUE TRUE : NEAR(3) = 6

    k = 4

    NEAR(4) 0 dan COST(4,NEAR(4)) > COST(4,6) ?

    1 0 dan 30 > 20 TRUE dan TRUE TRUE : NEAR(4) = 6

    k = 5

    NEAR(5) 0 dan COST(5,NEAR(5)) > COST(5,6) ?

    2 0 dan 40 > 55 TRUE dan FALSE FALSE

    k = 6

    NEAR(6) 0 dan COST(6,NEAR(6)) > COST(6,6) ?

    0 0 dan ~ > ~ FALSE dan FALSE FALSE

    i = 3

    Pilih j = 3 karena NEAR(3) 0 dan COST(3,NEAR(3)) adalah minimum

    (T(3,1),T(3,2)) (3,6)

    mincost 35 + COST(3,6) = 35 + 15 = 50

    NEAR(3) 0

    k = 1

    NEAR(1) 0 dan COST(1,NEAR(1)) > COST(1,3) ?

    0 0 dan ~ > ~ FALSE dan FALSE FALSE

    k = 2

    NEAR(2) 0 dan COST(2,NEAR(2)) > COST(2,3) ?

  • 7/22/2019 Teori Graf (Materi)

    81/95

    0 0 dan ~ > 50 FALSE dan TRUE FALSE

    k = 3

    NEAR(3) 0 dan COST(3,NEAR(3)) > COST(3,3) ?

    0 0 dan ~ > ~ FALSE dan FALSE FALSE

    k = 4

    NEAR(4) 0 dan COST(4,NEAR(4)) > COST(4,3) ?

    6 0 dan 20 > ~ TRUE dan FALSE FALSE

    k = 5

    NEAR(5) 0 dan COST(5,NEAR(5)) > COST(5,3) ?

    2 0 dan 40 > 35 TRUE dan TRUE TRUE : NEAR(5) = 3

    k = 6

    NEAR(6) 0 dan COST(6,NEAR(6)) > COST(6,3) ?

    0 0 dan ~ > 15 FALSE dan TRUE FALSE

    i = 4

    Pilih j = 4 karena NEAR(4) 0 dan COST(4,NEAR(4)) adalah minimum

    (T(4,1),T(4,2)) (4,6)

    mincost 50 + COST(4,6) = 50 + 20 = 70

    NEAR(4) 0

    k = 1

    NEAR(1) 0 dan COST(1,NEAR(1)) > COST(1,4) ?

    0 0 dan ~ > 30 FALSE dan TRUE FALSE

    k = 2

    NEAR(2) 0 dan COST(2,NEAR(2)) > COST(2,4) ?

    0 0 dan ~ > ~ FALSE dan FALSE FALSE

    k = 3

    NEAR(3) 0 dan COST(3,NEAR(3)) > COST(3,4) ?

    0 0 dan ~ > ~ FALSE dan FALSE FALSE

    k = 4

    NEAR(4) 0 dan COST(4,NEAR(4)) > COST(4,4) ?

  • 7/22/2019 Teori Graf (Materi)

    82/95

    0 0 dan ~ > ~ FALSE dan FALSE FALSE

    k = 5

    NEAR(5) 0 dan COST(5,NEAR(5)) > COST(5,4) ?

    3 0 dan 35 > ~ TRUE dan FALSE FALSE

    k = 6

    NEAR(6) 0 dan COST(6,NEAR(6)) > COST(6,4) ?

    0 0 dan ~ > 20 FALSE dan TRUE FALSE

    i = 5

    Pilih j = 5 karena NEAR(5) 0 dan COST(5,NEAR(5)) adalah minimum

    (T(5,1),T(5,2)) (5,3)

    mincost 70 + COST(5,3) = 70 + 35 = 105

    NEAR(5) 0

    k = 1

    NEAR(1) 0 dan COST(1,NEAR(1)) > COST(1,5) ?

    0 0 dan ~ > 45 FALSE dan TRUE FALSE

    k = 2

    NEAR(2) 0 dan COST(2,NEAR(2)) > COST(2,5) ?

    0 0 dan ~ > 40 FALSE dan TRUE FALSE

    k = 3

    NEAR(3) 0 dan COST(3,NEAR(3)) > COST(3,5) ?

    0 0 dan ~ > 35 FALSE dan TRUE FALSE

    k = 4

    NEAR(4) 0 dan COST(4,NEAR(4)) > COST(4,5) ?

    0 0 dan ~ > ~ FALSE dan FALSE FALSE

    k = 5

    NEAR(5) 0 dan COST(5,NEAR(5)) > COST(5,5) ?

    0 0 dan ~ > ~ FALSE dan FALSE FALSE

    k = 6

    NEAR(6) 0 dan COST(6,NEAR(6)) > COST(6,5) ?

  • 7/22/2019 Teori Graf (Materi)

    83/95

    0 0 dan ~ > 55 FALSE dan TRUE FALSE

    mincost ~ ?

    105 ~ FALSE

    terdapat sebuah pohon rentangan, yang mempunyai nilai minimal = 105

    Berikut adalah bentuk pohon rentangan minimalnya :

    1

    6

    3

    4 5

    210

    25

    20

    35

    15

  • 7/22/2019 Teori Graf (Materi)

    84/95

    Pertemuan ke-14

    Pemrograman Dinamis

    Metode Umum

    Pemrograman Dinamis adalah metode rancangan algoritma yang dapat dipakai bila

    pemecahan masalah yang mungkin dipandang sebagai hasil dari rangkaian keputusan-

    keputusan.

    Untuk beberapa masalah dari masalah-masalah ynag dapat dipandang dengan cara ini,

    rangkaian optimal dari keputusan-keputusan mungkin dapat ditemukan dengan

    membuat satu dari keputusan-keputusan pada satu waktu dan jangan pernah membuatkeputusan yang keliru.

    Satu cara untuk memecahkan masalah-masalah yang mana ini tidak mungkin untuk

    membuat sebuah rangkaian dari langkah-langkah keputusan yang dapat dilakukan

    mengacu (mengarah) kepada rangkaian keputusan optimal adalah untuk mencoba

    semua kemungkinan rangkaian-rangkaian keputusan.

    Pemrograman Dinamis seringkali secara drastic (spontan) mengurangi jumlah

    pembilangan dengan menghindari pembilangan dari beberapa rangkaian keputusan

    yang tidak memungkinkan menjadi optimal.

    Dalam merumuskan hubungan-hubungan kembali pemrograman dinamis yang harus

    dipecahkan, seseorang dapat menggunakan 1 dari 2 pendekatan yang berbeda yaitu

    forwardatau backward.

    Multistage Graf

    Sebuah multistage graf adalah sebuah graf berarah dimana bentuk tersebut dibagi

    dalam k 2 disjoint set V1.

    Berikut ini adalah contoh sebuah graf 5 stage.

  • 7/22/2019 Teori Graf (Materi)

    85/95

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    9

    7

    3

    2

    4

    2

    2

    7

    11

    1

    11

    8

    6

    3

    54

    5

    6

    2

    4

    5

    ts

    V1

    V4

    V2

    V3

    V5

    Algoritma untuk menyelesaikan masalah multistage graf, dengan pendekatan forward

    adalah sebagi berikut :

    ProcedureFGRAPH(E,k,n,P)

    1. realCOST(n), integerD(n-1), P(k), r, j, k, n

    2. COST(n) 0

    3. forj n-1 to 1 by-1 do

    4. let r be a vertex such that j , r E and c( j,r ) +

    COST(r) is minimum

    5. COST(j) c( j,r ) + COST(r)

    6. D(j) r

    7. repeat

    8. P(1) 1 ; P(k) n

    9. forj 2 to k-1 do

    10. P(j) D(P(j-1))

    11. repeat

    12. endFGRAPH

  • 7/22/2019 Teori Graf (Materi)

    86/95

    Contoh Soal

    Graf & Analisis Algor itma

    1. Orang yang dikenal sebagai bapak dari lahirnya (awal) teori graf adalah :

    A. Solin dan Kruskal

    B. Hamilton

    C. Welch-Powell

    D. Leonhard Euler

    2. Bila size dari suatu graf adalah n, maka jumlah derajat grafnya adalah :

    A. 2n-1B. 2 (n-1)

    C. 2nD. 2n+1

    3. Pada pohon, simpul yang bukan merupakan akar dan berderajat simpul 1 adalah :

    A. Cabang

    B. Daun

    C. Brother

    D. Level

    4. Suatu bentuk graf yang terbentuk karena penambahan sejumlah vertex baru

    terhadap graf asal disebut :

    A. Isomorfis

    B. Isograf

    C. Homomorfis

    D. Isographic

    5. Suatu tree yang mempunyai cabang / anak selalu 2 disebut :

    A. Unary tree

    B. Binary tree

    C. Union tree

    D. Threenary Tree

    6. Graf yang tidak memiliki self loop atau ruas sejajar disebut :

    A. multigraf

    B. graf sederhana

    C. graf null

    D. graf lengkap

  • 7/22/2019 Teori Graf (Materi)

    87/95

    Graf & Analisis Algoritma Halaman 87 dari 95 halamanRAT

    7. Algoritma Welch-Powell digunakan untuk mencari :

    A. Minimal Spanning Tree

    B. Aliran Maksimal

    C. Bilangan Kromatik

    D. Jalur Terpendek

    8. Perjalanan (walk) yang semua simpul dalam barisan berbeda adalah

    A. jalur (path)

    B. lintasan ( trail)

    C. sirkuit (cycle)

    D. diameter

    9. Graf regular adalah graf yang memiliki :

    A. gelung atau self-loop

    B. ruas sejajar

    C. derajat setiap simpulnya berbeda

    D. derajat setiap simpulnya sama

    Untuk soal no. 10 s/d 16, gunakan graf di bawah ini :

    10. Order dan Size dari graf G1adalah :

    A. 4 dan 12

    B. 12 dan 16

    C. 12 dan 17

    D. 16 dan 12

    11. Derajat dari graf G1adalah :

    A. 12

    B. 24

    C. 32

    D. 34

    J

    G

    L

    I

    AB

    C

    D

    E

    K

    H F

    GrafG1

  • 7/22/2019 Teori Graf (Materi)

    88/95

    Logika & Algoritma Halaman 88dari 95 halamanRAT

    12. Bilangan Kromatik dari graf G1adalah :

    A. 2

    B. 3

    C. 4

    D. 5

    13. Pada pewarnaan graf G1, simpul yang boleh menggunakan warna yang sama adalah

    :

    A. A dan L

    B. A dan B

    C. C dan H

    D. B dan H

    14. Jarak antara simpul A dan G pada graf G1adalah :

    A. 2

    B. 3

    C. 4

    D. 5

    15. Graf G1mempunyai diameter :

    A. 2

    B. 3

    C. 4

    D. 5

    16. Yang merupakan jalur (path) dalam graf G1adalah :

    A. A,B,C,H,A

    B. E,D,K,J,C,D

    C. A,L,K,F

    D. A,H,C,J,F

    17. Graf G2 berikut ini, mempunyai region sebanyak :

    HE

    F I

    A D

    C

    B

    G J

    K

    Graf G2

  • 7/22/2019 Teori Graf (Materi)

    89/95

    Logika & Algoritma Halaman 89dari 95 halamanRAT

    A. 2

    B. 3

    C. 4

    D. 5

    18. Pembuatan jadwal kuliah pada suatu Perguruan Tinggi dapat diselesaikan dengan

    membawanya ke masalah graf, yakni masalah :

    A. jalur terpendek

    B. minimal spanning tree

    C. pewarnaan graf

    D. travelling salesman

    19. Matriks adjasensi suatu graf bersifat :

    A. simetris

    B. refleksif

    C. transitif

    D. antisimetris

    20. Pada graf berarah, simpul yang mempunyai derajat kedalam = 0 disebut :

    A. muara

    B. sumber

    C. terpencil

    D. artikulasi

    21. Pada graf berarah, simpul yang mempunyai derajat keluar = 0 disebut :

    A. muara

    B. sumber

    C. terpencil

    D. artikulasi

    22. Formula Euler untuk graf planar; dimana V adalah banyaknya simpul, E banyaknya

    ruas dan R banyaknya region, adalah :

    A. V - R + E = 2

    B. V - E + R = 2

    C. V - E + 2 = R

    D. V + E - R = -2

    23. Yang bukanmerupakan graf planar adalah :

    A. graf kubus

    B. graf segitiga

    C. graf berbentuk pohon

    D. graf lengkap dengan 5 simpul

    (K5)

    24. Manakah dari pernyataan berikut yang paling benar ?

  • 7/22/2019 Teori Graf (Materi)

    90/95

    Logika & Algoritma Halaman 90dari 95 halamanRAT

    A. Graf Regular juga merupakan

    Graf Lengkap

    B. Graf Lengkap juga merupakan

    Graf Regular

    C. Graf Bipartisi juga merupakan

    Graf Regular

    D. Graf Regular juga merupakan

    Graf Bipartisi

    25. Bilangan Kromatik dari graf bipartisi adalah :

    A. 2

    B. 3

    C. 4

    D. 5

    26. Suatu urutan dari barisan langkah-langkah guna menyelesaikan masalah disebut :

    A. algoritma

    B. semi algoritma

    C. instruksi

    D. semi instruksi

    27. Suatu prosedur yang hanya akan berhenti jika menghasilkan penyelesaian yang

    diharapkan disebut :

    A. algoritma

    B. semi algoritma

    C. instruksi

    D. semi instruksi

    28. Diagram alur dari proses penyelesaian masalah, yang paling benar adalah :

    A. masalah semi algoritma model program eksekusi hasil

    B. masalah model algoritma program eksekusi hasil

    C. masalah algoritma model program eksekusi hasil

    D. masalah program algoritma model eksekusi hasil

    29. Penilaian dari suatu algoritma pertama kali dilihat dari :

    A. efisiensi

    B. efektivitas

    C. terstruktur

    D. ada output

    30. Yang bukantermasuk kriteria dari suatu algoritma yang terbaik adalah :

    A. efisiensi

    B. terstruktur

    C. berakhir

    D. prosesnya cepat

  • 7/22/2019 Teori Graf (Materi)

    91/95

    Logika & Algoritma Halaman 91dari 95 halamanRAT

    31. Jika diketahui F(x) = 20 x7+ 12 x4+ 38 merupakan fungsi waktu tempuh, maka

    A. F(x) = O(20 x7)

    B. F(x) = 20 O(x7)

    C. F(x) = O(x7+ x4)

    D. F(x) = O(x7)

    32. Bila terdapat 4 algoritma sorting (kita sebut algoritma A, B, C dan D), dimana

    algoritma A memiliki kompleksitas O(n2), algoritma B memiliki kompleksitas O(n3),

    algoritma C memiliki kompleksitas O(log n), dan algoritma D memiliki kompleksitas

    O(n), maka algoritma manakah dari keempat algoritma tersebut yang lebih baik ?

    A. algoritma A

    B. algoritma B

    C. algoritma C

    D. algoritma D

    33. Diberikan sebuah algoritma sebagai berikut :

    Set A[i,j], B[i,j], C[i,j] real

    untuk i 1 s/d n kerjakan

    untuk j 1 s/d n kerjakan

    C[i,j] A[i,j] + B[i,j]

    akhir jakhir i

    Algoritma diatas merupakan algoritma untuk :

    A. melakukan penjumlahan matriks

    B. melakukan perkalian matriks

    C. melakukan penjumlahan

    D. melakukan perkalian

    34. Algoritma pada soal nomor 33 mempunyai kompleksitas waktu :

    A. O(n)

    B. O(n2)

    C. O(log n)

    D. O(n3)

  • 7/22/2019 Teori Graf (Materi)

    92/95

    Graf & Analisis Algoritma Halaman 92 dari 95 halamanRAT

    35. Diberikan sebuah algoritma sebagai berikut :

    Function RAT (n : integer) : integer

    If n := 1 then RAT := 1

    Else RAT := n * RAT(n-1)

    End Function

    Algoritma di atas menggunakan teknik :

    A. Backtracking

    B. Rekursif

    C. Greedy

    D. Iteratif

    36. Bila Algoritma pada soal nomor 35 berinput n = 5, maka outputnya adalah :

    A. 120

    B. 720

    C. 7

    D. 5040

    37. Bila Algoritma pada soal nomor 35 berinput n = 5, maka pemanggilan ulang

    function RAT adalah :

    A. 1 kali

    B. 4 kali

    C. 5 kali

    D. n kali

    38. Algoritma pada soal nomor 35 mempunyai kompleksitas waktu :

    A. O(n)

    B. O(log n)

    C. O(n2)

    D. O(n3)

    39. Diberikan sebuah algoritma sebagai berikut :

    Set x, y, n, i, f : integer

    x 1 ; y 1

    If n 2 then

    begin

    for i 3 to n do

    begin

  • 7/22/2019 Teori Graf (Materi)

    93/95

    Graf & Analisis Algoritma Halaman 93 dari 95 halamanRAT

    F x + y

    x y

    y F

    end

    end

    else

    F x

    Write(F)

    End

    Algoritma di atas menggunakan teknik :

    A. Iteratif

    B. DANDC

    C. Greedy

    D. Rekursif

    40. Bila Algoritma pada soal nomor 39 berinput n = 13, maka outputnya adalah :

    A. 55

    B. 233

    C. 89

    D. 144

    41. Algoritma pada soal nomor 39 mempunyai keadaan kompleksitas waktu :

    A. keadaan terbaik keadaan

    terburuk

    B. keadaan terbaik = keadaan

    terburuk

    C. keadaan terbaik > keadaan

    terburuk

    D. keadaan terbaik < keadaan

    terburuk

    42. Dasar dari teknik algoritma Backtracking adalah :

    A. searching

    B. merging

    C. divide and conquer

    D. sorting

    43. Pencarian ruang solusi dengan menggunakan stack disebut juga dengan istilah :

    A. Depth First Search

    B. Breadth First Search

    C. Binary Search

    D. Mergesort

  • 7/22/2019 Teori Graf (Materi)

    94/95

    Logika & Algoritma Halaman 94dari 95 halamanRAT

    44. Pencarian ruang solusi dengan menggunakan queue disebut juga dengan istilah :

    A. Depth First Search

    B. Breadth First Search

    C. Binary Search

    D. Mergesort

    45. Solusi yang diperoleh dengan cara Depth First Search berupa tupel yang :

    A. berbeda secara teratur

    B. seragam atau sama

    C. sembarang

    D. berbeda dan tidak teratur

    46. Teknik Divide AND Conquer adalah teknik yang digunakan untuk merancang

    sebuah algoritma dengan cara :

    A. memecah n input menjadi 2 subset input

    B. memecah n input sebanyak k input, k < n

    C. memecah n input sebanyak 2 input

    D. memecah n input menjadi k subset input, 1 < k n

    47. Perhatikan procedure berikut ini :

    PROCEDURE STRAITMAXMIN(A,n,max,min)

    INTEGER i,nmax min A(1)

    FOR i 2 TO n DO

    IF A(i) > max THEN max A(i)

    ELSE IF A(i) < min THEN min A(i) ENDIF

    REPEAT

    END STRAITMAXMIN

    Pada procedure STRAITMAXMIN di atas, akan tercapai keadaan terbaik bila :

    A. elemen A(1: n) disusun secara menaik

    B. elemen A(1: n) disusun secara menurun

    C. elemen A(1: n) disusun secara acak

    D. elemen A(1: n) disusun secara tidak naik

  • 7/22/2019 Teori Graf (Materi)

    95/95

    48. Bila diketahui sebuah prosedur sebagai berikut :

    PROCEDURE XXX(A,n)

    solusi 0 ......{solusi awal}

    FOR i 1 TO n DO

    x SELECT(A)

    IF FEASIBLE (solusi,x)

    THEN solusi UNION(solusi,x)

    ENDIF

    REPEAT

    RETURN (solusi)

    END XXX

    Algoritma di atas adalah algoritma secara umum dari :

    A. Metode DANDC

    B. Teknik BackTracking

    C. Pemrograman Dinamis

    D. Metode Greedy

    49. Pada permainan menara HANOI, algoritma yang paling baik adalah digunakannya

    teknik/metode :

    A. Backtracking

    B. Iteratif

    C. Greedy

    D. Rekursif

    50. Pada permainan menara HANOI, bila banyaknya piringan adalah 5 buah, maka

    banyaknya pemindahan adalah sebanyak :