matematika diskrit

Matematika Diskrit

6. GRAF

Kuliah 9

Dr.-Ing. Erwin Sitompulhttp://zitompul.wordpress.com

9/2Erwin Sitompul Matematika Diskrit

Pekerjaan Rumah (PR7)

Seorang ketua dan seorang bendahara dari Himpunan Mahasiswa IT, Extension Program, PU, akan dipilih dari 50 orang anggotanya. Berapa banyak cara yang mungkin untuk memilih ketua dan bendahara, apabila:(a) Tidak ada pembatasan khusus.(b) Amir hanya mau bertugas bila dipilih sebagai ketua.(c) Budi dan Cora hanya mau bertugas bersama-sama, atau

tidak sama sekali.(d) Dudi dan Encep tidak mau bekerja bersama-sama.

• Posisi ketua himpunan berbeda dengan posisi bendahara himpunan.

• Urutan penentuan posisi dalam hal ini diperhatikan.

• Permasalahan pada PR ini berhubungan dengan permutasi.


Solusi Pekerjaan Rumah (PR7)

(a) Tidak ada pembatasan khusus.

(50,2)P 50 49 2450 cara

(b) Amir hanya mau bertugas bila dipilih sebagai ketua.

(49,1) (49,2) P P 49 2352 2401 cara

Amir terpilih sebagai ketua, dengan 49 pilihan untuk mengisi posisi bendahara

Amir tidak terpilih sebagai ketua dan tidak mau bertugas, akibatnya dari 49 anggota lain akan dipilih ketua dan bendahara



(c) Budi dan Cora hanya mau bertugas bersama-sama, atau tidak sama sekali.

(2,2) (48,2)P P 2 2256 2258 cara

Budi dan Cora terpilih untuk bertugas bersama-sama, terdapat 2 cara

Keinginan Budi dan Cora tidak tercapai, dari 48 orang akan dipilih 2 orang untuk mengisi posisi yang tersedia



(d) Dudi dan Encep tidak mau bekerja bersama-sama.

(48,1) (48,1) (48,1) (48,1) (48,2)P P P P P 2248 cara

Dudi sebagai ketua, Encep tidak sebagai bendahara

Dudi dan Encep sama-sama tidak terpilih, baik sebagai ketua maupun bendahara

(50,2) 2P 2448 cara

Keseluruhan cara yang mungkin

Kejadian dimana Dudi dan Encep bekerja bersama-sama

Dudi sebagai bendahara, Encep tidak sebagai ketua

Encep sebagai ketua, Dudi tidak sebagai bendahara

Encep sebagai bendahara, Dudi tidak sebagai ketua


Definisi Graf

Graf digunakan untuk merepresentasikan obyek-obyek diskrit dan hubungan antara obyek-obyek tersebut.

Gambar di bawah ini adalah sebuah graf yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah.


Jembatan Königsberg (1736)

Bisakah orang melalui setiap jembatan tepat satu kali dan kembali lagi ke tempat semula?

Sebuah graf dapat merepresentasikan rangkaian jembatan Königsberg:

Simpul (vertex) menyatakan daratan Busur (arc) atau sisi (edge) menyatakan jembatan


Representasi Graf

Graf G = (V,E) dimana:V = Himpunan tidak-kosong dari simpul-simpul (vertices)

= { v1,v2,...,vn } E = Himpunan sisi (edges) yang menghubungkan sepasang

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


Representasi Graf

G1

G1 adalah graf denganV = { 1,2,3,4 } E = { (1,2),(1,3),(2,3),(2,4),(3,4) }

Graf sederhana


Representasi Graf

G2 Graf ganda

G2 adalah graf denganV = { 1,2,3,4 }E = { (1,2),(2,3),(1,3),(1,3),(2,4),(3,4),(3,4) }

= { e1,e2,e3,e4,e5,e6,e7 }


Representasi Graf

G3 Graf semu

G3 adalah graf denganV = { 1,2,3,4 }E = { (1,2),(2,3),(1,3),(1,3),(2,4),(3,4),(3,4),(3,3) }

= { e1,e2,e3,e4,e5,e6,e7,e8 }


Klasifikasi Graf

Berdasarkan ada tidaknya gelang (loop) atau sisi ganda (double edge) pada suatu graf, maka graf diklasifikasikan atas 2 jenis:1. Graf sederhana (simple graph), yaitu graf yang tidak mempunyai gelang maupun sisi ganda.2. Graf tak-sederhana (unsimple graph), yaitu graf mempunyai sisi ganda atau gelang.


Klasifikasi Graf

Berdasarkan orientasi arah pada sisinya, maka secara umum graf diklasifikasikan atas 2 jenis:1. Graf tak-berarah (undirected graph), yaitu graf yang sisinya tidak mempunyai orientasi arah.2. Graf berarah (directed graph atau digraph), yaitu graf yang setiap sisinya mempunyai orientasi arah.


Analisa Program

Contoh Terapan Graf

t:=0;read(x);while x <> 1945 do begin if x < 0 then writeln(‘Tahun tidak boleh negatif.’); else

t:=t+1; read(x); end;writeln(‘Tertebak sesudah’,t,’kali coba.’);

1 : t:=02 : read(x)3 : x <> 1945 4 : x < 05 : writeln(‘Tahun...’)6 : t:=t+17 : read(x)8 : writeln(‘Tertebak ...)


Teori Automata pada Mesin Penjaja(Vending Machine)

Contoh Terapan Graf

D : Dime (10 cent)Q : Quarter (25 cent)

Harga 1 botol minuman 45 cent


Terminologi Graf

1. Ketetanggaan (Adjacency) Dua buah simpul dikatakan bertetangga bila keduanya

terhubung langsung. Tinjau graf G1:

Simpul 1 bertetangga dengan simpul 2 dan 3. Simpul 1 tidak bertetangga dengan simpul 4.

G1


Terminologi Graf

2. Bersisian (Incidency) Untuk sembarang sisi e = (vj,vk) dikatakan e bersisian dengan simpul vj , dan

e bersisian dengan simpul vk . Tinjau graf G1:

Sisi (2,3) bersisian dengan simpul 2 dan simpul 3. Sisi (2,4) bersisian dengan simpul 2 dan simpul 4.Sisi (1,2) tidak bersisiandengan simpul 4.

G1


3. Simpul Terpencil (Isolated Vertex) Simpul terpencil ialah simpul yang tidak mempunyai sisi

yang bersisian dengannya. Tinjau graf G4:

Simpul 5 adalah simpul terpencil.

Terminologi Graf

G4


4. Graf Kosong (Empty Graph, Null Graph) Graf kosong adalah graf yang himpunan sisinya

merupakan himpunan kosong. Tinjau graf G5:

merupakan graf kosong.

Terminologi Graf

G5


5. Derajat Simpul (Degree of Vertex) Derajat suatu simpul adalah jumlah sisi yang bersisian

dengan simpul tersebut. Notasi: d(v). Tinjau graf G1:

d(1) = d(4) = 2.d(2) = d(3) = 3.

G1

Terminologi Graf


Tinjau graf G4:d(5) = 0 simpul terpencild(4) = 1 simpul gantung (pendant vertex)

Tinjau graf G6:d(1) = 3 bersisian dengan sisi gandad(3) = 4 bersisian dengan sisi gelang (loop)

G4 G6

Terminologi Graf


Terminologi GrafPada graf berarah:

din(v) = derajat-masuk (in-degree)= jumlah busur yang masuk ke simpul

dout(v) = derajat-keluar (out-degree)= jumlah busur yang keluar dari simpul v

d(v) = din(v) + dout(v)


Terminologi Graf

G7

Tinjau graf G7:din(1) = 2 dout(1) = 1din(2) = 2 dout(2) = 3 din(3) = 2 dout(3) = 1din(4) = 1 dout(4) = 2


Terminologi Graf

Lemma Jabat Tangan (Handshake Lemma) Jumlah derajat semua simpul pada suatu graf adalah

genap, yaitu dua kali jumlah sisi pada graf tersebut. Dengan kata lain, jika G = (V, E), maka

( ) 2v V

d v E

G1

Tinjau graf G1:d(1) + d(2) + d(3) + d(4) =

= 2 + 3 + 3 + 2= 2 jumlah sisi= 2 5


G4 G6

Tinjau graf G4:d(1) + d(2) + d(3) + d(4) + d(5)

= 2 + 2 + 3 + 1 + 0= 2 jumlah sisi= 2 4

Terminologi Graf

Tinjau graf G6:d(1) + d(2) + d(3)

= 3 + 3 + 4= 2 jumlah sisi= 2 5


Contoh:Diketahui bahwa sebuah graf memiliki lima buah simpul. Dapatkah kita menggambar graf tersebut jika derajat masing-masing simpulnya adalah:(a) 2, 3, 1, 1, 2 ?(b) 2, 3, 3, 4, 4 ?

Terminologi Graf

Solusi:(a) Tidak dapat,

karena 2 + 3 + 1 + 1 + 2 = 9 adalah ganjil.

(b) Dapat, karena 2 + 3 + 3 + 4 + 4 = 16 adalah genap.


G1

Terminologi Graf

6. Lintasan (Path) Lintasan yang panjangnya n dari simpul awal v0 ke simpul

tujuan vn di dalam graf G ialah urutan berselang-seling antara simpul dan sisi yang berbentuk v0, e1, v1, e2, v2, ..., vn

–1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ..., en = (vn–1, vn) adalah sisi-sisi dari graf G.

Panjang lintasan ditentukan oleh jumlah sisi dalam lintasan tersebut.

Tinjau graf G1: Lintasan 1, 2, 4, 3 adalah lintasan

dengan urutan sisi (1,2), (2,4), dan (4,3).Panjang lintasan 1, 2, 4, 3 adalah 3.


G1

Terminologi Graf

7. Sirkuit (Circuit) Lintasan yang berawal dan berakhir pada simpul yang

sama disebut sirkuit. Tinjau graf G1:

Lintasan 1, 2, 3, 1 adalah sebuah sirkuit.Panjang sirkuit 1, 2, 3, 1 adalah 3.


8. Keterhubungan (Connectivity) Dua buah simpul v1 dan simpul v2 disebut terhubung jika

terdapat lintasan dari v1 ke v2. Suatu graf G disebut graf terhubung (connected graph)

jika untuk setiap pasang simpul vi dan vj dalam himpunan V terdapat lintasan dari vi ke vj.

Jika tidak, maka G disebut graf tak-terhubung (disconnected graph).

Contoh graf tak-terhubung:

Terminologi Graf


Terminologi Graf Graf berarah G dikatakan terhubung jika graf tak-

berarahnya terhubung (graf tak-berarah dari G diperoleh dengan menghilangkan semua arah/kepala panah).

Dua simpul, u dan v, pada graf berarah G disebut simpul terhubung kuat (strongly connected vertex) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u.

Jika u dan v tidak terhubung kuat tetapi graf tak-berarahnya terhubung, maka u dan v dikatakan simpul terhubung lemah (weakly connected vertex).


Terminologi Graf Graf berarah G disebut graf terhubung kuat (strongly

connected graph) apabila sembarang pasangan simpul u dan v di G terhubung kuat.

Bila tidak, G disebut graf terhubung lemah.

Graf terhubung lemah Graf terhubung kuat


Terminologi Graf

9. Subgraf (Subgraph) dan Komplemen Subgraf Misalkan G = (V,E) adalah sebuah graf,

maka G1 = (V1,E1) merupakan subgraf (subgraph) dari G jika V1 V dan E1 E.

Komplemen dari subgraf G1 terhadap graf G adalah graf G2 = (V2,E2) sedemikian sehingga E2 = E – E1 dan V2 adalah himpunan simpul-simpul dengan mana anggota-anggota E2 bersisian.

G8 Sebuah subgraf

dari G8

Komplemen subgraf


Terminologi Graf

10. Subgraf Rentang (Spanning Subgraph) Subgraf G1 = (V1,E1) dari G = (V,E) dikatakan subgraf

rentang jika V1 = V, yaitu bila G1 mengandung semua simpul dari G.

G9 Subgraf rentang

dari G9

Bukan subgraf rentang dari G9


Terminologi Graf

11. Himpunan Potong (Cut Set) Himpunan potong (cut-set) dari graf terhubung G adalah

himpunan sisi yang bila dibuang dari G akan menyebabkan G tidak terhubung.

Pada graf di bawah, { (1,2),(1,5),(3,5),(3,4) } adalah cut-set.

G10 G10 tanpa cut set, menjadi graf tak terhubung


Terminologi Graf

Cut-set dari sebuah graf terhubung dapat saja berjumlah lebih dari satu.

Misalnya, himpunan { (1,2),(2,5) }, { (1,3),(1,5),(1,2) } dan { (2,6) } adalah juga cut-set dari G10.

{ (1,2),(2,5),(4,5) } bukan cut-set sebab himpunan bagiannya, { (1,2),(2,5) } adalah cut-set.

G10 G10 tanpa cut set, menjadi graf tak terhubung


Terminologi Graf

12. Graf Berbobot (Weighted Graph) Graf berbobot adalah graf yang setiap sisinya diberi

bilangan pembobot.



Graf G adalah sebuah graf seperti ditunjukkan pada gambar dibawah ini.(a) Tuliskan semua lintasan yang mungkin dari A ke C.(b) Tuliskan semua sirkuit yang ada.(c) Tuliskan minimal 4 himpunan potong (cut-set) yang ada.(d) Gambarkan subgraf G1 = { B,C,X,Y }.(e) Gambarkan komplemen dari subgraf G1.

Graf G



Perhatikan graf H dibawah ini.(a) Tuliskan paling tidak 4 lintasan dari b ke c.(b) Tuliskan paling tidak 4 sirkuit.(c) Tuliskan paling tidak 4 himpunan potong dari graf H.(d) Gambar komplemen dari subgraf H1 terhadap H.(e) Gambar satu graf rentang dari H.

Graf H

New

Graf H1

matematika diskrit

Documents