Home
Add Document
Sign In
Register
Seminar Nasional Matematika HIMPUNAN KRITIS PADA GRAF CYCLE CATERPILLAR. Chairul Imron Jurusan Matematika ITS
Home
Seminar Nasional Matematika HIMPUNAN KRITIS PADA GRAF CYCLE CATERPILLAR. Chairul Imron Jurusan Matematika ITS
1 Semar Nasoal Matematka HIMPUNAN KRITIS PADA GRAF CYCLE CATERPILLAR Charul Imro Jurusa Matematka ITS ABSTRAK Pelabela ada graf cycle caterllar C adal...
Author:
Dewi Pranoto
56 downloads
158 Views
199KB Size
Report
DOWNLOAD PDF
Recommend Documents
Aplikasi Himpunan Kritis Pada Pelabelan Graf Caterpillar Teratur C 4n
Himpunan Kritis Pada Graph Cycle
Seminar Nasional MATEMATIKA
Seminar Nasional MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA
Seminar Nasional MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA
Seminar Nasional Matematika dan Pendidikan Matematika 2010
SEMINAR HASIL TUGAS AKHIR Jurusan Matematika FMIPA ITS
PROSIDING SEMINAR NASIONAL MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA
PROSIDING SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA
Seminar Nasional Matematika 2009
78
HIMPUNAN KRITIS PADA GRAF CYCLE CATERPILLAR Chairul Imron Jurusan Matematika ITS
[email protected]
ABSTRAK Pelabelan pada graf cycle caterpillar C n ( s1, s 2,...,sn) adalah memberi label simpul dan sisi pada graf cycle caterpillar. Graf tersebut mempunyai sifat ajaib, jika jumlah label sisi dan label simpul yang insiden dengan sisi mempunyai jumlah yang sama pada semua sisi. Karena graf cycle caterpillar dapat dilabeli sedemikian hingga jumlah setiap sisi dan simpul yang insiden adalah sama maka graf cycle caterpillar mempunyai sifat ajaib. Himpunan kritis adalah suatu himpunan yang beranggotakan elemen-elemen yang dapat menentukan elemen lain dari suatu himpunan secara tunggal. Oleh karena itu, jumlah anggota dari himpunan kritis harus seminimal mungkin. Karena graf cycle caterpillar ajaib, maka dapat ditemukan himpunan kritis dari graf tersebut. Dengan mengetahui himpunan kritis dari suatu graf, khususnya graf cycle caterpillar, maka dapat direkonstruksi pelabelan dari graf tersebut beserta label yang lain sehingga graf ajaib (tetap ajaib). Dari hasil analisa pembahasan ditemukan anggota dari himpunan kritis dari graf cycle caterpillar adalah banyaknya daun plus a dari graf tersebut dengan 0
PENDAHULUAN Pelabelan yang domainnya berupa himpunan simpul, himpunan sisi, atau keduanya yang biasanya disebut dengan pelabelan simpul, pelabelan sisi, atau pelabelan total. Pada paper ini akan digunakan pelabelan total, sedangkan evaluasinya pada sisi. Telah dibahas pelabelan total sisi ajaib pada graf caterpillar dan pelabelan total sisi ajaib pada cycle, yakni pelabelan dimana jumlah label sisi dan label simpul-simpul yang menempel atau yang insiden pada sisi tersebut selalu sama untuk setiap sisi. Jumlah tersebut disebut angka ajaib, yang biasa dilambangkan dengan simbol huruf k. Ide pelabelan ini dikenalkan pertama kali oleh Sedlaek(Sed63) pada 1960-an, selanjutnya diformulasikan oleh Kotzig dan Rosa(KR70) pada tahun 1970-an. Bujursangkar latin adalah matriks berukuran n n dengan elemen-elemennya dipilih dari himpunan bilangan asli dengan n elemen sehingga setiap elemen terdapat pada Chairul Imron : 78-90 Himpunan Kritis Pada Graf Cycle Caterpillar
Seminar Nasional Matematika 2009
79
setiap baris dan setiap kolom sehingga setiap elemen yang sama tidak pernah terjadi pada baris atau kolom yang sama. Konsep tersebut yang digunakan untuk mencari himpunan kritis. Salah satu aplikasi dari himpunan kritis adalah pada bidang kriptographi. Pada paper ini akan dicari himpunan kritis pada pelabelan suatu graph. Graf yang akan dikaji adalah graf cycle caterpillar. Pelabelan pada sebuah graf diberi tanda dengan sejumlah label pada simpul dan sisi graf, sehingga setiap label sisi pada graf tersebut tergantung kepada label kedua simpul yang menempel pada sisi tersebut. Biasanya, label yang digunakan adalah bilangan bulat positif atau bilangan asli. Himpunan kritis pelabelan pada suatu graf adalah subhimpunan label dan posisi label tersebut yang bila dilengkapiakan menghasilkan pelabelan tersebut secara tunggal. Secara sederhana, jika diberikan subhimpunan label suatu graf dan posisinya, apakah himpunan tersebut hanya membangun graf yang sama dengan pelabelannya tersebut secara tunggal ? Jika ya, maka himpunan tersebut adalah himpunan kritis. Pada paper ini akan dihasilkan: antara lain mengkonstruksi pelabelan total sisi ajaib pada graf cycle caterpilar C n ( s1, s 2,...,sn) , kemudian menentukan himpunan kritis dari pelabelan total sisi ajaib di atas. Graf Graf tak berarah, selanjutnya disebut graf G , didefinisikan sebagai pasangan terurut
G
(V , E ) dimana V (G ) adalah himpunan hingga tak kosong {v1 , v2 , v3 ,..., vn } dan
E (G ) adalah
himpunan
mengakibatkan (v, u )
bagian
dari
V V dimana
berlaku
(u, v)
E (G)
E (G) . Anggota dari V (G ) disebut simpul dan anggota dari
E (G ) disebut sisi. Secara graphis simpul digambarkan sebagai titik dan sisi digambarkan sebagai ruas garis yang menghubungkan dua buah simpul. Banyak sisi dari G dilambangkan dengan | E (G ) | q dan banyak simpul dari G dilambangkan dengan | V (G) | p . Dua buah simpul disebut bertetangga, jika kedua simpul tersebut dihubungkan oleh sebuah sisi. Derajat suatu simpul, misal v , dilambangkan dengan
(v) , adalah banyaknya simpul yang bertetangga dengan v . Simpul berderajat satu pada
Chairul Imron : 78-90 Himpunan Kritis Pada Graf Cycle Caterpillar
Seminar Nasional Matematika 2009
80
suatu graf disebut daun.
Graf S4
Graf C3
Graf C(2,2,2)
Gambar 1. Graf Cycle, Star dan Caterpillar Suatu graf G dikatakan terhubung jika dapat dibuat lintasan yang menghubungkan setiap dua simpul pada graf tersebut. Lihat Gambar 1, adalah contoh dari graf cycle dengan tiga simpul, graf star dengan empat daun dan graf caterpillar dengan tiga star masing-masing star dengan dua daun. Semua graf di atas termasuk graf terhubung. Pelabelan Graf Pelabelan graf G adalah pemetaan satu-satu yaitu memetakan semua elemen (simpul dan sisi) dari graf ke suatu bilangan (bilangan bulat positif atau bilangan bulat tak negatif). Dengan kata lain, pelabelan graf adalah pemberian label pada simpulsimpul dan sisi-sisi dari graf, sehingga setiap simpul dan setiap sisi mempunyai label yang berbeda. Ada beberapa macam pelabelan, yaitu pelabelan yang domainnya berupa himpunan simpul, himpunan sisi, atau keduanya. Macam-macam pelabelan ini berurutan disebut pelabelan simpul, pelabelan sisi, dan pelabelan total. Pada penelitian ini, hanya membahas pelabelan total sisi ajaib yang didefinisikan sebagai berikut: Definisi: Pelabelan total sisi ajaib pada ( p, q) grafG adalah fungsi bijektif
: V (G)
E (G)
{1,2,3,, p q}
sedemikian sehingga ada suatu bilangan konstan k dimana
(u) dengan
(uv)
u, v V (G) dan
(v) uv
k
(1)
E (G) dan k dinamakan jumlahan ajaib (Magic
Sum) dari graf G . Graf yang mempunyai pelabelan total sisi ajaib dinamakan sisi-
Chairul Imron : 78-90 Himpunan Kritis Pada Graf Cycle Caterpillar
Seminar Nasional Matematika 2009
81
(V (G)) {1,2,3,, p} , dan G dikatakan super total sisi
ajaib \cite{Wall}. Jika ajaib\cite{Eno}.
2
10
6
7
10
3 4
19
11
7
8 5
4
8
6
2
1
2
3 7
1 9
8
18
3
13
9
(b)
5
10
16
1
4 (a)
12
14
20
5
9
11
17
6
(c)
Gambar 2. Pelabelan Total Sisi Ajaib dari Graf Cycle, Star dan Caterpillar Perhatikan Gambar 2. (a) adalah contoh pelabelan total sisi ajaib dari graf cycle dengan angka ajaib k
19 , Gambar 2. (b) adalah contoh pelabelan total sisi ajaib
dari graf star dengan angka ajaib k
14 ,dan Gambar 2. (c) adalah contoh pelabelan
total sisi ajaib dari graf caterpillar dengan angka ajaib k
28 .
Perhitungan Dasar Diketahui graf G
M
p
(V , E ) dengan p | V (G ) | simpul dan q | E (G) | sisi. Misal
q dan simpul v i berderajat
Sedangan sisi e j
v jv j
1
i
mempunyai label x i ditulis
mempunyai label y j ditulis
(e j )
y j dan
(vi ) i
xi .
derajat dari
simpul ke-i yang bukan simpul daun. Maka jumlah total sisi ajaib dari semua sisi pada suatu graf, adalah jumlah label dari semua sisi ditambah dengan semua simpul, sehingga label pada simpul dihitung p
qk
i q
xi i 1
kali, maka p
yi i 1
(
1) xi
i
i 1 p
qk
(1 2 3 M )
(
i
1) xi
i 1
atau qk
M
1 2
p
(
i
1) x i
i 1
Chairul Imron : 78-90 Himpunan Kritis Pada Graf Cycle Caterpillar
Seminar Nasional Matematika 2009
82
Himpunan Kritis Himpunan kritis awalnya diterapkan pada persegi latin, yaitu suatu persegi yang setiap kolom atau baris tidak boleh diisi dengan bilangan sama. Jika persegi tersebut berukuran n n , maka perlu menyimpan data sebanyak n 2 , tetapi tidak perlu menyimpan secara keseluruhan data, yang disimpan hanya beberapa yang dapat mewakili data tersebut. Himpunan beberapa data tersebut dinamakan himpunan kritis dari persegi latin. Pada penelitian ini akan ditentukan himpunan kritis dari suatu graf dengan pelabelan total sisi ajaibnya, khususnya graf cycle caterpillar, dengan mengadaptasi sifat-sifat himpunan kritis pada persegi latin. Diberikan graf G dengan pelabelan
yang dikenakan pada graf G . Misalkan
Q
{Q1 , Q2 , , Qc } , | Q | c , pada pelabelan
Qi
( j , x j ) dengan j menunjukkan posisi dari suatu simpul atau sisi dengan label
dari graf G adalah himpunan
ajaib x j . Q (G ) adalah himpunan kritis untuk pelabelan
pada graf G dan, jika
memenuhi : 1.
Q (G) hanya dapat membangun
2.
Setiap subset dari Q (G) tidak memenuhi sifat (1)
pada graf G
Jika suatu himpunan kritis memiliki c anggota maka himpunan kritis tersebut berukuran c . Himpunan da kritis Q (G) dikatakan minimal jika ukuran setiap himpunan kritis lainnya lebih ri atau sama dengan Q (G) . METODE Secara formal, himpunan kritis Q
{Q1 , Q2 , , Qc } untuk pelabelan total sisi ajaib
pada graf G dengan n titik adalah himpunan sejumlah label titik dan/atau sisi dimana jika salah satu dihapuskan maka pelabelan total sisi ajaib pada graf tersebut tidak dapat dilengkapi secara tunggal. Disamping mengetahui himpunan kritis, dapat juga melakukan pencacahan dari semua pelabelan total sisi ajaib yang mungkin untuk graf yang akan digunakan. Chairul Imron : 78-90 Himpunan Kritis Pada Graf Cycle Caterpillar
Seminar Nasional Matematika 2009
83
Dalam hal ini, graf yang akan digunakan adalah graf cycle caterpillar. Pelabelan total sisi-ajaib pada graf-graf tersebut telah banyak dikaji dan diantaranya dihasilkan oleh penulis (dkk). Pencacahan semua pelabelan yang mungkin untuk suatu graf diperlukan untuk mendapatkan variasi dari skema membagi rahasia. Penelitian ini akan dilakukan dengan pentahapan berikut ini: 1.
Tahap Pelabelan Graf. Pada tahap ini dilakukan bagaimana memberi label atau enumerasi pada graf cycle caterpillar yang merupakan gabungan graf cycle dan graf star. Pada tahap ini pula peneliti akan mencari berbagai cara atau berapa cara memberi label pada graf sedemikian hingga graf menjadi total sisi ajaib.
2.
Tahap Pencarian Himpunan Kritis. Setelah ditemukan cara memberi label pada graf dan graf sudah terlabeli, selanjutnya adalah menyelidiki tentang himpunan kritis pada pelabelan total sisi ajaib pada graf di atas. Pada tahap ini diharapkan mendapatkan pengetahuan tentang bagaimana merekonstruksi himpunan kritis dari suatu pelabelan. HASIL DAN PEMBAHASAN Pada bagian ini akan dibahas bagaimana mencari perhitungan dasar dari graf cycle caterpillar, kemudian melabeli graf cycle caterpillar, dan dilanjutkan dengan mencari himpunan kritis graf cycle caterpillar. Setelah ditemukan himpunan kritis akan dicari atau disusun skema pembagian rahasia berdasarkan pelabelan total sisi ajaib dari graf cycle caterpillar. Gambar 3. adalah gambar dari graf cycle caterpillar. vn 1
vn2
vnm
v11
v12
v1k v2 1
vn 0
v22
v10
v2 l
v2 0
Gambar 3. Graf Cycle Caterpillar
Chairul Imron : 78-90 Himpunan Kritis Pada Graf Cycle Caterpillar
Seminar Nasional Matematika 2009
84
Perhitungan Dasar Perhatikan Gambar 3, sebuah graf cycle caterpillar terdiri sebuah graf cycle C n dan n buah star, sehingga derajat dari pusat star ke-i (misal:
derajatnya bertambah menjadi
i
) pada cycle, maka
2 . Graf cycle caterpillar C n ( S1, S 2,, Sn) terdiri dari
i
p simpul dengan p | V (C n ( S1, S 2,, Sn) ) | dan q sisi dengan q | E (C n ( S1, S 2,, Sn) ) | , n
dimana p
s i dan q
n
p untuk semua simpul dan sisi dilabeli dengan
i 1
bilangan bulat positip dengan bilang ajaibnya k , maka q
p
qk
(e i )
(
i 1
2) ( v i )
i
i 1
q
p
(e i )
p
(v i )
i 1
(
i 1 p q
i
1) (v i )
i 1 p
i i 1
(
i
1) (v i )
i 1
Besar kecilnya bilangan ajaib tergantung pada label yang ada pada simpul. Label simpul dengan derajat yang paling besar diberi label bilangan yang besar memungkinkan bilangan ajaibnya akan paling besar. Label simpul dengan derajat yang paling besar diberi label bilangan yang paling kecil memungkinkan bilangan ajaibnya akan paling kecil. Pelabelan Graf Cycle Caterpillar Dengan menggunakan ide dari ketiga graf di atas yaitu graf cycle, graf star dan graf caterpillar dan dengan menggunakan definisi diatas, dapat ditemukan beberapa variasi pelabelan graf cycle caterpillar dengan teorema dibawah ini. Gambar 3 dimodifikasi bentuknya, yaitu dengan mengubah susunan simpul pusat star dengan sim[pul daun, sehingga terbentuk seperti Gambar 5. a1
a2
am+1
as+1 as
as+2 am
am+2 am+3
ap-1
ap
Gambar 4 Modifikasi Graf Cycle Caterpillar Chairul Imron : 78-90 Himpunan Kritis Pada Graf Cycle Caterpillar
Seminar Nasional Matematika 2009
85
Teorema Setiap Graf cycle caterpillar C n ( S1, S 2,, Sn) merupakan pelabelan total sisi ajaib. Bukti: Dengan memberi label pada setiap simpul dengan (ai ) i dengan i 1,2,3, , p
dan label pada sisi ( e i ) yang menghubungkan simpul pusat star dan simpul daun (ei ) i dengan i
p
q, p
q 1, p
q 2, , p 1
untuk memahami lebih jelasnya, perhatikan contoh graf cycle caterpillar C 3( 2,3, 4 ) . 1
2
24
23
3 22
21 20
8
4
5
6 15 17 18 16 19 14
7
9 10
11
12
13
Gambar 5 Graf Cycle Caterpillar C 3( 2,3, 4 ) dengan k
33
Himpunan Kritis Graf Cycle Caterpillar Pada bab ini akan dibahas beberapa teorema (sebagai hasil utama) yang berkaitan dengan himpunan kritis pelabelan suatu graph. Sebelum menerapkan konsep himpunan kritis pada pelabelan suatu graph, pandang persegi latin parsial $L_1$ dan $L_2$, dan persegi latin $L$ berorde $3 \times 3$ berikut : Sekarang yang akan dicari adalah himpunan kritis dari suatu graph, khususnya graf cycle caterpillar. Perhatikan lemma berikut ini. Lemma Jika n adalah banyaknya daun yang dimiliki oleh suatu graf G , maka Q (G) untuk setiap pelabelan total sisi ajaib
n
.
end{lemma} Bukti:
Chairul Imron : 78-90 Himpunan Kritis Pada Graf Cycle Caterpillar
Seminar Nasional Matematika 2009
86
Misalkan {v1 , v2 , v3 , , vn } adalah daun dari graf G dan {e1 , e2 , e3 , , en } adalah sisi yang menempel pada daun. Misalkan Q (G) n , maka ada suatu i , misal i
dan/atau
(vi )
xi dan
j , sehingga
(ei )
y i . Andaikan
Q (G ) tidak memuat x j
y j sekaligus. Dengan menukarkan posisi x j dan y j akan diperoleh
pelabelan total sisi ajaib yang lain. Maka Q (G ) bukan himpunan kritis dari G . Jadi haruslah Q (G)
n.
Graf cycle caterpillar dibangun dari gabungan graf cycle dan graf star, yaitu setiap simpul dari cycle merupakan pusat star. Lihat Gambar 3 atau 4 dan dengan mengacu teorema diatas dapat ditulis teorema berikut: Teorema Misal
n
adalah pelabelan total sisi ajaib pada graf cycle caterpillar C n ( S1, S 2,, Sn) n
maka ada suatu Q i (C n ( S1, S 2,, Sn) ) dimana Q i (C n ( S1, S 2,, Sn) )
d i , dengan d i i 1
adalah banyaknya daun pada star ke- i . Bukti: Pandang graf cycle caterpillar C n ( S1, S 2,, Sn) dengan V
{S1 , S 2 , S 3 , , S n } dimana
S1
v10 , v11 , v12 , , v1d1 dan d 1 adalah banyaknya daun pada S 1 ,
S2
v 20 , v 21 , v 22 , , v 2 d 2 dan d 2 adalah banyaknya daun pada S 2 ,
seterusnya samapai dengan Sn
v n0 , v n1 , v n 2 , , v ndn dan d n adalah banyaknya daun pada S n ,
vi 0 adalah simpul pusat star ke- i .
Jumlah simpul pada graf cycle caterpillar C n ( S1, S 2,, Sn) adalah jumlah semua daun pada setiap star ditambah dengan jumlah simpul pusat star atau
Chairul Imron : 78-90 Himpunan Kritis Pada Graf Cycle Caterpillar
Seminar Nasional Matematika 2009
|V |
(d 1
1)
87
(d 2 d1
1) d2
(d 3 1) (d n d3 dn n
1)
n
n
di i 1
Telah diketahui diatas bahwa banyaknya anggota himounan kritis dari sebuah graf star dengan n daun adalah minimal n , sedangkan anggota himpunan kritis pada graf cycle tergantung pada posisi dan label. Sedangkan graf cycle caterpillar merupakan gabungan dari graf cycle dan graf star, maka banyaknya anggota himunan kritis dari graf cycle caterpillar minimal banyaknya daun pada graf teresebut atau n
Q i (C n ( S1, S 2,, Sn) )
.
di i 1
Oleh karena itu, banyaknya anggota himpunan kritis dari graf cycle caterpillar sama dengan atau lebih besar dari banyaknya daun dari graf tersebut. Dengan memperhatikan label pada
daun dapat ditukar dengan label pada sisi yang
menghubungkannya, sehingga anggota dari himpunan kritis dapat bervariasi. Artinya anggota dari himpunan kritis dapat berupa posisi dan label daun saja, posisi dan label sisi yang menghubungkan ke daun, atau kombinasi keduanya.
5
3
13
2
1
15 17
4
2 1
6
8
10
18
12 14
13
16 15
16 6
7 9
17
7
8
11
3
14
4 5 12 11
9
18 10
(a)
(b)
Gambar 6 Posisi dan Label dari C 3(1, 2,3) dengan k
25
Perhatikan Gambar 6 (a) adalah posisi dan Gambar 6 (b) adalah label dari graf cycle caterpillar yang merupakan pelabelan total sisi ajaib dengan k
25 . Sehingga dapat
ditulis sebagai berikut
(C 3(1, 2,3) )
{(1,6), (2,18), (3,1), (4,17), (5,2), (6,16), (7,7), (8,15), (9,8), (10,14), (11,9), (12,13), (13,3), (14,2), (15,4), (16,11), (17,5), (18,10)} Chairul Imron : 78-90
Himpunan Kritis Pada Graf Cycle Caterpillar
Seminar Nasional Matematika 2009
2
1 18
17
13
16
14
15 6
3
7
88
5
18
12 11
17
6
14
7
4 5 12 11
9
8
10
3 13
16
15
9
8
2
1
4
10
(a)
(b)
Gambar 7 Himpunan Kritis dari Gambar 6 (b) Pandang Gambar 7 (a), merupakan himpunan kritis dari Gambar 6 (b), jika ditulis Q
{(2,18), (6,16), (8,15), (12,13), (14,12), (16,11)}
1
begitu juga untuk Gambar 7 (b), merupakan himpunan kritis Gambar 6 (b), jika ditulis Q
2
{(1,6), (2,18), (6,16), (8,15), (12,13), (14,12), (16,11)} 2
1 18
17
13
16 15
6
3
7 8
14
10
1
4 5 12 11
9
18
9
3
6 13
16 15
14
4 5 12 11
7 8
17
2
10 (a)
(b)
Gambar 8 Hasil rekronstruksi ulang Gambar 7 (a) Tetapi setelah dilakukan rekonstruksi, maka Gambar 7 (a) atau Q 1 (C 3(1, 2,3) ) bukan merupakan himpunan kritis, sebab setelah direkonstruksi ulang menghasilkan lebih dari satu buah pelabelan yang berbeda, yaitu pada Gambar 8. Sedangkan Gambar 7 (b) merupakan himpunan kritis karena setelah dilakukan rekonstruksi hanya menghasilkan satu pelabelan saja. Jadi himpunan kritis dari sebuah pelabelan total sisi ajaib pada graf cycle caterpillar C 3(1, 2,3) , adalah tergantung pada banyaknya daun dan anggota dari himpunan kritis
terdiri dari label daun saja, sisi dari daun saja atau kombinasi keduanya plus label pusat star.
Chairul Imron : 78-90 Himpunan Kritis Pada Graf Cycle Caterpillar
Seminar Nasional Matematika 2009
89
KESIMPULAN Dari uraian diatas dapat diambil kesimpulan sebagai berikut: 1. Graf cycle caterpillar C n ( S 1, S 2, S 3,, Sn) mempunyai sifat graf ajaib, karena dapat dilabeli sedemikian hingga jumlah setiap sisi dengan simpul yang insiden dengan sisi tersebut berjumlah sama untuk setiap sisi pada graf tersebut. n
2. Jika p
d i yaitu banyaknya daun pada graf caterpilar C n ( S 1, S 2, S 3,, Sn) , i 1
maka banyaknya anggota himpunan kritis dari graf tersebut adalah minimal
p
a dengan 0 a
n.
3. Anggota dari himpunan kritis terdiri dari label daun saja, sisi dari daun saja atau kombinasi keduanya plus label pusat star. SARAN Penelitian ini merupakan penelitian awal, jadi masih banyak yang harus dilakukan atau lebih tepatnya belum sempurna. Hasil penelitian ini dapat diaplikasikan untuk pembagian kunci rahasia, baik kunci rahasia di suatu perusahaan atau yang lainnya. Harapan dari peneliti, bahwa aplikasi dari himpunan kritis dari suatu graf ajaib dapat dimaksimalkan penggunaannya. DAFTAR PUSTAKA 1. Kotzig and A. Rosa, Magic Valuations of Finite Graph, {\em Canad. Math. Bull.} 13 (1970), 451-461. 2. Chairul Imron, Variasi Pelabelan Graf Lintasan dan Star, Seminar Nasional Matematika ITS, 4 Desember 2004. 3. Chairul Imron, Several Ways to Obtain Edge-Magic Total Labelings of Caterpillars, International Workshop on Graf Labeling, Batu, Malang, 6-9 Desember 2004. 4. Chairul Imron, Budi S., Rinovia S, Edy T. Baskoro, Himpunan Kritis pada Graph Caterpillar, KNM XIII, UNNES, Semarang, 24-27 Juli 2006. (prosiding) 5. Chairul Imron, Budi S., Rinovia S, Edy T. Baskoro, Critical Set of Caterpillar Graph for Secret Sharing Scheme, ICGTIS, Matematika ITB, Bandung, 10-13 Februari 2007. (prosiding) Chairul Imron : 78-90 Himpunan Kritis Pada Graf Cycle Caterpillar
Seminar Nasional Matematika 2009
90
6. Chairul Imron, Budi S., Rinovia S, Edy T. Baskoro, Laporan Penelitian Himpunan Kritis pada Graph Caterpillar, DP2M DIKTI, 2006, 2007. 7. Chairul Imron, Batasan Bilangan Ajaib pada Graph Caterpillar, Jurnal Limits Matematika ITS, Vol. 3 No. 2 Nov 2006. 8. Enomoto, H., A.S. Llado, T. Nakamigawa and G. Ringel, 1998, Super EdgeMagic Graphs, SUT Jurnal of Mathematics, Vol. 34, No. 2, 105-109. 9. J. Sedlacek, problem 27, {\em Theory of Graphs and it's Applications} (Smolenice, 1963), 163-164, Publ. House Czechoslovak Acad. Sci.,Prague, 1964). 10. K.A. Sugeng, {\em Magic and Antimagic Labeling of Graphs}, Disertasi, 2005. 11. W.D. Wallis, {\em Magic Graphs}, Birkhauser , Boston, 2001.
Chairul Imron : 78-90 Himpunan Kritis Pada Graf Cycle Caterpillar
×
Report "Seminar Nasional Matematika HIMPUNAN KRITIS PADA GRAF CYCLE CATERPILLAR. Chairul Imron Jurusan Matematika ITS"
Your name
Email
Reason
-Select Reason-
Pornographic
Defamatory
Illegal/Unlawful
Spam
Other Terms Of Service Violation
File a copyright complaint
Description
×
Sign In
Email
Password
Remember me
Forgot password?
Sign In
Our partners will collect data and use cookies for ad personalization and measurement.
Learn how we and our ad partner Google, collect and use data
.
Agree & close