1

Graf12006

MATEMATIKA DISKRIT II

( 2 SKS)

Rabu, 18.50 – 20.20Ruang Hard Disk

PERTEMUAN X, XIGRAFDosen

Lie Jasa

Graf22006

GRAF

Oerip S Santoso

Matematika Diskrit

2

Graf32006

Pendahuluan

• Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut

• Representasi dari graf adalah dgn menyatakanobjek sebagai noktah, bulatan atau titik, sedangkan hubungan antar objek dinyatakan dgngaris.

• Contoh : Sebuah peta jaringan jalan raya ygmenghubungkan sejumlah kota pd sebuahpropinsi. Sesungguhnya peta tsb adalah sebuahgraf, yg dalam hal ini kota dinyatakan sebagainoktah, sedangkan jalan raya dinyatakan sbggaris.

Graf42006

Contoh

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

Brebes Tegal

Slawi

Pemalang

Purwokerto

Cilacap

Banjarnegara

Wonosobo

Kebumen

Purworejo

KendalSemarang

Pekalongan

Purbalingga

Magelang

Salatiga

Klaten

Solo

Purwodadi

DemakKudus

Rembang

Blora

Sukoharjo

Wonogiri

SragenBoyolali

Kroya

Temanggung

3

Graf52006

Sejarah Graf

• Masalah jembatan Königsberg (tahun 1736). Di kota Königsberg (sebelah timurnegara bagian Prussia, Jerman), ygsekarang bernama kota Kaliningrad, terdapat sungai Pregal yg mengalirmengintari pulau Kneiphof lalu bercabangmenjadi dua buah anak sungai. Ada 7 buah jembatan yg menghubungkandaratan yg dibelah oleh sungai tsb.

Graf62006

Masalah Jembatan Königsberg

C

A

B

D

• Graf yang merepresentasikan jembatanKönigsberg:– Simpul (vertex) à menyatakan daratan– Sisi (edge) à menyatakan jembatan

• Bisakah melalui setiap jembatan tepat sekalidan kembali lagi ke tempat semula?

4

Graf72006

Definisi Graf• Graf G = (V, E), yang dalam hal ini:

– V = himpunan tidak-kosong dari simpul-simpul(vertices) = { v1 , v2 , ... , vn }

– E = himpunan sisi (edges) yang menghubungkansepasang simpul = {e1 , e2 , ... , en }

• Definisi diatas mengatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong.

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

Graf82006

Contoh Graf1

2 3

41

2 3

4

e1

e2

e3

e4

e5

e6

e71

2

4

3

e1

e2

e3

e4

e5

e6

e7

e8

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

G2 : graf gandaG2 adalah graf dengan V = { 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}

G3 : graf semuG3 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}

(a).

(b).

(c).

5

Graf92006

Contoh• Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1,

3) dinamakan sisi-ganda (multiple edgesatau paralel edges) karena kedua sisi inimenghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3.

• Pada G3, sisi e8 = (3, 3) dinamakangelang atau kalang (loop) karena iaberawal dan berakhir pada simpul yang sama.

Graf102006

Jenis-Jenis Graf • Berdasarkan ada tidaknya gelang atau sisi

ganda pada suatu graf, maka graf digolongkanmenjadi dua jenis:1. Graf sederhana (simple graph).

Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G1 pada contohgraf sederhana

2. Graf tak-sederhana (unsimple-graph).Graf yang mengandung sisi ganda atau gelangdinamakan graf tak-sederhana (unsimple graph). G2dan G3 pada contoh adalah graf tak-sederhana

6

Graf112006

• Berdasarkan jumlah simpul pada suatugraf, maka secara umum graf dapatdigolongkan menjadi dua jenis:

1. Graf berhingga (limited graph)Graf berhingga adalah graf yang jumlahsimpulnya, n, berhingga.

2. Graf tak-berhingga (unlimited graph)Graf yang jumlah simpulnya, n, tidakberhingga banyaknya disebut graf tak-berhingga.

Jenis-Jenis Graf (cont.)

Graf122006

Jenis-jenis Graf (cont.)• Berdasarkan orientasi arah pada sisi, maka secara umum graf

dibedakan atas 2 jenis:1. Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graftak-berarah. Tiga buah graf pada contoh a,b,dan c adalah graftak-berarah.

2. Graf berarah (directed graph atau digraph)Graf yang setiap sisinya diberikan orientasi arah disebutsebagai graf berarah.

Contoh Graf berarah : 1

2 3

4

G4 :graf berarah

G5 : graf ganda berarah

1

2 3

4

7

Graf132006

Tabel Jenis-jenis Graf

Graf142006

Contoh Terapan Graf

8

Graf152006

Contoh Terapan Graf (cont.)

Graf162006

Contoh Terapan Graf (cont.)

9

Graf172006

Contoh Terapan Graf (cont.)

Graf182006

Terminologi Graf

10

Graf192006

Terminologi Graf (cont.)

Graf202006

Terminologi Graf (cont.)

11

Graf212006

Terminologi Graf (cont.)

Graf222006

Lemma Jabat Tangan• 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

• Tinjau graf G1: d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10 = 2 × jumlah sisi = 2 × 5

• Tinjau graf G2: d(1) + d(2) + d(3) = 3 + 3 + 4 = 10= 2 × jumlah sisi = 2 × 5

• Tinjau graf G3: d(1) + d(2) + d(3) + d(4) + d(5) = 2 + 2 + 3 + 1 + 0 = 8 = 2 × jumlah sisi = 2 × 4

EvdVv

2)( =∑∈

12

Graf232006

Contoh• Diketahui graf dengan lima buah simpul.

Dapatkah kita menggambar graf tersebut jika derajat masing-masing simpul adalah:

(a) 2, 3, 1, 1, 2(b) 2, 3, 3, 4, 4

Penyelesaian: a. tidak dapat, karena jumlah derajat semua

simpulnya ganjil

(2 + 3 + 1 + 1 + 2 = 9).b. dapat, karena jumlah derajat semua

simpulnya genap(2 + 3 + 3 + 4 + 4 = 16).

Graf242006

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

ke simpul tujuan vn di dalam graf G ialah barisanberselang-seling simpul-simpul dan sisi-sisiyang berbentuk v0, e1, v1, e2, v2,... , vn–1, en, vnsedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ... , en = (vn-1, vn) adalah sisi-sisi dari graf G.

• Tinjau graf G1: lintasan 1, 2, 4, 3 adalah lintasandengan barisan sisi (1,2), (2,4), (4,3).

• Panjang lintasan adalah jumlah sisi dalamlintasan tersebut. Lintasan 1, 2, 4, 3 pada G1memiliki panjang 3.

13

Graf252006

7. Siklus (Cycle) atau Sirkuit (Circuit)

• Lintasan yang berawal dan berakhir padasimpul yang sama disebut sirkuit atausiklus.

• Tinjau graf G1: 1, 2, 3, 1 adalah sebuahsirkuit.

• Panjang sirkuit adalah jumlah sisi dalamsirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G1memiliki panjang 3.

Graf262006

8. Terhubung (Connected)• Dua buah simpul v1 dan simpul v2 disebut terhubung jika

terdapat lintasan dari v1 ke v2. • G disebut graf terhubung (connected graph) jika untuk

setiap pasang simpul vi dan vj dalam himpunan V terdapatlintasan dari vi ke vj.

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

1

2

3

4

5

6

78

Contoh graf tak-terhubung:

14

Graf272006

Graf terhubung kuat dam lemah• Dua simpul, u dan v, pada graf

berarah G disebut terhubung kuat(strongly connected) jika terdapatlintasan berarah dari u ke v dan juga lintasan berarah dari v ke u.

• Jika u dan v tidak terhubung kuattetapi terhubung pada graf tidakberarahnya, maka u dan v dikatakan terhubung lemah(weakly coonected).

• Graf berarah G disebut grafterhubung kuat (stronglyconnected graph) apabila untuksetiap pasang simpul sembarang udan v di G, terhubung kuat. Kalautidak, G disebut graf terhubunglemah.

1

2

3 4

1

2 3

graf berarah terhubung lemah

graf berarah terhubung kuat

Graf282006

9. Upagraf (Subgraph) dan Komplemen Upagraf

• Misalkan G = (V, E) adalah sebuah graf. G1 = (V1, E1) adalah upagraf (subgraph) dari G jika V1 ⊆ V dan E1 ⊆ E.

• Komplemen dari upagraf G1 terhadap graf G adalah graf G2= (V2, E2) sedemikian sehingga E2 = E - E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya.

1

2

3

4 5

6

1

6

5

31

2

3

52

(a) Graf G1 (b) Sebuah upagraf (c) komplemen dari upagraf (b)

15

Graf292006

10. Upagraf Rentang (Spanning Subgraph)

• Upagraf G1 = (V1, E1) dari G = (V, E) dikatakan upagraf rentang jika V1 =V (yaitu G1 mengandung semua simpul dari G).

1

2 3

4 5

1

2 3

4 5

1

2 3

a) graf G, (b) upagraf rentang dari G, (c) bukan upagrafrentang dari G

Graf302006

11. Cut-Set

• Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-setselalu menghasilkan dua buah komponen.

• Pada graf di bawah, {(1,2), (1,5), (3,5), (3,4)} adalah cut-set. Terdapat banyak cut-set pada sebuah graf terhubung.

• Himpunan {(1,2), (2,5)} juga adalah cut-set, {(1,3), (1,5), (1,2)} adalah cut-set, {(2,6)} juga cut-set,

• tetapi {(1,2), (2,5), (4,5)} bukan cut-set sebab himpunanbagiannya, {(1,2), (2,5)} adalah cut-set.

1

2 3

4

5

6

51

2

4

3

6

(a) (b)

16

Graf312006

12. Graf Berbobot (Weighted Graph)

• Graf berbobot adalah graf yang setiap sisinyadiberi sebuah harga (bobot).

a

b

cd

e

10 12

8

15 911

14

Graf322006

Beberapa Graf Sederhana Khusus

17

Graf332006

Graf342006

Graf Bipartite

18

Graf352006

Representasi Graf

Contoh :

Graf362006

Contoh adjacency matrix

(d)

19

Graf372006

Derajat tiap simpul i

Graf382006

2. Matriks Bersisian (incidency matrix)

20

Graf392006

3. Senarai Ketetanggaan (adjacency list)

Graf402006

Graf Isomorfik (Isomorphic Graph)

21

Graf412006

Contoh

Graf422006

Contoh

22

Graf432006

contoh

Graf442006

Graf Planar (Planar Graph)• Graf yang dapat digambarkan pada

bidang datar dengan sisi-sisi tidak saling memotong disebut sebagai graf planar, jika tidak, ia disebut graf tak-planar.

23

Graf452006

Graf Bidang (Plane Graph)• Graf planar yang digambarkan dengan

sisi-sisi yang tidak saling berpotongan disebut graf bidang (plane graph).

Graf462006

Persoalan utilitas (utility problem)