POHON (TREE)

-

Definisi
Pohon adalah graf tak-berarah terhubung
yang tidak mengandung sirkuit













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.


Pohon Merentang (spanning tree)
•  Pohon merentang dari graf terhubung adalah upagraf
merentang yang berupa pohon.
•  Pohon merentang diperoleh dengan memutus  sirkuit di dalam graf












+ Setiap graf terhubung mempunyai paling sedikit satu buah
   pohon merentang.
+ Graf tak-terhubung dengan k komponen mempunyai  k buah
   hutan merentang yang disebut hutan merentang (spanning forest).


Aplikasi Pohon Merentang
1. Jumlah ruas jalan seminimum mungkin yang
menghubungkan semua kota sehingga setiap kota tetap
terhubung satu sama lain.
2. Perutean (routing) pesan pada jaringan komputer.


   









Pohon Merentang Minimum
•  Graf terhubung-berbobot mungkin mempunyai lebih dari 1
pohon merentang.
•  Pohon merentang 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.

Contoh








































Pohon merentang minimum yang dihasilkan:

  







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

+ Pohon merentang yang dihasilkan tidak
   selalu unik meskipun bobotnya tetap sama.
+ Hal ini terjadi jika ada beberapa sisi yang
   akan dipilih berbobot sama.


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









Sisi-sisi diurut menaik



      























Komentar

Posting Komentar

Postingan populer dari blog ini

RELASI PENGURUTAN PARSIAL DAN KESETARAAN

-
Gambar
RELASI PENGURUTAN PARSIAL     Secara intuitif, di dalam relasi pengurutan parsial, istilah pengurutan berarti dua buah benda saling berhubungan jika salah satunya lebih kecil (lebih besar), daripada, atau lebih rendah (lebih tinggi) daripada lainnya menurut sifat atau kriteria tertentu. Istilah pengurutan itu sendiri memang menyatakan bahwa benda-benda di dalam himpunan tersebut diurutkan berdasarkan sifat atau criteria tersebut. Akan tetapi, ada juga kemungkinan dua buah benda di dalam himpunan tidak berhubungan dalam suatu relasi pengurutan parsial. Dalam hal demikian, kita tidak dapat mmbandingkan keduanya sehingga tidak dapat diidentifikasi mana yang lebih besar atau lebih kecil. Oleh karena itulah digunakan istilah pengurutan parsial atau pengurutan tidak-lengkap. Secara formal didefinisikan sebagai berikut. Definisi Jika R relasi pada A dan R memenuhi sifat : Reflektif, yaitu   berlaku  Antisimetri, yaitu  ,   dan   be...
Baca selengkapnya

GERBANG LOGIKA

-
Gambar
Pengertian Gerbang Logika Dasar   dan Jenis-jenisnya – Gerbang Logika atau dalam bahasa Inggris disebut dengan  Logic Gate  adalah dasar pembentuk Sistem Elektronika Digital yang berfungsi untuk mengubah satu atau beberapa Input (masukan) menjadi sebuah sinyal Output (Keluaran) Logis. Gerbang Logika beroperasi berdasarkan sistem bilangan biner yaitu bilangan yang hanya memiliki 2 kode simbol yakni  0  dan  1  dengan menggunakan Teori Aljabar Boolean. Jenis-jenis Gerbang Logika Dasar dan Simbolnya Terdapat 7 jenis Gerbang Logika Dasar yang membentuk sebuah Sistem Elektronika Digital, yaitu : Gerbang AND Gerbang OR Gerbang NOT Gerbang NAND Gerbang NOR Gerbang X-OR (Exclusive OR) Gerbang X-NOR (Exlusive NOR) Tabel yang berisikan kombinasi-kombinasi Variabel Input (Masukan) yang menghasilkan Output (Keluaran) Logis disebut dengan  “Tabel Kebenaran”  atau  “Truth Table”. Input dan Output pada Gerbang Logika hanya memi...
Baca selengkapnya

HIMPUNAN

-
Gambar
Pengertian Himpunan Himpunan adalah kumpulan benda atau objek yang dapat didefinisikan dengan jelas. Benda atau objek dalam himpunan disebut elemen atau anggota himpunan. Dari defi nisi tersebut, dapat diketahui objek yang termasuk anggota himpunan atau bukan. Contoh himpunan: • Himpunan warna lampu lalu lintas, anggota himpunannya adalah merah, kuning, dan hijau. • Himpunan bilangan prima kurang dari 10, anggota himpunannya adalah 2, 3, 5, dan 7. Contoh bukan himpunan: • Kumpulan baju-baju bagus. • Kumpulan makanan enak.   Notasi Himpunan Sebuah himpunan biasanya dinyatakan dengan simbol simbol tertentu, biasanya sebuah himpunan dinyatakan dengan menggunakan huruf besar/kapital seperti A, B, C, D, E, dst. atau bisa juga ditandai dengan adanya kurung kurawal, {…} sedangkan anggota dari himpunan tersebut biasanya ditandai dengan menggunakan huruf alfabet kecil seperti a,b,c,d,e, dst.  Untuk menyatakan sebuah himpunan, ada 4 buah cara yang bisa dilaku...
Baca selengkapnya