Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
TRAIL EULER MINIMAL DI DALAM GRAF BERARAH YANG TERBOBOTI Siti Julaeha 1, Murtiningrum2, Rida Novrida3, Endang Retno Nugroho 4 Dosen Jurusan Matematika, Fakultas Sains dan Teknologi, UIN Sunan Gunung Djati Bandung email: siti.julaeha @ui.ac.id 2 Mahasiswa Program Magister Matematika, Departemen Matematika FMIPA Universitas Indonesia email:
[email protected] 3 Guru SMAN 11 Kota Jambi email:
[email protected] 4 Dosen Universitas Nasional Jakarta email:
[email protected] 1
Abstract Suppose G is a Eulerian directed graph with an edge labeling. In this paper will discuss the literature studies an algorithm to construct Euler trail that starts at a node r with the lexicographic minimum label among all Euler trail that starts node r is. Keywords: Euler graph, directed graph labeling
Leonard Euler (1736) yang menulis paper
A. Pendahuluan Meskipun
merupakan
pokok
mengenai masalah jembatan Konigsberg.
bahasan yang sudah tua usianya namun
Papernya
teori graf banyak memiliki terapan sampai
mengenai teori graf [2].
saat
ini.
Graf
digunakan
merupakan
paper
pertama
untuk
Graf berarah G = (V,A) terdiri dari
merepresentasikan objek-objek diskrit dan
himpunan tak kosong V(G) sebagai
hubungan antara objek-objek tersebut.
simpul, dan A(G) sebagai busur berarah
Representasi dari graf adalah menyatakan
(arc). Pada graf berarah, simpul dapat
obyek dengan noktah, bulatan atau titik,
digambarkan sebagai titik v atau w,
sedangkan
sedangkan busur berarah {vw} A
hubungan
antara
objek
dinyatakan dengan garis.
sebagai garis yang menghubungkan kedua
Suatu graf G terhubung disebut
simpul v dan w dengan simpul v sebagai
sebagai graf Euler jika terdapat jalur
titik awal dan simpul w sebagai titik
tertutup yang melalui semua sisi di G.
ujung. Dua buah simpul v dan w
Dinamakan
demikian
sebagai
dikatakan hadir (incident) bila ada busur
penghargaan
atas
kontribusi
berarah vw yang menghubungkan kedua
bernama
simpul tersebut. Misalkan e = {vw} A
matematikawan
Swiss
yang
111
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
dan {v, w} V maka simpul v dan w
(isolated vertex) adalah terhubung secara
dikatakan bertetangga (adjacent) bila
kuat
terdapat
memiliki
sifat-sifat
keduanya. Gelang (loop) adalah busur
terhubung
secara
berarah yang berawal dan berakhir pada
connected) [2].
busur
berarah e di antara
(strongly
connected) yang
meskipun memenuhi
lemah
(weakly
simpul yang sama, tanpa melalui simpul
Graf yang dibahas dalam makalah
yang lainnya. Jumlah busur berarah yang
ini adalah graf dengan pelabelan busur
hadir pada suatu simpul v disebut dengan
dimana memenuhi sifat bahwa setiap
derajat (degree) dari simpul tersebut dan
busur yang keluar dari simpul yang sama
dinotasikan dengan deg (v). Derajat
harus memiliki label yang berbeda.
keluar menyatakan jumlah busur berarah
Aplikasi yang menarik pada graf ini
yang keluar dari simpul. Derajat masuk
adalah menemukan barisan de Bruijn dari
menyatakan jumlah busur berarah yang
suatu graf de Bruijn dengan menentukan
masuk ke simpul. Jalan (walk) pada suatu
sirkuit Euler yang ada pada graf de Bruijn.
graf berarah adalah barisan dari simpul
Sirkuit Euler dengan lintasan paling
dan busur berarah yang menyatakan
minimal pada suatu graf de Bruijn
lintasan yang berawal dan berakhir pada
merepresentasikan
barisan
de
Bruijn.
suatu simpul. Lintasan adalah jalan Pada makalah ini akan dibahas
dengan semua simpulnya berbeda [2].
ada
Suatu graf disebut terhubung apabila
studi literatur mengenai suatu algoritma
lintasan
untuk menyusun suatu trail Euler dengan
di
antara
setiap
dua
label minimal dari suatu simpul tertentu.
simpulnya. Suatu graf berarah dikatakan terhubung secara kuat apabila untuk setiap
B. Algoritma Menyusun Trail Euler Dengan Label Minimal
dua simpulnya v dan w di graf tersebut ada suatu lintasan dari v ke w, sama
Misalkan G adalah graf berarah dan
halnya ada sebuah lintasan dari w ke v .
misalkan l : A(G ) N adalah pelabelan
Suatu graf berarah adalah graf euler jika
busur berarah di G dengan alfabet N
dan hanya jika derajat masuk dan derajat
sedemikian sehingga busur berarah yang
keluar dari simpulnya adalah sama dan
keluar dari simpul yang sama tidak
memiliki paling banyak sebuah subgraf terhubung
yang
tak
nol
memiliki label yang sama.
(nontrivial
Sebuah trail adalah adalah barisan
component). Setiap graf euler berarah
simpul-simpul sedemikian sehingga setiap
yang tidak memiliki simpul terisolasi 112
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
dari simpul-simpul tersebut ada suatu
TAHAP I. Menyusun trail alpabetik pada graf G.
busur ke simpul berikutnya dan tidak ada
Suatu trail alphabetik W pada suatu
suatu busur yang digunakan dua kali di dalam
trail
tersebut.
graf G yang dimulai pada simpul r
Barisan
disimbolkan dengan W G , r . Dan suatu
W v1a1v2a2 vk 1ak1vk adalah sebuah
prosedur untuk menyusuri trail tersebut
trail dimana vi adalah simpul dan a j
akan didefinisikan sebagai berikut:
adalah busur berarah sedemikian sehingga
Dimulai
vi
adalah
untuk
i 1,2, , k 1 . Jika v1 vk
V(W)
dan
himpunan
a1, a2 , a3 ,...,ak1
dengan hasil suatu trail dan trail tersebut mencakup simpul r. Adapun
oleh
Lexicographic
didefinisikan oleh Priyanto, H [6] sebagai
busur-busur
himpunan yang terdiri dari beberapa disimbolkan dengan
alfabet atau simbol yang memenuhi poset
A(W). Ketika busur-busur W dianggap
dengan relasi . Bila diberikan dua buah
tidak begitu penting kita akan memberi
“kata” a a1, a2 ,...,an dan b b1, b2,...,bn
simbol W dengan dengan lebih sederhana sebagai
dan
lexicographic. Prosedur tersebut berakhir
maka W
v1, v2 , v3 ,...,vk disimbolkan
r
dikunjungi dengan label minimal secara
setiap
adalah trail tertutup. Himpunan simpulsimpul
simpul
dilanjutkan menyusuri busur yang belum
titik ujung a j adalah vi 1 dan titik awal
aj
pada
v1, v2 , v3 ,...,vk .
Sebuah
maka a b jika : a dan b identik atau di
trail
dalam susunan alfabet, yakni pada suatu
disebut trail Euler jika busur berarah di W
posisi
adalah busur berarah di G. Graf Euler
i
pertama memiliki kesamaan
“kata” dan selanjutnya “kata” yang
adalah graf yang mengandung trail Euler.
berbeda.
Label di W adalah kata l (a1 ) l (ak 1 ) .
Misalkan
a 00101dan
b 00110, maka a b, karena pada 3
Pada makalah ini, studi literatur
posisi pertama “kata” a dan b memiliki
algoritma untuk menyusun suatu trail
kesamaan, namun pada posisi ke empat
euler minimal dari simpul r pada suatu
“kata” a mendahului b , atau ai bi
graft G secara lexicographic terdiri dari
untuk
dua tahap yaitu :
i 1,..., n tetapi n m . (kondisi
“kata” a lebih pendek dari b ).
113
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
dapat mengunjungi simpul vi berulang TAHAP II. Menyusun trail euler minimal yang dimulai pada simpul r .
kali, sehingga trail W tersebut dapat dibagi ke dalam beberapa subtrail sebagai
Lemma 1 [1]
berikut :
Misal T adalah trail dengan label minimal
diantara
mencakup
semua
himpunan
trail
simpul
di
v1a1v2 a2 ...vi1ai1vi
- subtrail
yang
disimbolkan dengan Wvi ,
X.
Misalkan Y X adalah himpunan simpul
vi ai vi1ai1...vk 1ak 1vk
- subtrail
yang terkandung dalam himpunan simpul
disimbolkan dengan viW dan
yang dicakup oleh T. Maka T adalah jalur
v i a i v i1 a i1 ...v j 1 a j 1 v j
- subtrail
dengan label minimal diantara semua jalur
disimbolkan dengan viWv j untuk i<j.
yang ada di Y. Bukti:
0
sedangkan simbol v W adalah trail v W
Diketahui: Dimisalkan T adalah trail
tanpa simpul v.
dengan label minimal diantara trail-trail yang mencakup himpunan simpul di X.
Misal X adalah subset dari simpul-
Akan dibuktikan bahwa T adalah trail
simpul di G. Suatu cut didefinisikan
dengan label minimal.
sebagai
Misalkan pula ada trail lain T’ yang
suatu
kumpulan
busur-busur
dengan salah satu ujungnya berada di X
merupakan trail dengan label minimal
dan
satunya
berada
yang mencakup Y. Berdasarkan fakta disimbolkan
bahwa Y X , maka pada saat mencatat
dengan
di
V(G)\X,
G X . Secara
sederhana untuk trail T kita menuliskan
barisan simpul-simpul yang menghasilkan label untuk T’ kita akan memperoleh label
G T sebagai G V T , dimana V(T)
minimal pada himpunan X tersebut,
adalah himpunan dari simpul-simpul yang
sehingga T’ mencakup X.
Dengan
merupakan ujung dari busur-busur di T.
demikian maka benar bahwa T’ adalah
Sebuah simpul v dicakup oleh trail T jika
trail dengan label minimal pada X,
G\ AT v [1].
sehingga bertentangan dengan pemisalan
Lemma 2 [1]
bahwa T merupakan trail dengan label
Misal v adalah simpul terakhir yang
minimal. Misalkan
dikunjungi oleh trail tertutup T diantara trail
simpul-simpul yang tidak dicakup oleh T
W v1a1v2 a2 ...vk1ak1vk dan trail W 114
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
dan misalkan w adalah simpul selanjutnya
Misal T adalah trail tertutup yang
0 di T, maka G\ ATv v T vw
mencakup r dan v adalah simpul terakhir
Bukti
simpul yang tidak terpakai oleh T dan T
yang dikunjungi oleh T diantara simpul-
Diketahui: 1. v
adalah trail tertutup dengan label minimal
adalah
simpul
terakhir
yang
diantara
semua
dikunjungi oleh trail tertutup T diantara trail
T,
vw
trail
vT
label
minimal
tertutup
yang
dan
misal
W W G \ A (T ), v .
yang
Maka
Z=
Tv W vT .
0
mengunjungi simpul-simpul di v T .
Bukti:
Misal a adalah sembarang busur dari 0
dengan
semua
mencakup
Akan dibuktikan: busur
yang
v T . Dan misalkan Z adalah
tertutup
diantara
2. w adalah simpul selanjutnya di T
ada
tertutup
0
mencakup
simpul-simpul yang tidak dicakup oleh
Hanya
trail
Diketahui :
G v T karena semua simpul v T 0
1. T adalah trail tertutup dengan label minimal diantara semua
dicakup oleh T, maka a A(T ) .
trail tertutup yang mencakup
Yang bisa saja memiliki arti
0
vT .
a A(Tv )
2. Z adalah trail tertutup dengan
atau
label minimal diantara semua a A(vT ) .
Dengan
w
selanjutnya
di
trail tertutup yang mencakup vT . adalah
simpul
T,
maka
3. W W G \ A (T ), v Akan dibuktikan Z= Tv W vT
0
a G\ ATv vT jika dan hanya jika
Karena Z mencakup vT maka Z juga
a=vw.
mencakup v T sehingga
0
l Z l T .
Dari definisi sebuah trail alphabetik Dan karena v adalah simpul terakhir
yang dimulai pada r adalah suatu trail
yang dikunjungi oleh T diantara
dengan label minimal diantara semua trail
simpul-simpul yang tidak terpakai
yang diawali r dan mencakup r, maka
oleh T maka
akan dinyatakan suatu Lemma berikut ini: Lemma 3 [1]
115
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
l Z l Tv
(1)
Algoritma 1 [1] 1. T
Dari l Z l Tv diperoleh bahwa Z
2. vNoEx(T)
mencakup vT dan dengan jelas
{v=r}
3. while vNULL do
Tv W vT juga mencakup vT ,
4. WW(G\A(T),v) G\A(T)
maka l Z l Tv W vT
(2) Dari (1) dan (2) hanya dapat
5.
T(Tv)W(vT)
6.
vNoEx(T)
over
7. end while
diperoleh apabila Z Tv Z ' , untuk
Catatan : NoEx(T) mengembalikan
suatu trail Z’.
simpul terakhir yang tidak dipakai yang
Karena v adalah simpul terakhir
dikunjungi oleh T atau NULL jika
yang dikunjungi oleh T diantara
simpulnya tidak ada.
simpul-simpul yang tidak dicakup
oleh T dan misalkan w adalah
Teorema 1 [1] Algoritma 1 menghasilkan suatu
simpul selanjutnya di T maka hanya
trail Euler yang dimulai pada r dan
ada satu busur vw yang bisa
labelnya adalah minimal diantara semua
0
trail Euler yang dimulai pada r.
mengunjungi simpul-simpul di v T , 0
dan v T adalah label minimal yang mencakup
0 V vT di G \ A(Tv) .
berakhir pada sejumlah langkah tertentu. Sehingga
Untuk suatu trail tertutup Z’’ dengan
kita
pembuktian
label minimal label di G \ A(T )
dapat
secara
menggunakan induksi
untuk
membuktikannya.
yang mencakup v dan Z adalah trail tertutup dengan label minimal maka
Kita definisikan pernyataan berikut
Z Tv Z ' ' vT . Oleh karena itu
maka
Bukti: Algoritma tersebut di atas akan
secara induktif:
Z ' ' W W G \ A(T ), v
W WG , v T T v W v Gi G \ A T i1 ,
sehingga Z= Tv W vT .
i
i
Dan berikut ini diberikan algoritma
T0
untuk menyusun trail Euler minimal yang dimulai pada simpul r. 116
i
i 1 i 1
vi NoExTi ,
i
i
dan
i 1 i 1
T
dengan
Edisi Juni 2011 Volume V No. 1 - 2
Akan
kita
buktikan
ISSN 1979-8911
dengan
menggunakan induksi bahwa T i adalah
i
W v
i 1 i 1
i
T
l T i l T i 1vi1 Wi v11T i 1
diperoleh
1
T W (G, r) adalah trail tertutup
Karena v i 1 adalah simpul terakhir
1
Dan berdasarkan Lemma 1 T W (G, r) yang adalah trail dengan label minimal yang
dikunjungi
mencakup v T .
selanjutnya di T maka hanya ada satu
Misalkan T
i 1
adalah benar sebagai
busur v i 1 wi 1 yang bisa mengunjungi
trail tertutup dengan label minimal yang 0
0
adalah label minimal yang mencakup
adalah trail tertutup dengan label minimal semua
trail
tertutup
0
simpul-simpul di v i 1T i 1 , dan v i 1T i 1
Dan misalkan T i
mencakup v i 1T i 1 .
0 V vi 1T i 1 di Gi G \ A T i 1vi 1 . Untuk
yang
mencakup vi 1T i 1 .
i
i 1
mencakup v T 0
i 1
i 1
maka
sehingga
Ti
v i 1 dan
adalah trail
tertutup dengan label minimal maka
. i 1
yang
diantara
i 1
adalah simpul
dikunjungi
simpul-simpul
i
oleh yang
i
lT lT Dari
i
i
i
maka T ' ' W W G , v .
T i 1
Dan diperoleh bahwa T i adalah
tidak trail
terpakai oleh T i 1 maka i
T i T i 1v i 1 W v i1T i1 . Oleh karena itu
Dan karena v terakhir
Gi G \ A T i1 yang
minimal label di mencakup
i 1
juga mencakup v T
l T l T
suatu trail tertutup ( T i )’’ dengan label
Berdasarkan lemma 3:
i
diantara
T i 1 dan misalkan wi 1 adalah simpul
Untuk i-1,
T
T i 1
oleh
simpul-simpul yang tidak terpakai oleh
1
Karena T
T i T i1vi1 T i ' ,
apabila
untuk suatu trail ( T i )’.
dengan label minimal yang mencakup r.
i
(4)
Dari (3) dan (4) hanya dapat
Untuk i=1,
diantara
i
mencakup v T .
0
juga mencakup
vi 1T i 1 , maka
trail tertutup dengan label minimal yang 0
i 1 i 1
jelas T v
tertutup
diantara
dengan
semua
trail
label
minimal
tertutup
yang
i1 i1
l T l T v i
(3) i1 i1
v
mencakup vi 1T i . diperoleh
Untuk
bahwa T i mencakup vi 1T i 1 dan dengan
vi NoExTi
dan
berdasarkan lemma 1, T i adalah trail
117
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
dengan label minimal yang mencakup
Gambar 1 C. Contoh
0
v iT i . Jadi terbukti benar untuk semua i.
Berikut ini akan diberikan sebuah
Oleh karena itu algoritma ini akan
contoh untuk mencari trail euler dengan
menghasilkan sebuah trail tertutup T yang
label minimal secara lexicographic pada
mencakup semua simpul V(T), akan tetapi
graf G berikut :
G hanya memiliki sebuah komponen terhubung
secara
kuat
sehingga
A(T)=A(G). Yang artinya bahwa T adalah trail Euler dengan label minimal. Sebagai Catatan : simpul awal r dapat dipilih secara sembarang, suatu simpul
awal
menghasilkan
yang trail
berbeda yang
akan
berbeda,
sekalipun yang dibahas adalah label sebagai suatu circular string. Sebagai contoh pada gambar 1 berikut, barisan de Bruijn minimal berikut yang dimulai pada Gambar 2
u adalah 001122 tetapi yang dimulai pada v adalah 100122.
TAHAP I. Menyusun trail alpabetik pada graf G. Pada tahap ini akan dicari trail-trail alphabetik simbolkan
dari
graf G
dengan
Wi
yang ,
kami dengan
i=0,1,2,3,… . Untuk lebih mempermudah pemahamannya kami proses tersebut kami sajikan dalam urutan gambar-gambar sebagai berikut :
118
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
Trail W0 : v0 a0 Lokasi : v0
Trail W0 : Lokasi : v0
Gambar 4.0.2
Gambar 4.0.1 Trail W0 : v0 a0 v0 Lokasi : v0
Trail W1 : Lokasi : v0
Gambar 4.1
Gambar 4.2
119
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
Trail W0 : v0 a0 v0 a1 Lokasi : v1
v1
Trail W0: v0 a0 v0 a1 v1 a2 Lokasi : v2
v0
v0
000
000
a8=1000
a9=1001
001
v2
a2=0010 a3=0011
100
v1
v3
a9=1001
001
v2
a4=0100
010
a5=0101
010
a10=1010
a12 =1100
a3=0011
a5=0101
101
a11 =1011 v4
011
a8=1000 100
a4=0100 a10=1010
a11 =1011 110
a6=0110
a7=0111
v6
v4
a14=1110
011
v5
a13=1101
a6=0110
a7=0111 111
v7
v7
a15=1111
a15=1111
Gambar 4.3
Gambar 4.4
a8=1000
a9=1001
100
v3
v2 010
a3=0011
a5=0101
a10=1010
a12=1100
101
a11=1011 v4
011
v5
a13=1101 110
a6=0110
a7=0111
v6
Trail W1: v0 a1 v1 a2 v2 a4 v3 a8 Lokasi : v0
v0
001
110
a14=1110
111
Trail W1: v0 a1 v1 a2 v2 a4 Lokasi : v3
v1
a12 =1100
101
a13=1101
v5
000
v3
v6
a14=1110 111
v7 a15=1111
Gambar 4.6
Gambar 4.5
120
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
Trail W1 : v0 a1 v1 a2 v2 a4 v3 a8 v0 Lokasi : v3
v1
a3=0011
v0
v0
000
000
a9=1001
001
Trail W2 : Lokasi : v3
100
v1
v3
v2
v2
010
010
a5=0101
a10=1010
a3=0011
a12 =1100
a5=0101
v4
011
v5
100
a10=1010
v3
a12=1100
101
101
a11 =1011
a9=1001
001
a11=1011
a13=1101 110
a6=0110
a7=0111
v4
v6
011
v5
110
a6=0110
a7=0111
a14=1110
a13=1101
a14=1110 111
111
v7
v7
a15=1111
a15=1111
Gambar 4.8
Gambar 4.7 Trail W2 : v3 a9 Lokasi : v1
Trail W2 : v3 a9 v1 a3 Lokasi : v4
Gambar 4.9
Gambar 4.10
121
v6
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
Trail W2 : v3 a9 v1 a3 v4 a6 Lokasi : v6
Trail W2 : v3 a9 v1 a3 v4 a6 v6 a12 Lokasi : v3
Gambar 4.11
Gambar 4.12
Trail W2 : v3 a9 v1 a3 v4 a6 v6 a12 v3 Lokasi : v6
Trail W3 : Lokasi : v6
Gambar 4.14
Gambar 4.13
122
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
Trail W3 : v6 a13 Lokasi : v5
v1
Trail W3 : v6 a13 v5 a10 Lokasi : v2
v0
v0
000
000
001
100
v1
v3
001
v2
v2
010
010
a5=0101
a10=1010
v4
011
110
v6
v4
a14=1110
011
a7=0111
a14=1110 111
v7
v7
a15=1111
a15=1111
Gambar 4.16
Trail W3 : v6 a13 v5 a10 v2 a5 Lokasi : v5
Trail W3 : v6 a13 v5 a10 v2 a5 v5 a11 Lokasi : v4
v0 000
001
100
v3
110
v6
v2 010
101
a11=1011 v4
v5
011
a7=0111
v6
v5
111
Gambar 4.15
v1
110
101
a11 =1011
v5
a7=0111
v3
a5=0101
101
a11 =1011
100
a14=1110 111
v7 a15=1111
Gambar 4.18
Gambar 4.17
123
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
Trail W3 : v6 a13 v5 a10 v2 a5 v5 a11 v4 a7 Lokasi : v7
Gambar 4.19
Trail W3 : v6 a13 v5 a10 v2 a5 v5 a11 v4 a7 v7 a14 Lokasi : v6
Gambar 4.20
Trail W3 : v6 a13 v5 a10 v2 a5 v5 a11 v4 a7 v7 a14 v6 Lokasi : v7
Trail W4 : Lokasi : v7
Gambar 4.22
Gambar 4.21
124
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
Trail W3 : v7 Lokasi : v7
Trail W3 : v7 a15 v7 Lokasi : v7
Gambar 4.24
Gambar 4.23 Dari
atas
minimal euler yang akan kita cari, adapun
diperoleh 5 buah trail alphabetik yang
v adalah simpul terakhir yang dikunjungi
mungkin pada graf G tersebut di atas yaitu
oleh T diantara simpul-simpul yang tidak
sebagai berikut :
dicakup oleh T. Penyusunan trail euler
-
W0 = v0 a0 v0 W1 =v0 a1 v1 a2 v2 a4 v3 a8 v0 W2 = v3 a9 v1 a3 v4 a6 v6 a12 v3 - W3 = v6 a13 v5 a10 v2 a5 v5 a11 v4 a7 v7 a14 v6 W4 = v7 a15 v7 Yang untuk selanjutnya akan dipergunakan untuk menyusun trail euler yang minimal secara lexicographic dengan menggunakan Algoritma 1.
minimal ini kami sajikan dalam urutan
-
proses-proses sebagai berikut :
TAHAP II. minimal
proses
tersebut
di
Diketahui : W0 = v0 a0 v0 W1 = v0 a1 v1 a2 v2 a4 v3 a8 v0 W2 = v3 a9 v1 a3 v4 a6 v6 a12 v3 W3 = v6 a13 v5 a10 v2 a5 v5 a11 v4 a7 v7 a14 v6 W4 = v7 a15 v7 T v v0
Proses 1
Menyusun trail euler
W0 v0 a0 v0 T(Tv) W0 (vT)= v0 a0 v0 v v0
Pada tahap ini akan digunakan Algoritma 1 untuk menyusun trail euler minimal. Adapun W0 ,W1 , W2 ,W3 , W4
Proses 2
adalah trail-trail aphabetik yang diperoleh
W1 v0 a1 v1 a2 v2 a4 v3 a8 v0 T(Tv) W1 (vT)= (v0 a0 v0 )( v0 a1 v1 a2 v2 a4 v3 a8 v0)(v0) v v3
dari tahap I, sedangkan T adalah trail 125
Edisi Juni 2011 Volume V No. 1 - 2
ISSN 1979-8911
T= v0 a0 v0 a1 v1 a2 v2 a4 v3 a9 v1 a3 v4 Proses 3
a6 v6 a13 v5 a10 v2 a5 v5 a11 v4 a7 v7 a15 v7 a14
W2 v3 a9 v1 a3 v4 a6 v6 a12 v3 T(Tv) W2 (vT)= (v0 a0 v0 a1 v1 a2 v2 a4 v3 )( v3 a9 v1 a3 v4 a6 v6 a12 v3 )( v3 a8 v0) = v0 a0 v0 a1 v1 a2 v2 a4 v3 a9 v1 a3 v4 a6 v6 a12 v 3 a8 v 0 v v6
v6 a12 v3 a8 v0 . Untuk contoh graf ini maka rangkaian euler minimal tersebut berpadanan dengan barisan 16 angka biner 0000100110101111000.
Proses 4 W3 v6 a13 v5 a10 v2 a5 v5 a11 v4 a7 v7 a14 v6 T(Tv) W3 (vT)= (v0 a0 v0 a1 v1 a2 v2 a4 v3 a9 v1 a3 v4 a6 v6)( v6 a13 v5 a10 v2 a5 v5 a11 v4 a7 v7 a14 v6) ( v6 a12 v3 a8 v0) = v0a0 v0 a1v1 a2 v2 a4 v3 a9 v1 a3 v4a v6 a13 v5 a10 v2 a5 v5 a11 v4 a7 v7 a14 v6 a12 v3 a8 v0 v v7
D. Daftar Pustaka Bang-Jensen, J. and Gutin, G. Digraphs Theory, Algorithms an Application. Springer-Verlag, Berlin Heidelberg, New York, London, Paris, Tokyo, Hongkong, Barcelona, Budhapest, 15th August 2007. Bo Huai Victor, L. Eulerian Path and Circuit. January 24, 2010. Liu, C.L. Dasar-Dasar Matematika Diskrit, Alih Bahasa Ir. Bambang Sumantri, PT Gramedia Pustaka Utama, Jakarta 1995. Matamala, M. and Moreno, E. (2004). Minimal Eulerian trail in a labeled digraph. Departemen Matematika UCHILE-CNRS, Casilla 170-3, Correo 3, Santiago, Chile. Priyanto, H (2010). Konstruksi Barisan de Bruijn. Departemen Matematika Universitas Indonesia, Indonesia. West, D. B (2001). Introduction to Graph Theory, Second Edition. University of Illinois-Urbana: Prentice Hall.
Proses 5 W4 v7 a15 v7 T(Tv) W4 (vT)= (v0 a0 v0 a1 v1 a2 v2 a4 v3 a9 v1 a3 v4 a6 v6 a13 v5 a10 v2 a5 v5 a11 v4 a7 v7)( v7 a15 v7)( v7 a14 v6 a12 v3 a8 v0) = v0 a0 v0 a1 v1 a2 v2 a4 v3 a9 v1 a3 v4 a6 v6 a13 v5 a10 v2 a5 v5 a11 v4 a7 v7 a15 v7 a14 v6 a12 v3 a8 v0 v NULL Proses Selesai
Dari
proses
tersebut
di
atas
diperoleh trail euler minimal sebagai berikut :
126
