Sebuah graf sederhana G adalah pasangan terurut G = (V, E) dengan V adalah

BAB II KAJIAN TEORI

II.1 Teori-teori Dasar Graf II.1.1 Definisi Graf Sebuah graf sederhana G adalah pasangan terurut G = (V, E) dengan V adalah himpunan tak kosong dari titik graf G, dan E, himpunan sisi graf G adalah subset dari 2-subset dari V. Misalkan graf G = (V, E) dengan V = {v1 , v2 , v3 ,v4, v5} dan E = {v1v2, v3v3, v2v3, v3v4, v3v5}. Untuk selanjutnya, sehubungan dengan batasan masalah yang telah diuraikan pada Bab pendahuluan dalam tugas akhir ini, setiap graf mengacu pada graf sederhana.

Orde dari sebuah graf adalah banyaknya titik dalam graf tersebut.

Jika dua buah titik u, v ∈ V dan sebuah sisi uv ∈ E, maka u dan v adalah titik-titik ujung dari sisi uv. Maka, graf G pada contoh di atas, dengan sisi v1v2 mempunyai ujung v1 dan v2, sisi v3v3 mempunyai titik ujung di v3 dan v3 , sisi v2v3 mempunyai ujung v2 dan v3 , dan sisi v3v4 mempunyai ujung v3 dan v4, sisi v3v5 memiliki ujung v3 dan v5. 8 Pelabelan Pseudo Edge-Magic dan Pseudo Vertex-Magic pada Graf Sebarang

Bab II Dasar Teori

II.1.2 Keterkaitan dan Ketetanggaan Sebuah titik v dikatakan terkait oleh sisi e jika titik tersebut merupakan salah satu titik ujung dari sisi e. Dua buah sisi dikatakan saling terkait jika salah satu ujung dari kedua sisi terebut adalah sama.

Dua buah titik yang berbeda dalam sebuah graf G dikatakan bertetangga bila terdapat sisi di mana kedua titik tersebut merupakan titik ujungnya. Dari contoh graf G di bagian awal definisi, v1 bertetangga dengan v2, v2 bertetangga dengan v3 , v3 bertetangga dengan v2 dan v4

Derajat dari sebuah titik v dalam graf G adalah banyaknya tetangga dari titik v.

Graf n-regular adalah graf dengan derajat setiap titiknya adalah n

II.1.3 Walk, Trail, Path, dan Cycle Sebuah walk pada graf G didefinisikan sebagai sebuah barisan W = v0e1v1e2v2...ekvk dengan titik ujung dari ei adalah vi-1 dan vi. W disebut juga walk dari walk dari v0 ke vk atau ditulis sebagai (v0 , vk)-walk. Titik v0 disebut sebagai origin dari W dan vk disebut 9 Pelabelan Pseudo Edge-Magic dan Pseudo Vertex-Magic pada Graf Sebarang

Bab II Dasar Teori terminus dari W, sedangkan v1, v2 …, vk -1 disebut titik internal dan k merupakan panjang barisan.

Jika terdapat sebuah walk dengan ei ≠ ej untuk setiap i ≠ j, maka barisan ini disebut sebagai trail atau ditulis sebagai (v0 , vk)-trail.

Jika terdapat sebuah trail dengan vi ≠ vj untuk setiap i ≠ j, maka barisan tesebut disebut path atau lintasan yang ditulis sebagai (v0 , vk)-path.

Jarak dari v0 ke vk adalah panjang (v0 , vk)-path yang merupakan path terpendek di G.

Sebuah walk dan trail dikatakan tertutup jika panjangnya positif, dan memiliki origin dan terminus-nya berupa titik yang sama. Sebuah trail tertutup yang titik internal-nya berbeda-beda disebut cycle. Sebuah cycle dengan panjang k dinamakan k-cycle. Suatu k-cycle dibedakan menjadi cycle genap atau cycle ganjil sesuai dengan bilangan k tersebut. Di bawah ini adalah ilustrasi mengenai walk, trail, path, dan cycle

10 Pelabelan Pseudo Edge-Magic dan Pseudo Vertex-Magic pada Graf Sebarang

Bab II Dasar Teori

Gambar 2.1

II.1.4 Keterhubungan Dua buah titik u,v ∈ V dikatakan terhubung jika terdapat satu atau lebih (u,v)-path di graf G.

Sebuah graf G dikatakan terhubung jika dan hanya jika untuk setiap dua titik u,v ∈ V yang berbeda terdapat satu atau lebih path yang menghubungkannya.

II.1.5 Tree dan Spanning Tree Tree atau graf pohon adalah sebuah yang graf tidak memuat cycle yang terhubung.

Teorema 2.11 Jika G adalah graf pohon, maka ε = v − 1 , untuk ε adalah banyaknya sisi pada graf G

1

( E (G) )

dan v adalah banyaknya titik pada graf G

( V (G) )

Bondy dan Murty 1976 [25]


Bab II Dasar Teori

Bukti : Dengan menggunkan induksi pada v. Jika v = 1, maka graf tersebut tidak memiliki sisi atau E ( G ) = 1 − 1 = 0 . Misalkan teorema tersebut benar untuk semua graf pohon dengan titik kurang dari v. Misalkan G adalah graf pohon dengan v ≥ 2. Misalkan uv ∈ E. Maka G-uv tidak memuat lintasan (u,v). Jadi G-uv tidak terhubung, sehingga ω(G - uv) = 2. Sebut komponen dari G-uv sebagai G1 dan G2. Maka Gi adalah pohon dan v(Gi) < v, i = 1,2. Berdasarkan hipotesa induksi berlaku

ε (Gi) = v(Gi) – 1, i = 1,2 Akibatnya

W

ε (G) = ε (G1) + ε (G2) + 1 = v(G1) + v(G2) – 1 = V – 1

Suatu graf H adalah subgraf dari graf G ( H ⊆ G ) bila terdapat graf H sedemikian sehingga V(H) ⊆ V dan E(H) ⊆ E .


Bab II Dasar Teori Gambar 2.2 Sebuah graf dan subgrafnya

Spanning tree dari suatu graf terhubung G, adalah subgraf pembangun G yang berbentuk pohon.

Gambar 2.3 Sebuah spanning tree G1 pada graf terhubung G

Akibat 2.1.1: Setiap graf terhubung memiliki spanning tree.

Bukti

:

Misalkan G graf terhubung dan H subgraf pembangun terhubung yang minimal dari G. Karena H terhubung, maka ω(H) = 1 dan ω(H - e) > 1 untuk tiap e di H. Ini berarti tiap sisi di H adalah cut edge dan akibatnya, H adalah pohon. Jadi, H merupakan spanning tree dari G.

Graf star dinotasikan dengan Sn, dengan n titik v1 , . . . , vn adalah graf yang merupakan 13 Pelabelan Pseudo Edge-Magic dan Pseudo Vertex-Magic pada Graf Sebarang

Bab II Dasar Teori

sebuah graf dengan sisi-sisi yang menghubungkan v1 dano vj untuk

2≤ j≤n.

Gambar 2.4 Contoh graf star

Graf wheel Wn adalah sebuah graf dengan n titik yang dibangun dengan menghubungkan sebuah titik ke semua titik dari sebuah (n-1)-cycle. Penomoran dalam graf wheel dalam penulisan berbagai literatur tidaklah sama. Sebagian menuliskan n sebagai panjang cycle, sehingga Wn berjumlah n+1 titik.


Bab II Dasar Teori

Gambar 2.5 Contoh graf wheel

Graf caterpillar adalah sebuah graf yang dibangun dari path dengan masing-masing titik internal terhubung dengan titik di luar path sebagai kaki.

Gambar 2.6 Contoh graf caterpillar


Bab II Dasar Teori

Sebuah graf G:=(V,E) adalah graf bipartit bila terdapat partisi himpunan titik V=V1 V2 sehingga V1 dan V2 saling lepas. Graf bipartit dengan partisi V1 dan V2 biasa ditulis sebagai G:=( V1+V2,E). Jika jumlah elemen dalam V1 dan V2 (| V1 | = | V2 |) maka G disebut balanced bipartite graph atau graf bipartit seimbang.

Gambar 2.7 Contoh graf bipartit

Graf lengkap adalah sebuah graf dengan semua titiknya saling bertetangga.

Gambar 2.8 Contoh graf lengkap


Bab II Dasar Teori

II.2 Pelabelan Magic dan Pseudo Magic Pelabelan adalah suatu pemetaan yang memetakan titik dan atau sisi pada graf G ke bilangan bulat. Pelabelan yang memetakan sisi saja disebut sebagai edge-labelings atau pelabelan sisi, dan pelabelan yang memetakan titik saja disebut sebagai vertex-labelings atau pelabelan titik. Sedangkan pelabelan yang memetakan sisi dan titik dan sisi disebut total labelings atau pelabelan total.

Pelabelan edge-magic dari sebuah graf G (V,E) didefinisikan sebagai pemetaan satu-satu dari himpunan bilangan bulat positif {1,2, . . . ,|V|+|E|} ke V∪E dengan jumlah label setiap sisi dengan label kedua titik ujungnya adalah sama untuk setiap sisi dalam graf.

Pelabelan vertex-magic dari sebuah graf G (V,E) didefinisikan sebagai pemetaan satu-satu dari himpunan bilangan bulat positif {1,2, . . . ,|V|+|E|} ke V∪E dengan jumlah label setiap titik dengan label semua sisi yang terkait dengan titik tersebut adalah sama untuk setiap titik dalam graf.

Pelabelan pseudo magic adalah suatu pelabelan yang mengacu pada pelabelan magic, 17 Pelabelan Pseudo Edge-Magic dan Pseudo Vertex-Magic pada Graf Sebarang

Bab II Dasar Teori

dalam prakteknya, pelabelan pseudo magic merupakan perluasan dari pelabelan magic, dalam artian, pelabelan magic termuat dalam pelabelan pseudo magic.

Sebuah graf dikatakan pseudo edge-magic jika terdapat pemetaan satu-satu dan pada λ : V (G)

E (G) → N dari graf G sehingga untuk setiap edge vw ∈ E ( G ) berlaku:

λ (v) + λ (vw) + λ ( w) = κ

Sebuah graf dikatakan pseudo vertex-magic jika terdapat pemetaan satu-satu dan pada λ:V

E → N dari graf G sehingga untuk setiap verteks v ∈ V ( G ) berlaku:

λ (v ) +

∑

vw∈E ( v )

λ (vw) = κ

dengan κ adalah suatu konstanta.

Sebuah graf dikatakan pseudo edge-antimagic jika terdapat pemetaan satu-satu dan pada λ : V → N dari graf G sehingga untuk setiap edge vw, xy ∈ E berbeda berlaku

λ (v ) + λ ( w) ≠ λ ( x ) + λ ( y )

Sebuah graf dikatakan pseudo vertex-antimagic jika terdapat pemetaan satu-satu dan pada λ: E → N dari graf G sehingga untuk setiap verteks v, w ∈ V berbeda berlaku:


Bab II Dasar Teori

∑

λ (vx ) ≠

vx∈E ( v )

∑

λ ( wx )

wx∈E ( v )

Pengamatan 1 Dalam sebuah pelabelan pseudo edge-magic, pelabelan sisi nya

adalah pseudo edge-antimagic Bukti : Jika λ adalah sebuah pelabelan pseudo edge-magic dari sebuah graf G=(V,E), maka untuk

setiap

sisi

vw, xy ∈ E

yang

berbeda,

λ ( v ) + λ ( vw) + λ ( w) = λ ( x ) + λ ( xy ) + λ ( y ) = κ . Karena label yang digunakan tidak boleh sama, maka λ ( vw) ≠ λ ( xy ) sehingga pastilah λ ( v ) + λ ( w ) ≠ λ ( x ) + λ ( y ) , yaitu sebuah pelabelan edge-antimagic

Pengamatan 2: Dalam sebuah pelabelan pseudo vertex-magic, pelabelan titik nya

adalah pseudo vertex-antimagic Bukti : Jika λ adalah sebuah pelabelan pseudo vertex-magic dari sebuah graf G=(V,E), maka untuk setiap dia titik v, w ∈V yang berbeda, λ ( v )

∑ λ ( vx ) = λ ( w) ∑ λ ( wx ) .

vx∈E ( v )

wx∈E ( w)

Karena label yang digunakan tidak boleh sama, maka λ ( v ) ≠ λ ( w ) sehingga pastilah,

∑ λ ( vx ) ≠ ∑ λ ( wx )

vx∈E ( v )

yaitu sebuah pelabelan vertex-antimagic

wx∈E ( w)


Bab II Dasar Teori

Karena setiap pelabelan pseudo-magic selalu memuat pelabelan pseudo anti-magic, maka proses pelabelan dalam tugas akhir ini dilakukan dalam dua tahap. Tahap pertama yaitu tahap pelabelan pelabelan sisi anti-magic pada pelabelan pseudo vertex-magic dan pelabelan titik anti-magic pada pelabelan pseudo edge-magic. Kemudian tahap kedua yaitu melakukan pelabelan total pada graf hasil pelabelan pseudo anti-magic.

Pelabelan edge-ant-magic memiliki kaitan yang sangat erat dengan suatu barisan yang disebut barisan Sidon. Sebuah barisan a1 , a 2 , ..., a n disebut barisan Sidon jika untuk setiap i,j,k, dan l yang berbeda, berlaku a i + a j ≠ a k + a l . Sebagai contoh, 1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, ........, untuk setiap sebarang dua anggota barisan yang berbeda, jumlahnya tidak pernah sama. Beberapa tokoh yang berperan dalam barisan Sidon ini antara lain adalah Halberstam,Roth, Cilleruelo, Jia, Kolountzakis, Lindstrom, dan Ruzsa.


Sebuah graf sederhana G adalah pasangan terurut G = (V, E) dengan V adalah

Recommend Documents