teori graph 2 revisi

18
MAKALAH TEORI GRAPH GRAPH BIPARTISI, GRAPH BIPARTISI KOMPLIT, DERAJAT TITIK PADA GRAPH, GRAPH BERATURAN, DAN TEORI JABAT TANGAN Dosen Pembimbing: Ririn Febriyanti, S.Pd, M.Pd Kelompok 10 : Oleh: Kelompok 2 1. Usfi Muchayana (1151055) 2. Imam Santoso (1151099) 3. Achmad Utsman Y. Z (1151104) PROGRAM STUDI MATEMATIKA 2011-D

Upload: phiepie-uzzuphie

Post on 27-Dec-2015

100 views

Category:

Documents


9 download

DESCRIPTION

Teori

TRANSCRIPT

MAKALAH

TEORI GRAPH

GRAPH BIPARTISI, GRAPH BIPARTISI KOMPLIT, DERAJAT

TITIK PADA GRAPH, GRAPH BERATURAN,

DAN TEORI JABAT TANGAN

Dosen Pembimbing:

Ririn Febriyanti, S.Pd, M.Pd

Kelompok 10:

Oleh:

Kelompok 2

1. Usfi Muchayana (1151055)

2. Imam Santoso (1151099)

3. Achmad Utsman Y. Z (1151104)

PROGRAM STUDI MATEMATIKA 2011-D

SEKOLAH TINGGI KEGURUAN DAN ILMU PENDIDIKAN

PERSATUAN GURU REPUBLIK INDONESIA

JOMBANG

2014

KATA PENGANTAR

Dengan mengucap syukur kehadirat Allah SWT yang telah memberi berkat dan

rahmatnya. Sholawat serta salam tetap tercurah kepada nabi besar Muhammmad SAW.

Atas bantuan dan pertolongan-Nya maka penulis berhasil menyelesaikan tugas makalah

yang berjudul:

“GRAPH BIPARTISI, GRAPH BIPARTISI KOMPLIT, DERAJAT

TITIK PADA GRAPH, GRAPH BERATURAN,

DAN TEORI JABAT TANGAN”

Pada kesempatan ini penulis ingin mengucapkan terima kasih yang sebesar-

besarnya kepada :

1. Tuhan YME serta Nabi Muhammad SAW.

2. Ririn Febriyanti, S.Pd, M.Pd, selaku pembimbing tugas makalah. Dan terima

kasih untuk motivasi dan ilmu yang tiada ternilai harganya.

Penulis menyadari bahwa tugas akhir ini tidaklah sempurna, dan berharap ini

dapat memberikan kontribusi yang berarti dan dapat menambah wawasan bagi

pembaca dan mahasiswa yang nanti dapat digunakan sebagai referensi pengerjaan

tugas akhir baru.

Jombang, 30 Maret 2013

Penulis

PEMBAHASAN

A. Graph Bipartisi

Graph bipartisi (bipartite graph) adalah graph yang himpunan titiknya

dapat dipisahkan menjadi dua himpunan tak kosong X dan Y sehingga masing-

masing sisi di graph tersebut menghubungkan satu titik di X dan satu titik di Y,

X dan Y disebut himpunan partisi.

Dalam graf bipartisi, setiap simpul X tidak harus adjacent

(berdampingan) ke semua simpul dalam Y.

Contoh 1

a. Gambar berikut merupakan graph sederhana yang akan dibentuk menjadi

graph bipartisi

Langkah-langkah untuk menentukan apakah graph sederhana tersebut

merupakan graph bipartisi adalah:

1. Tentukan satu titik sebagai anggota himpunan pertama, dimisalkan titik

X

2. Selanjutnya setiap titik yang berhubungan dengan titik X diberikan nama

titik Y dan sebaliknya, yang nanti akan menjadi anggota himpunan kedua

Jadi graph sederhana di atas merupakan graph bipartisi karena sisi digraph

tersebut yang menghubungkan satu titik X dan titik Y.

b. Dari graph sederhana di atas dapat dibentuk menjadi himpunan partisi seperti

gambar berikut

atau

Contoh 2

Dimisalkan G (V, E) dengan V (G )={a , b , c , d , e } dan

E(G )={e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8 , e9 , e10 , e11 ,e12 }

Ambil satu titik misalkan titik 1 dan beri nama baju (B) dan setiap titik yang

dihubungkan dengan titik 1 diberi nama celana (C) dan sebaliknya.

Karena graph sederhana tersebut dapat dipartisi menjadi dua himpunan tak

kosong yaitu B= {1,3,5,6 } dan C={2,4,7 } dengan setiap sisi dari G

menghubungkan sebuah titik di B dan sebuah titik di C maka G adalah Graph

Bipartisi

Dalam bentuk

Contoh 3

Gambar di atas merupakan graph sederhana tetapi bukan graph bipartisi

karena terdapat sisi yang menghubungkan satu titik dengan satu titik lain dalam

satu himpunan yaitu sisi yang menghubungkan x1 dan x4.

Untuk memudahkan, kita dapat membedakan titik di X dan titik di Y dengan

menggambar satu himpunan dengan titik berwarna hitam dan satu himpunan

titik berwarna putih.

Contoh 4:

Graph (B, C) – contoh 2

B. Graph Bipartisi Komplit

Graph bipartisi komplit (complete bipartite graph) adalah graph

sederhana dan bipartisi dengan partisi (X, Y) sedemikian hingga setiap titik di X

berhubungan langsung dengan setiap titik di Y. Graph bipartisi komplit

dilambangkan dengan Km,n dimana banyaknya titik pada himpunan X = m atau |

X| = m dan banyaknya titik pada himpunan Y = n atau |Y| = n.

Banyaknya titik pada graph bipartisi komplit (Km,n) adalah m + n

sedangkan banyaknya sisi adalah m ∙ n.

Contoh

Untuk gambar K5,1:

m = 5 dan n = 1 maka jumlah titik pada graph tersebut adalah m + n = 5 + 1 = 6

dan jumlah sisinya adalah m ∙ n = 5 ∙ 1 = 5.

C. Derajat Titik Pada Graph

Derajat suatu titik v pada sebuah grap G, ditulis dengan deg(v) atau d(v),

adalah jumlah sisi yang terkait di titik v (dengn catatan setiap gulungan atau loop

dihitung dua kali). Dengan kata lain, Derajat Titik adalah banyaknya sisi yang

bertemu pada satu titik.

a. Derajat minimum G (δG)Didefinisikan sebagai δG=minimum {d (v)|v∈V (G)}

b. Derajat maksimum G (∆G)

Didefinisikan sebagai ∆ G=maksimum {d (v )|v∈V (G)}Contoh 1

Misalkan graph tersebut adalah H(V, E) dengan

- V ( H )={a , b , c , d , e }

- E( H )={e1 , e2 , e3 , e4 , e5}

= {(a ,b ) , (a , c ) , (b ,d ) , (c ,d ) , (d , e ) }

Maka derajat titik pada graph H adalah

d (a )=2 , d (b )=2 , d (c )=2 , d( d )=3 , d (e )=1

Dengan δH=1dan ΔH=3

Contoh 2

Misalkan Graph N dengan V ( N )={ p ,q , r , s , t , u , v } dan

E( N )={e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8 , e9 , e10 , e11 , e12 , e13 }

Maka derajat titik pada graph tersebut adalah

d ( p )=3 , d (q )=3 , d (r )=3 , d (s )=3 , d( t )=3 , d (u)=4 , d ( v )=7 dengan

δN=3 dan ΔN=7

Contoh 3

Misalkan Graph G dengan

- V (G )={u1 ,u2 ,u3 ,u4 ,u5 ,u6 , u7 , u8 }

- E(G )={e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8 , e9 , e10 , e11 ,e12 ,e13 , e14 , e15 , e16 }

={ (u1 , u2) , (u1 ,u2) , (u1 ,u1 ) , (u1 , u3 ) , (u1 , u4 ) , (u2 , u3 ) , (u2 , u4) , (u3 , u5) ,(u3 , u5) , (u3 ,u6) , (u4 ,u6) , (u5 ,u5) , (u5 ,u7) , (u6 , u7) , (u6 , u8 ) , (u7 , u8 ) }

Maka derajat titik pada graph tersebut adalah

d (u 1 )=6 , d (u 2 )=4 , d (u 3 )=5 ,d (u 4 )=3 ,d (u 5 )=5 , d (u 6 )=4 , d (u 7 )=3 , d (u 8 )=2

dengan δG=2 dan ΔG=6

D. Graph Beraturan ( Regular Graph )

Suatu graph G dikatakan beraturan jika semua titiknya memiliki derajat

yang sama. Jika derajat titik adalah r, maka G dikatakan beraturan dengan

derajat r.

Contoh 1

V (G )={v1 , v2 , v3 }d (v1)=2

d (v2)=2

d (v3)=2

Gambar Graph Beraturan 2

Contoh 2

V (G )={1,2,3,4 }d (1 )=3d (2 )=3d (3 )=3d (4 )=3

Gambar Graph G beraturan 3

E. Teorema Jabat Tangan ( Hand Shaking Teorm )

Contoh:

Bila diamati bahwa graph di atas merupakan graph beraturan dengan

derajat 4 dan memiliki 5 titik, sehingga jumlah derajat titiknya 20. Juga diamati

bahwa graph ini memiliki 10 sisi. Dengan kata lain, jumlah derajat titik itu tepat

dua kali banyak sisinya.

Hasil yang sesuai berlaku untuk semua graph, dan disebut lemma jabat tangan.

Atau dinyatakan bahwa untuk sebarang graph G berlaku

∑v∈V (G )

d (v )=2|E(G )|

Lemma Jabat Tangan

Pada sebarang graph, jumlah dari semua derajat titik-titiknya sama dengan dua kali jumlah sisi-sisinya.

Dimana d(v) adalah derajat titik pada suatu graph dan |E (G )|adalah jumlah sisi

pada graph tersebut.

Pembuktian

Karena setiap sisi memiliki dua ujung, maka kedua ujung itu

menyumbang 2 derajat. Sehingga jumlah derajat titiknya dua kali banyak

sisinya.

Pembuktian lain

Perhatikan sebarang graph berikut

Gambar 1

Diketahui graph G dengan

V (G )={a , b , c }E(G )={e1 , e2}

Dari graph sederhana di atas telah terlihat bahwa

e1 dihitung satu kali dari titik A ke B (1 derajat)

e1 dihutung satu kali dari titik B ke A (1 derajat)

e2 dihitung satu kali dari titik A ke C (1 derajat)

e2 dihutung satu kali dari titik C ke A (1 derajat) +

2 e1+2 e2=4

2 (e1+e2)=4

2|E (G )|=42|E (G )|= ∑

v∈V ( G )d (v )

Jadi, Jumlah derajat titik pada graph tersebut adalah 4 dengan 2 sisi dimana

setiap sisi dihitung dua kali sehingga ∑ d (v )=2|2|=4

Gambar 2

Dari graph sederhana di atas telah terlihat bahwa

e1 dihitung satu kali dari titik u1 ke u2 (1 derajat)

e1 dihutung satu kali dari titik u2 ke u1 (1 derajat)

e2 dihitung satu kali dari titik u1 ke u3 (1 derajat)

e2 dihutung satu kali dari titik u3 ke u1 (1 derajat)

e3 dihitung dua kali dari titik u3 ke u3 (2 derajat) +2 e1+2 e2+2 e3=6

2 (e1+e2+e3 )=6

2|E (G )|=62|E (G )|= ∑

v∈V ( G )d (v )

Catatan: setiap loop (gelung) dihitung dua kali.

Jadi, Jumlah derajat titik pada graph tersebut adalah 6 dengan 3 sisi dimana

setiap sisi dihitung dua kali, sehingga ∑ d (v )=2|3|=6

Jadi, terbukti bahwa jumlah derajat titik pada graph sama dengan dua kali

jumlah sisi pada graph tersebut.

LATIHAN SOAL

1. Tunjukkan dari keempat graph di bawah ini, manakah yang merupakan graph

bipartisi, sertakan pula alasannya!

2. Diketahui sebuah Graph Z dimana V ( Z )= {a ,b , c , d , e , f , g , h ,i } . Tentukan derajat

titik pada Graaph Z tersebut dan tentukan pula derajat maksimum dan minimumnya!

3. Buatlah sebuah graph beraturan dengan ketentuan sebagai berikut:

a. Graph beraturan 11

b. Graph beraturan 15 dengan 11 vertex.

4. Dari soal no. 3 buktikan bahwa graph tersebut memenuhi Lemma Jabat Tangan!

5. Gambarkan Graph Bipartisi Komplit K9,5!

DAFTAR PUSTAKA

Anis, Khoiriyah. Teri Graph, http://www.slideshare.net/anis_khoriyah/teori-graph,

diakses pada tanggal 30 Maret 2014, 07.01 WIB.

Nofyta, Arlianti. 2010. Makalah Graph Tentang Derajat Titik,

http://nofytaarlianti.wordpress.com/2010/12/17/makalah-graph-derajat-titik/,

diakses pada tanggal 29 Maret 2014, 14.53 WIB.

Rinaldi, Munir. Teori Graph, http://www.slideshare.net/esa_esa/teori-graph-rinaldi-

munir, diakses pada tanggal 29 Maret 2014, 07.10 WIB

http://math5graph.blogspot.com/2012/10/pengertian-graph.html, diakses pada tanggal

30 Maret 2014, 14.21 WIB.

http://chasmair.blogspot.com/2010/03/konsep-konsep-dasar-teori-graph.html, diakses

pada tanggal 30 Maret 2014, 07. 13 WIB.