Transcript
  • TEORI GRAF

    MINIMUM SPANNING TREE

    HALAMAN JUDUL

    Oleh :

    ATIKAH ARI PRAMESTI

    4611412016

    TEKNIK INFORMATIKA

    FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

    UNIVERSITAS NEGERI SEMARANG

    2014

  • TEORI GRAF

    A. Defenisi Graf

    Suatu graf G adalah suatu himpunan berhingga tak kosong dari objek-objek

    yang disebut verteks (titik/simpul) dengan suatu himpunan yang anggotanya adalah

    pasangan tak berurut dari verteks yang berbeda pada G yang disebut edge (mungkin

    kosong), dan dinotasikan dengan G{V(G),E(G)}. Himpunan verteks dari G

    dinotasikan dengan V(G) dan himpunan edge(sisi) dinotasikan dengan E(G).

    Banyaknya anggota dari himpunan verteks pada G disebut order G dan dinotasikan

    dengan p(G), atau dengan singkat ditulis p. Edge e = {u,v} atau juga dapat ditulis e =

    uv adalah sebuah edge dalam G, yaitu u dan v adalah titik-titik ujung dari e, maka u

    dan v dikatakan adjacent (berelasi) dimana u dan e adalah incident (terhubung),

    begitu juga dengan v dan w. Banyaknya edge yang incident dengan verteks u disebut

    degree / valensi / derajat dari u, dengan kata lain degree u adalah banyaknya edge

    yang memuat u sebagai titik ujung. Degree u dinotasikan dengan deg(u).

    Suatu graf biasanya dipresentasikan secara grafis, dengan setiap verteks

    dipresentasikan sebagai titik atau lingkaran kecil, dan setiap edge e = uv

    dipresentasikan dengan sebuah garis atau kurva yang menghubungkan titik-titik yang

    bersesuaian dengan u dan v.

    Gambar 2.1 menunjukkan bahwa graf G = G(V, E), di mana V(G) = {v1, v2, v3, v4,

    v5, v6} dan E(G) = {e1, e2, e3, e4, e5, e6, e7, e8, e9}.

  • B. Macam-macam Graf

    Berdasarkan arah dan bobotnya, graf digolongkan atas 4 jenis, yaitu :

    1. Graf berarah dan berbobot graf yang setiap sisinya mempunyai orientasi arah

    dan bobot.

    2. Graf berarah dan tak berbobot graf yang setiap sisinya mempuyai arah dan

    tidak berbobot.

    3. Graf tidak berarah dan berbobot graf yang setiap sisinya tidak mempunyai

    arah tetapi memiliki bobot.

    4. Graf tidak berarah dan tidak berbobot graf yang setiap sisinya tidak memiliki

    arah dan bobot.

    C. Terminologi dalam Graf

    Terminologi (istilah) yang berkaitan dengan graf akan sering digunakan. Di bawah ini

    didefenisikan beberapa istilah yang sering dipakai dan berhubungan dengan

    maximum spanning tree.

    1. Walk adalah suatu barisan berhingga dari verteks dan edge secara bergantian,

    yang diawali dari verteks dan diakhiri dengan verteks. Bentuk umum dari walk :

    Dalam hal ini v0 merupakan verteks awal dan vn merupakan vertex akhir. Jika

    verteks awal dan vertex akhir dari suatu walk adalah sama, maka walk disebut

    close walk (walk tertutup).

    2. Trail adalah suatu walk dengan setiap edgenya berlainan.

    3. Path adalah suatu walk dengan setiap verteksnya berbeda.

    4. Cycle adalah suatu path yang memiliki verteks awal sama denga verteks akhir.

    5. Length (panjang) adalah bilangan yang menyatakan banyaknya edge yang

    muncul dalam suatu walk.

    6. Edge e adalah sebuah jembatan untuk G jika G e tidak terhubung. Secara

    umum edge e adalah jembatan untuk suatu graf G jika G-e mempunyai

    komponen terhubung lebih dari G.

  • D. Pohon dan Hutan

    1. Pohon (Tree)

    Sejumlah masalah yang berhubungan dengan graf yang ditemukan manusia

    dalam kehidupan nyata menimbulkan penemuan konsep-konsep pemecahan

    masalah graf. Konsep pohon pernah diterapkan pada tahun 1870-an oleh

    Matematikawan Inggris yang bernama Arthur Cayley dalam penghitungan

    molekul kimia. Karya yang lebih baru membuktikan bahwa pohon digunakan di

    banyak bidang, mulai dari linguistik sampai komputer. Pohon adalah suatu graf

    terhubung yang tidak memuat sirkuit. Tree dinotasikan dengan T.

    Sebuah graf G dengan n verteks dikatakan sebuah tree jika :

    G terhubung dan tak memuat sirkuit,atau

    G terhubung dan memiliki n 1 edge,atau

    G tak memuat sirkuit dan memiliki n 1 edge,atau

    Terdapat tepat satu path diantara setiap pasangan verteks-verteks di G,atau

    G setidaknya merupakan sebuah graf terhubung.

    Pohon adalah graf yang khusus. Menurut defenisi 9.1 (Munir, 2005:444),

    ada dua sifat penting pada pohon, yaitu : merupakan graf terhubung dan tidak

    mengandung sirkuit.

    Pada Gambar 2.6, hanya G1 dan G2 merupakan pohon, sedangkan G3 dan G4

    bukan pohon. G3 bukan pohon karena mengandung sirkuit a, d, f, a sedangkan

    G4 bukan pohon karena merupakan graf tak-terhubung.

  • Sifat-sifat Pohon

    Teorema. Misalkan G = (V, E) adalah graf tak-berarah sederhana dan jumlah

    simpulnya n. Maka, semua pernyataan di bawah ini adalah ekivalen:

    1) G adalah pohon.

    2) Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal.

    3) G terhubung dan memiliki m = n 1 buah sisi.

    4) G tidak mengandung sirkuit dan memiliki m = n 1 buah sisi.

    5) G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan

    membuat hanya satu sirkuit.

    6) G terhubung dan semua sisinya adalah jembatan.

    Teorema di atas dapat dikatakan sebagai definisi lain dari pohon.

    2. Hutan (Forest)

    Hutan merupakan :

    Kumpulan pohon yang saling lepas.

    Graf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen

    didalam graf terhubung tersebut adalah pohon.

  • E. Pohon Merentang dan Pohon Merentang Maximum

    1. Defenisi Pohon Merentang (Spanning Tree)

    Pohon rentang suatu graf G adalah subgraf G yang merupakan pohon dan

    semua memuat titik dalam G. Disebut pohon merentang karena semua simpul

    pada pohon T sama dengan semua simpul pada graf G, dan sisi-sisi pada pohon T

    gh sisi-sisi pada graf G. Dengan kata lain, V1 = V dan E1 E.

    Pada Contoh 2.4 berikut akan diberikan bagaimana cara menentukan pohon

    merentang dari sebuah graf.

    Contoh 2.4 :

    Perlu dicermati bahwa spanning tree didefenisikan hanya untuk graf

    terhubung, karena pohon selalu terhubung. Pada graf tak terhubung dengan n

    buah simpul kita tidak dapat ditemukan subgraf terhubung dengan n buah titik.

    Tiap komponen dari graf tak-terhubung mempunyai satu buah spanning tree.

  • Dengan demikian, graf tak-terhubung dengan k komponen mempunyai hutan

    merentang (spanning forest) yang terdiri dari k buah pohon merentang. (Munir,

    2005:449)

    Kelebihan Spanning Tree

    Dapat menyediakan system jalur backup & juga mencegah loop yang

    tidak diinginkan pada jaringan yang memiliki beberapa jalur menuju ke satu

    tujuan dari satu host. Loop terjadi bila ada route/jalur alternative di antara

    host-host. Untuk menyiapkan jalur back up, Spanning tree membuat status

    jalur back up menjadi stand by atau diblock. Spanning tree hanya

    membolehkan satu jalur yang active (fungsi pencegahan loop) di antara dua

    host namun menyiapkan jalur back up bila jalur utama terputus. Bila "cost"

    spanning tree berubah atau ada jalur yang terputus, algoritma spanning tree

    mengubah topology spanning tree dan mengaktifkan jalur yang sebelumnya

    stand by. Tanpa spanning tree pun sebenarnya memungkinkan koneksi antara

    dua host melewati beberapa jalur sekaligus namun dapat juga membuat

    looping yang tidak pernah akan selesai di dalam jaringan anda. Yang pasti

    akan menghabiskan kapasitas jalur yang ada hanya untuk melewatkan packet

    data yang sama secara berulang dan berlipat ganda.

  • 2. Pohon Merentang Maksimum (Maximum Spanning Tree)

    Jika G adalah graf berbobot, maka bobot pohon merentang T dari G

    didefenisikan sebagai jumlah bobot semua sisi di T. Pohon merentang yang

    berbeda mempunyai bobot yang berbeda pula. Di antara semua pohon merentang

    di G, pohon merentang yang berbobot maksimum dinamakan pohon merentang

    maksimum atau maximum spanning tree.

    F. Algoritma Greedy

    Metode ini digunakan untuk memperoleh solusi yang optimal dari suatu masalah

    yang mempunyai 2 indikator yaitu: adanya fungsi tujuan & pembatas (Constrain).

    PROCEDURE GREEDY (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 GREEDY

    Keterangan :

    A(1:n) mengandung n input data.

    FEASIBLE merupakan fungsi yang bernilai boolean (0 atau 1)

    UNION penggabungan dan pemeriksaan fungsi obyektifnya (update)

    SELECT merupakan fungsi untuk mengambil data input dari A

    CONTOH :

    Himpunan A merupakan himpunan pasangan terurut (x,y), yaitu { (2,1),(3,2),(7,1)

    dan (1,0)}. Dari data-data tersebut akan ditentukan suatu pasangan terurut yang

    memiliki jumlah x dan y yang minimum. Adapun batasan dari x dan y masingmasing

    lebih besar dari nol.

  • Dari himpunan solusi yang mungkin tersebut diperoleh solusi yang optimal (dalam

    hal ini minimum) adalah (2,1) yang jumlahnya sebesar 2 + 1 = 3.

    Jadi solusi = (2,1)

    METODE GREEDY banyak digunakan dalam berbagai penyelesaian maslah, antara

    lain adalah :

    1.Optimal Storage on Tapes Problem

    2.Kanpsack Problem

    3.Minimum Spanning Tree Problem

    4.Shortest Path Problem

    Dalam hal ini hanya akan dibahas megenai minimum Spanning Tree saja.

    Untuk masalah minimum spanning tree, syarat graph dapat dicari minimum

    spanning treenya adalah :

    1. Graph harus terhubung

    2. Ruasnya punya bobot / nilai

    3. Graphnya tidak berarah

    Algoritma yang dapat dipakai untuk menentukan minimum spanning tree adalah :

    1. Algoritma Prims

    2. Algoritma Kruskal

    3. Algoritma Solin

  • G. Algoritma Prim

    Masalah pohon merentang minimum dapat dipecahkan dengan bantuan suatu

    pohon yang ditemukan oleh Prim (1957). Algoritma ini biasa disebut dengan

    Algoritma Prim. Algoritma Prim adalah suatu algoritma di dalam teori graf yang

    bertujuan menentukan suatu pohon merentang minimum dari suatu graf terhubung

    yang berbobot. Metode ini digunakan untuk menemukan suatu subset dari sisi yang

    membentuk suatu pohon yang melibatkan tiap-tiap titik, dimana total bobot dari

    semua sisi di dalam pohon adalah minimum. Algoritma Prim juga dapat digunakan

    dalam menentukan maximum spanning tree. Secara terurut, algoritma Prim untuk

    mencari maximum spanning tree dapat dituliskan sebagai berikut :

    1. Menentukan sebarang titik awal dan dilanjutkan mengambil sisi dari graf G

    yang berbobot maksimum dari titik awal yang dipilih tadi, masukkan ke dalam

    T yang kosong.

    2. Pilih sisi e yang mempunyai bobot maksimum berikutnya dan bersisian

    dengan titik di T, tetapi e tidak membentuk sirkuit di T. Masukkan e ke dalam

    T.

    3. Ulangi langkah 2 hingga terbentuk maximum spanning tree.

    H. Algoritma Kruskal

    Algoritma Kruskal adalah suatu algoritma di dalam teori graf yang digunakan

    untuk mengkonstruksi pohon merentang minimum di di dalam graf berbobot

    terhubung secara berurutan dari sisi yang berbobot kecil sampai berbobot besar

    hingga tidak terbentuk cycle. Algoritma Kruskal dapat diasumsikan dengan memilih

    sisi dari graf secara berurutan berdasarkan bobotnya dari bobot kecil ke bobot besar.

    Algoritma Kruskal juga dapat digunakan dalam menentukan maximum spanning tree.

    Secara terurut, algoritma Kruskal untuk mencari maximum spanning tree dapat

    dituliskan sebagai berikut :

    1. Urutkan sisi-sisi graf dari besar ke kecil. T merupakan himpunan kosong.

    2. Pilih sisi e dengan bobot maksimum yang tidak membentuk sirkuit di T.

    Masukkan e ke dalam T.

    3. Ulangi langkah 2 sebanyak n 1 kali hingga terbentuk maximum spanning

    tree.

  • I. Algoritma Sollin

    Algoritma Sollin adalah suatu algoritma dalam teori graf yang digunakan

    untuk menentukan pohon merentang minimum di dalam graf berbobot terhubung

    dengan cara melakukan penghapusan sisi-sisi yang tidak menyebabkan graf menjadi

    tidak berhubung atau membentuk sirkuit. Penghapusan tersebut dimulai dari sisi yang

    memiliki bobot terbesar hingga terkecil. Algoritma Sollin juga dapat digunakan dalam

    menentukan maximum spanning tree. Untuk menentukan maximum spanning tree

    dari sebuah graf dengan menggunakan Algoritma Sollin maka diperlukan langkah-

    langkah sebagai berikut :

    1. Urutkan sisi-sisi pada graf berdasarkan bobotnya dari kecil ke besar.

    2. Lakukan penghapusan setiap sisi yang tidak menyebabkan graf menjadi

    3. tidak terhubung. Penghapusan dimulai dari sisi yang memiliki bobot

    terkecil.

    4. Ulangi langkah 2 hingga diperoleh maximum spanning tree.

    J. Aplikasi Pohon Merentang

    1. Jalan-jalan seminimum mungkin yang menghubungkan semua kota sehingga

    setiap kota tetap terhubung satu sama lain.

    2. Perutean (routing) pesan pada jaringan komputer.

    (a) (b)

    Router

    Subnetwork

    (a) Jaringan komputer, (b) Pohon merentang multicast

  • Pohon Rentang Minimum

    1. Graf terhubung-berbobot mungkin mempunyai lebih dari 1 pohon merentang.

    2. Pohon rentang yang berbobot minimum dinamakan pohon merentang

    minimum (minimum spanning tree).

    Algoritma Prim

    Langkah 1: Ambil sisi dari graf G yang berbobot minimum, masukkan ke

    dalam T.

    Langkah 2: Pilih sisi (u, v) yang mempunyai bobot minimum dan bersisian

    dengan simpul di T, tetapi (u, v) tidak membentuk sirkuit di T.

    Masukkan (u, v) ke dalam T.

    Langkah 3: Ulangi langkah 2 sebanyak n 2 kali.

    Jumlah langkah seluruhnya di dalam algoritma Prim adalah:

    1 + (n 2) = n 1

    yaitu sebanyak jumlah sisi di dalam pohon rentang dengan n buah simpul.

  • Contoh :

  • Pohon merentang minimum yang dihasilkan:

    Bobot = 10 + 25 + 15 + 20 + 35 = 105

    Pohon merentang yang dihasilkan tidak selalu unik meskipun bobotnya tetap

    sama. Ini terjadi jika ada beberapa sisi yang akan dipilih berbobot sama.

    Contoh:

    Algoritma Kruskal

    ( Langkah 0: sisi-sisi dari graf sudah diurut menaik berdasarkan bobotnya

    dari bobot kecil ke bobot besar)

    Langkah 1: T masih kosong

    Langkah 2: pilih sisi (u, v) dengan bobot minimum yang tidak membentuk

  • sirkuit di T. Tambahkan (u, v) ke dalam T.

    Langkah 3: Ulangi langkah 2 sebanyak n 1 kali.

    Contoh:

  • Pohon merentang minimum (sapanning tree) yang dihasilkan:

  • K. Kesimpulan

    Dari permasalahan diatas dapat ditarik kesimpulan yaitu:

    1. Algoritma Prim dan Algoritma Kruskal dapat menyelesaikan permasalahan

    pencarian pohon merentang minimum dengan tepat.

    2. Algoritma Prim lebih efisien dibanding algoritma Kruskal saat graf yang

    diberikan memiliki banyak sisi dengan simpul yang sedikit (graf lengkap).

    3. Algoritma Kruskal lebih efisien dibanding algoritma Prim saat graf yang

    diberikan memiliki banyak simpul dengan sisi yang sedikit.


Top Related