albyzack's Blog

Just another WordPress.com weblog

Graph

Graph merupakan struktur data yang paling umum. Jika struktur linear memungkinkan pendefinisian keterhubungan sikuensial antara entitas data, struktur data tree memungkinkan pendefinisian keterhubungan hirarkis, maka struktur graph memungkinkan pendefinisian keterhubungan tak terbatas antara entitas data. Banyak entitas-entitas data dalam masalah-masalah nyata secara alamiah memiliki keterhubungan langsung (adjacency) secara tak terbatas demikian. Contoh: informasi topologi dan jarak antar kota-kota di pulau Jawa. Dalam masalah ini kota x bisa berhubungan langsung dengan hanya satu atau lima kota lainnya. Untuk memeriksa keterhubungan dan jarak tidak langsung antara dua kota dapat diperoleh berdasarkan data keterhubungan-keterhubungan langsung dari kota-kota lainnya yang memperantarainya. Representasi data dengan struktur data linear ataupun hirarkis pada masalah ini masih bisa digunakan namun akan membutuhkan pencarian-pencarian yang kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straightforward) dilakukan pada strukturnya sendiri. Masalah-masalah Graph Masalah path minimum (Shortest path problem) mencari route dengan jarak terpendek dalam suatu jaringan transportasi. Masalah aliran maksimum (maximum flow problem) menghitung volume aliran BBM dari suatu reservoir ke suatu titik tujuan melalui jaringan pipa. Masalah pencariah dalam graph (graph searching problem) mencari langkah-langkah terbaik dalam program permainan catur komputer. Masalah pengurutan topologis (topological ordering problem) menentukan urutan pengambilan mata-mata kuliah yang saling berkaitan dalam hubungan prasyarat (prerequisite). Masalah jaringan tugas (Task Network Problem) membuat penjadwalan pengerjaan suatu proyek yang memungkinkan waktu penyelesaian tersingkat. Masalah pencarian pohon rentang minimum (Minimum Spanning Tree Problem) mencari rentangan kabel listrik yang totalnya adalah minimal untuk menghubungkan sejumlah kota. Travelling Salesperson Problem tukang pos mencari lintasan terpendek melalui semua alamat penerima pos tanpa harus mendatangi suatu tempat lebih dari satu kali. Four-color problem dalam menggambar peta, memberikan warna yang berbeda pada setiap propinsi yang saling bersebelahan. Definisi 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) 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. Digraph & Undigraph Graph Berarah (directed graph atau digraph): jika sisi-sisi pada graph, misalnya {x, y} hanya berlaku pada arah-arah tertentu saja, yaitu dari x ke y tapi tidak dari y ke x; verteks x disebut origin dan vertex y disebut terminus dari sisi tersebut. Secara grafis maka penggambaran arah sisi-sisi digraph dinyatakan dengan anak panah yang mengarah ke verteks terminus, secara notasional sisi graph berarah ditulis sebagai vektor dengan (x, y). graph di samping ini adalah suatu contoh Digraph G = {V, E} dengan V = {A, B, C, D, E, F, G, H, I,J, K, L, M} dan E = {( (A,B),(A,C), (A,D), (A,F), (B,C), (B,H), (C,E), (C,G), (C,H), (C,I), (D,E), (D,F), (D,G), (D,K), (D,L), (E,F), (G,I), (G,K), (H,I), (I,J), (I,M), (J,K), (J,M), (L,K), (L,M)}. Graph Tak Berarah (undirected graph atau undigraph): setiap sisi {x, y} berlaku pada kedua arah: baik x ke y maupun y ke x. Secara grafis sisi pada undigraph tidak memiliki mata panah dan secara notasional menggunakan kurung kurawal. graph di samping ini adalah suatu contoh Undigraph G = {V, E} dengan V = {A, B, C, D, E, F, G, H, I,J, K, L, M} dan E = { {A,B},{A,C}, {A,D}, {A,F}, {B,C}, {B,H}, {C,E}, {C,G}, {C,H}, {C,I}, {D,E}, {D,F}, {D,G}, {D,K}, {D,L}, {E,F}, {G,I}, {G,K}, {H,I}, {I,J}, {I,M}, {J,K}, {J,M}, {L,K}, {L,M}}. Dalam masalah-masalah graph undigraph bisa dipandang sebagai suatu digraph dengan mengganti setiap sisi tak berarahnya dengan dua sisi untuk masing-masing arah yang berlawanan. Undigraph di atas tersebut bisa dipandang sebagai Digraph G = {V, E} dengan V = {A, B, C, D, E, F, G, H, I,J, K, L, M} dan E = { (A,B),(A,C), (A,D), (A,F), (B,C), (B,H), (C,E), (C,G), (C,H), (C,I), (D,E), (D,F), (D,G), (D,K), (D,L), (E,F), (G,I), (G,K), (H,I), (I,J), (I,M), (J,K), (J,M), (L,K), (L,M), (B,A), (C,A), (D,A), (F,A), (C,B), (H,B), (E,C), (G,C), (H,C), (I,C), (E,D), (F,D), (G,D), (K,D), (L,D), (F,E), (I,G), (K,G), (I,H), (J,I), (M,I), (K,J), (M,J), (K,L), (M,L)} Selain itu, berdasarkan definisi ini maka struktur data linear maupun hirarkis adalah juga graph. Node-node pada struktur linear atupun hirarkis adalah verteks-verteks dalam pengertian graph dengan sisi-sisinya menyusun node-node tersebut secara linear atau hirarkis. Sementara kita telah ketahui bahwa struktur data linear adalah juga tree dengan pencabangan pada setiap node hanya satu atau tidak ada. Linear 1-way linked list adalah digraph, linear 2-way linked list bisa disebut undigraph. Aspek Algoritmis Walau secara konseptual struktur linear adalah subset dari tree dan demikian pula tree adalah subset dari graph, dalam aplikasinya perlu dibedakan cara penanganan struktur-struktur tersebut untuk mencapai efisiensi algoritmis. Algoritma-algoritma untuk graph secara umum terlalu mahal apabila digunakan pada struktur hirarkis (tree), apalagi pada struktur linear. Jadi apabila masalah yang dihadapi pada dasarnya hanya merupakan masalah dengan struktur data hirarkis saja maka cukup lah kita menggunakan representasi dan algoritma-algoritma tree. Konektivitas pada Undigraph * Adjacency: Dua verteks x dan y yang berlainan disebut berhubungan langsung (adjacent) jika terdapat sisi {x, y} dalam E. * Path: Sederetan verteks yang mana setiap verteks adjacent dengan verteks yang tepat berada disebelahnya. * Panjang dari path: jumlah sisi yang dilalui path. * Siklus: suatu path dengan panjang lebih dari satu yang dimulai dan berakhir pada suatu verteks yang sama. * Siklus sederhana: dalan undigraph, siklus yang terbentuk pada tiga atau lebih verteks-verteks yang berlainan yang mana tidak ada verteks yang dikunjungi lebih dari satu kali kecuali verteks awal/akhir. * Dua verteks x dan y yang berbeda dalam suatu undigraph disebut berkoneksi (connected) apabila jika terdapat path yang menghubungkannya. * Himpunan bagian verteks S disebut terkoneksi (connected) apabila dari setiap verteks x dalam S terdapat path ke setiap verteks y (y bukan x) dalam S. * Suatu komponen terkoneksi (connected components) adalah subgraph (bagian dari graph) yang berisikan satu himpunan bagian verteks yang berkoneksi. * Suatu undigraph dapat terbagi atas beberapa komponen yang terkoneksi; jika terdapat lebih dari satu komponen terkoneksi maka tidak terdapat path dari suatu verteks dalam satu komponen verteks di komponen lainnya. * Pohon bebas (free tree): suatu undigraph yang hanya terdapat satu komponen terkoneksi serta tidak memiliki siklus sederhana. Konektivitas pada Digraph Terminologi di atas berlaku juga pada Digraph kecuali dalam digraph harus dikaitkan dengan arah tertentu karena pada arah yang sebaliknya belum tentu terdefinisi. * Adjacency ke / dari: Jika terdapat sisi (x,y) maka dalam digraph dikatakan bahwa x “adjacent ke” y atau y “adjacent dari” x. Demikian pula jika terdapat path dari x ke y maka belum tentu ada path dari y ke x Jadi dalam digraph keterkoneksian didefinisikan lebih lanjut lagi sebagai berikut. * Terkoneksi dengan kuat: Himpunan bagian verteks S dikatakan terkoneksi dengan kuat (strongly connected) bila setiap pasangan verteks berbeda x dan y dalam S, x berkoneksi dengan y dan y berkoneksi dengan x (dpl., ada path dari x ke y dan sebaliknya dari y ke x). * Terkoneksi dengan Lemah: Himpunan bagian verteks S dikatakan terkoneksi dengan lemah (weakly connected) bila setiap pasangan verteks berbeda x dan y dalam S, salah satu: x berkoneksi dengan y (atau y berkoneksi dengan x) dan tidak kebalikan arahnya (dpl., hanya terdefinisi satu path: dari x ke y atau sebaliknya dari y ke x). Himpunan Keterhubungan Langsung 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 adjacency set di atas. . Degree * Degree dari suatu verteks x dalam undigraph adalah jumlah sisi di mana di salah satu ujungnya terdapat x. * Indegree dari suatu verteks x dalam digraph adalah jumlah dari predesesor x. * Outdegree dari suatu verteks x dalam digraph adalah jumlah dari suksesor x. Graph berbobot (weighted graph) Apabila sisi-sisi pada graph disertai juga dengan suatu (atau beberapa) harga yang menyatakan secara unik kondisi keterhubungan tersebut maka graph tersebut disebut graph berbobot. Biasanya dalam masalah-masalah graph bobot tersebut merupakan “biaya” dari keterhubungan ybs. Pengertian “biaya” ini menggeneralisasikan banyak aspek: biaya ekonomis dari proses/aktifitas, jarak geografis/tempuh, waktu tempuh, tingkat kesulitan, dan lain sebagainya. Dalam beberapa masalah lain bisa juga bobot tersebut memiliki pengertian “laba” yang berarti kebalikan dari “biaya” di atas. Dalam pembahasan algoritma-algoritma graph nanti pengertian bobot akan menggunakan pengertian biaya sehingga apabila diaplikasikan pada masalah yang berpengertian laba maka kuantitas-kuantitas terkait adalah kebalikannnya. Misalnya mencari jarak tempuh minimum digantikan dengan mencari laba maksimum. Lihat contoh graph berikut ini. Graph ini merupakan Undirected Weighted Graph. Order dari verteks A = 4, verteks B = 3, dst. Adjacentcy list dari D adalah = {A, E, F, G, K, L}. Graph merupakan struktur data yang paling umum. Jika struktur linear memungkinkan pendefinisian keterhubungan sikuensial antara entitas data, struktur data tree memungkinkan pendefinisian keterhubungan hirarkis, maka struktur graph memungkinkan pendefinisian keterhubungan tak terbatas antara entitas data. Banyak entitas-entitas data dalam masalah-masalah nyata secara alamiah memiliki keterhubungan langsung (adjacency) secara tak terbatas demikian. Contoh: informasi topologi dan jarak antar kota-kota di pulau Jawa. Dalam masalah ini kota x bisa berhubungan langsung dengan hanya satu atau lima kota lainnya. Untuk memeriksa keterhubungan dan jarak tidak langsung antara dua kota dapat diperoleh berdasarkan data keterhubungan-keterhubungan langsung dari kota-kota lainnya yang memperantarainya. Representasi data dengan struktur data linear ataupun hirarkis pada masalah ini masih bisa digunakan namun akan membutuhkan pencarian-pencarian yang kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straightforward) dilakukan pada strukturnya sendiri. Masalah-masalah Graph Masalah path minimum (Shortest path problem) mencari route dengan jarak terpendek dalam suatu jaringan transportasi. Masalah aliran maksimum (maximum flow problem) menghitung volume aliran BBM dari suatu reservoir ke suatu titik tujuan melalui jaringan pipa. Masalah pencariah dalam graph (graph searching problem) mencari langkah-langkah terbaik dalam program permainan catur komputer. Masalah pengurutan topologis (topological ordering problem) menentukan urutan pengambilan mata-mata kuliah yang saling berkaitan dalam hubungan prasyarat (prerequisite). Masalah jaringan tugas (Task Network Problem) membuat penjadwalan pengerjaan suatu proyek yang memungkinkan waktu penyelesaian tersingkat. Masalah pencarian pohon rentang minimum (Minimum Spanning Tree Problem) mencari rentangan kabel listrik yang totalnya adalah minimal untuk menghubungkan sejumlah kota. Travelling Salesperson Problem tukang pos mencari lintasan terpendek melalui semua alamat penerima pos tanpa harus mendatangi suatu tempat lebih dari satu kali. Four-color problem dalam menggambar peta, memberikan warna yang berbeda pada setiap propinsi yang saling bersebelahan. Definisi 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) 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. Digraph & Undigraph Graph Berarah (directed graph atau digraph): jika sisi-sisi pada graph, misalnya {x, y} hanya berlaku pada arah-arah tertentu saja, yaitu dari x ke y tapi tidak dari y ke x; verteks x disebut origin dan vertex y disebut terminus dari sisi tersebut. Secara grafis maka penggambaran arah sisi-sisi digraph dinyatakan dengan anak panah yang mengarah ke verteks terminus, secara notasional sisi graph berarah ditulis sebagai vektor dengan (x, y). graph di samping ini adalah suatu contoh Digraph G = {V, E} dengan V = {A, B, C, D, E, F, G, H, I,J, K, L, M} dan E = {( (A,B),(A,C), (A,D), (A,F), (B,C), (B,H), (C,E), (C,G), (C,H), (C,I), (D,E), (D,F), (D,G), (D,K), (D,L), (E,F), (G,I), (G,K), (H,I), (I,J), (I,M), (J,K), (J,M), (L,K), (L,M)}. Graph Tak Berarah (undirected graph atau undigraph): setiap sisi {x, y} berlaku pada kedua arah: baik x ke y maupun y ke x. Secara grafis sisi pada undigraph tidak memiliki mata panah dan secara notasional menggunakan kurung kurawal. graph di samping ini adalah suatu contoh Undigraph G = {V, E} dengan V = {A, B, C, D, E, F, G, H, I,J, K, L, M} dan E = { {A,B},{A,C}, {A,D}, {A,F}, {B,C}, {B,H}, {C,E}, {C,G}, {C,H}, {C,I}, {D,E}, {D,F}, {D,G}, {D,K}, {D,L}, {E,F}, {G,I}, {G,K}, {H,I}, {I,J}, {I,M}, {J,K}, {J,M}, {L,K}, {L,M}}. Dalam masalah-masalah graph undigraph bisa dipandang sebagai suatu digraph dengan mengganti setiap sisi tak berarahnya dengan dua sisi untuk masing-masing arah yang berlawanan. Undigraph di atas tersebut bisa dipandang sebagai Digraph G = {V, E} dengan V = {A, B, C, D, E, F, G, H, I,J, K, L, M} dan E = { (A,B),(A,C), (A,D), (A,F), (B,C), (B,H), (C,E), (C,G), (C,H), (C,I), (D,E), (D,F), (D,G), (D,K), (D,L), (E,F), (G,I), (G,K), (H,I), (I,J), (I,M), (J,K), (J,M), (L,K), (L,M), (B,A), (C,A), (D,A), (F,A), (C,B), (H,B), (E,C), (G,C), (H,C), (I,C), (E,D), (F,D), (G,D), (K,D), (L,D), (F,E), (I,G), (K,G), (I,H), (J,I), (M,I), (K,J), (M,J), (K,L), (M,L)} Selain itu, berdasarkan definisi ini maka struktur data linear maupun hirarkis adalah juga graph. Node-node pada struktur linear atupun hirarkis adalah verteks-verteks dalam pengertian graph dengan sisi-sisinya menyusun node-node tersebut secara linear atau hirarkis. Sementara kita telah ketahui bahwa struktur data linear adalah juga tree dengan pencabangan pada setiap node hanya satu atau tidak ada. Linear 1-way linked list adalah digraph, linear 2-way linked list bisa disebut undigraph. Aspek Algoritmis Walau secara konseptual struktur linear adalah subset dari tree dan demikian pula tree adalah subset dari graph, dalam aplikasinya perlu dibedakan cara penanganan struktur-struktur tersebut untuk mencapai efisiensi algoritmis. Algoritma-algoritma untuk graph secara umum terlalu mahal apabila digunakan pada struktur hirarkis (tree), apalagi pada struktur linear. Jadi apabila masalah yang dihadapi pada dasarnya hanya merupakan masalah dengan struktur data hirarkis saja maka cukup lah kita menggunakan representasi dan algoritma-algoritma tree. Konektivitas pada Undigraph * Adjacency: Dua verteks x dan y yang berlainan disebut berhubungan langsung (adjacent) jika terdapat sisi {x, y} dalam E. * Path: Sederetan verteks yang mana setiap verteks adjacent dengan verteks yang tepat berada disebelahnya. * Panjang dari path: jumlah sisi yang dilalui path. * Siklus: suatu path dengan panjang lebih dari satu yang dimulai dan berakhir pada suatu verteks yang sama. * Siklus sederhana: dalan undigraph, siklus yang terbentuk pada tiga atau lebih verteks-verteks yang berlainan yang mana tidak ada verteks yang dikunjungi lebih dari satu kali kecuali verteks awal/akhir. * Dua verteks x dan y yang berbeda dalam suatu undigraph disebut berkoneksi (connected) apabila jika terdapat path yang menghubungkannya. * Himpunan bagian verteks S disebut terkoneksi (connected) apabila dari setiap verteks x dalam S terdapat path ke setiap verteks y (y bukan x) dalam S. * Suatu komponen terkoneksi (connected components) adalah subgraph (bagian dari graph) yang berisikan satu himpunan bagian verteks yang berkoneksi. * Suatu undigraph dapat terbagi atas beberapa komponen yang terkoneksi; jika terdapat lebih dari satu komponen terkoneksi maka tidak terdapat path dari suatu verteks dalam satu komponen verteks di komponen lainnya. * Pohon bebas (free tree): suatu undigraph yang hanya terdapat satu komponen terkoneksi serta tidak memiliki siklus sederhana. Konektivitas pada Digraph Terminologi di atas berlaku juga pada Digraph kecuali dalam digraph harus dikaitkan dengan arah tertentu karena pada arah yang sebaliknya belum tentu terdefinisi. * Adjacency ke / dari: Jika terdapat sisi (x,y) maka dalam digraph dikatakan bahwa x “adjacent ke” y atau y “adjacent dari” x. Demikian pula jika terdapat path dari x ke y maka belum tentu ada path dari y ke x Jadi dalam digraph keterkoneksian didefinisikan lebih lanjut lagi sebagai berikut. * Terkoneksi dengan kuat: Himpunan bagian verteks S dikatakan terkoneksi dengan kuat (strongly connected) bila setiap pasangan verteks berbeda x dan y dalam S, x berkoneksi dengan y dan y berkoneksi dengan x (dpl., ada path dari x ke y dan sebaliknya dari y ke x). * Terkoneksi dengan Lemah: Himpunan bagian verteks S dikatakan terkoneksi dengan lemah (weakly connected) bila setiap pasangan verteks berbeda x dan y dalam S, salah satu: x berkoneksi dengan y (atau y berkoneksi dengan x) dan tidak kebalikan arahnya (dpl., hanya terdefinisi satu path: dari x ke y atau sebaliknya dari y ke x). Himpunan Keterhubungan Langsung 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 adjacency set di atas. . Degree * Degree dari suatu verteks x dalam undigraph adalah jumlah sisi di mana di salah satu ujungnya terdapat x. * Indegree dari suatu verteks x dalam digraph adalah jumlah dari predesesor x. * Outdegree dari suatu verteks x dalam digraph adalah jumlah dari suksesor x. Graph berbobot (weighted graph) Apabila sisi-sisi pada graph disertai juga dengan suatu (atau beberapa) harga yang menyatakan secara unik kondisi keterhubungan tersebut maka graph tersebut disebut graph berbobot. Biasanya dalam masalah-masalah graph bobot tersebut merupakan “biaya” dari keterhubungan ybs. Pengertian “biaya” ini menggeneralisasikan banyak aspek: biaya ekonomis dari proses/aktifitas, jarak geografis/tempuh, waktu tempuh, tingkat kesulitan, dan lain sebagainya. Dalam beberapa masalah lain bisa juga bobot tersebut memiliki pengertian “laba” yang berarti kebalikan dari “biaya” di atas. Dalam pembahasan algoritma-algoritma graph nanti pengertian bobot akan menggunakan pengertian biaya sehingga apabila diaplikasikan pada masalah yang berpengertian laba maka kuantitas-kuantitas terkait adalah kebalikannnya. Misalnya mencari jarak tempuh minimum digantikan dengan mencari laba maksimum. Lihat contoh graph berikut ini. Graph ini merupakan Undirected Weighted Graph. Order dari verteks A = 4, verteks B = 3, dst. Adjacentcy list dari D adalah = {A, E, F, G, K, L}.

Juni 8, 2010 - Posted by | Uncategorized

Belum ada komentar.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: