UAS MATEMATIKA DISKRIT

1. PERMUTASI
 

Permutasi adalah suatu susunan yang dapat dibentuk dari suatu kumpulan benda yang diambil sebagian atau seluruhnya dengan memperhatikan urutan.

Contoh I:
{a,b,c}
Jika dipilih 2 dari 3 unsur tersebut, maka banyaknya permutasi dari 3 unsur setiap pengambilan 2 unsur adalah 6, yaitu ab, ba, ac, ca, bc, cb.
Ditulis 3P2 = 6.

Contoh II:
{a,b,c}
maka, banyaknya permutasi dari 3 unusr setiap pengambilan 3 unsur adalah 6, yaitu abc, acb, bac, bca, cab, cba.
Ditulis 3P3 = 6
RUMUS :
Catatan: Notasi Faktorial
3! = 3x2x1
5! = 5x4x3x2x1
1! = 1
Def 0! = 1

Contoh :

Terdapat 6 Mahasiswa yang memenuhi syarat dan bersedia menjadi pengurus Himpunan Mahasiswa Jurusan (HMJ).Jika pengurus HMJ  itu terdiri dari ketua,sekretaris dan bendahara.Ada berapa macam susunan pengurus yang mungkin di bentuk?

Jawab :

Persoalan ini termasuk dalam  persoalan mencari banyak susunan terdiri dari 4 benda yang diambil dari 6 benda. Jadi kita hendak mencari P6.4 . P6.4 = 6.5.4.3 = 360.Berikut ini adalah penjelasannya.Ada 6 mahasiswa yang bisa dipilih menjadi ketua.Seandainya ketua telah dipilah,maka 5 pilihan untuk wakil ketua.Jika ketua dan wakil ketua telah terpilih, maka ada 4 pilihan untuk sekretaris.Jika ketua,wakil ketua dan sekretaris telah dipilih, maka tinggal 3 mahasiswa yang bisa dipilih untuk bendahara. Jadi banyaknya susunan pengurus yang mungkin 6.5.4.3=360 atau dapat diubah menjadi bentuk  faktorial sebagai berikut

P6.4 =    =  =  = 360

Ø  Permutasi Siklis

Permutasi Siklis = banyaknya cara untuk n objek disusun melingkar dengan uritan berlainan.

P =  (n-1) !
Contoh:
Ada berapa cara 7 orang yang duduk mengelilingi meja dapat menempati ketujuh tempat duduk dengan urutan yang berlainan?
Jawab:
Banyaknya cara duduk ada (7 - 1) ! = 6 ! ® 6 . 5 . 4. 3 . 2 . 1 = 720 cara.

2. Kombinasi 
 Kombinasi adalah menggabungkan beberapa objek dari suatu grup tanpa memperhatikan urutan. Di dalam kombinasi, urutan tidak diperhatikan.
{1,2,3} adalah sama dengan {2,3,1} dan {3,1,2}.

- Contoh 1: Seorang anak hanya diperbolehkan mengambil dua buah amplop dari tiga buah amplop yang disediakan yaitu amplop A, amplop B dan amplop C. Tentukan ada berapa banyak kombinasi untuk mengambil dua buah amplop dari tiga buah amplop yang disediakan?

Solusi: Ada 3 kombinasi yaitu; A-B, A-C dan B-C.
Sedangkan permutasi adalah menggabungkan beberapa objek dari suatu grup dengan memperhatikan urutan. Di dalam permutasi, urutan diperhatikan.
{1,2,3} tidak sama dengan {2,3,1} dan {3,1,2}

-Contoh 2: Ada sebuah kotak berisi 3 bola masing-masing berwarna merah, hijau dan biru. Jika seorang anak ditugaskan untuk mengambil 2 bola secara acak dan urutan pengambilan diperhatikan, ada berapa permutasi yang terjadi?

Solusi: Ada 6 permutasi yaitu; M-H, M-B, H-M, H-B, B-M, B-H.

Permutasi pengulangan

Jika urutan diperhatikan dan suatu objek dapat dipilih lebih dari sekali maka jumlah permutasinya adalah:

di mana n adalah banyaknya objek yang dapat dipilih dan r adalah jumlah yang harus dipilih.

Sebagai contoh, jika kamu memiliki huruf A, B, C, dan D dan kamu ingin mencari tahu ada berapa cara untuk menyusunnya dalam suatu grup yang berisi tiga angka maka kamu akan menemukan bahwa ada 4³ atau 64 cara untuk menyusunnya. Beberapa cara untuk menyusunnya adalah: AAA, BBB, CCC, DDD, ABB, CBB, DBB, dst.

Permutasi tanpa pengulangan

Jika urutan diperhatikan dan setiap objek yang tersedia hanya bisa dipilih atau dipakai sekali maka jumlah permutasi yang ada adalah:

di mana n adalah jumlah objek yang dapat kamu pilih, r adalah jumlah yang harus dipilih dan ! adalah simbol faktorial.

Sebagai contoh, ada sebuah pemungutan suara dalam suatu organisasi. Kandidat yang bisa dipilih ada lima orang. Yang mendapat suara terbanyak akan diangkat menjadi ketua organisasi tersebut. Yang mendapat suara kedua terbanyak akan diangkat menjadi wakil ketua. Dan yang mendapat suara ketiga terbanyak akan menjadi sekretaris. Ada berapa banyak hasil pemungutan suara yang mungkin terjadi? Dengan menggunakan rumus di atas maka ada 5!/(5-3)! = 60 permutasi.

Umpamakan jika n = r (yang menandakan bahwa jumlah objek yang bisa dipilih sama dengan jumlah yang harus dipilih) maka rumusnya menjadi:

karena 0! = 1! = 1

Sebagai contoh, ada lima kotak kosong yang tersedia. Kelima kotak kosong itu harus diisi (tidak boleh ada yang kosong). Kelima kotak kosong itu hanya boleh diisi dengan angka 1,2,3,4,5. Ada berapa banyak cara untuk mengisi kotak kosong? Dengan menggunakan rumus n! maka ada 5! = 120 permutasi.

Kombinasi tanpa pengulangan

Ketika urutan tidak diperhatikan akan tetapi setiap objek yang ada hanya bisa dipilih sekali maka jumlah kombinasi yang ada adalah:

Di mana n adalah jumlah objek yang bisa dipilih dan r adalah jumlah yang harus dipilih.

Sebagai contoh, kamu mempunyai 5 pensil warna dengan warna yang berbeda yaitu; merah, kuning, hijau, biru dan ungu. Kamu ingin membawanya ke sekolah. Tapi kamu hanya boleh membawa dua pensil warna. Ada berapa banyak cara untuk mengkombinasikan pensil warna yang ada? Dengan menggunakan rumus di atas maka ada 5!/(5-2)!(2)! = 10 kombinasi.

Kombinasi pengulangan

Jika urutan tidak diperhatikan dan objek bisa dipilih lebih dari sekali, maka jumlah kombinasi yang ada adalah:

Di mana n adalah jumlah objek yang bisa dipilih dan r adalah jumlah yang harus dipilih. Sebagai contoh jika kamu pergi ke sebuah toko donat. Toko donut itu menyediakan 10 jenis donat berbeda. Kamu ingin membeli tiga donat. Maka kombinasi yang dihasilkan adalah (10+3-1)!/3!(10-1)! = 220 kombinasi.

3.  Distribusi Binomial

Distribusi Binomial adalah suatu distribusi probabilitas yang dapat digunakan bilamana suatu proses sampling dapat diasumsikan sesuai dengan proses Bernoulli. Misalnya, dalam perlemparan sekeping uang logam sebanyak 5 kali, hasil setiap ulangan mungkin muncul sisi gambar atau sisi angka. Begitu pula, bila kartu diambil berturut-turut, kita dapat memberi label “berhasil” bila kartu yang terambil adalah kartu merah atau “gagal” bila yang terambil adalah kartu hitam. Ulangan-ulangan tersebut bersifat bebas dan peluang keberhasilan setiap ulangan tetap sama,taitu sebasar ½..(Ronald E. Walpole).

B. Syarat Distribusi Binomial

1.      jumlah trial merupakan bilangan bulat  Contoh melambungkan coin 2 kali, tidak mungkin2 ½ kali.

2.      Setiap eksperiman mempunya idua outcome (hasil). Contoh:sukses/gagal,laki/perempuan, sehat/sakit,setuju/tidaksetuju.                                                                 

3.      Peluang sukses sama setiap eksperimen.

Contoh: Jika pada lambungan pertama peluang keluar mata H/sukses adalah ½, pada lambungan seterusnya juga ½. Jika sebuah dadu, yang diharapkan adalah keluar mata lima, maka dikatakan peluang sukses adalah 1/6, sedangkan peluang gagal adalah 5/6.Untuk itu peluang sukses dilambangkan p, sedangkan peluang gagal adalah (1-p) atau biasa juga dilambangkan q, di mana q = 1-p.

C. Ciri-ciri Distribusi Binomial.

Distribusi Binomial dapat diterapkan pada peristiwa yang memiliki ciri-ciri percobaan Binomial atau Bernoulli trial sebagai berikut :

1.      Setiap percobaan hanya mempunyai 2 kemungkinan hasil : sukses(hasil yang dikehendakai, dan gagal(hasil yang tidak dikehendaki)

2.      Setiap percobaan beersifat independen atau dengan pengembalian.

3.      Probabilita sukses setiap percobaan harus sama, dinyatakan dengan p. Sedangkan probabilita gagal dinyatakan dengan q, dan jumlah p dan q harus sama dengan satu.

4.      Jumlah percobaan, dinyatakan dengan n, harus tertentu jumlahnya.

D. Penerapan  Distribusi Binomial

Beberapa kasus dimana distribusi normal dapat diterapkan yaitu:

1.      Jumlah pertanyaan dimana anda dapat mengharapkan bahwa terkaan anda benar  dalam ujian pilihan ganda.

2.      Jumlah asuransi kecelakaan yang harus dibayar oleh perusahaan asuransi.

3.      Jumlah lemparan bebas yang dilakukan oleh pemain basket selama satu musim.

Rumus Distribusi Binomial

b(x;n,p) = nCx px qn-x dimana x = 0,1,2,3,…,n
n : banyaknya ulangan
x : banyaknya keberhasilan dalam peubah acak x
p : peluang berhasil dalam setiap ulangan
q : peluang gagal, dimana q = 1-p dalam setiap ulangan

Contoh Distribusi Binomial :

1.Berdasarkan data biro perjalanan PT Mandala Wisata air, yang khusus menangani perjalanan wisata turis manca negara, 20% dari turis menyatakan sangat puas berkunjung ke Indonesia, 40% menyatakan puas, 25% menyatakan biasa saja dan sisanya menyatakan kurang puas. Apabila kita bertemu dengan 5 orang dari peserta wisata turis manca negara yang pernah berkunjung ke Indonesia, berapakah probabilitas :

a)      Paling banyak 2 di antaranya menyatakan sangat puas.

b)      Paling sedikit 1 di antaranya menyatakan kurang puas 

c)      Tepat 2 diantaranya menyatakan biasa saja 

d)     Ada 2 sampai 4 yang menyatakan puas

Jawab :

a.X ≤ 2

Lihat tabel dan lakukan penjumlahan sebagai berikut :

b(x; n, p) = b(0; 5, 0.20) + b(1; 5, 0.20) + b(2; 5, 0.20) =
0.32768 + 0.40960 + 0.20480 = 0.94208 atau
b(x=0) = 5C0 (0.20)0 (0.80)5 = 0.32768
b(x=1) = 5C1 (0.20)0 (0.80)4 = 0.40960
b(x=2) = 5C2 (0.20)0 (0.80)3 = 0.20480
+Maka hasil x ≤ 2 adalah = 0.94208

b.X ≥ 1

Lihat tabel dan lakukan penjumlahan sebagai berikut :

b(1; 5, 0.15) + b(2; 5, 0.15) + b(3; 5, 0.15) + b(4; 5, 0.15) + b(5; 5, 0.15) =
0.3915 + 0.1382 + 0.0244 + 0.002 + 0.0001 = 0.5562 atau
b(x ≥1; 5, 0.15) = 1 – b(x = 0)
1 – 5C0 (0.15)0 (0.85)5
1 – 0.4437 = 0.5563

c.X = 2

b(2; 5, 0.25) = 0.2637

d.X ≤ 2 X ≤ 4

Lihat tabel dan lakukan penjumlahan sebagai berikut :

b(2; 5, 0.40) + b(3; 5, 0.40) + b(4; 5, 0.40) = 0.3456 + 0.2304 + 0.0768 = 0.6528
Analisis masing – masing point :

a.Sebanyak paling banyak 2 dari 5 orang dengan jumlah 0.94208 atau 94,28% yang menyatakan sangat puas adalah sangat besar.
b.Paling sedikit 1 dari 5 orang (berarti semuanya) dengan jumlah 0,5563 atau 55,63% yang menyatakan kurang puas dapat dikatakan cukup besar (karena lebih dari 50%).
c.Tepat 2 dari 5 orang yang menyatakan biasa saja dengan jumlah 0,2637 atau 26,37% adalah kecil (karena dibawah 50%).
d.Ada 2 sampai 4 yang menyatakan puas dengan jumlah 0,6528% atau 65,28% dapat dikatakan cukup besar.

Analisis keseluruhan :

A. Persentase
Jika diambil persentase terbesar tanpa memperhatikan jumlah X, maka persentase terbesar ada di point pertama (a) yaitu 94,28% yang menyatakan sangat puas. Hal tersebut menandakan banyak turis manca negara yang sangat menyukai Indonesia.

B. Nilai X
Jika dilihat dari jumlah X, maka perlu diperhatikan point kedua (b). Jumlah X adalah paling sedikit 1 dari 5 orang (berarti X>=1) yaitu 55,63% yang menyatakan kurang puas .

Hal tersebut berarti kelima (semua) turis manca negara kurang puas terhadap kunjungannya ke Indonesia.

2.Kepala bagian produksi PT SAMSUNG melaporkan bahwa rata - rata produksi televisi yang rusak setiap kali produksi adalah sebesar 15 %. Jika dari total produksi tersebut diambil secara acak sebanyak 4 buah televisi, berapakah perhitungan dengan nilai probabilitas 2 ? 

Jawab :

 p ( rusak ) = 0,15, q ( baik ) = 0,85, x = 2, n = 4
Rumus : b ( x ; n ; p ) = nCx px q n-x
b (x = 2 ; 4 ; 0,12 ) = 4C2 (0,15)2 (0,85)(4 – 2)
= 0,0975

Analisis : Dengan jumlah 0,0975 atau 9,75% dari sampel acak sebanyak 4 buah televisi dan rata – rata produk rusak setiap kali produksi adalah sebesar 15%, dapat dikatakan kecil. Namun pada kenyataannya, meskipun dilihat secara persentase kecil (hanya 9,75%) yang namanya produk rusak harus tetap dikurangi atau bahkan dihilangkan untuk mengurangi kerugian.

RATA – RATA dan RAGAM DISTRIBUSI BINOMIAL

Rata – rata μ = n . p
Ragam σ2 = n . p . q
n : ukuran populasi
p : peluang berhasil dalam setiap ulangan
q : peluang gagal, dimana q = 1-p dalam setiap ulangan

Contoh Rata – rata dan Ragam Distribusi Binomial :
Untuk b (5; 5, 20) dimana x = 5, n = 5 dan p = 0.20
q = 1-p ; q = 1-0.20 = sehingga q = 0.80
maka : m = 5 x 0.20 = 1
s2 = 5 x 0.20 x 0.8 = 0.80
s = Ö 0.80 = 0.8944.

4.  Graf

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

Suatu graph G dapat dinyatakan sebagai . Graph G terdiri atas himpunan V yang berisikan simpul pada graf tersebut dan himpunan dari E yang berisi sisi pada graf tersebut. Himpunan E dinyatakan sebagai pasangan dari simpul yang ada dalam V. Sebagai contoh definisi dari graf pada gambar di atas adalah : dan

Gambar dengan node yang sama dengan yang di atas, tapi merupakan digraf.

Pada digraf  maka pasangan-pasangan ini merupakan pasangan terurut. Untuk menyatakan digraf (gambar kedua yang menggunakan tanda panah) kita dapat menggunakan himpunan edge sebagai berikut :

Dalam himpunan edge untuk digraf, urutan pasangan verteks menentukan arah dari edge tersebut.

Definisi Graph 

         Graph G = (V, E), yang dalam hal ini:

         V  = himpunan tidak-kosong dari simpul-simpul

             (vertices)

          = { v1 , v2 , ... , vn }

         E  = himpunan sisi  (edges) yang 

            menghubungkan sepasang simpul

         = {e1 , e2 , ... , en }

 

Jenis-Jenis Graph

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

1. Graph berhingga (limited graph)
2. Graph tak-berhingga (unlimite graph)

Graph berhingga (limited graph)

Graph berhingga adalah graph yang jumlah simpulnya, n, berhingga.

Graph tak-berhingga (unlimited graph) 

Graph yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graph tak-berhingga.

Berdasarkan orientasi arah pada sisi, maka secara umum graph  dibedakan atas 2 jenis:

1. Graph tak-berarah (undirected graph) Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak-berarah. Tiga buah graph pada Gambar 2 adalah graph tak-berarah.
2.  Graph berarah (directed graph atau digraph)                                                                       Graph yang setiap sisinya diberikan orientasi arah disebut sebagai graph berarah. Dua buah graph pada Gambar 3 adalah graph berarah.

Jenis-Jenis Graph

Berdasarkan orientasi arah pada sisi, maka secara umum graph dibedakan atas 2 jenis :

1. Graph tak-berarah (undirected graph) 
2. Graph berarah (directed graph atau digraph)   

5. Tree

Pohon (tree) merupakan  salah satu bentuk khusus dari  struktur  suatu  graf.

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

 
SIFAT-SIFAT POHON

Sifat-sifat pohon dinyatakan dengan Teorema 9.1 di bawah ini .

TEOREMA 9.1 Misalkan G=(V, E) adalah graf tak-berarah sederhana dan jumlah simpulnya n.Maka ,Semua pernyataan di bawah ini adalah eqivalen :

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.

C.    POHON MERENTANG

Misalkan G = (V , E) adalah graf tak-berarah terhubung yang bukan pohon , yang berarti di G terdapat beberapa sirkuit. G dapat di ubah menjadi pohon T = ( V1,E1) dengan cara memutuskan sirkuit – sirkuit yang ada . Caranya , mula – mula  dipilih sebuah sirkuit , lalu hapus sebuah sisi dari sirkuit ini . G akan tetap terhubung dan jumlah sirkuitnya berkurang satu. Bila proses ni dilakukan berulang – ulang sampai semua sirkuit di G hilang , maka G menjadi sebuah pohon T, yang dinamakan pohon merentang (spanning tree) . di sebut pohon merentang karena semua simpul pada pohon T  sama dengan semua simpul pada graf G, dan sisi-sisi pada pohon  T  sisi-sisi pada Graf G . Dengan kata lain , V1 = V dan E1   

Aplikasi pohon merentang misalny pada pemeliharaan jalan raya.Misalakan graf G pada gambar 9.4 adalah peta jaringan jalanraya yang menghubungkan empat buah kota. Karena dana pemeliharaan yang tebatas, pemerintah daerah mempertimbangkan hanya memelihara jalan – jalan sesedikit mungkin sehingga keempat kota masih tetp terhubung satu sama lain . Masalah ini dapat dipecahkan dengan membuat upgraf yang mengandung jumlah sisi minimum dan mengandung semua simpul di dalam graf. Graf semacam ini haruslah pohon merentang.

Pohon merentang juga memainkan peranan yang penting dalam jaringan komputer . Jaringan komputer dapat dimodelkan sebagai sebuah graf . Simpul pada graf dapat menyatkan suatu simpul terminal komputer ( work station ) atau suatu router(  router adalah komputer yang difungsikan untuk meneruskan data dari suatu simpul( atau data) ke komputer lain ( melalui router) , maka komputer tersebut mengirimkannya ke seluruh simpul-simpul di jaringan . Setiap pesan yang sampai ke suatu router akan diteruskan ke satu atau lebih router lainnya . Dengan cara ini , maka pesan akan sampai ke komputer penerima.pesan yang telah sampai ke router di harapkan tidak pernah kembali diterima oleh router tersebut .  Teteapi karena router-routr pada jaringan umumnya membentuk sirkuit , maka menerima pesan yang sama lebih sekali itu sering terjadi . Untuk mengatasi Hal ini , maka algoritma jaringan membentuk pohon merentang di dalam graf sehingga antaara sepasang simpul roter yang hanya ada satu lintasan tunggal dan simpul –simpul router tidak penah menerima pesan yang sama lebih dari sekali. Metode penyebaran pesan ( routing) seperti ini dinamkan IP multicasing . Gambar 9.5 memperlihatkan contoh sebuah  jaringan komputer dan router –router yang membentk pohon merentnag

 

                                                                                         

Harus di ingat bahwa pohon merentan didefinisikan hanya untuk graf terhubung,karena pohon selalu terhubung.Pada graf tak-terhubung dengan n buah simpul kita tidak dapat menemukan upgraf terhubung dengan n buah simpul . Tipa komponen dari graf tak – terhubung dengan k komponen mempunyai hutan merentang (Spanning forest) yang terdiri dari k buah pohon merentang.

TEOREMA 9.2 Setiap graf terhubung mempunyai paling sedikit satu buah pohon merentang.

Teorema 9.2 menyatakan bahwa graf yang tidak mengandung sirkuit adalah pohon merentang itu sendiri. Pada graf yang mengandung sirkuit , pohon merentangnya diperoleh dengan cara memutuskan sirkuit yang ada.

Sisi  pada pohon merentang – disebut cabang ( branch) adalah sisi dari graf  semula , sedangkan tali – hubung ( chord atau link ) dari pohon adalah sisi dari graf yang tidak terdapat di dalam pohon merentang. Pada graf terhubung dengan m buah sisi dan n buah simpul terdapat n-1  buah cabang dan m-n+1 buah tali . Himpunan hubun beserta simpul dan m bua sisi  , kita dapat menghitung jumlah cabang dan tali hubung dengan rumus

 Jumlah cabang =  n - 1

Jumlah tali – hubung = m-n+ 1

Dan pada graf tidak terhubung dengan k  komponen  , m buah sisi dan n buah simpul

Jumlah cabang = n – k

Jumlah tali – hubung m –n+k

Jumlah cabang pada pohon merentang dari sebuah graf G disebut rank graf G , dan jumlah tali – hubung pada graf G .Dapat di lihat bahwa

   Rank + nullity = jumlah sisi Graf G

Nullity  graf sering diacu sebagai Bilangan siklomatik , atau bilangan pertama

a)      Pohon Merentang Minimum

Jika G adalah graf berbobot , maka bobot pohon merenytang T dari G  didefinisikan sebagai jumlah bobot semua sisi di T . Pohon merentang yang berbeda mempunyai bobot yang berbeda pula . Diantara semua pohon merentang di G , pohon merentang yang berbobot minimum – dinamakan Pohon merentang minimum ( minimum spanning tree ) – merupakan pohon merentang yang paling penting .Pohon merentang minimum mempunyai terapan yang luas . Misalnya pemerinta akan membuat jalur rel kereta api yang menghubungkan sebuah kota yang digambarkan oleh graf 9.6 . Membangun rel kereta api biayanya mahal , karena itu pembangunan jalur ini tidak perlu menghubungkan langsung ke kota ,  tapi cukup membangun jalur kereta api sepeerti pohon merentang . Karena itu dalam sebuah graf mungkin saja terdapat lebih dari satu pohon merentang, harus dicari pohon merentang yang mempunyai jarak terpendek , dengan kata lain harus di cari pohon merentang terpendek

 

a.       Graf  yang menyatakan jalur kereta api . Bobot pada tiap sisi menyatkan panjang rel kereta ai

b.      Pohon merentang yang mempnyai jumlah jarak minimum .

b)     Algoritma Prim

Misalkan T adalah pohon merentang yang sisi – sisinya di ambil dari graf G .

Algoritma prim membentuk pohon merentang minimum langkah perlangkah .

Pada setiap langkah kita mengabil e dri graf G yang mempunyai bobot dengan simpul –simpul di dalan T tetapi e tidak membentuk sirkuit  di dalam T  .

1.          Ambil sisi dari graf G yang berbobot minimum,  masukkan ke dalam T.

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.

3.          Ulangi langkah 2 sebanyak n – 2 kali.

c)      Algoritma Kruskal

Pada algortitma Kruskal , sisi – sisi dalam graf di urut terlebih dahulu berdasarkan bobotnya dari  kecil ke besar . Sisi yang di maksudkan ke dalam himpunan T adalah sisi  graf G sehingga T adalah pohon . Pada keadaan awal , sisi – sisi sudah di urut berdasarkan bobot  membentuk hutan ( forest) , masing – masing pohon di hutan hanya berupa satu buah simpul . Hutan tersebut dinamakan hutan merentang ( Spanning forest ) . Sisi dari graf G ditambahkan ke T jika ia tidak membentuk siklus di T.

 Asumsi : sisi –sisi dari graf sudah diurut menaik berdasarkan bobotnya

1.      T masih kosong

2.       Pilih sisi (u, v) dengan bobot minimum yang tidak membentuk  sirkuit di T. Tambahkan (u, v) ke dalam T.

3.      Ulangi langkah 2 sebanyak n – 1 kali.

                                                                      SELESAI