Algoritma Prims dan Kruskal

Langkah langkah algoritma Prims :

1. ambil sisi dari graf G berbobot minimum , masukkan dalam T
2. pilih sisi lain dengan bobot minimum dan incident dengan simpul di T, dan tak terbentuk sirkuit
3. ulangi langkah 2 sebanyak n-2 kali

Lintasan dan sirkuit Hamilton

• Lintasan Hamilton ialah lintasan yang melalui tiap simpul didalam graf tepat satu kali

• Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul didalam graf tepat satu kali, kecuali simpul awal (juga mrpk simpul akhir) dilalui 2 kali
• Graf yang memiliki sirkuit Hamilton disebut graf Hamilton , sedangkan graf yang memiliki lintasan Hamilton disebut graf semi Hamilton

Contoh :

Graf Di samping memiliki lintasan Hamilton dengan lintasan :

b,c,d,e,f,g,a,b

dan Graf di samping juga memiliki sirkuit Hamilton karena di awali di simpul b dan berakhir di simpul b








Graf disamping memiliki lintasan Hamilton dengan lintasan :

a,b,c,d,e,i,f,g,h

Tapii graf disamping tidak memiliki sirkuit Hamilton.











Teorema Untuk Lintasan dan Sirkuit Hamilton

• Syarat cukup (bukan syarat perlu) supaya graf sederhana G dengan n buah simpul (n>=3) adalah graf Hamilton ialah jika derajad tiap simpul paling sedikit n/2
• Setiap graf lengkap adalah graf Hamilton
• Dalam graf l engkap dengan n buah simpul (n>=3) terdapat (n-1)! /2 buah sirkuit Hamilton
• Dalam graf lengkap G dengan jumlah simpul n>=3 dan n ganjil , terdapat (n-1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika n genap dan n>=4 , maka dalam G terdapat (n-2)/2 buah sirkuit Hamilton

Lintasan dan Sirkuit Euler

Lintasan dan Sirkuit Euler

• Lintasan Euler ialah lintasan yang melalui tiap sisi dalam graf tepat sekali
• Sirkuit Euler ialah sirkuit yang melalui tiap sisi dalam graf tepat satu kali
• Graf yang mempunyai sirkuit Euler disebut graf Euler, sedang graf yang mempunyai lintasan Euler disebut semi Euler

Contoh
a. Apakah Ada Lintasan Euler ?
b. Apakah ada sirkuit Euler ?

Jawab
a. ADA lintasan euler dengan lintasan :
a,b,c,d,e,f,g,b,d,f,a,g

b. Tidak ADA sirkuit Euler.








a. Apakah ada lintasan Euler ?
b. Apakah ada Sirkuit Euler ?

Jawab
a. ADA lintasan Euler dengan lintasan :
a,b,c,d,e,c,h,b,f,h,e,f,g,a
b. Ada sirkuit euler karena berawal dari simpul a dan berakhir di simpul a

Teorema Untuk Lintasan dan sirkuit euler

• Graf tak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan mempunyai 2 buah simpul berderajat ganjil atau tidak ada simpul berderajad ganjil samasekali

• Graf tak berarah G adalah graf Euler jika hanya jika setiap simpul berderajad genap

• Graf berarah G memiliki sirkuit Euler jika hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama kecuali 2 simpul, yang pertama memiliki derajad keluar satu lebih besar dari derajad masuk, dan yang kedua memiliki derajad masuk satu lebih besar dari derajad keluar

Terminologi Graf

• Ketetanggaan (adjocent) antara 2 simpul: bila kedua simpul tersebut terhubung langsung
• Contoh: G1= {{1,2},{1,3},{2,3},{2,4},{3,4}}
• Simpul 1 bertetangga dengan simpul 2 dan 3
• Simpul 1 tdk bertetangga dengan simpul 4
• Bersisian (incidency)
• Sisi e= {vj,vk}
• e bersisian dengan simpul vj dan
• e bersisian dengan simpul vk

Contoh :

• Simpul terpencil adalah simpul yang tidak mempunyai sisi yang bersisian dengannya

• Graf kosong adalah graf yang himpunan sisinya merupakan himpunan kosong

• Derajad suatu simpul pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul tersebut

Derajad (a) = 2
Derajad (b) = 2
Derajad (c) = 3
Derajad (d) = 1
Derajad (e) = 0

Jumlah Derajad = 8

Derajad pada graf tak berarah adalah GENAP atau 2x sisinya.

• Notasi : d(v)
• d(simpul terpencil)?
• d(simpul anting-anting) ?

Pada Graf Berarah

• din (v)= derajad masuk
• =jumlah sisi yang masuk kesimpul tersebut
• dout(v) = derajad keluar
• =jumlah sisi yang keluar dari simpul tersebut
• d(v)= din (v) + dout(v)

Contoh :

• Lintasan dari simpul awal v0 kesimpul tujuan vn
• Panjang lintasan adalah jumlah sisi dalam lintasan tersebut
• Sirkuit adalah lintasan yang berawal dan berakhir pada simpul yang sama
• Graf disebut terhubung jika untuk setiap 2 pasang simpul vi dan vj terdapat lntasan dari vi ke vj

Definisi Graf

Definisi Graf

• Graf G=(V,E)
• V=himpunan tdk kosong dari simpul-simpul
• E=himpunan sisi yang menghubungkan sepasang simpul

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


Graf

• Untuk menggambarkan obyek diskrit dan hubungan antar obyek
• Misal menggambarkan peta jaringan jalan raya yang menghubungkan sejumlah kota
• Untuk menyelesaikan masalah jembatan Konigsberg pada 1736
• Simpul menyatakan daratan dan sisi menyatakan jembatan
• Masalah: bisakah melalui setiap jembatan tepat sekali dan kembali lagi ketempat semula?

Jenis Graf

• Graf sederhana: graf tak berarah dengan setiap pasang simpul paling banyak 1 sisi

• Graf ganda : graf tak berarah yang mengandung sisi ganda

• Graf semu : graf tak berarah yang mengandung sisi gelang dan bisa mengandung sisi ganda

Jenis graf menurut orientasi arah

• Graf tak berarah : graf yang sisinya tidak mempunyai orientasi arah

• Graf berarah : graf yang sisinya mempunyai orientasi arah