Category Archives: teory graph

MENCARI JARAK MINIMUM PADA GRAPH SEMI EULER

Perhatikan graph bobot G pada gambar di atas merepresentasikan suatu jaringan jalan di sekitar kantor pos tertentu. Misalkan titik v5 merepresentasikan kantor pos. Dalam hal ini kantor pos tidak mungkin menelusuri setiap jalan tepat satu kali berawal dan berakhir di kantor pos, karena graph G bukan graph Euler (karena titik v1 dan titik v10 berderajat ganjil). Ini berarti harus ada jalan-jalan yang harus ditelusuri lebih dari satu kali. Untuk menentukan jalan-jalan yang harus ditelusuri lebih dari satu kali agar total jarak yang ditempuh minimum, kita cari lintasan terpendek yang menghubungkan v1 dan titik v1. Dengan menggunakan algoritma Djikstra, diperoleh lintasan terpendek dari titik v1 ke titik v10 adalah P = (v1, v4, v5, v6, v7, v8, v10), seperti tampak pada gambar berikut. Read the rest of this entry

ALGORITMA FLEURY

Leonhard Euler

Image via Wikipedia

Algoritma Fleury digunakan untuk mengkontruksi sebuah sirkit Euler pada graph Euler.

  • Langkah-langkah dari algoritma Fleury:

INPUT : Graph Euler

STEP 1 : Pilih sebuah titik v0 di graph G Tulis J0  = V0

STEP 2 : Misal jejak J = (v0 ,e1 ,v1 ,…,vi-1 ,ei ,vi ) telah terpilih.Selanjutnya, pilih sebuah sisi ei+1 dari E (G)-{e1, e2, …,ei } sedemikian hingga :

 (i)  sisi ei+1  terkait di titik vi , dan

 (ii) sisi e  bukan sisi pemutus pada graph Gi , dengan Gi = G – {e1, e2, …,ei }, kecuali tidak ada pilihan lain.

Tulis jejak Ji+1 = Ji U {e}

STEP 3 : STOP bila STEP 2 tidak bisa dilanjutkan; dan beri pesan : “Ji+1  adalah jejak Euler tutup (sirkit Euler) di graph G”. Read the rest of this entry

ALGORITMA DUA SISI OPTIMAL

Algoritma Penyisipan-titik

INPUT                        : Graph bobot komplit dengan n titik, n > 3

STEP 1            : Pilih sebuah G sebarang untuk membentuk sikel-1 C1 di G.

STEP 2            : Jika sikel-k Ck di G telah terbentuk dan 1 ≤ n < k, maka tentukan sebuah titik vk yang tidak terletak di Ck dan terdekat ke sebuah titik uk di Ck sikel Hamilton yang di kehendaki dan stop.

STEP 3            : Misal Ck+1 adalah sikel-(k+1) yang di dapat dengan menyisipkan titik vk persis sebelum uk di Ck dan kembali ke STEP 2.

Read the rest of this entry

GRAPH HAMILTON

Graph hamilton adalah graph yang memuat sikel hamilton. Sedangkan sikel hamilton adalah sebuah sikel yang memuat semua titik di graph.

Contoh :

Perhatikan graph dibawah ini :

Pada graph H terdapat sikel hamilton yaitu sikel (V1,V2,V3,V4,V5,V1). Jadi graph H adalah graph hamilton.

Kemudian perhatikan pada graph G. Kita tidak bisa  membuat sikel yang memuat titik di graph G. Jadi graph G bukan graph hamilton.

Kemudian perhatikan graph G1 dibawah ini :

Graph tersebut memuat lintasan P=(V2,V1,V5,V4,V3) lintasan ini disebut dengan lintasan hamilton karena lintasan ini memuat  semua titik di graph G1. Perhatikan bahwa jika sebuah graph memuat sikel hamilton maka graph tersebut pasti memuat lintasan hamilton. Tetapi sebaliknya tidak berlaku,  artinya jika sebuah graph memuat lintasan hamilton belum tentu memuat sikel hamilton. Misalnya pada graph G yang memuat sikel hamilton, graph G juga memuat lintasan hamilton, tetapi pada graph G1 yang mempunyai  lintasan hamilton graph G1 tersebut tidak memuat sikel hamilton.

ALGORITMA DIJKSTRA

ALGORITMA DIJKSTRA  digunakan untuk mencari rute terpendek……

berikut ini contohnya ::

Graph G dengan matrik berhubungan langsung sebagai berikut ::

A B C D E F G
A 0 60 70
B 60 0 50 50 20
C 70 50 40 70
D 50 40 0 60 50
E 20 60 0 30 40
F 70 50 30 0 50
G 40 50 0

Read the rest of this entry

%d bloggers like this: