Free E-Book

Ads 468x60px

Welcome to The SMART chip

Membuka wawasan seluas Cakrawala..

Minggu, 07 Juli 2013

Konsep dan Pengertian dasar GRAPH (Graf)

Konsep dan Pengertian dasar GRAPH (Graf)


Definisi 1
Suatu graph G adalah pasangan (V,E) yang mana V adalah himpunan tak kosong yang anggotanya disebut vertex dan E adalah himpunan yang anggotanya adalah pasangan – pasangan tak berurut dari vertex V dan disebut edge.
Secara umum graph diartikan sebagai diagram, yang mana vertex ditampilkan berupa titik dan dinotasikan dengan vi, i = 1,2,3, … , p dan edge ditampilkan berupa garis yang menghubungkan dua vertex (vi,vj) dan dinotasikan dengan ek, k = 1,2,3, … ,q. vi dan vj disebut vertex – vertex ujung dari edge ek. Contoh dari suatu graph dapat dilihat dari gambar 1.

Definisi 2
Suatu edge yang menghubungkan pasangan vertex yang sama, yaitu (vi,vi) disebut loop. Dua buah edge atau lebih yang mempunyai vertex ujung yang sama disebut paralel edge (multiple edge).
Pada Gambar 1 e4 adalah loop dan e1, e2 merupakan paralel edge.
Definisi 3
Suatu graph yang mengandung loop dan paralel edge seperti contoh pada gambar 1 disebut graph semu ( pseudo graph ) dan graph yang mengandung paralel edge tanpa loop disebut multiple graph. Gambar 1 merupakan multiple graph jika e4 dihilangkan.
Definisi 4
Suatu graph yang tidak memuat loop dan paralel edge disebut simple graph. Contoh Simple graph pada gambar 2.
 
 
Definisi 5
Suatu graph dengan jumlah vertex dan jumlah edge yang berhingga disebut finite graph ( graph berhingga ), sebaliknya jika jumlah vertex dan edge tak berhingga disebut infinite graph ( graph tak berhingga ).
Definisi 6
Vertex vi dalam graph disebut insident terhadap edge ek jika dan hanya jika edge tersebut merupakan penghubung dari vertex vi.
Dua buah vertex vi dan vj disebut saling adjacent jika kedua vertex tersebut dihubungkan oleh suatu edge yang sama.
Dua buah edge ek dan el yang non paralel disebut adjacent jika kedua edge tersebut insident pada suatu vertex persekutuan.
Definisi 7
Degree atau derajat dari vertex vi adalah banyaknya edge yang insident pada vertex vi dalam graph G dan loop dihitung dua kali.Dinotasikan dengan d(vi).
Vertex yang berderajat 1 disebut end vertex ( pendant vertex ) sedangkan vertex yang berderajat nol disebut dengan isolated vertex ( vertex terasing ).
Dari gambar 1 diperoleh bahwa :
d( v1 ) = d( v5 ) = 1, d ( v2 ) = 3, d ( v3 ) = 4, dan d ( v4 ) = 2 , v1 dan v5 merupakan end vertex dan v6 merupakan isolated vertex dari graph pada gambar 1.
Teorema 1
Jumlah derajat pada seluruh vertex pada suatu graph adalah dua kali jumlah edgenya, 
Bukti :
Karena edge e insident dengan dua vertex, sehingga jumlah derajat dari seluruh vertex sama dengan 2 kali jumlah edgenya.
Definisi 8
Suatu graph G yaitu (V,E) dengan E suatu himpunan kosong, sehingga graph tersebut tanpa edge, disebut null graph. Dengan kata lain null graph adalah suatu graph dengan semua vertex nya berderajat nol. Akibatnya setiap vertex pada null graph adalah isolated vertex.
 
Definisi 9
Suatu simple graph yang mana setiap dua vertex yang berlainan dihubungkan oleh suatu edge maka graph itu disebut graph lengkap ( komplit graph ). Komplit graph dengan n vertex dinotasikan dengan Kn. Pada bab selanjutnya karena keterbatasan penulis, perangkat lunak yang dirancang hanya mampu menampilkan hingga K20 meskipun secara konsep dasar graph minimum spanning tree dapat diperoleh hingga ke Kn dan komplit graph yang ditampilkan adalah komplit graph yang tak berarah dan terboboti.
 
Definisi 10
Graph beraturan ( Regular Graph ) adalah suatu simple graph yang semua vertexnya mempunyai derajat yang sama. Jika graph G adalah simple graph yang mana setiap vertexnya berderajat r, maka graph tersebut dinamakan reguler graph berderajat r. Setiap komplit graph dengan n vertex merupakan regular graph dengan derajat ( n – 1 ).
 
Definisi 11
Graph S disebut subgraph dari graph G jika semua vertex dan edge di S termuat di dalam G, dan edge dari S mempunyai vertex ujung yang sama dengan edge dari G.
 
Definisi 12
Walk dalam suatu graph G adalah suatu deretan berhingga dari vertex dan edge secara bergantian yang diawali dan diakhiri dengan vertex sedemikian hingga setiap edge yang insident dengan dua vertex yang berdekatan.
Suatu walk dapat ditulis dengan atau tanpa mengikutsertakan edgenya. Apabila walk dengan vertex awal dan vertex akhir yang sama maka walk tersebut disebut closed walk ( walk tertutup ). Bila vertex awal dan vertex akhir berbeda maka disebut open walk ( walk terbuka ).
Pada gambar 6 (a) dapat diambil beberapa walk antara lain adalah :
· v1 e1 v2 e5 v5 e6 v6 ( open walk )
· v3 e3 v4 e4 v5 e5 v2 e2 v3 ( closed walk )
Walk di atas dapat juga ditulis tanpa mengikutsertakan edgenya menjadi :
· v1 v2 v5 v6
· v3 v4 v5 v2 v3

Defenisi 13
Path adalah suatu walk yang semua vertex yang dilaluinya berbeda, dan path dengan vertex awal sama dengan vertex akhir disebut dengan circuit ( cycle ). Loop bukan merupakan path atau circuit karena loop menghubungkan dua vertex yang sama. Banyaknya edge yang terdapat dalam suatu path disebut lenght dari path.

Definisi 14
Distance antara 2 vertex vi dan vj diartikan sebagai panjang path yang terpendek dari vi dan vj. Dinotasikan sebagai d ( vi,vj ).
Length atau panjang suatu graph adalah bilangan yang menyatakan banyaknya edge yang muncul dalam suatu walk.
d(v3,v5) pada graph 6 (a) adalah 2 yaitu : - v3 v2 v5
- v3 v4 v5
Pada graph 6 ( a ) v3 v4 v5 v2 v3 adalah walk dengan length 4.

2.2 Connected Graph dan Undirected Graph
Suatu graph G disebut graph terhubung ( connected graph )jika untuk setiap pasangan vertex di dalam G terdapat paling sedikit satu path, sebaliknya jika dalam graph G terdapat pasangan vertex yang tidak mempunyai path penghubung maka graph itu disebut disconnected graph. Atau dengan kata lain suatu connected graph adalah suatu graph yang tidak memiliki isolated vertex.
Dalam suatu disconnected graph memungkinkan terdapat dua atau lebih connected graph. Setiap connected graph dari disconnected graph disebut komponen.
 
Definisi 15
Directed graph adalah suatu graph G yang terdiri dari himpunan vertex V = {v1, v2, …, vp } dan himpunan edge E = {e1, e2, …, eq }dan suatu pemetaan f yang memetakan setiap edge onto terhadap pasangan berurut dari vertex ( vi,vj ), yang mana vertex disajikan dengan titik dan edge disajikan dengan sepotong garis berarah dari vi ke vj. Garis berarah yang menghubungkan dua vertex disebut arcus ( arc ) sehingga dari defenisi di atas dapat ditulis : f : eq ® ( vi,vj )
yang mana eq adalah arcus ke q Î G yang dipetakan oleh f ke pasangan vertex (vi,vj).

 
Definisi 16
Mixed graph adalah suatu graph G yang terdiri dari pasangan himpunan { V, E } yang mana V adalah himpunan berhingga tak kosong yang anggotanya merupakan titik yang disebut vertex, dan E adalah himpunan berhingga yang anggotanya merupakan potongan garis berarah dan tak berarah yang menghubungkan pasangan vertex tersebut disebut edge.
Gambar 9 Mixed Graph
Definisi 17
Undirected graph adalah suatu graph G yang terdiri dari pasangan himpunan { V,E } yang mana V adalah himpunan berhingga tak kosong yang anggotanya disebut vertex dan E adalah himpunan berhingga yang anggotanya disebut edge, yang merupakan potongan garis tak berarah yang menghubungkan pasangan vertex tersebut.

Definisi 18
Suatu graph G disebut weighted graph jika setiap edge dari graph G diberi bobot dengan suatu bilangan real. Jika setiap edge nya dikaitkan dengan suatu simbol yang bukan bilangan real disebut labeled graph.

 
Definisi 19
Jika vi adalah suatu vertex dalam graph G, maka G – vi merupakan suatu subgraph dari G yang diperoleh dengan menghapus vertex vi beserta edge yang insident dengan vertex tersebut. Jika ej adalah suatu edge dalam graph G, maka G – ej merupakan suatu subgraph dari G yang diperoleh dengan menghapus edge ej dari G.
( a ) Graph G

 






0 komentar:

Poskan Komentar