“ pelabelan total (a,d) – sisi – anti ajaib pada lingkaran dan lintasan“

“ “ Pelabelan Total (a,d) – Sisi – Anti Pelabelan Total (a,d) – Sisi – Anti Ajaib pada lingkaran dan lintasan“Ajaib pada lingkaran dan lintasan“

OlehOleh

DartonoDartono

PEMBIMBING : Dr. RINOVIA SIMANJUNTAKPEMBIMBING : Dr. RINOVIA SIMANJUNTAK

Institut Teknologi BandungInstitut Teknologi Bandung

NIM : 20104020NIM : 20104020

TOPIK PEMBAHASAN

• KONSEP DASAR• HASIL SEBELUMNYA• PERMASALAHAN• TUJUAN• HASIL UTAMA

KONSEP DASARKONSEP DASAR► Pelabelan graf adalah suatu pemetaan satu-Pelabelan graf adalah suatu pemetaan satu-

satu yang memetakan himpunan dari elemen-satu yang memetakan himpunan dari elemen-elemen graf ke himpunan bilangan bulat positif.elemen graf ke himpunan bilangan bulat positif.

► Elemen-elemen graf : Elemen-elemen graf :

- Himpunan titik - Himpunan titik

- Himpunan sisi - Himpunan sisi

- Himpunan titik dan sisi - Himpunan titik dan sisi

► Pelabelan graf G = (V, E ) adalah suatu pemetaan: D → N, dimana D : domain, N : himp. label dari G.

► D = V maka disebut pelabelan titik

► D = E maka disebut pelabelan sisi

► D = V UE maka disebut pelabelan total

► Bobot sisiBobot sisi : jumlah label sisi dan label dua titik yang : jumlah label sisi dan label dua titik yang menempel pada sisi.menempel pada sisi.

► jika semua sisi mempunyai bobot sisi yang sama jika semua sisi mempunyai bobot sisi yang sama

maka pelabelan tersebut disebut pelabelan total- maka pelabelan tersebut disebut pelabelan total-

sisi-ajaib.sisi-ajaib.

► Jika semua sisi mempunyai bobot sisi yang Jika semua sisi mempunyai bobot sisi yang berbeda dan himpunan bobot sisi dari semua berbeda dan himpunan bobot sisi dari semua sisi sisi

membentuk barisan aritmetika dengan suku membentuk barisan aritmetika dengan suku pertama pertama aa dan beda dan beda d d maka pelabelan tersebut maka pelabelan tersebut

disebut pelabelan total-sisi-anti ajaibdisebut pelabelan total-sisi-anti ajaib

► Pelabelan total Pelabelan total ((a,da,d))-sisi-anti ajaib -sisi-anti ajaib pada pada grafgrafGG==GG((V,EV,E) adalah pemetaan satu-satu dari ) adalah pemetaan satu-satu dari V V ((GG) ) E E ((GG) pada {1, 2, . . . , ) pada {1, 2, . . . , v + ev + e}, sedemikian }, sedemikian hingga himpunan bobot sisi dari semua sisi di hingga himpunan bobot sisi dari semua sisi di G G adalah {adalah {a, a + d, a + a, a + d, a + 22d, . . . , a + d, . . . , a + ((e – 1e – 1))dd} } untuk suatu bilangan bulat positif untuk suatu bilangan bulat positif aa dan dan dd..

► Pelabelan total (Pelabelan total (a,da,d)-sisi-anti ajaib pertama kali )-sisi-anti ajaib pertama kali diperkenalkan oleh Rinovia Simanjuntak, Mirka diperkenalkan oleh Rinovia Simanjuntak, Mirka Miller, dan Francois BertaultMiller, dan Francois Bertault pada tahun 2000. pada tahun 2000.

Hasil-hasil sebelumnya.Hasil-hasil sebelumnya.

Untuk setiap lingkaran Untuk setiap lingkaran CCnn sudah ditemukan pelabelan total sudah ditemukan pelabelan total (a,d)-sisi-anti ajaib untuk (a,d)-sisi-anti ajaib untuk d d = 1 dan = 1 dan d d = 2 untuk lingkaran = 2 untuk lingkaran genap genap CCnn serta serta d d = 3 untuk lingkaran ganjil = 3 untuk lingkaran ganjil CCnn . .

Simanjuntak dkk [9] tahun 2000Simanjuntak dkk [9] tahun 2000

Untuk setiap lingkaran Untuk setiap lingkaran CCn n , n , n ganjilganjil sudah sudah ditemukan pelabelan total (a,d)-sisi-anti ajaib ditemukan pelabelan total (a,d)-sisi-anti ajaib untuk untuk d d = 2 dan = 2 dan d d = 4 untuk lingkaran ganjil = 4 untuk lingkaran ganjil CCnn ..Baca dkk [3] tahun 2001Baca dkk [3] tahun 2001 Untuk setiap lintasan Untuk setiap lintasan PPnn , n , n genap sudah ditemukan genap sudah ditemukan pelabelan total (a,d)-sisi-anti ajaib untuk pelabelan total (a,d)-sisi-anti ajaib untuk d d = 1 dan = 1 dan d d = 3 = 3 untuk lintasan ganjil untuk lintasan ganjil PPnn . . Simanjuntak dkk [9] tahun 2000Simanjuntak dkk [9] tahun 2000

Untuk lintasan Untuk lintasan PPn n , n , n ganjilganjil sudah ditemukan sudah ditemukan pelabelan total (a,d)-sisi-anti ajaib untuk pelabelan total (a,d)-sisi-anti ajaib untuk d d = 2 = 2 dan 4.dan 4. Baca dkk [3] tahun 2001Baca dkk [3] tahun 2001

PERMASALAHAN

Apakah ada pelabelan total (a,d)-sisi-anti ajaib pada lingkaran dan lintasan dengan jumlah titik genap.

TUJUAN

Untuk membuktikan bahwa lingkaran dan lintasan dengan jumlah titik genap mempunyai pelabelan total (a,d)-sisi-anti ajaib

HASIL UTAMAHASIL UTAMA Teorema 4.1 Teorema 4.1 Untuk setiap Untuk setiap nn ≥ 4, dan ≥ 4, dan nn

genap, genap,

lingkaran lingkaran CCn n mempunyai pelabelan total mempunyai pelabelan total ((nn+4,3)-sisi-anti ajaib. +4,3)-sisi-anti ajaib.

Akibat 4.1Akibat 4.1 Untuk setiap Untuk setiap nn ≥ 4, dan ≥ 4, dan n n genap, lingkaran genap, lingkaran CCn mempunyai mempunyai pelabelan total (2pelabelan total (2nn+2,3)-sisi-anti ajaib.+2,3)-sisi-anti ajaib.

Teorema 4.2Teorema 4.2 Untuk setiap Untuk setiap nn ≥ 4, dan genap, ≥ 4, dan genap, lintasan lintasan PPnn mempunyai pelabelan total mempunyai pelabelan total ((nn+4,4)-sisi-anti ajaib+4,4)-sisi-anti ajaib..

Teorema 4.3 Untuk Teorema 4.3 Untuk n n 2, lintasan 2, lintasan PPnn mempunyai pelabelan total (6,6)-sisi-anti mempunyai pelabelan total (6,6)-sisi-anti ajaib.ajaib.

Pelabelan total (a,d)-sisi-anti ajaib pada lingkaran C4, C6, C8 untuk d = 3

6

3

1

4

8

5

7

28

3

1

6

12 7

11

4

10

5

92 11

210

3

1

8

16

915

614

7

13

4

12

5

(a,d)=(8,3) (a,d)=(10,3) (a,d)=(12,3)

Teorema 4.1 Untuk setiap n ≥ 4, dan n genap,

lingkaran Cn mempunyai pelabelan total (n+4,3)- sisi-anti ajaib.

Pembahasan Hasil Utama

Bukti : Misalkan V (Cn) = {xi│1≤i ≤n }

E (Cn)= {xi xi+1│1≤i ≤n -1} {xn x1}

Perhatikan pelabelan total:

f : V (Cn) E (Cn) {1, 2, 3, …, 2n}

1, 1,3,5,..., 1;

( ) 3, ;

3, 2,4,6,..., 2.

i

i i n

f x i n

i i n

1

1, 1,

( )

2 , 1,2,3,..., 2,i i

i n

f x x

n i i n

dan

1( ) 2.nf x x n

Maka bobot sisi wf (xi xi+1),1 ≤ i ≤ n dari Cn,

1 1 1( ) ( ) ( ) ( )f i i i i i iw x x f x f x x f x

1

1 3 4, 1,

( )

7 3 , 1,2,3,..., 2,f i i

n n i n

w x x

n i i n

dan

1( ) 7f nw x x n

Maka himpunan bobot sisi Wf :

1 1( ) 1 1 ( )

4, 7, 10,..., 4 1

f f i i f nW w x x i n w x x

n n n n

Jadi, untuk setiap n ≥ 4, dan n genap, lingkaran Cn mempunyai pelabelan total (n+4,3)-sisi-anti ajaib.

Dengan dualitas (Teorema 3.3.1) kita mempunyai,

Akibat 4.1 Untuk setiap n ≥ 4, dan n genap, lingkaran Cn mempunyai pelabelan total (2n+2,3)-sisi-anti ajaib.

(a,d)=(12,4)

Pelabelan total (a,d)-sisi-anti ajaib P4, P6, dan P8 untuk d = 4

1

2 4 6

5 3 7

1 5937

8642

11

10

2 4 6 8 10 12 14

15713511391

(a,d)=(8,4)

(a,d)=(10,4)

119

Teorema 4.2 Untuk setiap n ≥ 4, dan genap, lintasan Pn mempunyai pelabelan total (n+4,4)-sisi-anti ajaib.

, 1,3,5,..., 1,

( )

1, 2, 4,6,..., .i

i i n

g x

n i i n

1( ) 2 , 1,2,3,..., 1.i ig x x i i n

Bukti : Labelkan himpunan titik dan sisi dari Pn dengan cara sebagai berikut :

Misalkan wg menyatakan bobot sisi dari Pn dan Wg

adalah himpunan bobot sisi :

Jadi, untuk setiap n ≥ 4, dan n genap, lintasan Pn mempunyai pelabelan total (n+4,4)-sisi-anti ajaib.

1 1 1( ) ( ) ( ) ( ) 1 1g g i i i i i iW w x x g x g x x g x i n

2 ( 1) 1 4 , 1,3,5,..., 1,

( 1) 2 ( 1) 4 , 2,4,6,..., 2.

4 1,2,3,..., 1

4, 8, 12,...,5 4

g

i i n i n i i n

W

n i i i n i i n

n i i n

n n n n

8642

1 9753

Pelabelan total (6,6)-sisi-anti ajaib dari P2, P3, P4, P5.

3

2

1

7

6

5

4

3

2

1

5

42

1 3

Pelabelan total (6,6)-sisi-anti ajaib dari P6 dan P8

1 9753

8642

11

10

1412108642

1513

1197531

untuk 1 ≤ i ≤ n - 1

Teorema 4.3 Untuk n 2,lintasan Pn mempunyai pelabelan total (6,6)-sisi-anti ajaib.

( ) 2 1,if x i

1( ) 2 ,i if x x i

untuk 1 ≤ i ≤ n

Bukti : Labelkan himpunan titik dan sisi dari Pn dengan cara sebagai berikut :

Jadi, untuk n 2, lintasan Pn mempunyai pelabelan total (6,6)-sisi-anti ajaib.

Maka himpunan bobot sisi Wf dari Pn:

1 1 1( ) ( ) ( ) ( ) 1 1

(2 1) (2 ) (2( 1) 11 1

6 1 1

6,12,18,...,6( 1)

f f i i i i i iW w x x f x f x x f x i n

i i i i n

i i n

n

Untuk lingkaran Cn , n genap, dengan d = 4,5, lingkaran Cn, n ganjil dengan d = 5, dan lintasan Pn , n genap dengan d = 5, kami belum dapat menemukan pelabelan total (a,d)-sisi-anti ajaib.

Pelabelan total (a,d)-sisi-anti ajaib pada lingkaran genap C4, C6, C8 dan C10 untuk d = 4

7

5

4

12

3

6

8

2

5

12

119

410

6

3

18

7

2

5

12

11

94

10

6

3

18

7

110

20

19

17

9

18

1416 7 11

156

8

4

5

12

32

13

Pelabelan total (a,d)-sisi-anti ajaib pada lingkaran genap C4, C6 dan C8 untuk d = 5

8

5

6

41

3

2

7

4

6

7

8

1211

10

5

2

13

9

9

32

5

14

12161315

8

11

7

64

10

1

Pelabelan total (a,d)-sisi-anti ajaib pada lingkaran ganjil C5 dan C7 untuk d = 5

3

2

7

6

910

8

5

4

21

9

3

4

5

7

6

128

13

14

11

2

10

1

(a,d)=(7,5) (a,d)=(8,5)

Pelabelan total (a,d)-sisi-anti ajaib dari lintasan genap P4 dan P6 untuk d = 5

7

5

4

6

1

2

3

4 6931

7582

10

11

(a,d)=(6,5)

(a,d)=(7,5)

OPEN PROBLEM

Untuk n genap, carilah pelabelan total (a,d)-sisi-anti ajaib dari lingkaran Cn dengan d = 4 dan 5.

Untuk n ganjil, carilah pelabelan total (a,d)-sisi-anti ajaib dari lingkaran Cn dengan d = 5. Untuk n genap, carilah pelabelan total (a,d)-sisi-anti ajaib dari lintasan Pn dengan d = 5.

TERIMA KASIHTERIMA KASIH