GRAF

GRAF

Dalam matematika dan ilmu komputer, sebuah graf adalah objek dasar pelajaran dalam teori graf. Dalam bahasa sehari-hari, sebuah graf adalah himpunan dari objek-objek yang dinamakan titik, simpul, atau sudut dihubungkan oleh penghubung yang dinamakan garis atau sisi. Dalam graf yang memenuhi syarat, di mana biasanya tidak berarah, sebuah garis dari titik A ke titik B dianggap sama dengan garis dari titik B ke titik A. Dalam graf berarah, garis tersebut memiliki arah. Pada dasarnya, sebuah graf digambarkan dengan bentuk diagram sebagai himpunan dari titik-titik (sudut atau simpul) yang digabungkan dengan kurva (garis atau sisi).

Tiap-tiap diagram memuat sekumpulan obyek (kotak, titik, dan lain-lain) beserta garis-garis yang menghubungkan obyek-obyek tersebut. Garis bisa berarah ataupun tidak berarah. Garis yang berarah biasanya digunakan untuk menyatakan hubungan yang mementingkan urutan antar objek-objek. Urut-urutan objek akan mempunyai arti yang lain jika arah garis diubah. Sebagai contoh adalah garis komando yang menghubungkan titik-titik struktur sebuah organisasi. Sebaliknya, garis yang tidak berarah digunakan untuk menyatakan hubungan antar objek-objek yang tidak mementingkan urutan. Sebagai contoh adalah garis untuk menyatakan jarak hubung 2 kota pada Gambar 2. Jarak dari kota A ke kota B sejauh 200 km akan sama dengan jarak dari kota B ke kota A. Apabila jarak 2 tempat tidak sama jika dibalik (misalnya karena harus melalui jalan memutar), maka garis yang digunakan haruslah garis yang berarah.

1.1    Definisi Graf

Graf merupakan struktur diskrit yang terdiri himpunan sejumlah berhingga obyek yang disebut simpul (vertices, vertex) dan himpunan sisi (edges) yang menghubungkan simpul-simpul terseut. terdiri dari dari Graf digunakan untuk merepresentasikan objekobjek diskrit dan hubungan antara objek-objek tersebut.

Notasi sebuah graf adalah G = (V, E), dimana : 

·    V merupakan himpunan tak kosong dari simpul-simpul (vertices), misalkan V = { v1 , v2 , ... , vn }

·    E merupakan himpunan sisi – sisi (edges) yang menghubungkan sepasang simpul, misalkan

E = {e1 , e2 , ... , en }

Contoh : 

Graf dari masalah jembatan Königsberg dapat disajikan sebagai berikut :

Misalkan graf tersebut adalah G(V, E) dengan

V     = { A, B, C, D }

E     = { (A, C), (A, C), (A, B), (A, B), (B, D), (A, D), (C, D)}

= { e1, e2, e3, e4, e5, e6, e7}

Pada graf tersebut sisi e1 = (A, C) dan sisi e2 = (A, C) dinamakan sisi-ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul A dan simpul C. Begitu pun dengan sisi e3 dan sisi e4. Sementara itu, pada graf diatas, tidak terdapat gelang (loop), yaitu sisi yang berawal dan berakhir pada simpul yang sama.

Dari definisi graf, himpunan sisi (E) memungkinkan berupa himpunan kosong. Jika graf tersebut mempunyai himpunan sisi yang merupakan himpunan kosong maka graf tersebut dinamakan graf kosong (null graph atau empty graph).

Contoh : 

Graf kosong dengan 3 simpul (graf N3 )

Dengan memperhatikan kondisi sisinya, suatu graf dapat dikategorikan sebagai graf tidak berarah dan graf berarah. Graf tidak berarah, seperti telah dijelaskan pada contoh graf untuk jembatan Königsberg. Sementara itu, graf berarah (directed graph, digraph) merupakan graf yang mempunyai sisi yang berarah, artinya satu buah simpul yang dihubungkan oleh sisi tersebut merupakan simpul awal (initial vertex) dan simpul yang lain dikatakan sebagai simpul akhir (terminal vertex). 

Contoh : 

Graf berikut merupakan graf berarah :

Terlihat bahwa e1 = (P, S), e3 = (R, Q), dan e5 = (Q, Q) R

Simpul P merupkan simpul awal bagi sisi e1 dan simpul S merupakan simpul akhir bagi sisi e1.

1.2   Terminologi Graf

Ada beberapa terminologi graf yang perlu diketahui, antara lain : ketetanggaan antara dua simpul, bersisian , derajat suatu simpul, dan lain-lain. Berikut ini adalah beberapa terminoogi yang penting, yaitu : 

1.  Bertetangga (Adjacent)

Dua buah simpul dikatakan bertetangga jika kedua simpul tersebut terhubung langsung oleh suatu sisi.

Contoh :

Perhatikan graf berikut :

Pada graf diatas : simpul P bertetangga dengan simpul Q dan S, tetapi simpul P tidak bertetangga dengan simpul R.

2. Bersisian (Incidency)

Suatu sisi e dikatakan bersisian dengan simpul v1 dan simpul v2 jika e menghubungkan kedua simpul tersebut, dengan kata lain e = (v1, v2).

Contoh :

Perhatikan graf dari masalah jembatan Königsberg berikut ini :

maka e1 bersisian dengan simpul A dan simpul C , tetapi sisi tersebut tidak berisian dengan simpul B.

3. Simpul Terpencil (Isolated Vertex)

Jika suatu simpul tidak mempunyai sisi yang bersisian dengannya maka simpul tersebut dinamakan simpul terpencil.

Contoh :

Perhatikan graf berikut :

Simpul T dan simpul U merupakan simpul terpencil.

4. Derajat (Degree)

Derajat suatu simpul merupakan jumlah sisi yang bersisian dengan simpul tersebut. Misalkan, suatu simpul v mempunyai 3 buah sisi yang bersisian dengannya maka dapat dikatakan simpul tersebut berderajat 3, atau dinotasikan oleh d(v) = 3.

Contoh :

Perhatikan graf berikut :

Pada graf diatas : d(P) = d(Q) = d (S)= 5, sedangkan d(R) = 3.

Derajat sebuah simpul pada suatu graf berarah dijelaskan sebagai berikut :

·         d_in(v) merupakan jumlah busur yang masuk ke simpul v

·         d_out(v) merupakan jumlah busur yang keluar dari simpul v

Dengan demikian derajat pada simpul tersebut, diperoleh : d(v) = d_in(v) + d_out(v)

5. Lintasan (Path)

Lintasan dari suatu simpul awal v0 ke simpul tujuan vT di dalam suatu graf G merupakan barisan sebuah sisi atau lebih (x0, x1), (x1, x2), (x2, x3), …, (xn-1, xn) pada G, dimana x0 = v0 dan xn = vT. Lintasan ini dinotasikan oleh :

x0, x1, x2, x3, …, xn

Lintasan ini mempunyai panjang n, karena lintasan ini memuat n buah sisi, yang dilewati dari suatu simpul awal v0 ke simpul tujuan vT di dalam suatu graf G. Suatu lintasan yang berawal dan berakhir pada simpul yang sama dinamakan Siklus (Cycle) atau Sirkuit (Circuit).

Contoh :

Perhatikan graf berikut ini :

• ·    Pada graf tersebut lintasan P, Q, R memiliki panjang 2. Sementara itu lintasan P, Q, S, R memiliki panjang 3.
• ·      Lintasan P, Q, R, S, P dinamakan siklus atau sirkuit dengan panjang 4.
• ·      Antara simpul P dan U maupun T tidak dapat ditemukan lintasan.

6. Cut-Set

Cut-set dari suatu graf terhubung G adalah himpunan sisi yang jika dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah subgraf . Pada graf di bawah, {(1,4), (1,5), (2, 3), (2,4)} adalah cut-set. Terdapat banyak cut-set pada sebuah graf terhubung. Himpunan {(1,5), (4,5)} juga adalah cut-set, {(1,4), (1,5), (1,2)} adalah cut-set, {(5,6)} juga cut-set,

tetapi {(1,4), (1,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,5), (4,5)} adalah cut-set.

1.3 Beberapa Jenis Graf

    Beberapa jenis graf tak berarah yang perlu diketahui adalah :

1.       Graf sederhana (simple graph)

Graf sederhana merupakan graf tak berarah yang tidak mengandung gelang maupun sisi-ganda. Contoh :

2.       Graf Ganda (multigraph)

Graf ganda merupakan graf tak berarah yang tidak mengandung gelang (loop).

Contoh :

Dengan demikian, graf sederhana pun merupakan graf ganda (multi graph).

3.       Graf semu (Pseudo graph)

Graf semu merupakan graf yang boleh mengandung gelang (loop).

Contoh :

1.4   Graf Isomorfik dan Homeomorfik

Perhatikan dua graf berikut ini :

Dua buah graf diatas, terdiri dari empat buah simpul dimana setiap simpul adalah berderajat tiga. Walaupun secara geometri kedua tersebut berbeda tetapi pada prinsipnya kedua graf tersebut adalah sama.

Definisi :

Dua buah graf G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul pada kedua graf tersebut dan antara sisi-sisi keduanya sehingga jika sisi e bersisian dengan simpul u dan v pada G1 maka sisi e’ pada G2 juga bersisian dengan simpul u’ dan v’.

Suatu graf dapat digambarkan dengan berbagai cara. Dua buah graf yang isomorfik adalah graf yang sama, kecuali penamaan simpul dan sisinya saja yang berbeda. Sebagai contoh dua graf diatas merupakan dua graf yang isomorfik .

Dua buah graf dikatakan isomorfik jika memenuhi ketiga syarat berikut (Deo, 1989):

1.       Mempunyai jumlah simpul yang sama.

2.       Mempunyai jumlah sisi yang sama

3.       Mempunyai jumlah simpul yang sama berderajat tertentu

Tetapi cara menunjukan dua graf yang isomorfik dapat diperhatikan pada contoh berikut ini.

Contoh :

Diketahui 2 buah graf berarah :

Periksa apakah kedua graf tersebut isomorfik? Jika ya, tentukan simpul-simpul yang saling berkorespondensi antara G1 dan G2

Jawab :

Ya, kedua graf tersebut adalah isomorfik. Terlihat graf tersebut memuat simpul dimana setiap simpulnya masing-masing berderajat tiga.

Simpul yang saling berkorespondensi dari kedua graf tersebut adalah :

·         Simpul u1 dengan simpul v1

·         Simpul u2 dengan simpul v3

·         Simpul u3 dengan simpul v5

·         Simpul u4 dengan simpul v6

·         Simpul u5 dengan simpul v4

·         Simpul u6 dengan simpul v2

Pada dua graf yang isomorfik, kedua graf tersebut memiliki matriks ketetanggaan yang sama. Perhatikan matriks ketetanggaan dari kedua graf tersebut.

Dibawah ini adalah matriks ketetanggaan dari graf G1 :

Sementara itu, berikut ini adalah matriks ketetanggaan dari graf G1 :

Terlihat bahwa kedua graf tersebut memiliki matriks ketetanggaan yang sama, yaitu MG1 = MG2.

Selanjutnya akan dijelaskan tentang definisi homeomorfik antara dua buah graf. Misalkan G2(V2, E2) diperoleh dari G1(V1, E1) dengan menambahkan simpul pada sebuah sisi atau lebih pada graf tersebut, maka graf G1(V1, E1) dan graf G2(V2, E2) dinamakan homeomorfik.

Contoh :

Perhatikan ketiga graf dibawah ini :

Ketiga graf diatas merupakan graf homeomorfik (homeomorphic graphs).