PENDAHULUAN MODUL I. 1 Teori Graph Pendahuluan Aswad 2013 Blog: 1

MODUL I

PENDAHULUAN

1.

Sejarah Graph

Teori Graph dilaterbelakangi oleh sebuah permasalahan yang disebut dengan masalah Jembatan Koningsberg. Jembatan Koningsberg berjumlah tujuh buah yang dibangun di atas aliran sungai Pregal yang mengitari pulau Kneiphof sebelum kemudian alirannya bercabang dua. Permasalahan yang timbul adalah apakah mungkin penduduk kota dapat melalui ketujuh buah jembatan tersebut masing-masing tepat satu kali lalu kembali lagi ke tempat semula? Sebagian penduduk kota mengatakan bahwa hal itu tidak mungkin dilakukan, namun mereka tidak mampu menjelaskan mengapa hal tersebut terjadi.

Gambar 1. Sketsa tujuh jembatan di Kota Koningsberg. Bermula pada 26 Agustus 1735, Leonhard Euler mempresentasekan sebuah tulisannya dengan judul “on The Solution of Problem Relating to The Geometry Position” dalam sebuah kesempatan di Academy of Sciences of St. Petersburg, Rusia. Tulisannya secara umum berisi pembahasan tentang ketidakmungkinan untuk melalui ketujuh jembatan Koningsberg dengan tepat satu kali lalu kembali lagi ke tempat semula. Euler tidak menggambarkan secara geometri permasalahan Jembatan Koningsberg, melainkan memberikan tinjauan secara ilmiah tentang

1 | Teori Graph – Pendahuluan ©Aswad 2013 Blog: http://aswhat.wordpress.com Email: [email protected]

permasalahan yang dimaksud. Adapun kesimpulan Euler dari masalah Jembatan Koningsberg adalah sebagai berikut: 

Jika terdapat dua atau lebih daerah dengan jembatan yang menghubungkan masing-masing daerah berjumlah ganjil, maka tidak mungkin melakukan perjalanan dengan melintasi jembatan tersebut masing-masing tepat satu kali lalu kembali lagi ke tempat semula.



Jika jumlah jembatan yang menghubungkan tepat ke dua daerah adalah ganjil, maka perjalanan yang dimaksud bisa saja dilakukan jika dimulai dari daerah di luar kedua daerah yang dimkasud.



Jika jumlah jembatan yang menghubungkan masing-masing daerah adalah semuanya genap, maka ketujuh jembatan tersebut pasti akan terlalui masingmasing satu kali, dari daerah manapun kita akan memulia perjalanan. Euler mengirimkan hasil pembahasannya tersebut ke sebuah Akademi

Scientiarum Imperialis Petropolitanie dengan judul yang berbeda. Namun, tulisan Euler tersebut baru dipublikasikan sekitar tahun 1752. Permasalahan Jembatan Koningsberg menarik minat beberapa ilmuwan untuk menjelaskannya dalam sebuah bentuk geometri yang selanjutnya menjadi cikal bakan lahirnya graph. Bermula dari L Poinsot di tahun 1809, T. Clausen di tahun 1844, M. Reiss di tahun 1871 yang kemudian dilanjutkan oleh G. Tarry. Nanti di tahun 1892, W. W. Rose Ball menulis sebuah jurnal dalam Mathematical Recreations and Problems yang berisi tentang bagaimana memodelkan permasalahan Jembatan Koningsberg kedalam sebuah graph seperti yang terlihat pada Gambar 2 berikut

Gambar 2. Bentuk graph dari jembatan di Kota Koningsberg.


Berdasarkan Gambar 2, setiap daerah A, B, C dan D, dimisalkan dengan sebuah titik yang selanjutnya dalam graph disebut dengan simpul atau noktah atau vertex. Sedangkan jembatan yang menghubungkan masing-masing daerah dimislkan dengan ruas garis a, b, c, d, e, f, dan g, yang selanjutnya dalam graph disebut dengan sisi atau edge. Pada simpul A, terdapat 5 sisi yang bersisian, sehingga simpul A berderajat 5. Demikian pula untuk simpul B, C, dan D masingmasing berderajat 3. Karena tidak semua simpul berderajat genap maka tidak mungkin melakukan perjalanan melintasi setiap sisi (jembatan) sebanyak satu kali lalu kemudian kembali lagi ke daerah semula. Konsep ini yang selanjutnya dikenal dengan sirkuit Euler. Graph G didefinisikan sebagai pasangan himpunan (V, E) ditulis dengan notasi G = (V, E). V adalah himpunan tidak kosong dari simpul-simpul (vertices atau node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul. Berdasarkan definisi graph tersebut, jelas bahwa V tidak boleh kosong. Dengan demikian, kemungkinan bentuk graph adalah sebagai berikut 

Sebuah graph dimungkinkan hanya terdiri dari satu simpul atau vertex saja. Graph ini dinamakan graph trivial.

Gambar 3. 

Sebuah graph dimungkinkan mempunyai simpul yang tak terhubung dengan simpul yang lain.

Gambar 4.




Sebuah graph belum tentu semua simpulnya terhubung oleh sisi.

Gambar 5. 

Sebuah graph dimungkinkan semua simpulnya saling berhubungan.

Gambar 6. Simpul pada graph dapat diberi label dengan huruf kecil seperti a, b, c, ..., dengan bilangan asli 1, 2, 3, ..., atau dengan gabungan keduanya. Sedangkan sisi yang menghubungkan dua simpul misalkan u dan v dinyatakan dengan pasangan (u, v), atau dinyatakan dengan lambang e1, e2, .... Atau dapat ditulis sebagai en = (u, v), dengan n adalah bilangan asli.

2.

Jenis-Jenis Graph

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graph, maka secara umum graph dapat digolongkan menjadi dua jenis yaitu 

Graph Sederhana (simple graph)  Graph sederhana tidak mengandung gelang maupun sisi ganda.  Sisinya adalah pasangan tak-terurut. Sehingga sisi (u, v) = (v, u).



Graph tak-Sederhana (unsimple graph)  Graph tak-sederhana mengandung sisi ganda dan atau gelang.  Ada dua macam graph tak-sederhana yaitu graph ganda (multigraph) dan graph semu (pseudograph).  Graph ganda adalah graph yang mengandung sisi ganda. Sisi ganda yang menghubungkan kedua simpul bisa lebih dari dua buah.


 Graph semu (pseudograph) adalah graph yang mengandung gelang (loop). Graph semu lebih umum daripada graph ganda. Jadi graph semu bisa saja bersifat graph ganda. Tetapi tidak sebaliknya.

Contoh 1. Perhatikan Gambar 7 berikut

(a) (b) (c) Gambar 7. (a). Graph sederhana; (b). Multigraph; (c). Pseudograph Gambar 7 memperlihatkan tiga buah graph. 

Gambar 7.(a), disebut graph sederhana. V = {1, 2, 3} E = {e1, e2, e3}



Gambar 7.(b), disebut sebagai multigraph. V = {1, 2, 3} E = {e1, e2, e3, e4, e5}



Gambar 7.(c), disebut sebagai pseudograph (meskipun juga bersifat mulitgraph). V = {1, 2, 3} E = {e1, e2, e3, e4, e5, e6} Berdasarkan jumlah simpul pada suatu graph, maka graph digolongkan

menjadi dua jenis yaitu: 

Graph Berhingga (limited Graph) Graph berhingga adalah graph dengan jumlah simpul berhingga.




Graph tak-berhingga (unlimited graph) Graph tak-berhingga adalah graph dengan jumlah simpul tak berhingga banyaknya. Berdasarkan orientasi arah pada sisi graph, dibedakan menjadi 3 jenis yaitu:



Graph tak-berarah (undirected graph)  Sisinya tidak mempunyai orientasi arah.  Urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan sehingga (u, v) = (v, u) merupakan sisi yang sama.



Graph berarah (directed graph)  Sisinya mempunyai orientasi arah dan biasa disebut dengan busur (arc).  Urutan pasangan simpul yang dihubungkan oleh sisi diperhatikan. Artinya (u, v) dan (v, u) menyatakan dua busur yang berbeda.  Untuk busur (u, v), simpul u dinamakan simpul asal (initial vertex) dan simpul v dinamakan simpul terminal (terminal vertex).  Pada graph berarah gelang diperbolehkan sedangkan sisi ganda tidak.



Graph ganda berarah (directed multigraph)  Pada dasarnya sifat dan karakteristiknya sama dengan graph berarah hanya saja pada graph-ganda berarah, gelang dan sisi ganda diperbolehkan ada.

Contoh 2. Perhatikan Gambar 8 berikut

Vertex Derajat masuk Derajat keluar (a)


1

2

3

4

2

2

2

1

1

3

1

2

Vertex Derajat masuk Derajat keluar

1

2

3

3

4

1

3

2

3

(b) Gambar 8. (a). Graph berarah; (b). Graph-ganda berarah 3. Terminologi Dasar

Ada beberapa terminologi (istilah) dasar yang berkaitan dengan graph. Beberapa diantaranya dijabarkan sebagai berikut: 

Subgraph dan Komplemen Subgraph Misalkan G = (V, E) adalah sebuah graph. G1 = (V1, E1) adalah subgraph dari G jika V1 ⊆ V dan E1 ⊆ E. Sedangkan Komplemen dari subgraph G1 terhadap graph G adalah graph G2 = (V2, E2) sedemikian sehingga E2 = E – E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya. Perhatikan Gambar 9 berikut

(a) (b) (c) Gambar 9. (a). Graph G; (b). Subgraph dari G (G1); (c). Komplemen dari G1




Subgraph yang Direntang (Spanning Subgraph) Subgraph G1 = (V1, E1) dari G = (V, E) dikatakan spanning subgraph jika V1 = V. Dalam hal ini G1 mengandung semua simpul dari G.

(a) (b) (c) Gambar 10. (a). Graph G; (b). Subgraph dari G; (c). Spanning subgraph 

Derajat (Degree) Derajat suatu simpul pada graph, disimbolkan d(v) adalah jumlah sisi yang bersisian dengan simpul tersebut.

(a) (b) (c) Gambar 11. (a). Graph G1; (b). Graph G2; (c). Graph G3. Pada Graph G1: d(1) = d(4) = 2 d(2) = d(3) = 3 Pada Graph G2: d(1) = 3, bersisian dengan ruas ganda. d(3) = 4, bersisian dengan loop. Catatan: loop dihitung berderajat dua; d(v) = 2. Hal ini dikarenakan loop direpresentasikan sebagai (v, v) dan simpul v bersisian dua kali pada sisi (v, v). Pada Graph G3: d(5) = 0, disebut simpul terpencil / simpul terisolasi. d(4) = 1, disebut simpul akhir atau simpul bergantung.


Lemma Jabat Tangan Jumlah derajat semua simpul pada suatu graph adalah genap, yaitu dua kali jumlah sisi pada graph tersebut. Dengan kata lain, jika G = (V, E), maka

 d v  2 | E | vV

Lemma jabat tangan juga benar untuk graph berarah, dalam hal ini d(v) = din(v) + dout(v) Perhatikan kembali Gambar 11. Jumlah derajat seluruh simpul pada Gambar 11.(a) adalah d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10 = 2 x jumlah sisi = 2 x 5 Jumlah derajat seluruh simpul pada Gambar 11.(b) adalah d(1) + d(2) + d(3) = 3 + 3 + 4 = 10 = 2 x jumlah sisi = 2 x 5 Jumlah derajat seluruh simpul pada Gambar 11.(c) adalah d(1) + d(2) + d(3) + d(4) + d(5) = 2 + 2 + 3 + 1 + 0 = 10 = 2 x jumlah sisi = 2 x4 

Ketetanggaan (Adjacent) Dua buah simpul dikatakan bertetangga jika keduanya terhubung langsung dengan sebuah sisi. Perhatikan kembali Gambar 11. Pada graph G1, simpul 1 bertetangga dengan simpul 2 dan simpul 3, tetapi tidak bertetangga dengan simpul 4.



Bersisian (Incidency) Untuk sembarang sisi e = (u, v), sisi e dikatakan bersisian dengan simpul u dan simpul v. Perhatikan kembali Gambar 11. Sisi e4 pada graph G2 bersisian dengan simpul 2 dan simpul 3.



Simpul Terpencil (Isolated Vertex) Simpul terpencil adalah simpul yang tidak mempunyai sisi yang bersisian dengannya. Perhatikan graph G3 pada Gambar 11. Simpul 5 adalah simpul terpencil.



Graph Kosong (Null Graph atau Empty Graph)


Graph kosonng adalah graph yang himpunan sisinya merupakan himpunan kosong. Graph kosong biasa ditulis dengan Nn dengan n adalah jumlah simpul.

Gambar 12. Graph Kosong N5 

Gelang (Loop) Loop adalah sisi yang menghubugkan sebuah simpul yang sama. e5 pada Graph G2 Gambar 11 disebut loop.



Lintasan (Path) Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujan vn di dalam graph G adalah barisan berselang seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, ..., vn-1, en, vn sedmikian sehingga e1 = (v0, v1), e2 = (v1, v2), ..., en = (vn-1, vn) adalah sisi-sisi dari graph. Catatan:  Simpul dan sisi yang dilalui didalam lintasan boleh berulang.  Sebuah lintasan dikatakan lintasan sederhana (simple path) jika semua simpulnya berbeda (setiap sisi yang dilalui hanya satu kali).  Lintasan yang berawal dan berakhir pada simpul yang sama disebut lintasan tertutup (closed path), sedangkan lintasan yang tidak berawal dan berakhir pada simpul yang sama disebut lintasan terbuka (open path). Mislanya pada Gambar 11 (b); 1, e1, 2, e4, 3, e5, 3, adalah lintasan dari simpul 1 ke simpul 3 yang melalui sisi e1, e4, dan e5.



Sirkuit atau Siklus (Cycle) Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus. Sebuah sirkuit dikatakan sirkuit sederhana jika setiap sisi yang dilalui berbeda. Pada Gambar 11(a), 1 , 2, 3, 1, adalah sebuah sirkuit sederhana dengan panjang 3, yang dihitung berdasarkan jmlah sisi di dalam


sirkuit tersebut. Sedangkan 1, 2, 3, 4, 2, 1, bukan merupakan sirkuit sederhana karena sisi (1, 2) dilalui sebanyak dua kali. 

Cut-set Cut-set dari graph terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi cut-set menghasilkan dua buah komponen terhubung. Yang harus diingat adalah di dalam cut-set tidak boleh mengandung himpunan bagian yang juga merupakan cut-set.

Gambar 13. Sebuah graph terhubung menjadi sebuah graph tak terhubung dikarenakan adanya cut set. Pada Gambar 13, jika kita membuang (1, 2), (1, 4), (6, 4), dan (6, 5) maka graph menjadi tidak terhubung. Jadi himpunan {(1, 2), (1, 4), (6, 4), (6, 5)} adalah cut-set. Himpunan {(1, 2), (2, 4)} juga merupakan cut-set. Tetapi himpunan {(1, 2), (2, 4), (4, 5)} bukan merupakan cut-set karena terdapat {(1, 2), (2, 4)} yang juga merupakan cut-set dan merupakan himpunan bagian dari {(1, 2), (2, 4), (4, 5)}.


PENDAHULUAN MODUL I. 1 Teori Graph Pendahuluan Aswad 2013 Blog: 1

Recommend Documents