Konstruksi PelabelanPada Line Digraph dari Graf Lingkaran Berarah dengan Dua Tali Busur Ma’rifah Puji Hastuti, Kiki Ariyanti Sugeng, Denny Riama Silaban Departemen Matematika, FMIPA Universitas Indonesia, Depok 16424 {marifah.puji, kiki, denny}@sci.ui.ac.id
Abstrak
Graf berarah adalah pasangan himpunan (V, A) dimana V himpunan tak kosong yang elemennya disebut simpul dan A himpunan pasangan terurut dari elemen-elemen himpunan V yang disebut busur berarah. Suatu graf berarah D = (V, A) dikatakan mempunyai pelabelanapabila tiap simpulnya dapat dilabel dengan dengan dan memenuhi sifat yaitu tiap simpulnya memiliki label yang berbeda dan untuk setiap busur berarah, (u, v) A jika dan hanya jika untuk i = 2, 3, … , k dengan dan k > 1. Pelabelan quasimemiliki definisi yang hampir sama, perbedaannya jika busur berarah, (u, v) A maka untuk i = 2, 3, … , k dengan dan k > 1. Pada makalah ini ditunjukkan bahwa graf lingkaran berarah dengan dua tali busur dapat dilabel dengan pelabelan quasidengan , line digraph dari graf lingkaran berarah dengan dua tali busur dapat dilabel dengan pelabelandengan sehingga line digraph dari graf lingkaran berarah dengan dua tali busur merupakan graf DNA.
Abstract
Directed graph is a pair sets (V, A) consists of a non-empty finite set V which its elements called vertices and A is a finite set of ordered pair of elements in V called arcs. A directed graph can be - labeled if every vertex assigned a label with and , all vertices have different labels, and for any arc (u, v) A if and only if for i = 2, 3, … , k with and k > 1. A quasilabeling almost have the same definition with labeling, except for the arc, if (u, v) A then for i = 2, 3, … , k with and k > 1. In this paper, it is shown that a dicycle with two chords can be quasilabeled, line digraph of a dicycle with two chords can be labeled so that the line digraph of dicycle with two chords is a DNA graph. Kata Kunci : DNA graph, dicycle with two chords, line digraph, (α, k)-labeling, quasi-(α, k) label .
1. PENDAHULUAN Graf berarah atau digraph (directed graph) D adalah pasangan himpunan (V, A) dimana V himpunan tidak kosong yang elemennya disebut dengan simpul dan A himpunan pasangan terurut dari elemen – elemen himpunan V yang disebut busur berarah, yaitu busur yang memiliki arah. Jika busur berarah menunjukkan pasangan terurut dimana , maka u disebut ekor (tail) dan v disebut kepala (head) dari busur tersebut [3]. Jalan (walk) pada suatu graf berarah D adalah suatu barisan dimana adalah simpul dan adalah busur dari D sedemikian sehingga ekor dari adalah dan kepala dari adalah untuk setiap i = 1, 2, … k – 1. Suatu jalan dikatakan tertutup jika . Jalan W dapat dikatakan sebagai jalan dari ke atau jalan. Jejak (Trail) adalah jalan dimana semua busurnya berbeda sedangkan jalan dimana semua
simpulnya berbeda disebut sebagai lintasan. Jika u dan v adalah simpul pada suatu graf berarah maka jarak (distance) dari u menuju v didefinisikan dengan panjang dari suatu lintasan terpendek (u,v). Line digraph (L(D)) dari graf berarah adalah graf berarah dengan himpunan simpul sedemikian sehingga ada busur berarah dari ke di L(D) jika dan hanya jika kepala dari busur di D adalah ekor dari busur di D [1]. Misal dan k > 1 adalah bilangan bulat. Suatu graf berarah D = (V, A) dapat dilabel dengan pelabelanjika tiap simpulnya dapat diberi label dengan panjang k dan memenuhi syarat: 1. , 2. Setiap simpul yang berbeda memiliki label yang berbeda, dan 3. (u,v) A jika dan hanya jika untuk i = 2, 3, … , k [2]. Pada [5] diperkenalkan suatu pelabelan lain yang dapat membantu mempelajari pelabelan. Didefinisikan suatu pelabelan lain yaitu pelabelan quasi. Misal dan k >1 bilangan bulat,
Konstruksi pelabelan..., Marifah Puji Hasturi, FMIPA UI, 2013
suatu graf berarah D = (V, A) dimana tiap simpulnya diberi label disebut pelabelan quasi-(α, k) pada D, jika memenuhi 1. , 2. Setiap simpul yang berbeda memiliki label yang berbeda, dan 3. Jika maka untuk i = 2, 3, … , k. Perbedaan antara pelabelan quasidengan pelabelanterletak pada sifat ketiga. Pada pelabelan quasisifat ketiga hanya dapat berlaku satu arah artinya jika (u,v) A maka untuk i = 2, 3, … , k sebaliknya jika untuk i = 2, 3, … , k maka (u,v) A tidak harus merupakan busur berarah pada D. Suatu graf berarah D merupakan graf DNA jika dan hanya jika sedemikan sehingga D memiliki pelabelan-(4, k). Jika suatu graf berarah D dapat dilabel dengan pelabelanuntuk beberapa dan k > 1 bilangan bulat, maka D adalah suatu line digraph [2]. Graf lingkaran berarah dan graf lintasan berarah merupakan graf DNA. Rooted tree dan self adjoint digraph merupakan graf DNA jika dan hanya jika derajat maksimumnya empat. Jika D dapat di label dengan pelabelan quasi maka line digraph dari D, L(D), dapat dilabel dengan pelabelan [5]. Line digraph dari graf lingkaran berarah dengan satu tali busur merupakan graf DNA [4]. Pada makalah ini dikonstruksi pelabelan quasidengan dan k>1 pada graf lingkaran berarah dengan dua tali busur dengan sehingga dapat diketahui line digraph dari graf lingkaran berarah dengan dua tali busur memiliki pelabelandengan dan dapat ditunjukkan line digraph dari graf lingkaran berarah dengan dua tali busur merupakan graf DNA.
2. DISKUSI DAN HASIL Alur untuk membuktikan bahwa line digraph dari graf lingkaran berarah dengan dua tali busur merupakan graf DNA adalah sebagai berikut: Mendefinisikan fungsi pelabelan untuk simpul. Menunjukkan bahwa label tersebut memenuhi sifat – sifat pelabelan quasi. Menunjukkan bahwa line digraph dari graf lingkaran berarah dengan dua tali busur memiliki pelabelan. Menunjukkan bahwa line digraph dari graf lingkaran berarah dengan dua tali busur adalah graf DNA. Pada Gambar 1. berikut ini diberikan pelabelan quasi-(3,3) pada graf lingkaran berarah dengan dua tali busur untuk n = 6 dan n = 7.
(1,3,2)
(3,3,2)
(3,2,3)
v6
v1
v2
v5
v4
v3
(3,1,3)
(3,3,1)
(2,3,3)
(a) (1,1,3)
(1,3,3)
(3,3,2)
(3,2,3)
v6
v7
v1
v2
v5
v4
v3
(3,1,1)
(3,3,1)
(2,3,3)
(b)
Gambar 1. Pelabelan quasi-(3,3) pada graf lingkaran berarah dengan dua tali busur (a) (b) Teorema 2.1 Graf lingkaran berarah dengan dua tali busur, dan , dengan tali busur ⌊ ⌋ ⌊ ⌋
, untuk
memiliki pelabelan
quasi-( ⌊ ⌋). Bukti. Nyatakan simpul – simpul pada dengan seperti pada Gambar 2 yaitu gambar umum graf lingkaran berarah dengan dua tali busur. Pada pembuktian ini dibagi menjadi dua kasus yaitu untuk n genap dan n ganjil.
Gambar 2. Gambar Umum Graf Lingkaran Berarah dengan dua Tali Busur Kasus 1. n genap Definisikan pelabelan l pada graf lingkaran berarah dengan dua tali busur, , dengan ( )
( ( )
( )
( )) (2.1)
dimana
Konstruksi pelabelan..., Marifah Puji Hasturi, FMIPA UI, 2013
(
)
sepanjang Dari definisi l berlaku ( ) ( )
(2.2)
(2.3) dimana untuk
( ) berlaku sebagai berikut
atau tupel ke – 1) pada label ini tupel ke – simpul tersebut. Dengan memperhatikan pelabelan pada persamaan (2.1), (2.2), (2.3), dan (2.4) terbukti bahwa label dua simpul dan tidak sama untuk setiap kasus. Sifat 3. Jika
(
)
(
)
(
. Untuk i = 1, … , n – 1, dari definisi berlaku sehingga untuk membuktikan pelabelan l memenuhi sifat 3, tinggal ditunjukkan bahwa ,
)
( { (2.4) Pada pelabelan di atas, 0 mod 4 ditulis sebagai 4. Akan dibuktikan bahwa l memenuhi ketiga sifat pelabelan quasisehingga menjadi pelabelan quasiuntuk , yaitu (
1. 2. Tiap simpul pada berbeda. 3. Jika . Sifat
maka
), dan
(
)
dengan
. Dari definisi l diketahui bahwa ( sepanjang ( )
(
dan berlaku
) ( ) berlaku
dimana untuk
) memiliki label yang
maka ( ) (
1.
(
)
(
)
(
)
)
. Berdasarkan persamaan (2.1), (2.2), (2.3), dan (2.4) diketahui ( ) pada fungsi pelabelan l mempunyai nilai mod 4 maka dari definisi fungsi yang ada, terlihat bahwa semua nilai pada l akan masuk dalam himpunan {1,2,3,4} atau . Dengan demikian, sifat 1 berlaku. 2. Tiap simpul yang berbeda pada memiliki label yang berbeda. Ambil dua simpul yang berbeda, dan , pada . Andaikan dan memiliki label yang sama. Dalam hal ini akan dilihat 7 kasus, bergantung pada nilai p dan q, dimana dan . Label pada setiap simpul terdiri dari
{ sehingga diperoleh (
) (
Sifat
tupel yaitu ( )
)
( )
( )
)
( (
berbeda maka terbukti bahwa label kedua simpul berbeda. Akan tetapi, jika pada tupel ke- bernilai sama, maka diperhatikan tupel lainnya (dalam kasus
(
) )
( )
. Dengan demikian, untuk pembuktian sifat ini harus diperhatikan setiap tupel pada setiap label. Akan tetapi, pada pembuktian ini hanya akan diperhatikan pada tupel ke- . Jika nilai pada tupel ke-
)
(
) (
(
Dengan kata lain, . Kemudian,
Konstruksi pelabelan..., Marifah Puji Hasturi, FMIPA UI, 2013
) … )
,
(
)
( (
)
(
dimana untuk
)
⌊ ⌋
( ) berlaku
⌊ ⌋
)
( ( (
( (
)
)) (
)
(
)
( (
(
( )
⌊ ⌋
(
))
(
)
(⌊ ⌋
)
⌊ ⌋ ⌊ ⌋
(
)
⌊ ⌋)
⌊ ⌋
Akan dibuktikan bahwa l memenuhi ketiga sifat pelabelan quasisehingga menjadi pelabelan quasi- ⌊ ⌋ untuk , yaitu
),
. Untuk, (
)
(
( (
)
(
)
( )
(
))
)
(
)
) (
(
lain,
)
2. Tiap simpul pada berbeda. 3. Jika ⌊ ⌋.
) ,
⌊ ⌋
)
memiliki label yang maka
(
Sifat 1.
) (
(
1.
)
(
(2.8)
{ Pada pelabelan di atas, 0 mod 4 ditulis sebagai 4. (
( )
⌊ ⌋ ⌊ ⌋
))
)
kata
)
⌊ ⌋
Dengan kata lain,
Dengan
(⌊ ⌋
)
(
(
⌊ ⌋
)
⌊ ⌋. Berdasarkan persamaan (2.5), (2.6), (2.7), dan (2.8) diketahui fungsi pelabelan l mempunyai nilai mod 4 maka dari definisi fungsi yang ada, terlihat bahwa semua hasil nilainya akan masuk sebagai elemen {1,2,3,4} atau . Dengan demikian, sifat 1 berlaku. Sifat 2. Tiap simpul yang berbeda pada memiliki label yang berbeda.
. Jadi sifat 3 berlaku. Terbukti bahwa pelabelan l memenuhi sifat – sifat pelabelan quasi-(4, ) untuk n genap.
Ambil dua simpul yang berbeda, dan , pada . Andaikan dan memiliki label yang sama. Dalam hal ini akan dilihat 8 kasus, bergantung pada nilai p dan q, dimana dan .
Kasus 2. n ganjil Definisikan pelabelan l pada graf lingkaran berarah dengan dua tali busur, , dengan ( )
( ( )
( )
⌊ ⌋
( )) (2.5)
dimana ⌊ ⌋
⌊ ⌋
(⌊ ⌋
sepanjang ⌊ ⌋ Dari definisi l berlaku ( ) ( )
Label pada setiap simpul tupel yaitu ( )
( )
( )
terdiri dari ⌊ ⌋ ⌊ ⌋
( )
. Dengan demikian, untuk pembuktian sifat ini harus diperhatikan setiap tupel pada setiap label. Akan tetapi, pada pembuktian ini hanya diperhatikan pada tupel ke- ⌊ ⌋. Jika pada tupel ke⌊ ⌋ berbeda maka terbukti bahwa label kedua simpul
) (2.6) ⌊ ⌋ (2.7)
berbeda. Akan tetapi, jika pada tupel ke- ⌊ ⌋ bernilai sama, maka diperhatikan pada tupel lainnya (dalam kasus ini pada tupel ke – ⌊ ⌋ atau tupel ke – 1) pada label simpul tersebut.
Konstruksi pelabelan..., Marifah Puji Hasturi, FMIPA UI, 2013
Dengan membandingkan pelabelan pada persamaan (2.5), (2.6), (2.7), dan (2.8) terbukti bahwa label dua simpul dan tidak sama untuk setiap kasus. Sifat 3. Jika
maka
. ⌊ ⌋ Untuk i = 1, … , n – 1, dari definisi berlaku sehingga ⌊ ⌋ untuk membuktikan pelabelan l memenuhi sifat 3, tinggal ditunjukkan bahwa , (
⌊ ⌋
),
(
dan
( ⌊ ⌋
) ⌊ ⌋
⌊ ⌋
Dengan kata lain, . Kemudian, (
⌊ ⌋
)
( (
)
⌊ ⌋
⌊ ⌋
⌊ ⌋
)
⌊ ⌋
⌊ ⌋
dengan ⌊ ⌋ . Dari definisi l diketahui bahwa ( ⌊ ⌋
⌊ ⌋
(⌊ ⌋
)
⌊ ⌋
sepanjang ( )
(
dan
)
⌊ ⌋
dimana untuk
⌊ ⌋
⌊ ⌋
(
(
⌊ ⌋
⌊ ⌋ )
(⌊ ⌋
)
⌊ ⌋ ⌊ ⌋
⌊ ⌋)
Dengan
kata ⌊ ⌋
⌊ ⌋
⌊ ⌋
)
⌊ ⌋
⌊
⌊ ⌋
⌊ ⌋
(⌊ ⌋
(
⌊
( ⌋
⌊ ⌋
(⌊ ⌋
))
(⌊ ⌋
(⌊ ⌋
⌊ ⌋
)
⌊ ⌋
(
⌊ ⌋
(
⌊ ⌋
)
) Dengan ⌊ ⌋
)
)
⌊ ⌋
⌊ ⌋
⌊ ⌋
)
⌊ ⌋
)
⌊ ⌋
)
⌊ ⌋
)
(
⌊ ⌋
(⌊ ⌋
⌊ ⌋
( ⌋
⌊ ⌋
⌊ ⌋
⌊ ⌋
(
),
)
⌊ ⌋
⌊ ⌋
sehingga diperoleh (
⌊ ⌋
. Untuk, ⌊ ⌋
(
(
)
(
⌊ ⌋
{
⌊ ⌋
(⌊ ⌋
lain,
⌊ ⌋
⌊ ⌋
))
)
(
⌊ ⌋
⌊ ⌋
(
⌊ ⌋
⌊ ⌋ (
⌊ ⌋
⌊ ⌋
(⌊ ⌋
)
))
)
( ⌊ ⌋
⌊ ⌋
⌊ ⌋
(⌊ ⌋
) (⌊ ⌋
⌊ ⌋
)
)
⌊ ⌋
⌊ ⌋
⌊ ⌋
( ) berlaku
(
⌊ ⌋
berlaku
⌊ ⌋
⌊ ⌋
))
)
⌊ ⌋
(
⌊ ⌋
(
⌊ ⌋
( (
⌊ ⌋
,
) (⌊ ⌋
)
kata ⌊ ⌋
) …,
lain,
⌊ ⌋
⌊ ⌋
)
⌊ ⌋ ⌊ ⌋
⌊ ⌋
(
⌊ ⌋
⌊ ⌋
(
)
⌊ ⌋
)
⌊ ⌋
⌊ ⌋
(
⌊ ⌋
(
⌊ ⌋
)
) ,
. Sifat 3 berlaku.
Terbukti bahwa pelabelan l memenuhi sifat – sifat pelabelan quasi-(4,⌊ ⌋) untuk n ganjil.
Konstruksi pelabelan..., Marifah Puji Hasturi, FMIPA UI, 2013
Dengan demikian, telah terbukti bahwa graf lingkaran berarah dengan dua tali busur, , dan dengan tali busur ⌊ ⌋ ⌊ ⌋
, untuk
memiliki pelabelan quasi-
pada line digraph-nya. Lemma 3.1 ini beserta pembuktiannya diberikan oleh [5]. Lemma 2.1 [5] Diberikan graf berarah . Jika D dapat dilabel dengan pelabelan quasimaka line digraph dari D, , dapat dilabel dengan pelabelan.
( ⌊ ⌋). Pada Gambar 3 dan Gambar 4 diberikan contoh pelabelan quasi-( ⌊ ⌋ untuk graf lingkaran berarah dengan dua tali busur, dan busur ⌊ ⌋
(1,3,2)
(3,3,2)
(3,2,3)
v6
v1
v2
v5
v4
v3
(3,1,3)
(3,3,1)
(2,3,3)
, dengan tali untuk ⌊ ⌋
. (4,4,3,2,1,4,3,2) (4,3,2,1,4,3,2,4)
v1
v2
(a) (1,4,4,3,2,1,4,3)
v16
v3
(3,2,1,4,3,2,4,4)
(3,1,4,4,3,2,1,4)
v15
v4
(2,1,4,3,2,4,4,3)
(4,3,1,4,4,3,2,1)
v14
v5
(1,4,3,2,4,4,3,2)
(1,4,3,1,4,4,3,2)
v13
v6
(4,3,2,4,4,3,2,1)
(2,1,4,3,1,4,4,3)
v12
v7
(3,2,4,4,3,2,1,4)
(3,2,1,4,3,1,4,4)
v11
v8
(2,4,4,3,2,1,4,3)
v10
v9
v56
(1,3,3,2)
(3,3,2,3)
v61
v12
v64
v13
(1,3,3,1)
(3,1,3,3)
(4,4,3,2,1,4,3,1)
Gambar 3. Pelabelan quasi-(4,8) pada (4,4,3,2,1,4,3,2)
v1 (2,4,4,3,2,1,4,3)
v17
v2
(4,3,2,1,4,3,2,4)
(1,2,4,4,3,2,1,4)
v16
v3
(3,2,1,4,3,2,4,4)
(3,1,2,4,4,3,2,1)
v15
v4
(2,1,4,3,2,4,4,3)
v14
v5
(1,4,3,2,4,4,3,2)
(4,3,1,2,4,4,3,2)
v45
v34 (2,3,3,1)
(b)
Gambar 5. (a) Pelabelan quasi-(3,3) pada Pelabelan-(3,4) pada L( (1,3,3)
(3,3,2)
(3,2,3)
v6
v7
v1
v2
v5
v4
v3
(3,1,1)
(3,3,1)
(2,3,3)
(1,4,3,1,2,4,4,3)
v13
v6
(4,3,2,4,4,3,2,1)
(1,1,3,3)
(2,1,4,3,1,2,4,4)
v12
v7
(3,2,4,4,3,2,1,4)
v67
v71
(3,2,1,4,3,1,2,4)
v11
v8
(2,4,4,3,2,1,4,3)
(3,1,1,3) v10
v9
quasi-
v56
(3,3,2,3)
v12
v74 (1,3,3,1) (2,3,3,2) v31
(4,4,3,2,1,4,3,1)
Gambar 4. Pelabelan quasi-(4,8) Lemma 2.1 memberikan hubungan pelabelan pada graf berarah D dengan pelabelan-
(b)
(1,1,3)
(a) (1,3,3,2)
(4,3,2,1,4,3,1,2)
(3,2,3,3)
(2,3,3,2)
(3,3,1,3) (4,3,2,1,4,3,1,4)
v23
v45 (3,3,1,1)
v34 (b)
Konstruksi pelabelan..., Marifah Puji Hasturi, FMIPA UI, 2013
(2,3,3,1)
v23
(3,2,3,3)
Gambar 6. (a) Pelabelan quasi-(3,3) pada (b) Pelabelan-(3,4) pada L Dari Gambar 5 dan Gambar 6 dapat dilihat bahwa line digraph dari graf lingkaran berarah dengan dua tali busur untuk dan dapat dilabel dengan pelabelan-(3,4). Telah ditunjukkan beberapa gambar contoh pelabelan quasi-( ⌊ ⌋) pada graf lingkaran berarah dengan dua tali busur. Selanjutnya dari Teorema 2.1 dan Lemma 2.1 diperoleh Akibat 2.1 dan Akibat 2.2 seperti dijabarkan berikut ini.
, sehingga suatu graf berarah D merupakan graf DNA jika dan hanya jika D memiliki pelabelanuntuk dan . Dengan demikian, berdasarkan Akibat 2.1, dan telah diketahui bahwa graf lingkaran berarah dengan dua tali busur dengan n = 6 dan n = 7 memiliki pelabelan quasi-(3,3) dan pelabelan-(3,4) dapat diperoleh Akibat 2.2. Akibat 2.2 Line digraph dari graf lingkaran berarah dengan dua tali busur, , dengan ⌊ ⌋ dan
Akibat 2.1 Line digraph dari graf lingkaran berarah dengan dua tali busur, , untuk dengan dan memiliki ⌊ ⌋ ⌊ ⌋ pelabelan-( ⌊ ⌋ ). Bukti. Berdasarkan Teorema 2.1 untuk lingkaran berarah dengan dua tali busur, dan dengan ⌊ ⌋ ⌊ ⌋
, memiliki
memiliki pelabelan-( ⌊ ⌋+1). (3,1,4,4)
(1,4,4,3)
(4,4,3,2)
(4,3,2,4)
v7
v8
v1
v2
v5
v4
v3
(4,4,3,1)
(2,4,4,3)
(3,2,4,4)
(3,1,4,4,3)
(1,4,4,3,2)
(4,4,3,2,4)
v78
v81
v12
v67
v85
v41
(1,4,4,3,1)
(2,4,4,3,2)
v56 (4,4,3,1,4)
(b)
v45
v34 (3,2,4,4,3)
(4,3,2,4,4)
Gambar 7. Pelabelan Pelabelan quasi-(4,4) pada (b) Pelabelan-(4,5) pada ( )
( ⌊ ⌋
Pada Gambar 7 diberikan contoh pelabelan) pada line digraph dari graf lingkaran
berarah dengan dua tali busur, dan ⌊ ⌋ ⌊
⌋
Berdasarkan Teorema 2.1 graf berarah mempunyai pelabelan quasi-( ⌊ ⌋) untuk telah diketahui pula untuk n = 6 dan n = 7 juga
dan
Berdasarkan Akibat 2.1
mempunyai
) untuk dan telah pelabelan-( ⌊ ⌋ diketahui pula untuk n = 6 dan n = 7 juga mempunyai pelabelan-( ⌊ ⌋ maka
). Karena
untuk
adalah graf DNA untuk
.
Dari pembahasan ini, dapat terlihat bahwa dengan mengkonstruksi pelabelanpada suatu graf berarah dapat membantu mengetahui graf berarah tersebut merupakan graf DNA atau bukan. Dari pembahasan ini pula dapat diketahui suatu line digraph dari graf lingkaran berarah dengan dua tali busur, , untuk dengan dan ⌊ ⌋ merupakan graf DNA.
3. KESIMPULAN v23
(2,4,4,3,1)
adalah graf DNA.
Bukti.
⌊ ⌋
v6 (4,3,1,4)
(4,3,1,4,4)
dan
mempunyai pelabelan quasi-( ⌊ ⌋). , graf
pelabelan quasi-( ⌊ ⌋). Dengan demikian berdasarkan Lemma 2.1 line digraph dari graf lingkaran berarah dengan dua tali busur, , untuk dengan dan ⌊ ⌋ ⌊ ⌋
(a)
⌊ ⌋
, dengan dengan
.
Suatu graf berarah D merupakan graf DNA jika dan hanya jika terdapat sedemikan sehingga D memiliki pelabelan-(4,k) [2]. Berdasarkan definisi pelabelan, suatu graf yang memiliki pelabelanjuga dapat dilabel dengan pelabelan-
Pada makalah ini, telah ditunjukkan bahwa graf lingkaran berarah dengan dua tali busur memiliki pelabelan quasi dengan dan k =3 untuk dan dan ⌊ ⌋ untuk seperti yang disebutkan pada Teorema 2.1 pada penjelasan sebelumnya. Pada makalah ini juga dapat ditunjukkan line digraph dari graf lingkaran berarah dengan dua tali busur memiliki pelabelan dengan dan k =4 untuk dan dan ⌊ ⌋ untuk seperti yang disebutkan pada Akibat 2.1 pada penjelasan sebelumnya. Telah ditunjukkan pula pada makalah ini, pada Akibat 2.2 bahwa line digraph dari graf lingkaran berarah dengan dua tali busur merupakan graf DNA untuk .
Konstruksi pelabelan..., Marifah Puji Hasturi, FMIPA UI, 2013
UCAPAN TERIMA KASIH Sebagian dari penelitian ini didanai oleh Hibah Kompetensi No 3686/H2.R12/HKP.05.00/20`2. Terima Kasih penulis ucapkan pula kepada berbagai pihak yang tidak bisa disebutkan satu persatu, yang telah banyak membantu dalam proses penyelesaian makalah ini.
DAFTAR ACUAN [1] Bang-Jensen, J. dan Gutin, G. 2007. Digraphs Theory, Algorithms and Applications. SpringerVerlag. [2] Blażewicz, J., Hertz, A., Kobler, D., dan de Wera, D. 1999. On Some properties of DNA Graphs. Discrete Appl. Math. 98 (1-2) 1 -19 [3] Hartsfield, N. dan Ringel, G. 2004. Pearls in Graph Theory, A Comprehensive Introduction. Dover Publication, Inc [4] Inne, Sugeng, K. A., dan Silaban, D. R. Preprint. DNA Graph Characterization for Line Digraph of Dicycle with One Chord. [5] Li, X. dan Zhang, H. 2007. Characterization for Some Types of DNA Graphs. Journal of Mathematical Chemistry Vol 42 No 2. 65 – 79.
Konstruksi pelabelan..., Marifah Puji Hasturi, FMIPA UI, 2013
