langsung saja monggo,,,,,,,
TUGAS MATAKULIAH STRUKTUR
DATA
GRAPH
12.2H.30
JURUSAN MANAJEMEN INFORMATIKA
AKADEMI MANAJEMEN INFORMATIKA DAN
KOMPUTER
BINA SARANA INFORMATIKA
2015
TUGAS MATAKULIAH STRUKTUR
DATA
GRAPH
Disusun Oleh :
Darussalim (12143544)
JURUSAN MANAJEMEN INFORMATIKA
AKADEMI MANAJEMEN INFORMATIKA DAN
KOMPUTER
BINA SARANA INFORMATIKA
2015
KATA PENGANTAR
Puji syukur penyusun panjatkan ke hadirat Allah SWT, karena
dengan karuniaNya kami dapat menyelesaikan Makalah Stuktur Data “GRAPH”. Tujuan penulisan makalah ini
adalah untuk menambah pengetahuan kepada pembaca di bidang Stuktur Data
Khususnya untuk pengertian GRAPH. Penysusun juga berharap dengan adanya makalah
ini dapat membantu mempermudah pemahaman dalam materi.
Dalam melengkapi penyusunan makalah ini kami sangat
menyadari bahwa masih banyak kekurangan pada penulisan ini. Dengan segala
kerendahan hati penyusun mengharap kritik dan saran.
Tiada mahkluk yang sempurna karna kesempurnaan hanyalah
milik Allah SWT semata. Semoga makalah ini menjadi salah satu titik cahaya
terang untuk mempermudah pemahan dan menjadi salah satu referensi untuk
pembelajaran. Amin.
Pontianak,
13 juni 2015
Penyusun
DAFTAR ISI
KATA PENGANTAR……………………………………………………………..i
DAFTAR ISI………………………………………………………………………ii
BAB PENDAHULUAN…………………………………………………..…………….1
A. LATAR BELAKANG…………………………….……...…………….............1
B. MAKSUD DAN TUJUAN……………………………………………………..1
C. RUANG LINGKUP……………………………………………..……………..1
BAB II
GRAPH
A. SEJARAH ……………………………………………………..…………......2
B. PENGERTIAN………………...………………………………………..……2
C. JENIS – JENIS GRAPH……………………………………………….……
.3
D. DERAJAT GRAPH…………………………………………………….……
4
E. PENELUSURAN
GRAPH……………………………………………...……5
F. BREADTH FIRST SEARCH (BFS)…………………………………...…….6
BAB
III PENUTUP
A.
KESIMPULAN …………………………..………..…………………..……..7
B. SARAN
…………………………………………………………………….…7
DAFTAR
PUSTAKA…………………………………………………………...8
BAB I
PENDAHULUAN
A.
LATAR
BELAKANG
Topik
Teori Graph pertama kali dikemukakan pada tahun 1937 oleh seorang matematikawan
bernama Leonhard Euler. Masalah ini muncul dilatarbelakangi adanya permasalahan
yang timbul di daerah asalnya yang dikenal dengan "Tujuh Jembatan
Konigsberg". Suatu jaringan telekomunikasi strukturnya dapat di
presentasikan dengan sebuah graph, titik-titiknya dapat dengan mudah di
hubungkan secara langsung yang di tunjukan dengan vertex-vertex yang adjacent.
Semua terminal station dapat di hubungkan, tetapi hampir semua hubungan atau
sambungan di kerjakan secara tidak langsung melalui titik-titik lainnya, sehingga
grapnya akan menjadi sangat kompleks, tetapi graph tersebut merupakan graph
yang terhubung (conneted graph).
Sebuah
graph dari suatu jaringan dapat di gunakan sebagai wahana untuk mempelajari
property strukturnya, ketepatan perputaran dan algoritma kontrolnya serta
kemungkinan kemacetannya.
Pada
jaringan yang paling sederhana ada tepat satu path antara dua titik yang di
tunjuk. Dalam system telepon modern menyediakan banyak path alternative.
Pendekatan secara graph dapat digunakan untuk menghitung path alternative
tersebut, untuk menunjukan apakah jumlahnya cukup atau tidak, untuk memastikan
kualitas yang dimiliki (seperti pembebasan dari blocking), untuk menemukan
struktur baru dan untuk mempelajari algoritma penyelesaiannya. Contoh lain
untuk penggunan graph masalah dalam jaringan komunikasi, penjadualan, optimisasi,
transportasi, ilmu komputer, riset operasi, ilmu kimia, Sosiologi, Kartographi
dan lain sebagainya.
B.
MAKSUD DAN TUJUAN
Maksud penulisan makalah ini adalah
untuk:
1.
Mempermudah pembaca
dalam Memahami Pengertian Graph
2.
Berbagi sedikit ilmu yang penulis pahami
Tujuan
pembuatan makalah ini adalah:
1.
Melengkapi tugas mata kuliah STRUKTUR DATA
2.
Dapat memperdalam ilmu pembaca khususnya pengarang.
C. RUANG LINGKUP
Karena keterbasan kemampuan penulis,
maka ruang lingkup tugas makalah ini hanyalah Graph. Hal tersebut dimaksudkan
agar terfokus materi yang dibahas, sehingga pembaca lebih mudah mempelajarinya.
BAB II
GRAPH
A.
SEJARAH
Sejarah Lahirnya Teori Graf Teori graph merupakan sebuah pokok
bahasan yang muncul pertama kali pada tahun 1736, yakni ketika Leonhard Euler
mencoba untuk mencari solusi dari permasalahan yang sangat terkenal yaitu 7
Jembatan Konigsberg. Di kota Konigsberg (sebelah timur Prussia, Jerman
sekarang).
B.
PENGERTIAN
Graph
adalah kumpulan dari titik ( node ) dan garis dimana pasangan-pasangan titik (
node ) tersebut dihubungkan oleh segmen garis. Suatu Graph mengandung 2
himpunan, yaitu :
1.
Himpunan V yang
elemennya disebut simpul (Vertex atau Point atau Node atau Titik)
2.
Himpunan E yang
merupakan pasangan tak urut dari simpul. Anggotanya disebut Ruas (Edge atau
rusuk atau sisi)
Graph seperti dimaksud diatas, ditulis sebagai
G(E,V).
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc
Simpul dan ruas
dalam graph dapat diperluas dengan penambahan informasi. Sebagai contoh, simpul
ias diberi nomor atau label dan ruas dapat diberi
nilai juga. Perluasan dengan pemberian informasi ini sangat berguna dalam
penggunaan graph.
V
(Titik) = X, Y dan Z
E
(Ruas) = O1, O2 dan O3
C.
JENIS
– JENIS GRAPH
Berdasarkan ada tidaknya gelang
atau sisi ganda pada suatu graf maka graph digolongkan menjadi dua jenis:
1. Graph sederhana (simple graph)
Graph
yang tidak mengandung gelang maupun sisi ganda dinamakan graph sederhana.
2. Graph tak-sederhana (unsimple graph)
Graf
yang mengandung sisi ganda atau gelang dinamakan graf tak sederhana (unsimple
graph). Ada dua macam Graph tak sederhana, yaitu Graph ganda (multigraph)
atau Graph semu (pseudograph). Graph ganda adalah Graph yang
mengandung sisi ganda. Graph semu adalah
Graph yang mengandung gelang (Self-Loop).
Graph juga
dibagi menjadi:
1.
Graph tidak berlabel
Graph tidak berlabel adal Graph yang tidak memiliki infor
masi.
2.
Graph berlabel
Graph berlabel ini
dibagi menjadi dua kategori yaitu:
a.
Graph berlabel ajaib
Graph berlabel ajaib adalah graph yang memiliki weight (W)
atau berat yang sama. Contoh:
W1 = 1 + 3 + 5 = 9
W2 = 3 + 4 + 2 =
9
Bobot W1 dan W2 adalah sama, yaitu
sama-sama 9. Maka graph ini disebut graph ajaib.
b.
Graph
berlabel anti ajaib
Graph anti ajaib adalah graph yang
memiliki weigh (W) yang berbeda-beda, namun dengan selisih yang sama.
Contohnya:
W1
= 1 + 10 + 3 = 14
W2
= 3 + 8 + 5 = 16
W3
= 5 + 6 + 7 = 18
W4
= 7 + 4 + 9 = 20
W5
= 9 + 2 + 11 = 22
W6
= 11 + 12 + 1 = 24
W1,
W2, W3, W4, W5, W6 memiliki selisih yang sama yaitu dua.
DERAJAT GRAPH
Derajat simpul V, ditulis d(v) adalah banyaknya ruas yang menghubungi v. Karena setiap ruas dihitung dua kali ketika menentukan derajat suatu Graph, maka : Jumlah derajat semua simpul suatu Graph (derajat) = dua kali banyaknya ruas Graph (Size) Atau dapat dituliskan :
Derajat simpul V, ditulis d(v) adalah banyaknya ruas yang menghubungi v. Karena setiap ruas dihitung dua kali ketika menentukan derajat suatu Graph, maka : Jumlah derajat semua simpul suatu Graph (derajat) = dua kali banyaknya ruas Graph (Size) Atau dapat dituliskan :
Derajat Graph = 2 x Size
Jika Derajat masing-masing simpul pada Graph
berjumlah
Genap maka Graph tersebut disebut EULER Graph
Pada gambar diSAMPING, banyak ruas/size = 5,
sedangkan
 |
derajat
masing-masing simpul adalah :
d(A) = 3
d(B) = 1
d(C) = 0
d(D) = 4
d(E) = 2
maka, total jumlah derajat simpul adalah : 10
B disebut simpul bergantung/akhir, yaitu simpul yang
berderajat satu. Sedangkan C disebut simpul terpencil, yaitu simpul yang
berderajat Nol.
Berdasarkan orientasi arah pada
sisi, maka secara umum Graph dibedakan atas 2 jenis :
1.
Graph tak-berarah (undirected graph)
Graph
yang sisinya tidak mempunyai orientasi arah disebut tak-berarah.
Graph tak terarah adalah Graph yang menghubungkan 2 verteks V1 ke
V2 dan V2 ke V1 (2arah). Bila verteks = n, maka Graph tak terarah komplit akan
mempunyai busur edge sama dengan : n ( n - 1 ) / 2 Pada Graph tak-berarah, urutan
pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, (u, v) =
(v, u) adalah sisi yang sama
2.
Graph berarah (directed graph atau
digraph)
Graph terarah adalah Graph yang dapat
menghubungkan V1 ke V2 saja (1 arah).
Maksimum jumlah busur dari n simpul adalah : n ( n - 1 )
Suatu Graph Berarah (Directed Graph) D terdiri atas 2 himpunan :
1) Himpunan V, anggotanya disebut simpul.
2) Himpunan A, merupakan himpunan pasangan terurut, yang disebut ruas berarah atau arkus.
Maksimum jumlah busur dari n simpul adalah : n ( n - 1 )
Suatu Graph Berarah (Directed Graph) D terdiri atas 2 himpunan :
1) Himpunan V, anggotanya disebut simpul.
2) Himpunan A, merupakan himpunan pasangan terurut, yang disebut ruas berarah atau arkus.
Contoh, Gambar dibawah ini adalah sebuah Graph Berarah D(V,A)
dengan :
1. V mengandung 7 simpul, yaitu
A,B,C,D,E,F dan G
2. A
mengandung 12 arkus, yaitu (A,B) ,(A,C), (B,D), (B,C), (B,E), (D,E), (D,F),
(D,G),(E,G) dan (F,G)
PENELUSURAN GRAPH
Dapat dilakukan dengan 2 cara, yaitu :
1. Depth First Search (DFS)
penelusuran dengan DFS pada Graph tak berarah dengan melakukan pengecekan pada Node dengan kedalaman pertama dari Node yang di tinjau.
bisa
dilihat contoh di bawah ini :
Hasil
Penelusuran dengan DFS :
A
B E G F C
H D
Penelusuran
DFS pada Graph G1, penjelasannya adalah sebagai berikut :
Pertama
Kali, penelusuran dimulai dengan vertex dengan abjad paling rendah (A),
kemudian penelusuran dilanjutkan dengan mencari anak cabang (adjacent) terdekat
dari A, dan lanjutkan penelusuran ke vertex dengan abjad yang lebih
rendah, yakni B. Ketika berada di B, terdapat dua cabang, pilih
vertex yang lebih rendah yakni E dan dilanjutkan ke vertex G.
Sekarang penelusuran sudah berada di G, namun anak cabang dari G
kembali lagi ke A yang sudah pernah di telusuri. Maka, penelusuran akan
kembali ke anak cabang level sebelumnya untuk mencari anak cabang lain. Dalam
konteks diatas, dari G akan kembali ke E, karena tidak ada lagi
adjacent maka akan kembali ke B. Dari B akan di lanjutkan ke C
lalu dilanjutkan ke H, kembali ke C dan kembali ke F lalu
dilanjutkan ke D. Vertex D merupakan penelusuran terakhir dari
Algoritma ini, karena semua vertex sudah dikunjungi.
Tampilan
DFS setelah dikunjungi
Jika diurutkan menurut kunjungan vertex, maka tampilan
diagram seperti dibawah ini :
tampilannya
diilustrasikan seperti pohon yang terbalik (A merupakan akar sedangkan D
merupakan akhir dari pohon).
2. Breadth First Search (BFS)
Breadth-first search adalah
algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul
secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi
semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu.
Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul
yang tadi dikunjungi , demikian seterusnya. Berbeda
dengan cara BFS, dengan BFS penelusuran akan diawasi dari Node-1, kemudian
melebar pada Adjacent Node dari Node-1 dan diteruskan pada Node-2, Node- 3 dan
seterusnya.
Breadth-first
search (BFS) melakukan proses searching pada
semua node yang berada pada level yang sama terlebih dahulu sebelum melanjutkan
proses searching pada node di level berikutnya.
BAB III
PENUTUP
A.
KESIMPULAN
Graph
muncul pada tahun 1937 di Jerman. Munculnya teori Graph dikarenakan suatu
masalah. Yang terkenal dengan masalah "Tujuh Jembatan Konigsberg".
Untuk kehidupan sehari hari teori ini sangat berguna karena sangat bermanfaat
contohnya dalam ,
transportasi, ilmu komputer, riset operasi, ilmu kimia, Sosiologi dan lain
sebagainya. Jika menyimak uraian tentang Graph diatas dapat kita simpulkan
Graph adalah kumpulan titik dan garis. Namun dari dua kata itu mempunyai arti
yang sangat berguna bagi kehidupan kita. Sebagai manusia secara tidak langsung
kita bias menggunakan Graph contohnya dalam menggambar rute tercepat dalam
sebuah peta.
B.
SARAN
Dalam
makalah singkat ini penulis ingin menyarankan kepada rekan mahasiswa hendaknya
kita membuat tugas yang dibebankan oleh dosen pengasuh kita yang berupa
makalah, kita membuat sendiri agar kedepannya kita menjadi mahasiswa yang
benar-benar siap pakai di kalangan masyarakat maupun dunian kerja.
DAFTAR PUSTAKA
:catatan jika gambarnya gak muncul searching aja di google banyak. :D :D
