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”.

  • Contoh penerapan alogoritma Fleury pada graph Euler G . Perhatikan bahwa setiap titik G berderajat genap dan G graph terhubung.

STEP 1 : Pilih titik v1. Tulis J0 = v0

STEP 2 : Jejak J0 telah terpilih.

Pilih sisi e1 = v1 v5.

Tulis jejak J1 = (v1, e1, v5)

Pilih sisi e2 = v5 v6.

Tulis jejak J2 = (v1, e1, v5, e2, v6, e3, v2,e4, v1, e5, v6)

Pilih sisi e3 = v6 v2.

Tulis jejak J3 = (v1, e1, v5, e2, v6, e3, v2)

Pilih sisi e4 = v2 v1.

Tulis jejak J4 = (v1, e1, v5, e2, v6, e3, v2,e4, v1)

Pilih sisi e5 = v1 v6.

Tulis jejak J5 = (v1, e1, v5, e2, v6, e3, v2,e4, v1, e5, v6)

Pilih sisi e6 = v6 v2.

Tulis jejak J6 = (v1, e1, v5, e2, v6, e3, v2,e4, v1, e5, v6, e6, v2)

Pilih sisi e7 = v2 v3.

Tulis jejak J7 = (v1, e1, v5, e2, v6, e3, v2,e4, v1, e5, v6, e6, v2, e7, v3)

Pilih sisi e8 = v3 v6.

Tulis jejak J8 = (v1, e1, v5, e2, v6, e3, v2,e4, v1, e5, v6, e6, v2, e7, v3,e8,v6)

Pilih sisi e9 = v6 v7.

Tulis jejak J9 = (v1, e1, v5, e2, v6, e3, v2,e4, v1, e5, v6, e6, v2, e7, v3,e8,v6, e9, v7)

Pilih sisi e10 = v7 v3.

Tulis jejak J10 = (v1, e1, v5, e2, v6, e3, v2,e4, v1, e5, v6, e6, v2, e7, v3 e8,v6, e9, v7, e10 ,v3)

Pilih sisi e11 = v3 v4.

Tulis jejak J11 = (v1, e1, v5, e2, v6, e3, v2,e4, v1, e5, v6, e6, v2, e7, v3,e8,v6, e9, v7, e10 ,v3, e11, v4)

Pilih sisi e12 = v4 v8.

Tulis jejak J12 = (v1, e1, v5, e2, v6, e3, v2,e4, v1, e5, v6, e6, v2, e7, v3,e8,v6, e9, v7, e10 ,v3, e11, v4, e12, v8)

Pilih sisi e13 = v8 v7.

Tulis jejak J13 = (v1, e1, v5, e2, v6, e3, v2,e4, v1, e5, v6, e6, v2, e7, v3,e8,v6, e9, v7, e10 ,v3, e11, v4, e12, v8, e13, v7)

Pilih sisi e14 = v7 v4.

Tulis jejak J14 = (v1, e1, v5, e2, v6, e3, v2,e4, v1, e5, v6, e6, v2, e7, v3,e8,v6, e9, v7, e10 ,v3, e11, v4, e12, v8, e13, v7, e14, v4)

Pilih sisi e15 = v4 v1.

Tulis jejak J15 = (v1, e1, v5, e2, v6, e3, v2,e4, v1, e5, v6, e6, v2, e7, v3,e8,v6, e9, v7, e10 ,v3, e11, v4, e12, v8, e13, v7, e14, v4, e15, v1)

STEP 3:

Jadi J15 = ( v1, e1, v5, e2, v6, e3, v2,e4, v1, e5, v6, e6, v2, e7, v3,e8,v6, e9, v7, e10 ,v3, e11, v4, e12, v8, e13, v7, e14, v4, e15, v1) adalah sirkit euler di graph G.

Sisi sirkit Euler J15 pada G secara berturt-turut adalah e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12, e13, e14, e15.

Algoritma Fleury dapat dimodifikasi sehingga bisa digunakan untuk mencari jejak Euler buka pada graph semi Euler, yaitu dengan mengganti graph Euler G pada input dengan graph semi Euler G. Step 1 diganti menjadi : pilih sebuah titik v0 yang berderajat ganjil di G. Tulis jejak J0 = v0, dan pada step 3, pesannya menjadi: Ji+1 jejak Euler buka di graph G.

RELATED POST ::

About NICO MATEMATIKA

Welcome to my blog. My name is Nico. Admin of this blog. I am a student majoring in mathematics who dreams of becoming a professor of mathematics. I live in Kwadungan, Ngawi, East Java. Hopefully in all the posts I can make a good learning material to the intellectual life of the nation. After the read, leave a comment. I always accept criticism suggestion to build a better me again .. Thanks for visiting .. : mrgreen:

Posted on August 17, 2011, in teory graph and tagged , . Bookmark the permalink. 4 Comments.

  1. ampun dijee, walau saya kul math tp masih puyeng liat ini

  2. Wadduh pusing tujuh keliling. tapi asyikkkk.
    sekalian nitip neh. buat TV Online Anda disini
    http://irfanhandi.wordpress.com/2011/08/17/membuat-tv-online-di-wordpress/

  3. hm…. materi kuliah ya? sip deh…

  1. Pingback: daftar isi « matematika blog for education

LEAVE A COMMENT IN HERE. COMMENTING IN HERE IS ALWAYS AUTO APPROVE. PLEASE NO SPAM!!! BECAUSE I HATE SPAM... THANKS A LOT..... :mrgreen:

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: