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

30
Pelabelan Total (a,d) – Sisi – Pelabelan Total (a,d) – Sisi – Anti Ajaib pada lingkaran dan Anti Ajaib pada lingkaran dan lintasan“ lintasan“ Oleh Oleh Dartono Dartono PEMBIMBING : Dr. RINOVIA SIMANJUNTAK PEMBIMBING : Dr. RINOVIA SIMANJUNTAK Institut Teknologi Bandung Institut Teknologi Bandung NIM : 20104020 NIM : 20104020

Upload: monet

Post on 06-Jan-2016

57 views

Category:

Documents


2 download

DESCRIPTION

“ Pelabelan Total (a,d) – Sisi – Anti Ajaib pada lingkaran dan lintasan“. Dartono. NIM : 20104020. Oleh. PEMBIMBING : Dr. RINOVIA SIMANJUNTAK. Institut Teknologi Bandung. TOPIK PEMBAHASAN. KONSEP DASAR HASIL SEBELUMNYA PERMASALAHAN TUJUAN HASIL UTAMA. KONSEP DASAR. - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: “ 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

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

TOPIK PEMBAHASAN

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

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

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

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

► 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

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

► 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

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

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

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

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

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

PERMASALAHAN

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

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

TUJUAN

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

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

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.

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

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)

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

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}

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

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

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

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

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

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.

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

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.

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

(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

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

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 :

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

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

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

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

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

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

1 9753

8642

11

10

1412108642

1513

1197531

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

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 :

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

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

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

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.

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

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

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

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

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

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)

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

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)

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

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.

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

TERIMA KASIHTERIMA KASIH