Teori Graf

Teori graf adalah cabang ilmu yang mempelajari sifat-sifat graf. Secara umum suatu Graf adalah himpunan busur (edge) dan simpul (vertex atau node) yang banyaknya berhingga dan busur busurnya menghubungkan sebagian atau keseluruhan pasangan dari simpulsimpulnya.

Graf G(V, E) terdiri atas himpunan simpul yang dinyatakan dengan V = {v1,v2, v3, ..., vn} dan himpunan busur yang dinyatakan dengan E = {e1, e2, e3, ..., en} dengan ei = (vi, vj) merupakan busur yang menghubungkan simpul vi dan simpul vj."

Himpunan E dinyatakan sebagai pasangan dari simpul yang ada dalam V. Sebagai contoh definisi dari graf pada gambar di atas adalah : V = {1,2,3,4,5,6} dan E = {(1,2),(1,5),(2,3),(3,4),(4,5),(5,2),(4,6)}

Beberapa terminologi berhubungan dengan teori graf :

• Degree atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.
• Path suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path b-> c -> g
• Cycle siklus ? path yang kembali melalui titik asal 2 f -> c -> d -> e kembali ke 2.
• Tree merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a dalam digraf diatas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge dalam suatu tree adalah nV - 1. Dimana nV adalah jumlah vertex
• Graf Tak Berarah (Undirected Graph) Graf G disebut graf tak berarah (undirected graph) jika setiap sisinya tidak berarah. Dengan kata lain (v_i,v_j)=(v_j,v_i)

Graf Berarah (Directed Graph) Graf G disebut graf berarah (directed graph) jika setiap sisinya berarah. Titik awal dari suatu sisi disebut verteks awal (initial vertex) sedangkan titik akhir dari suatu sisi disebut verteks akhir (terminal vertex). Loop pada graf adalah sisi yang verteks awal dan verteks akhirnya sama

Read more »

Graf Planar

Sebuah graf G = (V,E) disebut graf planar apabila graf tersebut dapat digambarkan dalam sebuah bidang datar tanpa ada sisi/edge yang saling berpotongan (kecuali sisi sisi berpotongan pada sebuah verteks).


Contoh Graf Planar



Contoh Graf Non Planar



Teorema Kuratowski :
“ Graf G bersifat planar jika dan hanya jika ia tidak mengandung subgraf yang sama dengan salah satu graf kuratowski atau homomorfis dengan salah satunya “

Sifat GRAF Kuratowski adalah :

1.kedua graf kuratowski adalah graf teratur
2.kedua graf kuratowski adalah graf non-planar
3.penghapusan sisi atau simpul dari graf kuratowski menyebabkan menjadi graf planar
4.K5 adalah graf non-planar dengan jumlah simpul minimum, K3,3 adalah graf non-planar dengan jumlah sisi minimum.

Read more »

DASAR – DASAR TEORI GRAF

Kelahiran Teori Graf

Teori graf pertama kali dikembangkan oleh Leonhard Euler dalam memecahkan masalah jembatan Königsberg (tahun 1736). Permasalahannya adalah " Apakah bisa seseorang  melalui  sekali setiap jembatan yang menghubungkan kota-kota tersebut, dan kembali lagi ke kota dari mana ia berjalan".

 

Graf yang merepresentasikan jembatan Königsberg :

Simpul (vertex)---  menyatakan daratan

Ruas (edge) ---menyatakan jembatan

Bisakah melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula?
• Perjalanan Euler adalah :
Perjalanan dari suatu simpul kembali ke simpul tersebut dengan melalui setiap ruas tepat satu kali.
• Perjalanan Euler akan terjadi, jika :
- Graf terhubung.
- Banyaknya ruas yang datang pada setiap simpul adalah genap.

Definisi Graf

Graf G (V, E), adalah koleksi atau pasangan dua himpunan
(1) Himpunan V yang elemennya disebut simpul atau titik, atau vertex, atau point, atau node.
(2) Himpunan E yang merupakan pasangan tak terurut dari simpul, disebut ruas atau rusuk, atau sisi, atau edge, atau line.

Banyaknya simpul (anggota V) disebut order Graf G, sedangkan banyaknya ruas (anggota E) disebut ukuran (size) Graf G.

G1 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }

G2 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) }
= { e1, e2, e3, e4, e5, e6, e7}

G3 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }
= { e1, e2, e3, e4, e5, e6, e7, e8}

• Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan ruas berganda atau ruas sejajar (multiple edges atau paralel edges), karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3.

• Pada G3, sisi e8 = (3, 3) dinamakan gelung atau self-loop karena ia berawal dan berakhir pada simpul yang sama.

Read more »