teori graph 2 revisi
DESCRIPTION
TeoriTRANSCRIPT
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.