1. PENDAHULUAN

 

  • Pada cabang matematika yang disebut Teori Graf, suatu Graf tidak berhubungan dengan graf yang menggambarkan data, seperti kemajuan bursa saham atau pertumbuhan planet. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

  • Di dalam teori Graf, graf adalah kumpulan titik yang mungkin terhubung maupun tidak terhubung dengan titik lainnya dengan garis. Tidak penting seberapa besar titik itu, atau seberapa panjang garisnya, atau apakah garis itu lurus atau melengkung. Dan titik itu puntidak harus bulat. Intinya adalah bahwa titik – titik itu terhubung oleh garis.

  • Gambar di bawah ini sebuah graf yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah

1.1 SEJARAH GRAF

 

Koenigsberg Bridge Problem” (PRUSIA, 1736)

 

Apakah mungkin melalui ketujuh buah jembatan masing-masing tepat satu kali, dan kembali ketempat semula (Euler Trip)?. Pertama kali graf diaplikasikan oleh LEONHARDT EULER (warga swiss) yang menyimpulkan Euler Trip bisa dilakukan jika derajat setiap titik adalah genap.

1. 2. DEFINISI GRAF

 

Graf G =G (V,E) didefinisikan sebagai pasangan himpunan (V,E), dimana :

V = himpunan vertex (titik) yang tidak kosong

= v1, v2, … , vn

dan

E = himpunan edge (garis/garis) yang menghubungkan sepasang vertex

= e1, e2, … , en


G1G2G3

Contoh 1.

Pada Gambar 2, 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, garis e3 = (1, 3) dan garis e4 = (1, 3) dinamakan garis parallel (multiple edges atau paralel edges) karena kedua garis ini menghubungi dua buah titik yang sama, yaitu titik 1 dan titik 3.

  • Pada G3, garis e8 = (3, 3) dinamakan loop atau kalang karena ia berawal dan berakhir pada titik yang sama.

1.3. JENIS-JENIS GRAF

Berdasarkan ada tidaknya loop atau garis paralel pada suatu graf, maka graf digolongkan menjadi dua jenis:

1. Graf sederhana (simple graph).

Graf yang tidak mengandung loop maupun garis paralel (dinamakan graf sederhana). G1 pada Gambar 2 adalah contoh graf sederhana

2. Graf tak-sederhana (unsimple-graph).

Graf yang mengandung garis paralel atau loop dinamakan graf tak-sederhana (unsimple graph). G2 dan G3 pada Gambar 2 adalah contoh graf tak-sederhana

 

Berdasarkan orientasi arah pada garis, maka secara umum graf dibedakan menjadi 2 jenis

  1. Graf tak berarah (undirected graph)

Graf yang garisnya tidak mempunyai orientasi arah disebut graf tidak berarah. Pada graf tak berarah, urutan pasangan titik yang dihubungkan oleh garis tidak diperhatikan. Jadi (vj, vk) = (vk, vj) adalah garis yang sama. Graf G1 s/d G3 pada contoh diatas merupakan graf tidak berarah.

  1. Graf berarah (directed graph)

Graf yang setiap garisnya diberikan orientasi arah disebut sebagai graf berarah. Garis berarah ditandai dengan tanda panah. Pada graf berarah, (vj, vk) dan (vk, vj) menyatakan dua arah yang berbeda, dengan kata lain (vj, vk) ≠ (vk, vj). Graf G4 dan G5 berikut merupakan graf berarah

(a) G4 (b) G5

1.4 CONTOH TERAPAN GRAF

1
.
Rangkaian listrik.

(a) (b)

2. Isomer senyawa kimia karbon


metana (CH
4) etana (C2H6) propana (C3H8)

3. Pengujian program

read(x);

while x <> 9999 do

begin

if x < 0 then

writeln(‘Masukan tidak boleh negatif’)

else

x:=x+10;

read(x);

end;

writeln(x);

Keterangan: 1 : read(x)

2 : x <> 9999

3 : x < 0

4 : writeln(‘Masukan tidak boleh negatif’);

5 : x := x + 10

6 : read(x)

7 : writeln(x)

5. Terapan graf pada teori otomata [LIU85].

M
esin jaja (
vending machine)

Keterangan:

a : 0 sen dimasukkan

b : 5 sen dimasukkan

c : 10 sen dimasukkan

d : 15 sen atau lebih dimasukkan

1.5. TERMINOLOGI GRAF

1.5.1 Ketetanggaan (Adjacent)

Dua buah titik dikatakan bertetangga bila keduanya terhubung langsung.

Tinjau graf G1 : titik 1 bertetangga dengan titik 2 dan 3, titik 1 tidak bertetangga dengan titik 4

 

 

 

 

 

 

 

G1 G2 G3

1.5.2. Bergarisan (Incidency)

Untuk sembarang garis e = (vj, vk) dikatakan

e bergarisan dengan titik vj , atau

e bergarisan dengan titik vk

Tinjau graf G1: garis (2, 3) bergarisan dengan titik 2 dan titik 3,

garis (2, 4) bergarisan dengan titik 2 dan titik 4,

tetapi garis (1, 2) tidak bergarisan dengan titik 4.

 

 

1.5.3. Titik Terpencil (Isolated Vertex)

Titik terpencil ialah titik yang tidak mempunyai garis yang bergarisan dengannya.

Tinjau graf G3: titik 5 adalah titik terpencil.

 

1.5.4. Graf Kosong (null graph atau empty graph)

Graf yang himpunan garisnya merupakan himpunan kosong (Nn).

Graf N5 :

1.5.5. Derajat (Degree)

Derajat suatu titik adalah jumlah garis yang bergarisan dengan titik tersebut. Notasi: d(v).

Tinjau graf G1: d(1) = d(4) = 2

d(2) = d(3) = 3

Tinjau graf G3: d(5) = 0 titik terpencil

d(4) = 1 titik pendant

Tinjau graf G2: d(1) = 3 memuat garis paralel

d(2) = 4 memuat loop

 

Pada graf berarah,

din(v) = derajat-masuk (in-degree)

= jumlah busur yang masuk ke simpul v

dout(v) = derajat-keluar (out-degree)

= jumlah busur yang keluar dari simpul v

d(v) = din(v) + dout(v)

 

G4G5

Tinjau graf G4:

din(1) = 2; dout(1) = 1

din(2) = 2; dout(2) = 3

din(3) = 2; dout(3) = 1

din(4) = 1; dout(3) = 2

Lemma Jabat Tangan (Handshaking). Jumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali jumlah sisi pada graf tersebut.

Dengan kata lain, jika G = (V, E), maka

Tinjau graf G1: d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10

= 2 jumlah sisi = 2 5

Tinjau graf G2: d(1) + d(2) + d(3) = 3 + 3 + 4 = 10

= 2 jumlah sisi = 2 5

Tinjau graf G3: d(1) + d(2) + d(3) + d(4) + d(5)

= 2 + 2 + 3 + 1 + 0 = 8

= 2 jumlah sisi = 2 4

 

 

 

 

 

 

 

 

 

Akibat dari lemma (corollary):

 

Teorema: Untuk sembarang graf G, banyaknya simpul berderajat ganjil selau genap.

Contoh 2. Diketahui graf dengan lima buah simpul. Dapatkah kita menggambar graf tersebut jika derajat masing-masing simpul adalah:

(a) 2, 3, 1, 1, 2

(b) 2, 3, 3, 4, 4

Penyelesaian:

  1. tidak dapat, karena jumlah derajat semua simpulnya ganjil

(2 + 3 + 1 + 1 + 2 = 9).

(b) dapat, karena jumlah derajat semua simpulnya genap

(2 + 3 + 3 + 4 + 4 = 16).

1.5.6 Subgraph dan Komplemen Subgraph

Misalkan G = (V, E) adalah sebuah graf. G1 = (V1, E1) adalah subgraph dari G jika V1 V dan E1E.

Komplemen dari subgraph G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = EE1 dan V2 adalah himpunan titil yang anggota-anggota E2 bersisian dengannya.

(a) Graf G1 (b) Sebuah subgraph (c) komplemen dari subgraph (b)

 

 

1.5.7 Graf Berbobot (Weighted Graph)

Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).

 

 

 

 

 

 

 

About these ads