konstruksi graf simpul busur antiajaib (a,2) dengan matrix adjacency (stefi rahmawati ui)

Kolokium 25 November 2010

PENDAHULUAN

ISIDefinisi Graf

Matriks Adjacency

Pelabelan Graf

Isomorfik

Hasil yang diketahui

Himpunan simpul Himpunan busur

Himpunan pasangan tak terurut dari simpul-simpul

Contoh graf

Graf Lintasan P5

Graf Lingkaran C3Graf Bintang S5

A = [aij] berukuran |V| x |V|

= 1, jika ada busur yang menghubungkan simpul vi dan vj

= 0, lainnya

Contoh

v1 v5v4v2 v3

0 1 0 0 0

1 0 1 0 0

0 1 0 1 0

0 0 1 0 1

0 0 0 1 0

1v 2v 3v 4v 5v

1v

2v

3v

4v

5v

v1

v3 v2

v1

v5

v4

v2

v3

v6

1v 2v 3v

1v

2v

3v

0 1 1

1 0 1

1 1 0

1v 2v 3v 4v 5v

1v

2v

3v

4v

5v

6v

6v

0 0 0 0 0 1

0 0 0 0 0 1

0 0 0 0 0 1

0 0 0 0 0 1

0 0 0 0 0 1

1 1 1 1 1 0

1v 2v 3v 4v 5v

1v

2v

3v

4v

5v

6v

6v

0 0 0 0 0 1

0 0 0 0 0 1

0 0 0 0 0 1

0 0 0 0 0 1

0 0 0 0 0 1

1 1 1 1 1 0

1

10

0

v1

v5

v4

v2

v3

v6

f : V, E, atau V E subhimpunan bilangan asli

f : V {1, 2, …, |V|}

i j

Jumlah dari label simpul yang dihubungkan.

Bobot busur ij = i + j

1 3 4 52

Bobot Busur : 3 5 7 9

a = 3

d = 2 PSBAA-(3, 2)

Contoh graf SBAA-(a,d)

Pelabelan simpul, sehingga

Himpunan bobot busur =

{a, a + d, a + 2d, …, a + (|E|-1) d}

Graf Isomorfik

10

v1

v2 v3

v4v5

v6

v1' v2'

v3'

v4'v5'

v6'

G = (V, E)G’ = (V’, E’)

f : V → V’

f(v1) = v3’, f(v2) = v1’, f(v3) = v5’, f(v4) = v6’, f(v5) = v4’, f(v6)

= v2’ uv E f(u)f(v) E’

Pelabelan Isomorfik

11

Contoh pelabelan isomorfik:

G = (V, E)

l : V → L

G’ = (V’, E’)

l’ : V’ → L

f : V → V’

uv E f(u)f(v) E’

l(v) = l’(f(v))

1 11

8

49

3

1

4

9

3

8

11

v1

v2v3

v4v5

v6

v1' v2'

v3'

v4'v5'

v6'

Pelabelan Isomorfik

12

Contoh pelabelan tidak isomorfik

G = (V, E)

l : V → L

G’ = (V’, E’)

l’ : V’ → L

f : V → V’

uv E f(u)f(v) E’

l(v) = l’(f(v))

1 2

3

4

6

2

5

3

4

1

65

• Sugeng dan Miller (2005) :

Hubungan antara matriks adjacency dan pelabelan simpul

busur antiajaib (a,d) untuk d = 1 serta pelabelan total super

busur anti ajaib (a,d).

• Cavalier (2009) :

Hubungan antara matriks adjacency dan pelabelan Graceful.

Permasalahan

Metode

Ruang Lingkup

Tujuan

• Bagaimana kaitan antara matriks adjacency dan PSBAA-

(a,2)?

• Dapatkah dikonstruksi graf PSBAA-(a,2) yang baru

dengan memanfaatkan sifat-sifat matriks adjacency-nya?

Dibatasi untuk graf sederhana berhingga tak berarah.

Studi pustaka yang dikembangkan untuk menganalisa dan

mengkonstruksi teori baru.

• Menemukan kaitan antara matriks adjacency dan

PSBAA-(a,2).

• Menemukan cara mengkonstruksi graf SBAA-(a,2) yang

baru dengan memanfaatkan sifat-sifat matriks adjacency-

nya.

PENDAHULUAN

ISI

Definisi Graf

Matriks Adjacency

Pelabelan Graf

Isomorfik

Hasil yang diketahui

Matriks Adjacency dan

Pelabelan Graf

Konstruksi Graf Baru

Skew Diagonal

MA dan PSBAA-(a,2)

MA dan PSBAA-(a,2) maksimal

MA dan PSBAA-(a,2)

bobot busur ganjil/genap

v1

v3 v2

1v 2v 3v

1v

2v

3v

0 1 1

1 0 1

1 1 0

1

23

1

1

2

2

3

3

Bobot Busur = 1 + 2 = 3

Bobot Busur = 1 + 2 = 3

0

a21

0

0

a12

0

1

0

0

0

0

0

1

0

1

0

0

1

0

0

1

1

0

0

1 2

1

2

a1v

a2v

0

1

0

av1 av2 0 1 0 0

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

...

...

...

.

.

.

aij

a(i+1)(j-1)

a(i+2)(j-2)

Memiliki bobot busur

yang sama yaitu i+j.

|V|

|V|

0

1

0

0

0

1

0

1

0

0

0

0

0

1

0

1

0

0

1

0

0

1

1

0

0

1 2 3 4 5

1

2

3

4

5

34

5

9

Skew

diagonal Sk

S3

S4

S5

S9

11 12 13 14 1( 1) 1

21 22 23 24 2( 1) 2

31 32 33 34 3( 1) 3

41 42 43 44 4( 1) 4

( 1)1 ( 1)2 ( 1)3 ( 1)4 ( 1)( 1) ( 1)

1 2 3 4 ( 1)

.

n n

n n

n n

n n

n n n n n n n n

n n n n n n nn

a a a a a a

a a a a a a

a a a a a a

a a a a a a

a a a a a a

a a a a a a

S2n-1

S5

S4

S3

PENDAHULUAN

ISI

Matriks Adjacency dan

Pelabelan Graf

Konstruksi Graf Baru

Skew Diagonal

MA dan PSBAA-(a,2)

MA dan PSBAA-(a,2) maksimal

MA dan PSBAA-(a,2)

bobot busur ganjil/genap

• Memiliki skew diagonal berisi entri “0 “seluruhnya

atau tepat dua entri “1”

• Setiap dua skew diagonal tidak nol yang berurutan

akan diselingi tepat satu skew diagonal nol.

1 3 4 52

PSBAA-(3, 2)

0

1

0

0

0

1

0

1

0

0

0

0

0

1

0

1

0

0

1

0

0

1

1

0

0

1 2 3 4 5

1

2

3

4

5

3 5 7 9

Contoh

S3

S5

S7

S9

PENDAHULUAN

ISI

Matriks Adjacency dan

Pelabelan Graf

Konstruksi Graf Baru

Skew Diagonal

MA dan PSBAA-(a,2)

MA dan PSBAA-(a,2) maksimal

MA dan PSBAA-(a,2)

bobot busur ganjil/genap

0

1

0

0

0

1

0

1

0

0

0

0

0

1

0

1

0

0

1

0

0

1

1

0

0

1 2 3 4 5

1

2

3

4

5

S3

S5

S7

S9

0

0

1

1

0

0

0

0

0

0

1

0

1

0

1

0

0

1

0

0

0

0

0

0

0

1 2 3 4 5

1

2

3

4

5

S4

S6

S7

Bobot Busur Ganjil Bobot Busur Genap

0

0

0

0

0

0

0

1

0

0

0

0

0

1

0

1

0

0

1

0

0

1

1

0

0

1 2 3 4 5

1

2

3

4

5

S5

S7

S9

0

0

1

1

0

0

0

0

0

0

1

0

1

0

1

0

0

1

0

0

0

0

0

0

0

1 2 3 4 5

1

2

3

4

5

S4

S6

S7

Bobot Busur Ganjil Bobot Busur Genap

Tidak Maksimal

(a) Banyaknya busur dari suatu graf PSBAA-(a,2)

bobot busur ganjil maksimal adalah |V|-1.

(b) Banyaknya busur dari suatu graf PSBAA-(a,2)

bobot busur genap maksimal adalah |V|-2.

Observasi 1

PENDAHULUAN

ISI

Matriks Adjacency dan

Pelabelan Graf

Konstruksi Graf Baru

Skew Diagonal

MA dan PSBAA-(a,2)

MA dan PSBAA-(a,2) maksimal

MA dan PSBAA-(a,2)

bobot busur ganjil/genap

Membentuk Graf SBAA-(a,2) yang Setara Bobot Busur

Mengkontraksi Suatu Subgraf SBAA-(a,2)

Membentuk Graf SBAA-(a,2) yang Lebih Besar

0

1

0

0

1

1

0

0

0

0

0

0

0

1

0

0

0

0

1

1

0

1

1

0

0

0

0

1

2

34

5

1 2 3 4 5

1

2

3

4

5

3

5

7

9

Himpunan bobot busur :

{3, 5, 7, 9}G1

Himpunan bobot busur :

{3, 5, 7, 9}G2

G1 dan G2 setara bobot busur

Sehingga, untuk |V|=5, didapat

1

2

34

5

3

5

7

9

1

2

34

5

3

5

7

9

1

2

34

5

3

5

7

9

1

2

34

5

3

57

9

Himpunan

bobot busur

{3, 5, 7, 9}

Observasi 2

Untuk graf dengan 5 simpul

1 542 3

1

54

2

3

1

54

2 31

54

2

3

Graf PSBAA-(a,2) Bobot Busur Ganjil Maksimal yang

Setara Bobot Busur

Untuk graf dengan 6 simpul

1 542 3 6

1

54

2

3 6

1

54

2 3

6

1

54

2 3

6

1

5

42 3

6

1

54

2 3

6

15 4 236

1

5

4 2

36

1

5

4 2

6 3

1

5

4 2

36

1

54

2 3

6

1 54 2 36

Graf PSBAA-(a,2) Bobot Busur Ganjil Maksimal yang

Setara Bobot Busur

PENDAHULUAN

ISI

Matriks Adjacency dan

Pelabelan Graf

Konstruksi Graf Baru

Membentuk Graf SBAA-(a,2) yang Setara Bobot Busur

Mengkontraksi Suatu Subgraf SBAA-(a,2)

Membentuk Graf SBAA-(a,2) yang Lebih Besar

0

0

0

0

0

0

0

1

0

1

0

1

0

1

0

1

0

0

1

0

0

1

1

0

0

1 2 3 4 5

1

2

3

4

5

4 51 323 5 7 9

Setiap graf SBAA-(a,2) maksimal memiliki

subgraf SBAA-(a,2) nontrivial yang maksimal.

Teorema 3.1

Bukti

S3

S4

Sk

Si+j

11 12 1 1( 1) 1

21 22 2 2( 1) 2

1 2 ( 1)

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

1 2 ( 1)

k k n

k k n

k k kk k k kn

k k k k k k k n

n n nk n k nn

a a a a a

a a a a a

a a a a a

a a a a a

a a a a a

11 12 13 1

21 22 23 2

31 32 33 3

1 2 3

k

k

k

k k k kk

a a a a

a a a a

a a a a

a a a a

S3

S4

Sk

AA’

S2k-1

S2n-1

PENDAHULUAN

ISI

Matriks Adjacency dan

Pelabelan Graf

Konstruksi Graf Baru

Membentuk Graf SBAA-(a,2) yang Setara Bobot Busur

Mengkontraksi Suatu Subgraf SBAA-(a,2)

Membentuk Graf SBAA-(a,2) yang Lebih Besar

Membentuk Graf SBAA-(a,2) yang Lebih Besar

Menambah Busur pada Graf Awal

Menggabungkan Dua atau Lebih Graf-graf SBAA-(a,2)

Menggabungkan Sekaligus Menambah Simpul dan Busur

Sembarang graf SBAA-(a,2) yang tidak

maksimal dapat diperluas menjadi graf SBAA-

(a,2) yang maksimal.

Teorema 3.2

0

0

0

0

0

0

0

0

0

1

0

1

0

1

0

1

0

0

0

0

0

0

0

0

0

1 2 3 4 5

1

2

3

4

5

7

94 5

1 323 5

1

1 1

1

Contoh

0

0

0

0

0

0

0

0

0

1

0

1

0

1

0

1

0

0

0

0

0

0

0

0

0

1 2 3 4 5

1

2

3

4

5

7

94 5

1 323 5

1

1

1

1

Membentuk Graf SBAA-(a,2) yang Lebih Besar

Menambah Busur pada Graf Awal

Menggabungkan Dua atau Lebih Graf-graf SBAA-(a,2)

Menggabungkan Sekaligus Menambah Simpul dan Busur

Misalkan G1 dan G2 adalah graf SBAA-(a,2) maksimal

dengan jenis bobot busur yang sama (genap atau ganjil) masing-

masing berorder v dan w. Maka terdapat graf G3 yang merupakan

graf SBAA-(a,2) maksimal berorder v+w yang memuat G1 dan

G2 sebagai subgraf. G3 memiliki jenis bobot busur yang sama

dengan G1 dan G2 dengan tambahan satu busur untuk bobot

busur ganjil dan tambahan dua busur untuk bobot busur genap.

Teorema 3.3

Bukti

G1 A1

G2 A2

Contoh untuk bobot busur ganjil

0

0

1

0

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

0

0

0

1

0

0

1 2 3 4 5

1

2

3

4

5

0 0

0

1

0

1

0

1

0

1

0

1

0

0

1

0

1 2 3 4

1

2

3

4

41 323 5 7

7

94 5

1 323 5

G1

G2

0

0

1

0

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

0

0

0

1

0

0

0 0

0

1

0

1

0

1

0

1

0

1

0

0

1

00

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1 7

94 5

1 323 5

96 8713 15 17

11

G3

Teorema 3.4

0

0

1

0

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

0

0

0

1

0

0

0 0

0

1

0

1

0

1

0

1

0

1

0

0

1

0

7

94 5

1 323 5

6 8713 15

11

G3

G1

G2

0

0

1

0

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

0

0

0

1

0

0

0 0

0

1

0

1

0

1

0

1

0

1

0

0

1

0

7

94 5

1 323 5

6 713

11

G3

G1

G2

Misalkan G1 dan G2 adalah dua graf SBAA-(a.2) bobot busur

ganjil dengan order masing-masing adalah v dan w. Maka terdapat

graf G3 yang merupakan graf SBAA-(a,2) bobot busur ganjil

berorder v+w-1 dan v+w-2 yang memuat G1 dan G2.

Teorema 3.5

Misalkan G1 dan G2 adalah dua graf SBAA-(a.2) bobot busur

genap dengan order masing-masing adalah v dan w. Maka terdapat

graf G3 yang merupakan graf SBAA-(a,2) bobot busur genap

berorder v+w-1 , v+w-2, dan v+w-3 yang memuat G1 dan G2.

Teorema 3.6

Gi graf SBAA-(a,2) order vi

Ai , (i = 1, 2, …, p)

1

2

0 0

0 0

0 0 p

A

AA

A

Teorema 3.7

Teorema 3.8

Setiap graf SBAA-(a,2) memiliki suatu supergraf

SBAA-(a,2).

Akibat 3.1

Gi graf SBAA-(a,2) order vi

Ai , (i = 1, 2, …, p)

1

2

0 0

0 0

0 0 p

A

AA

A

Teorema 3.9

Bentuk umum :

1

2kv+2

: Graf SBAA-(a,2) bobot busur ganjil

Sebanyak k grafSebanyak k graf

0

0

1

0

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

0

0

0

1

0

0

1 2 3 4 5

1

2

3

4

5

7

94 5

1 323 5

G1

0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1

1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0

0

0

0

0

0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

1 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1

1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0

65

432

1615

14

13

12

2625

242322

1110

987

2120

191817

3130

292827

1 32

• Matriks adjacency suatu graf SBAA-(a,2) memiliki karakterisrik

khusus, yaitu merupakan matriks yang simetris dengan skew

diagonal - skew diagonal yang berisi elemen “0” seluruhnya atau

tepat dua elemen “1” dan setiap dua skew diagonal tidak nol yang

berurutan akan diselingi tepat satu skew diagonal nol.

• Matriks adjacency dapat digunakan untuk mengkonstruksi graf

SBAA-(a,2) yang baru dari graf SBAA-(a,2) yang sudah ada, yaitu

dengan membentuk :

1. Graf yang setara bobot busur dengan graf awal

2. Subgraf

3. Graf baru yang lebih besar.

K.A. Sugeng and M. Miller. 2005. Relationship between Adjacency

Matrices and Super (a,d)-Edge-Antimagic-Total Labeling of

Graphs. University of Ballarat, Australia.

Cavalier , Charles Michael. 2009. Graceful Labelings. University of

South Carolina, South Carolina.

Gallian, J. A. (2009). A Dynamic Survey of Graph Labeling. The

Electronic Journal of Combinatorics 5 , #DS6.

Rosen, K. H. (2003). Discrete Mathematics and Its Applictions (5

ed.). New York: McGraw-Hill

West, Douglas B. 1996. Introduction to Graph Theory. New Jersey :

Prentice-Hall.