際際滷

際際滷Share a Scribd company logo

Pengertian dan Representasi Graph

Zaldy Eka Putra
Zaldy Eka Putra

Makalah Graph

1 of 14
Downloaded 698 times
1 BAB I PENDAHULUAN 1.1 Latar Belakang Graf merupakan salah satu dari beberapa struktur data yang paling sering diaplikasikan, dalam pemrograman komputer. Jika kita memutuskan untuk menggunakan penyimpanan data yang bersifat external, kita mungkin tidak terlalu membutuhkn graf, tetapi untuk beberapa permasalahan dimana kita memerlukan referesentasi internal dalam memori komputer untuk suatu struktur data, graf tidak bisa dihindari penggunaannya. Secara konseptual, graf merupakan suatu struktur data yang agak berbeda dengan pohon (tree). Dalam pernyataannya, pohon merupakan salah satu jenis graf; pohon merupakan kasus khusus dari graf. Dalam pemrograman komputer untuk berbagai terapan, graf sering digunakan dalam berbagai cara yang relatif lebih bermanfaat dibandingkan pohon(tree). Struktur-struktur data memiliki algoritma yang terkait pada struktur data yang bersangkutan. Sebagai contoh, pohon biner dibentuk dengan cara seperti itu karena bentuknya memudahkan pemrogram untuk melakukan pencarian data dan melakukan penyisipan data. Simpul-simpul (vertex) dalam pohon biner merepresentasikan cara yang efektif untuk melakukan penelusuran terhadapnya. Dalam hal ini, graf memiliki bentuk yang ditentukan oleh permasalahn nyata. Sebagai contoh, simpul-simpul dalam graf mungkin merepresentasikan kota-kota yang menggambarkan lintasan penerbangan antarkota/antarnegara, atau jalur-jalur elektronika pada sebuah IC (Integrated Circuit). Graf adalah salah satu jenis struktur data yang terdiri dari titik (vertex) dan garis (edge), dimana dalam graf tersebut, vertex - vertex yang ada dihubungkan oleh edge, hingga menjadi suatu kesatuan yang disebut graf. Sebagai contoh dari pemodelan graf adalah peta kota kota, dimana kota disini sebagai vertex dan jalur yang menghubungkannya berlaku sebagai edge. Ada terdapat beberapa jenis graf yang bisa kita gunakan, yaitu beberapa diantaranya adalah sebagai berikut : Graf Berarah : adalah graf yang edge-nya memiliki arah, sebagai contoh edge AB menghubungkan vertex A ke B, dimana hubungan vertex B ke A, harus diperoleh
2 dari edge lain, yaitu edge BA, dan jika edge BA tidak ada, maka vertex B ke A tidak memiliki hubungan, meski vertex A ke B memiliki hubungan Graf Tak Berarah : adalah graf yang edge-nya tidak memiliki arah, sehingga jika edge AB menghubungkan vertex A ke B, maka secara otomatis juga menghubungkan vertex B ke A. Graf Berbobot : adalah suatu graf dimana edge dari graf tersebut memiliki bobot atau nilai tertentu. Graf Tidak Berbobot : adalah suatu graf dimana edge dari graf tersebut tidak memiliki bobot atau nilai. Untuk merepresentasikannya dalam pemrograman komputer, graf dapat disusun dari LinkedList yang berada dalam LinkedList 1.2 Rumusan Masalah 1. Apa Definisi Graph? 2. Apa saja istilah-istilah dalam graph? 3. Bagaimana representasi graph dalam struktur data? 1.3 Tujuan 1. Untuk Mengetahui definisi graph 2. Untuk mengetahui istilah-istilah dalam graph 3. Untuk megetahui bagaimana bentuk representasi graph dalam struktur data
3 BAB II PEMBAHASAN A. Definisi Graph Suatu graph didefinisikan oleh himpunan verteks dan himpunan sisi (edge). Verteks menyatakan entitas-entitas data dan sisi menyatakan keterhubungan antara verteks. Biasanya untuk suatu graph G digunakan notasi matematis. G = (V , E) Dimana : G = Graph V = Simpul atau Vertex, atau Node, atau Titik E = Busur atau Edge, atau arc V adalah himpunan verteks dan E himpunan sisi yang terdefinisi antara pasangan- pasangan verteks. Sebuah sisi antara verteks x dan y ditulis {x, y}. Suatu graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunan bagian dari V dan E1 himpunan bagian dari E. Cara pendefinisian lain untuk graph adalah dengan menggunakan himpunan keterhubungan langsung Vx. Pada setiap verteks x terdefinisi Vx sebagai himpunan dari verteks-verteks yang adjacent dari x. Secara formal: Vx = {y | (x,y) -> E} Dalam digraph didefinisikan juga terminologi-terminologi berikut ini. Predesesor dari suatu verteks x (ditulis Pred(x)) adalah himpunan semua verteks yang adjacent ke x. Suksesor dari verteks x (ditulis Succ(x)) adalah himpunan semua verteks yang adjacent dari x, yaitu adjacenct set di atas. Struktur data yang berbentuk network/jaringan, hubungan antar elemen adalah many-to-many. Contoh dari graph adalah informasi topologi jaringan dan keterhubungan antar kota-kota. Keterhubungan dan jarak tidak langsung antara dua kota sama dengan data keterhubungan langsung dari kota-kota lainnya yang
4 memperantarainya. Penerapan struktur data linear atau hirarkis pada masalah graph dapat dilakukan tetapi kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straight forward) dilakukan pada strukturnya sendiri. 1. Struktur Data Linear = keterhubungan sekuensial antara entitas data 2. Struktur Data Tree = keterhubungan hirarkis 3. Struktur Data Graph = keterhubungan tak terbatas antara entitas data. B. Istilah-istilah dalam graf Kemudian terdapat istilah-istilah yang berkaitan dengan graph yaitu: a. Vertex ; adalah himpunan node / titik pada sebuah graph. b. Edge ; adalah himpunan garis yang menghubungkan tiap node / vertex. c. Adjacent adalah dua buah titik dikatakan berdekatan (adjacent) jika dua buah titik tersebut terhubung dengan sebuah sisi. Adalah Sisi e3 = v2v3 insident dengan titik v2 dan titik v3, tetapi sisi e3 = v2v3 tidak insident dengan titik v1 dan titik v4. Titik v1 adjacent dengan titik v2 dan titik v3, tetapi titik v1 tidak adjacent dengan titik v4.
5 d. Weight adalah Sebuah graf G = (V, E) disebut sebuah graf berbobot (weight graph), apabila terdapat sebuah fungsi bobot bernilai real W pada himpunan E, W : E 速 R, nilai W(e) disebut bobot untuk sisi e, " e E. Graf berbobot tersebut dinyatakan pula sebagai G = (V, E, W). Graf berbobot G = (V, E, W) dapat menyatakan * suatu sistem perhubungan udara, di mana 揃 V = himpunan kota-kota 揃 E = himpunan penerbangan langsung dari satu kota ke kota lain 揃 W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu * suatu sistem jaringan komputer, di mana 揃 V = himpunan komputer 揃 E = himpunan jalur komunikasi langsung antar dua komputer 揃 W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu e. Path Adalah Walk dengan setiap vertex berbeda. Contoh, P = D5B4C2A Sebuah walk (W) didefinisikan sebagai urutan (tdk nol) vertex & edge. Diawali origin vertex dan diakhiri terminus vertex. Dan setiap 2 edge berurutan adalah series. Contoh, W = A1B3C4B1A2. f. Cycle Adalah Siklus ( Cycle ) atau Sirkuit ( Circuit ) Lintasan yang berawal dan berakhir pada simpul yang sama C. Representasi Graf Dalam pemrograman, agar data yang ada dalam graph dapat diolah, maka graph harus dinyatakan dalam suatu struktur data yang dapat mewakili graph tersebut. Dalam hal ini graph perlu direpresentasikan kedalam bentuk array dan dimensi yang
6 sering disebut matrix atau direpresentasikan dalam bentuk linked list. Bentuk mana yang dipilih biasanya tergantung kepada efisiensi dan kemudahan dalam membuat program. Berikut ini beberapa bentuk representasi graph: 1. Representasi Graph dalam bentuk Matrix: 1. Adjacency Matrik Graf Tak Berarah Matrik yang digambarkan pada gambar 1b merupakan representasi dalam bentuk Adjacency Matrik dari graf yang digambarkan pada gambar 1a. Beberapa hal yang dapat dilihat atau dapat diterangkan pada Adjacency Matrik tersebut adalah sebagai berikut : 1. Matrik yang terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah simpul yang ada dalam graf tersebut. Matrik ini menyatakan hubungan antara simpul satu dengan simpul lainnya. 2. Matrik yang terbentuk adalah matrik simetris dengan sumbu simetris adalah diagonal dari titik kiri atas ke titik kanan bawah. 3. Data yang tedapat baik dalam baris maupun kolom, dapat menyatakan degree sebuah simpul. Contoh : baik pada baris D maupun kolom D jumlah angka 1 nya adalah 3 buah, dimana jumlah ini menyatakan degree simpul D.
7 2. Adjacency Matrik Graf Berarah Matrik yang digambarkan pada gambar 2b merupakan representasi dalam bentuk Adjacency Matrik dari graf yang digambarkan pada gambar 2a. Beberapa hal yang dapat dilihat atau dapat diterangkan pada Adjacency Matrik tersebut adalah sebagai berikut : 1. Matrik yang terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah simpul yang ada dalam graf tersebut. Matrik ini menyatakan hubungan antara simpul satu dengan simpul lainnya. 2. Matrik yang terbentuk mungkin simetris mungkin juga tidak simetris. Menjadi Simetris bila hubungan antara dua buah simpul (v1 dan v2) terdapat busur dari v1 ke v2 dan juga sebaliknya. 3. Hal pokok yang dinyatakan oleh matrik ini adalah : busur yang keluar dari suatu simpul. Dengan demikian, data yang terdapat dalam suatu baris, dapat menyatakan outdegree simpul yang bersangkutan. Contoh : Jumlah elemen yang nilainya = 1 pada baris B ada 3 elemen,ini menyatakan jumlah outdegree simpul B adalah 3 buah. 4. Data yang terdapat dalam suatu kolom, dapat menyatakan indegree simpul bersangkutan.
8 Contoh : Jumlah elemen yang nilainya 1 pada kolom B ada 2 elemen, ini menyatakan indegree simpul B adalah 2 buah. 3. Adjacency Matrik Graf Berbobot Tak Berarah Nilai yang ada dalam tiap elemen matrik, menyatakan bobot busur yang menghubungkan dua buah simpul yang bersangkutan. Untuk dua buah simpul yang tidak berhubungan langsung oleh sebuah busur, maka dianggap dihubungkan oleh sebuah busur yang nilai bobotnya tidak terhingga. Dalam pemograman, karena keperluan algoritma, maka dari total bobot seluruh busur yang ada atau yang mungkin ada. Contoh: pada gambar 3a simpul A dan C tidak berhubungan langsung melalui sebuah busur, maka untuk elemen matrik yang bersangkutan diisi dengan nilai 999 karena nilai 999 dalam kasus ini cukup mewakili nilai tidak terhingga.
9 2. Representasi graf dalam bentuk Linked List 1. Adjacency List Bila ingin direpresentasikan dalam bentuk linked list, dapat diilustrasikan secara sederhana seperti gamabar 4b. Dari ilustrasi sederhana tersebut terlihat ada 5 buah simpul A,B,C,D,dan E yang dibariskan dari atas kebawah seperti pada gambar 4a. Kemudian dari masing-masing simpul keluar pointer kearah kanan yang menunjuk simpul-simpul lain. Salah satu contoh, yang dapat dilihat pada gambar 4b dimana A menunjuk simpul B dan simpul D.
10 Dalam Adjacency List, kita perlu membedakan antara simpul-vertex dan simpul- edge. Simpul-vertex untuk menyatakan simpul atau vertex, dan simpul-edge untuk menyatakan hubungan antar simpul yang biasa disebut busur. Struktur keduanya bisa sama, bisa juga tidak sama,tergantung kebutuhan.Untuk memudahkan pembuatan program, struktur kedua macam simpul dibuat sama seperti yang digambarkan pada gambar 5c. Yang membedakan antara simpul-vertex dan simpul- edge, adalah anggapan terhadap simpul tersebut. Dalam contoh ini, terlihat struktur simpul dibuat terdiri dari 3 elemen. Satu elemen untuk INFO, dua elemen untuk pointer.pointer kiri (left) dan pointer kanan (right). Struct tipes{ Struct tipes *Left; int INFO; Struct tipes *Right; }; Struct tipes *First,*Pvertex,*Pedge; - Bila simpul dianggap sebagai simpul-vertex, maka : Pointer left digunakan untuk menunjuk simpul berikutnya dalam untaian simpul- simpul yang ada, atau diisi NULL bila sudah tidak ada simpul yang pelu ditunjuk.Sedangkan pointer Right digunakan untuk menunjuk simpul edge yang pertama. - Bila Simpul dianggap sebagai simpul-edge, maka : Pointer left digunakan untuk menunjuk simpul-vertex tujuan yang berhubungan dengan simpul-vertex asal dan pointer right digunakan untuk menunjuk simpul-edge berkiutnya bila masih ada, atau diisi NULL bila tak ada lagi simpul-busur yang ditunjuk.
11 D. Contoh program representasi Graph pada C++ #include <iostream> #include <conio.h> using namespace std; int main(void) { double matriks[10][10],matriksb[10][10],hasil[10][10]; int CC,i,j,k,l,edge,vertex,asal,tujuan,panjang; cout<<"Jumlah Vertex t : "; cin>>vertex; //jumlah vertex/simpul graph cout<<"Jumlah Edge t : "; cin>>edge; //jumlah sisi pada graph for (i=1;i<=vertex;i++) { for (j=1;j<=vertex;j++) { matriks[i][j]=0; //penginisialisasian awal matriks } } for (i=1;i<=edge;i++) //pembentukkan matriks berdasarkan graph { cout<<"~Edge ke-"<<i<<"~n"; cout<<"Vertex asal t : ";cin>>asal; cout<<"Vertex tujuan t : ";cin>>tujuan; matriks[asal][tujuan]+=1; matriks[tujuan][asal]+=1; }
12 for (i=1;i<=vertex;i++) { for (j=1;j<=vertex;j++) { hasil[i][j]=0; for (k=1;k<=vertex;k++) { CC=matriks[i][k]*matriks[k][j]; hasil[i][j]=hasil[i][j]+CC; } } } /*cout<<" Element matriks C [hasil] : "<<endl; for (i=1;i<=vertex;i++){ //menampilkan matriks hasil perkalian for (j=1;j<=vertex;j++){ cout<<" "<<hasil[i][j]; } cout<<endl; }*/ cout<<"~Menentukan Banyak Walk yang mungkin~nMasukkan vertex awal t : ";cin>>i; cout<<"Masukkan vertex Tujuan t : ";cin>>j; cout<<"Jumlah Walk dari vertex "<<i<<" ke vertex "<<j<<" dengan panjang "<<panjang<< " sebanyak "<<hasil[i][j]<<" Walks"; getch(); }
13 BAB III PENUTUP 3.1 Kesimpulan Teori Graph merupakan salah satu cabang dari bidang Matematika Diskrit yang mempunyai banyak terapan di berbagai bidang. Struktur data graph merupakan bentuk implementasi dari teori graph yang mencakup definisi, dan hukum-hukum yang menyertainya. Struktur data graph menggunakan representasi internal senarai ketetanggaan dengan alas an efisiensi penggunaan untuk komputasi, karena penggunaan matriks ketetanggan kurang efisisen dan cenderung boros untuk kasus jumlah sisi sedikit sedangkan matriks ketetanggaan yang dibentuk berupa matriks jarang (sparse) Suatu graph didefinisikan oleh himpunan verteks dan himpunan sisi (edge). Verteks menyatakan entitas-entitas data dan sisi menyatakan keterhubungan antara verteks. Graph dalam kehidupan sehari-hari dapat dianalogikan sebagai suatu jaringan satu dengan jaringan lainnya yang saling terhubung. Missal seperti Negara Indonesia yang memiliki banyak kota seperti : Jakarta, Bandung, Surabay, Yogyakarta, Gowa. Kota-kota itulah yang tergabung dalam Negara Indonesia dan kota-kota itulah yang saling berhubungan. 3.2 Saran Diharapkan dengan membaca dan mempelajari makalah graph ini, para pembaca dapat lebih memahami pengertian graph, representasinya dalam ilmu komputasi serta pengimplementasiaanya dalam kehidupan sehari-hari.
14 Daftar Pustaka Undip, BFS dan DFS, http://eprints.undip.ac.id/5202/2/BAB_I_dan_II. pdf, Tanggal Akses : 27 November 2014 Rachmat Antonius, Struktur Data http://lecturer.ukdw.ac.id/anton/download/TIstrukdat11. ppt Tanggal Akses : 27 November 2014 AlpenYap, Struktur Data Hirarkis http://alpz.files.wordpress.com/2007/12/tree-btree- graph.pdf Tanggal Akses : 27 November 2014 Ciptarjo Imam, Pengantar Graph http://134738.yolasite.com/resources/17782333-Struktur-Data- Graph- wwwaloneareacom.pdf Tanggal Akses : 28 November 2014

More Related Content

Pengertian dan Representasi Graph

  • 1. 1 BAB I PENDAHULUAN 1.1 Latar Belakang Graf merupakan salah satu dari beberapa struktur data yang paling sering diaplikasikan, dalam pemrograman komputer. Jika kita memutuskan untuk menggunakan penyimpanan data yang bersifat external, kita mungkin tidak terlalu membutuhkn graf, tetapi untuk beberapa permasalahan dimana kita memerlukan referesentasi internal dalam memori komputer untuk suatu struktur data, graf tidak bisa dihindari penggunaannya. Secara konseptual, graf merupakan suatu struktur data yang agak berbeda dengan pohon (tree). Dalam pernyataannya, pohon merupakan salah satu jenis graf; pohon merupakan kasus khusus dari graf. Dalam pemrograman komputer untuk berbagai terapan, graf sering digunakan dalam berbagai cara yang relatif lebih bermanfaat dibandingkan pohon(tree). Struktur-struktur data memiliki algoritma yang terkait pada struktur data yang bersangkutan. Sebagai contoh, pohon biner dibentuk dengan cara seperti itu karena bentuknya memudahkan pemrogram untuk melakukan pencarian data dan melakukan penyisipan data. Simpul-simpul (vertex) dalam pohon biner merepresentasikan cara yang efektif untuk melakukan penelusuran terhadapnya. Dalam hal ini, graf memiliki bentuk yang ditentukan oleh permasalahn nyata. Sebagai contoh, simpul-simpul dalam graf mungkin merepresentasikan kota-kota yang menggambarkan lintasan penerbangan antarkota/antarnegara, atau jalur-jalur elektronika pada sebuah IC (Integrated Circuit). Graf adalah salah satu jenis struktur data yang terdiri dari titik (vertex) dan garis (edge), dimana dalam graf tersebut, vertex - vertex yang ada dihubungkan oleh edge, hingga menjadi suatu kesatuan yang disebut graf. Sebagai contoh dari pemodelan graf adalah peta kota kota, dimana kota disini sebagai vertex dan jalur yang menghubungkannya berlaku sebagai edge. Ada terdapat beberapa jenis graf yang bisa kita gunakan, yaitu beberapa diantaranya adalah sebagai berikut : Graf Berarah : adalah graf yang edge-nya memiliki arah, sebagai contoh edge AB menghubungkan vertex A ke B, dimana hubungan vertex B ke A, harus diperoleh
  • 2. 2 dari edge lain, yaitu edge BA, dan jika edge BA tidak ada, maka vertex B ke A tidak memiliki hubungan, meski vertex A ke B memiliki hubungan Graf Tak Berarah : adalah graf yang edge-nya tidak memiliki arah, sehingga jika edge AB menghubungkan vertex A ke B, maka secara otomatis juga menghubungkan vertex B ke A. Graf Berbobot : adalah suatu graf dimana edge dari graf tersebut memiliki bobot atau nilai tertentu. Graf Tidak Berbobot : adalah suatu graf dimana edge dari graf tersebut tidak memiliki bobot atau nilai. Untuk merepresentasikannya dalam pemrograman komputer, graf dapat disusun dari LinkedList yang berada dalam LinkedList 1.2 Rumusan Masalah 1. Apa Definisi Graph? 2. Apa saja istilah-istilah dalam graph? 3. Bagaimana representasi graph dalam struktur data? 1.3 Tujuan 1. Untuk Mengetahui definisi graph 2. Untuk mengetahui istilah-istilah dalam graph 3. Untuk megetahui bagaimana bentuk representasi graph dalam struktur data
  • 3. 3 BAB II PEMBAHASAN A. Definisi Graph Suatu graph didefinisikan oleh himpunan verteks dan himpunan sisi (edge). Verteks menyatakan entitas-entitas data dan sisi menyatakan keterhubungan antara verteks. Biasanya untuk suatu graph G digunakan notasi matematis. G = (V , E) Dimana : G = Graph V = Simpul atau Vertex, atau Node, atau Titik E = Busur atau Edge, atau arc V adalah himpunan verteks dan E himpunan sisi yang terdefinisi antara pasangan- pasangan verteks. Sebuah sisi antara verteks x dan y ditulis {x, y}. Suatu graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunan bagian dari V dan E1 himpunan bagian dari E. Cara pendefinisian lain untuk graph adalah dengan menggunakan himpunan keterhubungan langsung Vx. Pada setiap verteks x terdefinisi Vx sebagai himpunan dari verteks-verteks yang adjacent dari x. Secara formal: Vx = {y | (x,y) -> E} Dalam digraph didefinisikan juga terminologi-terminologi berikut ini. Predesesor dari suatu verteks x (ditulis Pred(x)) adalah himpunan semua verteks yang adjacent ke x. Suksesor dari verteks x (ditulis Succ(x)) adalah himpunan semua verteks yang adjacent dari x, yaitu adjacenct set di atas. Struktur data yang berbentuk network/jaringan, hubungan antar elemen adalah many-to-many. Contoh dari graph adalah informasi topologi jaringan dan keterhubungan antar kota-kota. Keterhubungan dan jarak tidak langsung antara dua kota sama dengan data keterhubungan langsung dari kota-kota lainnya yang
  • 4. 4 memperantarainya. Penerapan struktur data linear atau hirarkis pada masalah graph dapat dilakukan tetapi kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straight forward) dilakukan pada strukturnya sendiri. 1. Struktur Data Linear = keterhubungan sekuensial antara entitas data 2. Struktur Data Tree = keterhubungan hirarkis 3. Struktur Data Graph = keterhubungan tak terbatas antara entitas data. B. Istilah-istilah dalam graf Kemudian terdapat istilah-istilah yang berkaitan dengan graph yaitu: a. Vertex ; adalah himpunan node / titik pada sebuah graph. b. Edge ; adalah himpunan garis yang menghubungkan tiap node / vertex. c. Adjacent adalah dua buah titik dikatakan berdekatan (adjacent) jika dua buah titik tersebut terhubung dengan sebuah sisi. Adalah Sisi e3 = v2v3 insident dengan titik v2 dan titik v3, tetapi sisi e3 = v2v3 tidak insident dengan titik v1 dan titik v4. Titik v1 adjacent dengan titik v2 dan titik v3, tetapi titik v1 tidak adjacent dengan titik v4.
  • 5. 5 d. Weight adalah Sebuah graf G = (V, E) disebut sebuah graf berbobot (weight graph), apabila terdapat sebuah fungsi bobot bernilai real W pada himpunan E, W : E 速 R, nilai W(e) disebut bobot untuk sisi e, " e E. Graf berbobot tersebut dinyatakan pula sebagai G = (V, E, W). Graf berbobot G = (V, E, W) dapat menyatakan * suatu sistem perhubungan udara, di mana 揃 V = himpunan kota-kota 揃 E = himpunan penerbangan langsung dari satu kota ke kota lain 揃 W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu * suatu sistem jaringan komputer, di mana 揃 V = himpunan komputer 揃 E = himpunan jalur komunikasi langsung antar dua komputer 揃 W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu e. Path Adalah Walk dengan setiap vertex berbeda. Contoh, P = D5B4C2A Sebuah walk (W) didefinisikan sebagai urutan (tdk nol) vertex & edge. Diawali origin vertex dan diakhiri terminus vertex. Dan setiap 2 edge berurutan adalah series. Contoh, W = A1B3C4B1A2. f. Cycle Adalah Siklus ( Cycle ) atau Sirkuit ( Circuit ) Lintasan yang berawal dan berakhir pada simpul yang sama C. Representasi Graf Dalam pemrograman, agar data yang ada dalam graph dapat diolah, maka graph harus dinyatakan dalam suatu struktur data yang dapat mewakili graph tersebut. Dalam hal ini graph perlu direpresentasikan kedalam bentuk array dan dimensi yang
  • 6. 6 sering disebut matrix atau direpresentasikan dalam bentuk linked list. Bentuk mana yang dipilih biasanya tergantung kepada efisiensi dan kemudahan dalam membuat program. Berikut ini beberapa bentuk representasi graph: 1. Representasi Graph dalam bentuk Matrix: 1. Adjacency Matrik Graf Tak Berarah Matrik yang digambarkan pada gambar 1b merupakan representasi dalam bentuk Adjacency Matrik dari graf yang digambarkan pada gambar 1a. Beberapa hal yang dapat dilihat atau dapat diterangkan pada Adjacency Matrik tersebut adalah sebagai berikut : 1. Matrik yang terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah simpul yang ada dalam graf tersebut. Matrik ini menyatakan hubungan antara simpul satu dengan simpul lainnya. 2. Matrik yang terbentuk adalah matrik simetris dengan sumbu simetris adalah diagonal dari titik kiri atas ke titik kanan bawah. 3. Data yang tedapat baik dalam baris maupun kolom, dapat menyatakan degree sebuah simpul. Contoh : baik pada baris D maupun kolom D jumlah angka 1 nya adalah 3 buah, dimana jumlah ini menyatakan degree simpul D.
  • 7. 7 2. Adjacency Matrik Graf Berarah Matrik yang digambarkan pada gambar 2b merupakan representasi dalam bentuk Adjacency Matrik dari graf yang digambarkan pada gambar 2a. Beberapa hal yang dapat dilihat atau dapat diterangkan pada Adjacency Matrik tersebut adalah sebagai berikut : 1. Matrik yang terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah simpul yang ada dalam graf tersebut. Matrik ini menyatakan hubungan antara simpul satu dengan simpul lainnya. 2. Matrik yang terbentuk mungkin simetris mungkin juga tidak simetris. Menjadi Simetris bila hubungan antara dua buah simpul (v1 dan v2) terdapat busur dari v1 ke v2 dan juga sebaliknya. 3. Hal pokok yang dinyatakan oleh matrik ini adalah : busur yang keluar dari suatu simpul. Dengan demikian, data yang terdapat dalam suatu baris, dapat menyatakan outdegree simpul yang bersangkutan. Contoh : Jumlah elemen yang nilainya = 1 pada baris B ada 3 elemen,ini menyatakan jumlah outdegree simpul B adalah 3 buah. 4. Data yang terdapat dalam suatu kolom, dapat menyatakan indegree simpul bersangkutan.
  • 8. 8 Contoh : Jumlah elemen yang nilainya 1 pada kolom B ada 2 elemen, ini menyatakan indegree simpul B adalah 2 buah. 3. Adjacency Matrik Graf Berbobot Tak Berarah Nilai yang ada dalam tiap elemen matrik, menyatakan bobot busur yang menghubungkan dua buah simpul yang bersangkutan. Untuk dua buah simpul yang tidak berhubungan langsung oleh sebuah busur, maka dianggap dihubungkan oleh sebuah busur yang nilai bobotnya tidak terhingga. Dalam pemograman, karena keperluan algoritma, maka dari total bobot seluruh busur yang ada atau yang mungkin ada. Contoh: pada gambar 3a simpul A dan C tidak berhubungan langsung melalui sebuah busur, maka untuk elemen matrik yang bersangkutan diisi dengan nilai 999 karena nilai 999 dalam kasus ini cukup mewakili nilai tidak terhingga.
  • 9. 9 2. Representasi graf dalam bentuk Linked List 1. Adjacency List Bila ingin direpresentasikan dalam bentuk linked list, dapat diilustrasikan secara sederhana seperti gamabar 4b. Dari ilustrasi sederhana tersebut terlihat ada 5 buah simpul A,B,C,D,dan E yang dibariskan dari atas kebawah seperti pada gambar 4a. Kemudian dari masing-masing simpul keluar pointer kearah kanan yang menunjuk simpul-simpul lain. Salah satu contoh, yang dapat dilihat pada gambar 4b dimana A menunjuk simpul B dan simpul D.
  • 10. 10 Dalam Adjacency List, kita perlu membedakan antara simpul-vertex dan simpul- edge. Simpul-vertex untuk menyatakan simpul atau vertex, dan simpul-edge untuk menyatakan hubungan antar simpul yang biasa disebut busur. Struktur keduanya bisa sama, bisa juga tidak sama,tergantung kebutuhan.Untuk memudahkan pembuatan program, struktur kedua macam simpul dibuat sama seperti yang digambarkan pada gambar 5c. Yang membedakan antara simpul-vertex dan simpul- edge, adalah anggapan terhadap simpul tersebut. Dalam contoh ini, terlihat struktur simpul dibuat terdiri dari 3 elemen. Satu elemen untuk INFO, dua elemen untuk pointer.pointer kiri (left) dan pointer kanan (right). Struct tipes{ Struct tipes *Left; int INFO; Struct tipes *Right; }; Struct tipes *First,*Pvertex,*Pedge; - Bila simpul dianggap sebagai simpul-vertex, maka : Pointer left digunakan untuk menunjuk simpul berikutnya dalam untaian simpul- simpul yang ada, atau diisi NULL bila sudah tidak ada simpul yang pelu ditunjuk.Sedangkan pointer Right digunakan untuk menunjuk simpul edge yang pertama. - Bila Simpul dianggap sebagai simpul-edge, maka : Pointer left digunakan untuk menunjuk simpul-vertex tujuan yang berhubungan dengan simpul-vertex asal dan pointer right digunakan untuk menunjuk simpul-edge berkiutnya bila masih ada, atau diisi NULL bila tak ada lagi simpul-busur yang ditunjuk.
  • 11. 11 D. Contoh program representasi Graph pada C++ #include <iostream> #include <conio.h> using namespace std; int main(void) { double matriks[10][10],matriksb[10][10],hasil[10][10]; int CC,i,j,k,l,edge,vertex,asal,tujuan,panjang; cout<<"Jumlah Vertex t : "; cin>>vertex; //jumlah vertex/simpul graph cout<<"Jumlah Edge t : "; cin>>edge; //jumlah sisi pada graph for (i=1;i<=vertex;i++) { for (j=1;j<=vertex;j++) { matriks[i][j]=0; //penginisialisasian awal matriks } } for (i=1;i<=edge;i++) //pembentukkan matriks berdasarkan graph { cout<<"~Edge ke-"<<i<<"~n"; cout<<"Vertex asal t : ";cin>>asal; cout<<"Vertex tujuan t : ";cin>>tujuan; matriks[asal][tujuan]+=1; matriks[tujuan][asal]+=1; }
  • 12. 12 for (i=1;i<=vertex;i++) { for (j=1;j<=vertex;j++) { hasil[i][j]=0; for (k=1;k<=vertex;k++) { CC=matriks[i][k]*matriks[k][j]; hasil[i][j]=hasil[i][j]+CC; } } } /*cout<<" Element matriks C [hasil] : "<<endl; for (i=1;i<=vertex;i++){ //menampilkan matriks hasil perkalian for (j=1;j<=vertex;j++){ cout<<" "<<hasil[i][j]; } cout<<endl; }*/ cout<<"~Menentukan Banyak Walk yang mungkin~nMasukkan vertex awal t : ";cin>>i; cout<<"Masukkan vertex Tujuan t : ";cin>>j; cout<<"Jumlah Walk dari vertex "<<i<<" ke vertex "<<j<<" dengan panjang "<<panjang<< " sebanyak "<<hasil[i][j]<<" Walks"; getch(); }
  • 13. 13 BAB III PENUTUP 3.1 Kesimpulan Teori Graph merupakan salah satu cabang dari bidang Matematika Diskrit yang mempunyai banyak terapan di berbagai bidang. Struktur data graph merupakan bentuk implementasi dari teori graph yang mencakup definisi, dan hukum-hukum yang menyertainya. Struktur data graph menggunakan representasi internal senarai ketetanggaan dengan alas an efisiensi penggunaan untuk komputasi, karena penggunaan matriks ketetanggan kurang efisisen dan cenderung boros untuk kasus jumlah sisi sedikit sedangkan matriks ketetanggaan yang dibentuk berupa matriks jarang (sparse) Suatu graph didefinisikan oleh himpunan verteks dan himpunan sisi (edge). Verteks menyatakan entitas-entitas data dan sisi menyatakan keterhubungan antara verteks. Graph dalam kehidupan sehari-hari dapat dianalogikan sebagai suatu jaringan satu dengan jaringan lainnya yang saling terhubung. Missal seperti Negara Indonesia yang memiliki banyak kota seperti : Jakarta, Bandung, Surabay, Yogyakarta, Gowa. Kota-kota itulah yang tergabung dalam Negara Indonesia dan kota-kota itulah yang saling berhubungan. 3.2 Saran Diharapkan dengan membaca dan mempelajari makalah graph ini, para pembaca dapat lebih memahami pengertian graph, representasinya dalam ilmu komputasi serta pengimplementasiaanya dalam kehidupan sehari-hari.
  • 14. 14 Daftar Pustaka Undip, BFS dan DFS, http://eprints.undip.ac.id/5202/2/BAB_I_dan_II. pdf, Tanggal Akses : 27 November 2014 Rachmat Antonius, Struktur Data http://lecturer.ukdw.ac.id/anton/download/TIstrukdat11. ppt Tanggal Akses : 27 November 2014 AlpenYap, Struktur Data Hirarkis http://alpz.files.wordpress.com/2007/12/tree-btree- graph.pdf Tanggal Akses : 27 November 2014 Ciptarjo Imam, Pengantar Graph http://134738.yolasite.com/resources/17782333-Struktur-Data- Graph- wwwaloneareacom.pdf Tanggal Akses : 28 November 2014