BAB 2 LANDASAN TEORI

BAB 2

LANDASAN TEORI

2.1 Konsep Dasar Graf

Definisi 2.1.1 Sebuah graf didefinisikan sebagai pasangan terurut himpunan dimana: 1.

adalah sebuah himpunan tidak kosong yang berhingga yang anggotaanggotanya dinamakan simpul (verteks).

2. Graf

adalah sebuah himpunan sisi (edge) yang menghubungkan sepasang simpul. dilambangkan dengan

.

Definisi 2.1.1 menyatakan bahwa

tidak boleh kosong, sedangkan

boleh

kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada minimal satu. Bila

adalah himpunan berhingga maka graf

yang demikian disebut dengan graf berhingga (finite graph).

Suatu graf dengan graf ditulis dengan

buah simpul dan . Untuk lebih mudah

buah sisi disebut dengan sebuah biasa ditulis dengan

. Secara

umum graf dapat digambarkan dengan suatu diagram dimana simpul yang ditunjukkan sebagai titik yang dinotasikan dengan

,

dan sisi yang digambarkan

dengan sebuah garis lurus atau dengan garis lengkung yang menghubungkan dua simpul

dan dinotasikan

,

disebut dengan simpul-simpul ujung

Universitas Sumatera Utara

7

dari

. Sebagai contoh dapat dilihat Gambar 2.1 yaitu sebuah graf dengan 6 simpul

dan 6 sisi, maka dapat dinotasikan dengan

.

Gambar 2.1 Graf dengan 6 simpul dan 6 sisi

Definisi 2.1.2 Loop dan sisi Paralel. Sebuah sisi yang menghubungkan pasangan simpul yang sama atau bisa disebut juga sebuah sisi yang berawal dan berakahir dengan pada simpul yang sama disebut dengan gelang (loop). Dan dua atau lebih sisi yang mempunyai simpul-simpul ujung yang sama disebut dengan sisi paralel. Maka jika sebuah graf

yang di dalamnya tidak terdapat loop dan sisi paralel disebut

dengan graf sederhana.

Gambar 2.2 Graf dengan loop dan edge paralel


8

Definisi 2.1.3 Subgraf. Sebuah subgraf dari graf

adalah sebuah

sedemikian hingga

graf

dan

dengan kata lain sebuah graf

disebut subgraf dari graf

semua sisi dalam

dan setiap sisi dari

sama dengan

ada dalam

. Atau

jika semua simpul dan

mempunyai simpul akhir yang

. Sebagai contoh graf dalam gambar 2.3(b) adalah salah satu subgraf

dari graf-graf dalam gambar 2.3(a).

Gambar 2.3 (a) Graf, (b) Subgraf

Konsep dasar subgraf mempunyai kesamaan dengan himpunan dari teori himpunan. Sebuah subgraf dapat menjadi bagian dari yang lain. Lambang dari dimaksudkan dalam arti

adalah sebuah subgraf dari

. Dengan penjelasan diatas

maka dapat dibuat hal-hal sebagai berikut :


9

1. Setiap graf adalah subgraf dari dirinya sendiri. 2. Sebuah subgraf dari sebuah subgraf

adalah juga subgraf dari .

3. Sebuah simpul tunggal dalam sebuah simpul

adlah sebuah subgraf dari .

4. Sebuah sisi yang tunggal bersam dengan simpul akhirnya adalah sebuah subgraf dari .

Jika

, maka

disebut spanning subgraf dari .

Gambar 2.4 Graf dengan 5 simpul dan 6 sisi

Definisi 2.1.4 Adjacent dan Incindent. Dua buah simpul pada graf tak berarah G dikatakan bertetangga ( adjacent ) bila keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain. vj bertetangga dengan vk jika (vj, vk) adalah sebuah sisi dari graf. Untuk sebarang sisi e = (vj, vk), sisi e dikatakan bersisian (incident) dengan simpul vj dan vk.

2.2 Terminologi Dasar

Definisi 2.2.1 Walk. Sebuah walk didefinisikan sebagai barisan alternatif berhingga dari simpul-simpul dan sisi yang diawali dan diakhiri dengan simpul sedemikian hingga tiap-tiap sisi yang bersisian (edge incident) dengan simpul yang terdahulu dan dengan simpul yang berikutnya. Simpul yang merupakan simpul awal dan simpul


10

akhir disebut dengan terminal simpul. Pada Gambar 2.5 dapat diplih sebuah walk yaitu .

Dapat juga sebuah walk dimulai dan diakhiri oleh simpul yang sama, walk yang demikian disebut dengan close walk. Sebaliknya sebuah walk yang tidak close disebut open walk.

Gambar 2.5 Graf dengan walk yang bergaris tebal

Definisi 2.2.2 Path. Sebuah open walk yang didalamnya tidak ada simpul yang muncul lebih dari sekali disebut dengan sebuah path (path sederhana atau path dasar).

Pada Gambar 2.5 dapat diambil sebuah path yaitu contoh. Tetapi

sebagai

bukan merupakan path tetapi sudah merupakan

cycle. Jumlah sisi-sisi dalam sebuah path disebut dengan length dari path.

Gambar 2.6 Path


11

Definisi 2.2.3 Sirkuit/Cycle. Sebuah path tertutup yang mana dimulai dari simpul awal sampai ke simpul tujuan dan kembali lagi ke simpul awal.

Gambar 2.7 Sirkuit

Definisi 2.2.4 Graf terhubung dan tidak terhubung (Connected dan Disconnected Graph). Sebuah graf

dikatakan connected jika ada sedikitnya satu path antara

setiap pasangan simpul dalam graf

. Sebaliknya graf

tidak ada path antara setiap pasangan simpul dalam graf

adalah disconnected jika . Sebagai contoh masing-

masing untuk connected graph dan disconnected graph dapat dilihat pada Gambar 2.7 dan 2.8.

Gambar 2.8 Graf yang berisi connected graph


12

Gambar 2.9 (a),(b). Disconnected graph

2.3

Jenis-jenis Graf

Definisi 2.3.1 Graf sederhana (simple graph). Graf sederhana adalah graf yang tidak mengandung gelang (loop) maupun sisi paralel.

Gambar 2.10 Graf sederhana


13

Definisi 2.3.2 Graf lengkap dan tidak lengkap. Graf lengkap adalah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya. Graf lengkap dengan n buah simpul dilambangkan dengan

sedangkan graf tidak lengkap adalah graf

sederhana yang mana setiap simpulnya tidak mempunyai sisi ke semua simpul lainnya.

Gambar 2.11(a) Graf lengkap

Gambar 2.11(b) Graf tidak lengkap

Definisi 2.3.3 Digraph (Directed Graph). Digraph adalah sebuah graf dari

himpunan

simpul

dan

yang terdiri

himpunan-himpunan

sisi

serta suatu pemetaan yang memetakan setiap sisi onto beberapa pasangan berurut dari simnpul garis berarah dari

ke

dimana simpul yang disajikan dengan sepotong

.


14

Dimana adalah arc ke-

dari

yang dipetakan kepasangan simpul

contohnya dapat dilihat pada Gambar 2.9.

Gambar 2.12 Directed graph

Pemetaaan dari gambar tersebut adalah simpul oleh

, maka dapat ditulis

dihubungkan oleh sisi

ke

dihubungkan ke simpul

dan seterusnya hingga simpul

itu sendiri.

Definisi 2.3.4 Undigraph (Undirected graph). Undigraph adalah suatu graph terdiri atas pasangan himpunan

dimana

yang

adalah himpunan berhingga yang

tidak kosong yang anggotanya disebut dengan simpul (verteks) dan

merupakan

himpunan berhingga yang anggotanya merupakan potongan garis tak berarah yang menghubungkan pasangan dari simpul .


15

Gambar 2.13 Undigraph

Definisi 2.3.5 Weighted graph dan Labelled graph. Suatu graf disebut dengan weighted graph jika terdapat suatu bilangan real yang dihubungkan dengan setiap sisi dari graf tersebut. Suatu graf disebut dengan labelled graph jika setiap sisi dari graf itu dihubungkan dengan simbol yang bukan bilangan. Pada Gambar 2.14 (a) dan gambar 2.14 (b) adalah contoh dari weighted graph dan labelled graph.

Gambar 2.14 (a). Weighted graph. (b). Labelled graph


16

2.4 Pohon Merentang Minimum (Minimum Spanning Tree)

2.4.1 Pohon (Tree)

Pohon adalah graf terhubung yang tidak memiliki jalan lingkar (cycle). Didalam sutu pohon tidak memuat sisi-sisi yang paralel dan loop. Karena itu pohon juga merupakan graf sederhana. Sebagai contoh pada Gambar 2.15 adalah pohon.

Gambar 2.15 (a),(b). Pohon

Definisi 2.4.1.1 Pohon yang hanya terdiri atas satu simpul (tanpa sisi) disebut dengan pohon yang menyusut atau pohon yang mengalami degenerasi atau pohon trivial.

Sebenarnya ada beberapa cara untuk mendefinisikan pohon: definisi-definisi yang dihasilkan ekuivalen. Hal ini dirangkum dalam teorema dibawah ini. Teorema ini sekaligus menjelaskan ciri-ciri dari pohon. Dalam teorema dibawah ini, perkataan ekuivalen digunakan dalam arti jika salah satu pernyataan itu benar maka pernyatanpernyataan yang lain itu pasti benar dan sebaliknya jika salah satu pernyataan itu salah, maka pernyataan-pernyataan yang lain pasti juga salah.


17

Teorema 2.4.1.2 Jika

adalah graf yang memiliki tepat

simpul; pernyataan-

pernyataan berikut ekuivalen: (i)

adalah pohon.

(ii)

memiliki tepat

sisi dan tidak memilik cycle

(iii) adalah graf terhubung yang memiliki tepat (iv)

sisi.

adalah graf terhubung yang setiap rusuknya adalah jembatan.

(v) Setiap dua simpul dari G dihubungkan oleh tepat satu alur. (vi)

tidak memiliki cycle, tetapi jika banyaknya sisi ditambah satu yang menghubungkan sebarang dua simpul, maka hasilnya ialah graf yang memiliki tepat satu cycle.

Bukti: Keadaan I : n = 1

(i) Jelas bahwa (ii)

adalah pohon yaitu pohon yang menyusut.

tidak memuat cycle, sedang banyaknya sisi dari . Jadi benar bahwa

memiliki tepat

(iii)

terhubung dan memiliki tepat

(iv)

terhubung dan tidak ada sisi dari dari

adalah nol, yaitu

sisi.

sisi. yang bukan jembatan, jadi setiap sisi

adalah jembatan.

(v)Tidak ada pasangan simpul dari

(dua simpul yang berbeda dari

) yang

tidak dihubungkan dengan jalur. (vi)

tidak memuat cycle dan jika banyaknya sisi dari

ditambah satu berarti

graf yang terjadi terdiri atas tepat satu cycle.

Keadaan II : n

2

a. Akan dibuktikan bahwa jika (i) benar maka (ii) benar. Andaikan

adalah pohon. Maka menurut definisi

Berarti bahwa pelenyapan satu sisi dari

tidak memiliki cycle.

akan menghasilkan dua graf baru


18

yang terpisah, yang masing-masing merupakan pohon. Karena memiliki

simpul berarti bahwa jika

tertinggal hanyalah simpul. Jadi

dilenyapkan

memiliki tepat

hanya

sisinya,yang

sisi.

b. Akan dibuktikan bahwa jika (ii) benar maka (iii) benar. Andaikata

tidak memiliki cycle dan memiliki

pohon ; namakan

sisi, maka

terdiri atas

: yang banyaknya simpul berturut-turut adalah

dimana

n. Berarti

+

=n

1

atau

Ternyata

hanya terdiri atas satu komponen. Jadi G terhubung.

c. Akan dibuktikan bahwa jika (iii) benar maka (iv) benar. Andaikan satu sisi dari

adalah graf terhubung yang memiliki tepat

sisi. Jika salah

dilenyapkan maka yang terjadi adalah graf

tepat n simpul dan tepat

sisi.Jadi setiap sisi dari

yang memiliki

adalah jembatan.

d. Akan dibuktikan bahwa jika (iv) benar maka (v) benar. Andaikan simpul dari

terhubung dan setiap sisinya adalah jembatan. Maka setiap dua dihubungkan dengan paling sedikit satu alur. Hal ini

bertentangan dengan keadaan bahwa setiap sisi dari setiap dua simpul dari

adalah jembatan. Jadi

dihubungkan oleh tepat satu alur.

e. Akan dibuktikan bahwa jika (v) benar maka (vi) benar. Andaikan

memuat cycle, maka setiap dua simpul pada cycle itu

dihubungkan oleh paling sedikitnya dua alur. Jadi kalau (v) benar, maka tidak memuat cycle. Jika

ditambah dengan sisi yang menghubungkan

kedua simpul itu maka terjadilah tepat satu cycle yang melalui kedua simpul tersebut.


19

f. Akan dibuktikan bahwa jika (vi) benar maka (i) benar. Misalkan

tidak memiliki cycle, dan setiap penambahan sisi pada

menghasilkan tepat satu cycle. Seandainya

tidak terhubung, maka

penambahan satu sisi yang menghubungkan satu simpul dari salah satu komponen dan simpul, salah satu komponen yang lain tidak akan menghasilkan cycle. Berarti G pasti terhubung. Jadi jika (vi) benar maka G terhubung dan tidak memiliki cycle. Artinya, jika (vi) benar maka (vii) benar.

Teorema 2.4.1.3 Sebuah graf

dengan

simpul, mempunyai

sisi dan tidak ada

sirkuit didalamnya adalah terhubung.

Bukti:

Andaikan terdapat sebuah graf tanpa sirkuit dengan

simpul dan

sisi

yang mana graf adalah tidak terhubung (disconnected). Dalam hal ini graf akan berisi dua atau lebih komponen tanpa sirkuit tanpa menghilangkan sifat keumuman. Misalkan

terdiri atas dua komponen

sebuah simpul dan

dalam

dan

dalam , penambahan

dan

dalam

tambahkan sebuah sisi

antara

. Dari sini bahwa tidak ada path antara

tidak menimbulkan sirkuit.

2.4.2 Pohon perentang (Spanning Tree)

Misalkan berarti di

adalah graf tak-berarah terhubung yang bukan pohon, yang terdapat beberapa sirkuit.

ini dapat diubah menjadi pohon

dengan cara memutuskan sirkuit-sirkuit yang ada. Caranya mula-mula dipilih sebuah sirkuit, lalu hapus satu buah sisi dari sirkuit ini.

akan tetap terhubung dan jumlah

sirkuitnya berkurang satu. Bila proses ini dilakukan berulang-ulang sampai semua sirkuit di

hilang, maka

menjadi sebuah pohon

, yang dinamakan pohon


20

merentang (spanning tree). Disebut pohon merentang karena semua simpul pada pohon

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

pada graf . Dengan kata lain

sisi-sisi

dan

Karena definisi pohon diacu dari graf, maka sebuah pohon dapat mempunyai hanya sebuah simpul tanpa sebuah sisi pun. Dengan kata lain, jika graf adalah pohon maka

tidak boleh berupa himpunan kosong namun

boleh kosong.

Pohon yang dimaksudkan sering disebut dengan pohon bebas (free tree). Pohon juga seringkali didefinisikan sebagai graf tak berarah dengan sifat bahwa hanya terdapat sebuah lintasan unik antara setiap pasang simpul.

Sebuah sisi dalam suatu spanning tree (branch) dari

dan sebuah sisi dari

disebut dengan sebuah cabang

yang tidak dimuat oleh spanning tree disebut

denga tali (chord). Suatu sisi bisa saja merupakan branch untuk suatu spanning tree tetapi merupakan chord untuk spanning tree yang lainnya.

Teorema 2.4.2.1 Setiap graf terhubung mempunyai sekurang-kurangnya satu spannig tree.

Bukti:

Jika treenya adalah

suatu graf terhubung dan sendiri, jika

tidak mempunyai sirkuit maka spanning

mempunyai sebuah sirkuit maka spanning treenya

dapat diperoleh dengan menghilangkan sisi pembentuk sirkuit tersebut. Selanjutnya jika

mempunyai banyak sirkuit (lebih dari satu sirkuit) maka cara diatas dapat

diulangi sampai sisi terakhir pembentuk sirkuit dihilangkan.


21

2.4.3 Minimum Spanning Tree

Jika G adalah graf berbobot, maka bobot perentang T dari G didefinisikan dengan jumlah bobot semua sisi di T. Pohon perentang yang berbeda mempunyai bobot yang berbeda pula. Di antara semua pohon perentang di G, pohon perentang yang berbobot minimum dinamakan pohon merentang minimum ( minimum spanning tree ).

2.5

Algoritma Greedy

Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah dimana pada setiap langkah dibuat pilihan optimum (local optimum) dengan harapan bahwa langkah berikutnya mengarah ke solusi optimum global (global optimum).

Algoritma greedy membuat keputusan berdasarkan pilihan yang ada sekarang, tidak melihat pilihan yang akan muncul kemudian. Padahal didalam permasalahan optimisasi terdapat banyak pilihan yang dapat dieksplorasi pada setiap langkah solusi. Namun begitu algoritma ini tetap menjadi pilihan utama untuk permasalahan sederhana karena ini metode yang cepat dibanding dengan metode yang lain dan dapat memberikan solusi hampiran atau aproksimasi terhadap nilai optimum yang diinginkan serta hasil yang diberikan masih merupakan solusi yang layak (feasible solution).

Dalam menyelesaikan permasalahan di dalam minimum spanning tree akan diperlihatkan strategi greedy pada algoritma Prim dan algoritma Kruskal untuk menyelesaikannya.

Beberapa algoritma yang menggunakan strategi greedy dalam menyelesaikan minimum spanning tree yaitu :

1. Algoritma Prim Algoritma Prim merupakan salah satu algoritma yang bekerja secara greedy. Algoritma Prim membentuk pohon merentang minimum dengan langkah per


22

langkah. Pada setiap langkah diambil sisi graf namun yang terhubung dengan pohon merentang

yang memiliki bobot minimum yang telah terbentuk.

Algoritma Prim: 1. Ambil sisi dari graf 2. Pilih sisi

yang berbobot minimum, masukan ke dalam .

yang memiliki bobot minimum dan bersisian dengan simpul di

, tetapi

tidak membentuk sirkuit di

Tambahkan

ke

dalam

. 3. Ulangi langkah 2 sebanyak

kali.

Jumlah seluruh langkah pada algoritma Prim ini adalah yaitu sama dengan jumlah sisi pada pohon merentang dengan

, buah simpul.

2. Algoritma Kruskal Algoritma Kruskal juga dapat digunakan dalam memecahkan permasalahan pada pemodelan pohon merentang minimum. Pada algoritma Kruskal mula-mula semua garis dalam

diurutkan berdasarkan bobotnya dari kecil hingga ke besar.

Pada setiap langkah, dipilih garis dengan bobot terkecil, tetapi tidak membentuk loop dengan garis-garis yang sudah dipilih terdahulu.

Algoritma Kruskal: 1. Isi T dengan semua titik-titik G tanpa garis. 2. Buat T dengan memasukkan satu sisi terpendek dari G tersebut. 3. Ambil sisi selanjutnya dari G, jika sisi itu tidak membentuk sirkuit. 4. Masukkan simpul-simpul sisi itu ke T.

2.6 Algoritma Program Dinamik Program dinamik adalah salah satu teknik matematika yang digunakan untuk mengoptimalkan proses pengambilan keputusan secara bertahap ganda. Inti dari


23

teknik ini ialah membagi satu persoalan atas beberapa bagian persoalan (tahap), kemudian memecahkan tiap tahap sampai seluruh persoalan telah terpecahkan.

Penggunanan program dinamik untuk mencari bobot minimum dari suatu pohon merentang merupkan salah satu alternatif selain penggunaan algoritma greedy. Prosedur pemecahan persoalan dlam program dinamik dilakukan secara rekursif. Ini berarti bahwa setiap kali diambil keputusan, diperhatikan keadaan yang dihasilkan oleh keputusan sebelumnya.

Program Dinamik (Dynamic Programming) adalah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Karakteristik penyelesaian masalah dengan algoritma program Dinamik :

1. terdapat sejumlah berhingga pilihan yang mungkin 2. solusi pada setiap tahap dibangun dari hasil solusi tahap sebelumnya. 3. kita menggunakan persyaratan optimasi dankendala untuk membatasi sejumlah pilihan yangharus dipertimbangkan pada satu tahap.


BAB 2 LANDASAN TEORI

Recommend Documents