Pelabelan Total (a,d) Sisi Anti-ajaib (Teori Graf)

Latar Belakang

Pelabelan adalah pemetaan dari elemen-elemen graf ke bilangan bulat positif dan banyak jenisnya.

Pelabelan total (a,d) sisi anti-ajaib masih merupakan suatu open problem untuk beberapa kelas graf, yaitu siklus Cndengan d=3,4,5 untuk n genapdan lintasan Pn dengan d=4 untuk n genap dan d=5,6 untuk n sembarang.

Jumlah dari hasil pelabelan biasanya disebut sebagai bobot dari elemen graf.

Graf yang memiliki bobot verteks atau bobot sisi yang berbeda disebut graf dengan pelabelan anti-ajaib.

Pelabelan total (a,d) sisi anti-ajaib adalah pelabelan pada verteks dan sisi graf dengan bobot sisi membentuk deret aritmatika {a, a+d , a+2d ,…, a+(|E|-1)d} dengan |E| jumlah sisi pada graf.

Sebuah graf G disebut mempunyai pelabelan total (a,d) sisi anti-ajaib jika terdapat bijeksi {1,2,…,|E|+|V|} sehingga bobot-bobot sisinya memenuhi deret {a, a+d , a+2d ,…, a+(|E|-1)d}

Tujuan

Mengetahui cara mengonstruksi suatu pelabelan total sisi anti-ajaib pada sebuah graf

Mengetahui rumus pada pelabelan total sisi-ajaib pada graf

Mengetahui cara menentukan bobot pada pelabelan verteks

Langkah-langkah

1.     Tentukan jumlah simpul dan simpul

2.     Jumlah dari gabungan simpul dan busur merupakan bilangan dari pelabelan graf ini.

3.     Tentukan nilai n terlebih dahulu

4.     Letakkan bilangan yang merupakan angka pelabelan pada graf tersebut.

5.     Terakhir, tentukanlah bobot dari pelabelan tersebut.

Contoh :

Hasil pelabelan total untuk Pn

a.     Pelabelan total (a,4) sisi anti-ajaib pada  Pn dengan n ganjil                              

     Pola pelabelan:

Pembuktian:

TeoremaUntuk setiap n ≥ 3 dan n ganjil,   P_n   mempunyai pelabelan total (n+5,4) sisi anti-ajaib

Pelabelan total didefinisikan:

Definisikan     bf (v_i v_i+1 ) , 1 ≤ i ≤ n-1 menyatakan bobot sisi pada maka:

Misalkan Bf  menyatakan bobot sisi pada Pn

Jadi untuk setiap n ≥ 3 dan n ganjil, Pn mempunyai pelabelan total (n+5,4) sisi anti-ajaib

b.     Pelabelan total (a,4) sisi anti-ajaib pada  Pn dengan n genap

Pola pelabelan:

TeoremaUntuk setiap n ≥ 3 dan n genap, Pn mempunyai pelabelan total (n+4,4) sisi anti-ajaib:

Pelabelan total         didefinisikan:

Definisikan , 1 ≤ i ≤ n-1 menyatakan bobot sisi pada Pn maka:

Misalkan Bf  menyatakan bobot sisi pada Pn :

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

Hasil pelabelan total untuk Cn :

Pola pelabelan:

Pembuktian :

TeoremaUntuk setiap n ≥ 3, Pn mempunyai pelabelan total (2n+2,1) sisi anti-ajaib :

Pelabelan total  didefinisikan:

Definisikan , 1 ≤ i ≤ n-1 menyatakan bobot sisi pada Cn maka :

 

 

Misalkan Bf  menyatakan bobot sisi pada Cn :

Jadi untuk setiap n ≥ 3, Cn mempunyai pelabelan total (2n+2,1) sisi anti-ajaib

Hasil pelabelan total untuk Cn

Pola pelabelan:

Pembuktian :

TeoremaUntuk setiap n ≥ 3, Cn mempunyai pelabelan total (2n+2,2) sisi anti-ajaib:

Pelabelan total didefinisikan:

Definisikan , 1 ≤ i ≤ n-1 menyatakan bobot sisi pada Cn maka :

Misalkan Bf  menyatakan bobot sisi pada Cn :

Jadi untuk setiap n ≥ 3, Cn mempunyai pelabelan total (2n+2,2) sisi anti-ajaib :

Pelabelan total (a,4) sisi anti-ajaib pada Cn dengan n ganjil :

Pembuktian :

TeoremaUntuk setiap n ≥ 3 dengan n ganjil, Cn mempunyai pelabelan total (n+3,4) sisi anti-ajaib :

Pelabelan total didefinisikan:

Definisikan   , 1 ≤ i ≤ n-1 menyatakan bobot sisi pada Cn maka:

Misalkan Bf  menyatakan bobot sisi pada Cn :

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