GRAPH STRUKTUR DATA

TUGAS MATAKULIAH STRUKTUR DATA

GRAPH

Kelas: 11.2A.07

Nama Anggota Kelompok:

Deoardo Putra

Muhammad Ibrahim

Kristi Indriani Saragih

Zubaidah Tanjung

JURUSAN SISTEM INFORMASI

STMIK NUSA MANDIRI

WARUNG JATI

2017

TUGAS MATAKULIAH STRUKTUR DATA

GRAPH

KATA PENGANTAR

Puji syukur kami 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. Kami 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.

DAFTAR ISI

KATA PENGANTAR……………………………………………………………..

DAFTAR ISI………………………………………………………………………

BAB PENDAHULUAN…………………………………………………..……

A. LATAR BELAKANG…………………………….……...…………….............

B. MAKSUD DAN TUJUAN……………………………………………………..

C. RUANG LINGKUP……………………………………………..……………..

BAB II GRAPH

A.    SEJARAH ……………………………………………………..…………......

B.     PENGERTIAN………………...………………………………………..……

C.     JENIS – JENIS GRAPH……………………………………………….…… .

D.    DERAJAT GRAPH…………………………………………………….……

E.     PENELUSURAN GRAPH……………………………………………...……

F.      BREADTH FIRST SEARCH (BFS)…………………………………...…….

G.  CONTOH PROGRAM.....................................................................................

BAB III  PENUTUP

          A. KESIMPULAN …………………………..………..…………………..……..

B. SARAN …………………………………………………………………….

C. VIDEO TENTANG GRAPH..................................................................

DAFTAR PUSTAKA…………………………………………………………...

                                                

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 kami, maka ruang lingkup tugas makalah ini hanyalah Graph. Hal tersebut dimaksudkan agar terfokus materi yang dibahas, sehingga pembaca lebih mudah mempelajarinya.

BAB II

GRAPH

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).

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

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

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 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.

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 Dmerupakan 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.

G. CONTOH PROGRAM

Ini Merupakan Program C++, yang dibuat untuk mengetahui sebuah graph terhubung atau tidak!
Berikut Source Codenya:

#include <iostream.h>
#include <conio.h>

int main(){
bool ketemu,nolsemua;
int matrix[10] [10];
int i,j,jumlah_simpul,jumlah_sisi,asal,tujuan;
//isnisialisasi matrix
cout<<"jumlah simpul:";
cin>>jumlah_simpul;
cout<<"jumlah_sisi:";
cin>>jumlah_sisi;
for (i=1;i<=jumlah_simpul;i++)
for (j=1;j<=jumlah_simpul;j++)
matrix[i][j]=0;
//isi matrix sesuai input graf
for (i=1;i<=jumlah_sisi;i++){
cout<<"simpul asal:";
cin>>asal;
cout<<"simpul tujuan:";
cin>>tujuan;
matrix[asal][tujuan]=1;
matrix[tujuan][asal]=1;
}
//telusuri graf
i=1;nolsemua=false;
while (i<=jumlah_simpul && !nolsemua){
j=1;ketemu=false;
while (j<=jumlah_simpul && !ketemu){
if (matrix[i][j]==1)
ketemu=true;
else
j++;
}
if (!ketemu)
nolsemua=true;
else
i++;
}

if(nolsemua)
cout<<"graf tidak terhubung";
else
cout<<"graf terhubung";
getch();

}

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 kami ingin menyarankan kepada rekan mahasiswa hendaknya kita membuat tugas yang dibebankan oleh dosen kita yang berupa makalah, kita membuat sendiri agar kedepannya kita menjadi mahasiswa yang benar-benar siap pakai di kalangan masyarakat maupun dunian kerja.

C. VIDEO TENTANG GRAPH

DAFTAR PUSTAKA

https://mpieslach.wordpress.com/2014/03/02/sejarah-teori-graf/

http://www.kampungtapsiun.com/2014/09/breadth-first-search-bfs.html

http://slideplayer.info/slide/3148733/

https://www.academia.edu/6108700/Terminologi_Graf_dan_Beberapa_Graf_Sederhana_Khusus

http://windahera.blogspot.com/2010/06/matriks-penyajian-graph.html

http://siprianusaralta.blogspot.com/2012/05/depth-first-search-dfs.html

http://lukmanreza.blogspot.com/2011/06/program-c-graph.html