BAB II Graf dan Pelabelan Total Sisi-Ajaib Super

BAB II Graf dan Pelabelan Total Sisi-Ajaib Super

BAB II Graf dan Pelabelan Total Sisi-Ajaib Super 2.1 Graf dan Beberapa Definisi Dasar Graf G=(V,E) didefinisikan sebagai pasangan terurut himpunan berhingga dan tak hampa V dan himpunan E. Himpunan V dinamakan himpunan titik dan himpunan E dinamakan himpunan sisi. E bisa pula berarti sebagai himpunan pasangan tak terurut dari titik-titik anggota V. Banyak titik pada suatu graf dinotasikan dengan |V| yang dikenal pula sebagai orde graf. Banyak sisi dinotasikan dengan |E|. Graf sering direpresentasikan dalam bentuk gambar. Sebagai ilustrasi, graf G1 dengan V={v1, v2, v3, v4, v5, v6, v7} dan E={v1v4, v2v6, v3v4, v6v4, v5v7, v6v7, v6v2, v3v5} dapat direpresentasikan seperti pada Gambar 2.1 di bawah ini. v1

v7

v2

e7

e6

e1

e5 e2 v6 v5

e8

v3

e3 v4

e4

Gambar 2.1: G1=(V1,E1)

Dari Gambar 2.1 terlihat bahwa e1=v1v4, e2=v2v6, e3=v3v4, e4=v6v4, e5=v5v7, e6=v6v7, e7=v6v2 dan e8=v3v5 . Banyak titik pada G1 adalah |V1|=7, sedangkan banyak sisi adalah |E1|=8. Dengan demikian orde G1 adalah |G1|=7. Titik v ∈ V dikatakan ujung sisi e ∈ E jika e=uv untuk suatu u ∈ V. Dalam hal ini, e dikatakan terkait di v. Setiap sisi senantiasa memiliki dua buah ujung yang berbeda yang dinamakan link atau memiliki dua buah ujung yang identik yang 4 Pelabelan total sisi ajaib super pada graf bintang yang diperumum


dinamakan loop. Banyak sisi terkait di v dinamakan derajat v, dinotasikan dengan d(v). Dua titik u dan v di V dikatakan bertetangga jika uv adalah sebuah sisi di E. Perhatikan Gambar 2.2 di bawah ini. e5 v7

e1

v1

e6 v2

e8

e7

e2 e3

v6 v3 v5 v4

e4


Pada Gambar 2.2 e4 adalah loop, sedangkan sisi-sisi lainnya di E2 adalah link. Kemudian d(v3) =d(v4) =d(v6) =1, d(v2)=2, d(v5)=3, d(v1)= d(v7)=4. Pada gambar dapat pula dilihat bahwa v3 bertetangga dengan v7, v2 bertetangga dengan v1, dan v1 bertetangga dengan v7. Misalkan G1=(V1,E1) dan G2=(V2,E2). G1 dikatakan subgraf dari G2, dinotasikan dengan G1 ⊆ G2, jika V1 ⊆ V2 dan E1 ⊆ E2. Gabungan graf G1 dan G2, dinotasikan dengan G1 ∪G2, didefinisikan sebagai graf dengan himpunan titik V1 ∪ V2 dan himpunan sisi E1 ∪ E2. n kali G1, dinotasikan dengan nG1, didefinisikan sebagai gabungan n buah G1. Perhatikan Gambar 2.3, 2.4, 2.5, dan 2.6 di bawah ini. e1 v1

v2 v2

e5

e2 e3

v3

e3

v5 v4 v4

e4


Gambar 2.4: G4=(V4,E4) ⊆ G3

5 Pelabelan total sisi ajaib super pada graf bintang yang diperumum


e1 v1

v2

v2 e2

e5

e3

v3

e3 v5

v6

e6

e6

v6 v4

v4

e4

Gambar 2.6: G3 ∪ G5


Graf lintasan Pn=(V,E) adalah graf berorde n dan titik-titiknya dapat diurutkan menjadi barisan v1,v2,v3,...,vn-1,vn sedemikian sehingga E={v1v2,v2v3,...,vn-1vn}. Dalam hal ini v2,v3,..., dan vn-1 dinamakan titik internal, dan v1 dan vn dinamakan titik ujung lintasan. Panjang lintasan didefinisikan sebagai banyaknya sisi di lintasan. Sebagai ilustrasi, perhatikan P5 pada Gambar 2.7. v1

e1

v2

e2

v3

e3

e4

v4

v5

Gambar 2.7: Graf lintasan P5

Graf lingkaran Cn=(V,E) adalah graf berorde n dan titik-titiknya dapat diurutkan menjadi barisan v1,v2,v3,...,vn-1,vn,v1 sedemikian sehingga E={v1v2,v2v3,...,vn-1vn, vnv1}. Sebagai ilustrasi, perhatikan C5 pada Gambar 2.8. e2 e1

v3 e3

v2

v4

v1

e5

v5

e4

Gambar 2.8: Graf lingkaran C5

Graf G dikatakan terhubung jika untuk setiap dua titik u,v yang berbeda di G, terdapat subgraf lintasan dari G dengan u,v sebagai ujung-ujungnya. 6 Pelabelan total sisi ajaib super pada graf bintang yang diperumum


2.2 Beberapa kelas graf Graf pohon Tn adalah graf terhubung berorde n yang tidak memuat lingkaran sebagai subgrafnya. Titik-titik berderajat satu pada pohon dinamakan daun. Setiap pohon yang nontrivial, memiliki setidaknya dua daun. Perhatikan gambar 2.9 di bawah ini, v3 e1

e2

v2

e3 v4

v1 v5

e4

Gambar 2.9: Graf pohon T5

Beberapa subkelas dari graf pohon adalah graf katerpilar Ĉn, graf bintang Sn, graf pohon pisang BT(n1,n2,n3,...,nk), dan graf bintang yang diperumum S mn . Graf katerpilar Ĉn ialah graf pohon berorde n yang bersifat jika semua daunnya dibuang, maka akan dihasilkan graf lintasan. Perhatikan graf katerpilar Ĉ9 pada Gambar 2.10. Jika semua daun pada Ĉ9 dibuang maka akan dihasilkan graf lintasan P3={v1,v2,v3}. v5

v7

v6

v1

v2

v3

v8

v4

v9

Gambar 2.10: Graf katerpilar Ĉ9

Graf bintang Sn adalah graf pohon berorde n+1 dan memiliki 1 titik berderajat n. Untuk mempermudah pembahasan, titik v ∈ Sn berderajat n dinamakan pusat bintang, dan setiap P2 ⊆ Sn dinamakan sinar bintang. Pada Gambar 2.11 dapat dilihat S8 dengan pusat bintang v1 dan 8 buah sinar bintang, yakni v1v2, v1v3, v1v4, v1v5, v1v6, v1v7, v1v8 dan v1v9. 7 Pelabelan total sisi ajaib super pada graf bintang yang diperumum


v4 v3

v5

v2

v1

v6

v7

v9 v8

Gambar 2.11: Graf bintang S8

Misalkan Sn1, Sn2,...,Snk masing-masing merupakan graf bintang yang saling lepas. Misalkan pula v suatu titik baru. Jika v dibuat bertetangga dengan satu titik ujung di Sn1, Sn2, ..., dan Snk, maka graf baru yang diperoleh dinamakan graf pohon pisang, dinotasikan dengan BT(n1,n2,…,nk). Untuk memudahkan ilustrasi perhatikan BT(5,4,3) pada Gambar 2.12.

v12

v13

v11

v21

v22

v23

v14 v15 v2

v1 v0

v3

v34

v31 v32

v33

Gambar 2.12: Graf pohon pisang BT(5,4,3)

Graf bintang yang diperumum S mn untuk n ≥ 3 dan m ≥ 0, adalah graf yang dibentuk dari graf bintang dengan cara men-subdivisi sisi-sisi pada setiap sinar bintang sedemikian hingga setiap sinar bintang yang terbentuk masing-masing memiliki m titik internal. Subdivisi suatu sisi e=uv ∈ G didefinisikan sebagai operasi menghapuskan e, kemudian menggantinya dengan sebuah lintasan 8 Pelabelan total sisi ajaib super pada graf bintang yang diperumum


w0w1w2…wmwm+1 dengan w0=u, wm+1=v. Akibatnya, S mn memiliki nm+n+1 titik dan nm+n sisi. Pada S mn , titik v ∈ S mn berderajat n dinamakan pusat bintang yang diperumum dan lintasan berorde m+2 dengan salah satu titik ujung v dinamakan sinar bintang yang diperumum. Sebagai contoh, tinjau kembali graf bintang S8 pada Gambar 2.11. Jika setiap sisi pada sinar bintang S8 disubdivisi sedemikian hingga setiap sinar bintangnya memiliki 2 titik internal, maka akan diperoleh graf baru yakni graf bintang yang diperumum S 82 seperti tampak pada Gambar 2.13. v4 v3

v5

v20 v19 v11

v2

v13

v10

v18

v17

v1 v16

v14

v6

v22

v15 v23

v25 v9

v21

v12

v24

v7

v8

Gambar 2.13: Graf bintang yang diperumum S 82

Pada Gambar 2.13, S 82 memiliki nm+n+1=8.2+8+1=25 titik dan nm+n= 8.2+8= 24 sisi. Pada S 82 , v1 merupakan pusat bintang yang diperumum dan beberapa sinar bintang yang diperumumnya adalah v1v10v18v2, v1v14v22v6, dan v1v16v24v8.

2.3 Pelabelan Total Sisi-Ajaib Super Pelabelan graf ialah fungsi yang mengaitkan titik atau sisi pada graf ke bilangan asli yang disebut label. Telah disinggung pada Bab I, beberapa jenis pelabelan yakni pelabelan titik, pelabelan sisi, dan pelabelan total. Pelabelan titik adalah pelabelan dengan domain himpunan titik, pelabelan sisi adalah pelabelan dengan domain himpunan sisi, dan pelabelan total adalah pelabelan dengan domain gabungan himpunan titik dan himpunan sisi. 9 Pelabelan total sisi ajaib super pada graf bintang yang diperumum


Misalkan G=(V,E) suatu graf dengan |V|=p dan |E|=q. Pelabelan total sisi-ajaib adalah fungsi injektif f dari V ∪ E ke {1,2,…,p+q} pada G sedemikian hingga terdapat bilangan bulat positif k yang memenuhi f(u) + f(uv) + f(v), untuk setiap uv ∈ E. k disebut konstanta ajaib, dan graf yang memenuhi pelabelan total sisi-ajaib dinamakan graf total sisi-ajaib. Pelabelan total sisi-ajaib dengan f(V) = {1,2,...,p} dinamakan pelabelan total sisiajaib super. Graf yang mempunyai pelabelan total sisi-ajaib super dinamakan graf total sisi-ajaib super. Perhatikan dua buah pelabelan total sisi-ajaib S4 pada Gambar 2.14.

9

1

2

2

8

8

5

7

3

1

9

5

4

6

6

4

Gambar 2.14.a: S4 total sisi-ajaib

7

3

Gambar 2.14.b: S4 total sisi-ajaib

Pada Gambar 2.14.a dan Gambar 2.14.b, S4 dengan banyak titik p=5 dan banyak sisi q=4, memiliki konstanta ajaib k yang sama yakni 15. Pada Gambar 2.14.a, terdapat label titik 6>p, maka S4 pada Gambar 2.14.a bukan graf total sisi-ajaib super. Namun pada Gambar 2.14.b, tidak terdapat label titik yang lebih besar daripada p, dengan kata lain f(V)={1,2,3,4,5}. Karenanya, S4 pada Gambar 2.14.b adalah graf total sisi-ajaib super

2.4 Hasil-hasil peneliti terdahulu Banyak sekali teori-teori pelabelan graf hasil peneliti terdahulu yang berkaitan dengan pelabelan total sisi-ajaib super. Berikut beberapa diantaranya. 10 Pelabelan total sisi ajaib super pada graf bintang yang diperumum


a. Lemma 2.1 (Enomoto et al., 1998) [1] Jika graf non-trivial G total sisi ajaib super, maka |E| ≤ 2|V|-3. Bukti. Tinjau nilai ekstrim label titik dan sisi. Konstanta ajaib k haruslah memenuhi 1+2+(|V|+|E|) ≤ k ≤ |V|+(|V|-1)+(|V|+1). Diperoleh |E| ≤ 2|V|-3. Secara kontrapositif, jika suatu graf G memenuhi |E|> 2|V|-3, maka G bukan total sisi-ajaib super.

b. Lemma 2.2 (Figuero-Centeno et al., 2002) [6] Graf G=(V,E) dengan |V|=p dan |E|=q adalah total sisi-ajaib super jika dan hanya jika terdapat fungsi satu-satu f: V Æ {1,2,…,p} sedemikian sehingga himpunan S = {f(x) + f(y) | xy ∈ E} terdiri dari q bilangan bulat berurutan. Dalam hal ini f dapat diperluas menjadi suatu pelabelan total sisi-ajaib super dari G dengan konstanta ajaib k=p+q+s, dengan s = min (S), dan S ={k-(p+1), k-(p+2), …, k-(p+q)}. Bukti. ( ⇐ ) Asumsikan bahwa fungsi f ada dan ambil uv ∈ E sedemikian sehingga f(u)+f(v)=min(S)= s. Kemudian perluas f hingga domainnya V ∪ E dengan cara berikut. Misalkan f(xy) = p + q + s – f(x) – f(y), dengan s = min (S) untuk sebarang xy di E, maka f(E) = {p+1, p+2, …,p+q}. ( ⇒ ) Jika G adalah graf total sisi-ajaib super dan f adalah suatu pelabelan total sisi-ajaib super pada G dengan konstanta ajaib k, maka S = {k - f(xy) | xy ∈ E} = {k – (p+1), k-(p+2), … , k – (p+q)}.

Lemma ini akan digunakan sebagai landasan penyusunan algoritma dalam mengkonstruksi suatu pelabelan total sisi-ajaib super.



c. Lemma 2.3 (Baskoro et al., 2005) [2] Jika g adalah suatu pelabelan total sisi-ajaib super pada graf G dengan konstanta ajaib k, maka fungsi g’: V ∪ E Æ {1,2 …, p+q} didefinisikan:

g’(x) =

{

p + 1 − g ( x)

, jika x ∈ V

2 p + q + 1 − g ( x) , jika x ∈ E

juga merupakan suatu pelabelan total sisi-ajaib super pada graf G dengan konstanta ajaib k’=4p+q+3–k. Dalam hal ini, g’ merupakan pelabelan dual super dari g. Sebagai ilustrasi penggunaan Lemma 2.3, perhatikan kembali Gambar 2.14.b. Graf S4 total sisi-ajaib super pada gambar 2.14.b memiliki pelabelan dual super seperti tampak pada Gambar 2.15. 4

7

5

6

1

8

3

9

2

Gambar 2.15: Pelabelan dual super dari S4 pada Gambar 2.14.b

d.

Hasil-hasil peneliti lainnya Selain lemma-lemma di atas, hasil-hasil peneliti tentang pelabelan total sisi-ajaib super, antara lain: Enomoto et al [1]. membuktikan bahwa Cn adalah total sisi-ajaib super jika dan hanya jika n ganjil. Pada [6] Figueroa-Centeno et al. membuktikan bahwa: C3 ∪ Cn total sisi-ajaib super jika dan hanya jika n ≥ 6 dan n genap; C4 ∪ Cn total sisi-ajaib super jika dan hanya jika n ≥ 5 dan n ganjil; C5 ∪ Cn total sisi-ajaib super jika dan hanya jika n ≥ 5 dan n genap; Sudarsana et al. [2] membuktikan bahwa graf Pn ∪ Pn+1, nP2 ∪ Pn dan nP2 ∪ Pn+2 adalah total sisi-ajaib 12

Pelabelan total sisi ajaib super pada graf bintang yang diperumum


super. Izzati [4] membuktikan bahwa S mn adalah total sisi-ajaib super untuk n ≥ 3 dan m=1, dan n ganjil ≥ 3 dan m=2. Izzati juga menunjukkan bahwa S 24 ,S 62 ,dan S 82 merupakan total sisi-ajaib super dengan konstanta ajaib berturut-turut 33, 47, dan 61 seperti tampak pada Gambar 2.16.

6 5

3 16

13

9 11

2

4

3 2 12

7

18

10

1

13

9

4

8

8

14

19

1

17 5

6

15

11

7 12

S

S

2 4

2 6

10

18 10

12

3 2

4 11 23

22

16

1

25 5

8

19

13

21

24 7 6

9 15 17

14 20

S 82 Gambar 2.16: Pelabelan total sisi-ajaib super pada S 24 , S 62 ,dan S 82


BAB II Graf dan Pelabelan Total Sisi-Ajaib Super

Recommend Documents