Abdussakir

Dzikir, Fikir, dan Amal Shaleh

Graph Labelings

Posted by abdussakir on November 3, 2008

Pelabelan pada suatu graph adalah sebarang pemetaan (fungsi) yang memasangkan unsur-unsur graph (titik atau sisi) dengan bilangan (biasanya bilangan bulat). Jika domain dari fungsi adalah titik, maka pelabelan disebut pelabelan titik (vertex labeling). Jika domainnya adalah sisi, maka disebut pelabelan sisi (edge labeling), dan jika domainnya titik dan sisi, maka disebut pelabelan total (total labeling).

GRACEFUL LABELING

Pelabelan Graceful pada graph G dengan q sisi adalah fungsi injektif  l dari V(G) ke {0, 1, 2, …, q} sedemikian hingga, seandainya sisi (x, y) dilabeli dengan

|l(x) – l(y)|

maka label sisi akan berbeda.

Balanced Labeling (a-labeling)

a-labeling adalah pelabelan Graceful dengan syarat terdapat bilangan bulat k sehingga untuk masing-masing sisi (x, y) maka l(x) £ k < l(y) atau l(y) £ k < l(x).

k-Graceful Labeling

Pelabelan k-Graceful pada graph G dengan q sisi adalah fungsi injektif  l dari V ke {0, 1, 2, …, q + k – 1} sedemikian hingga, seandainya sisi (x, y) dilabeli dengan |l(x) – l(y)| maka label sisi adalah {k, k + 1, …, q + k – 1}.

Skolem-Graceful Labeling

Pelabelan Skolem-Graceful pada graph G dengan p titik dan q sisi adalah fungsi injektif  l dari V(G) ke {1, 2, …, p} sedemikian hingga, seandainya sisi (x, y) dilabeli dengan

|l(x) – l(y)|

maka label sisi adalah 1, 2, …, q.

Odd Graceful Labeling

Pelabelan Graceful Ganjil pada graph G dengan q sisi adalah fungsi injektif  l dari V(G) ke {0, 1, 2, …, 2q – 1} sedemikian hingga, seandainya sisi (x, y) dilabeli dengan

|l(x) – l(y)|

maka label sisi adalah 1, 3, 5, …, 2q – 1.

Cordial Labeling

Misalkan l fungsi dari V(G) ke {0, 1} dan sisi (x, y) dilabeli dengan

|l(x) – l(y)|.

l disebut pelabelan cordial jika banyaknya titik yang berlabel 0 dan banyaknya titik berlabel 1 berbeda paling banyak 1, dan  banyaknya siis yang berlabel 0 dan banyaknya titik berlabel 1 berbeda paling banyak 1.

 

HARMONIOUS LABELING

Pelabelan Harmonis pada graph G dengan q sisi adalah fungsi injektif  l dari V(G) ke {0, 1, 2, …, q – 1} sedemikian hingga, seandainya sisi (x, y) dilabeli dengan

l(x) + l(y) (mod q)

maka label sisi akan berbeda.

Elegent Labeling

Pelabelan Elegent pada graph G dengan q sisi adalah fungsi injektif  l dari V(G) ke {0, 1, 2, …, q} sedemikian hingga, seandainya sisi (x, y) dilabeli dengan

l(x) + l(y) (mod q + 1)

maka label sisi akan berbeda dan tidak nol.

Felicitous Labeling

Pelabelan Felicitous pada graph G dengan q sisi adalah fungsi injektif  l dari V(G) ke {0, 1, 2, …, q} sedemikian hingga, seandainya sisi (x, y) dilabeli dengan

l(x) + l(y) (mod q)

maka label sisi akan berbeda.

 

MAGIC LABELING

Beberapa pelabelan pada graph sebenarnya digeneralisasi dari ide persegi ajaib (magic square).

Suatu graph terhubung disebut semi-magic jika terdapat pelabelan pada sisi-sisinya dengan bilangan bulat sehingga untuk masing-masing titik v, maka jumlah label sisi yang incident dengan v adalah sama untuk semua titik v. Pelabelan semi-magic yang memetakan sisi ke himpunan bilangan bulat positif yang berbeda disebut pelabelan magic. Pelabelan magic disebut super magic jika label sisi adalah bilangan bulat positif yang berurutan.

 

 

Berikut ini beberapa jenis pelabelan ajaib pada suatu graph.

a.       Misalkan G graph dengan himpunan titik V dan himpunan sisi E. Banyak titik di G adalah p dan banyak sisi di G adalah q. Pelabelan titik sisi ajaib (edge-magic vertex labeling) pada graph G adalah fungsi bijektif l dari V pada himpunan {1, 2, 3, …, p} sehingga untuk sebarang sisi (x, y) di G berlaku

l(x) +  l(y) = k

untuk suatu konstanta k. Selanjutnya k disebut bilangan ajaib pada G dan G disebut titik sisi ajaib.

b.      Misalkan G graph dengan himpunan titik V dan himpunan sisi E. Banyak titik di G adalah p dan banyak sisi di G adalah q. Pelabelan total titik ajaib (vertexmagic total labeling) pada graph G adalah fungsi bijektif l dari V È E pada himpunan {1, 2, 3, …, p + q} sehingga untuk sebarang titik x di G berlaku

l(x) + = k

      untuk suatu konstanta k. Selanjutnya k disebut bilangan ajaib pada G dan G disebut total titik ajaib.

c.       Misalkan G graph dengan himpunan titik V dan himpunan sisi E. Banyak titik di G adalah p dan banyak sisi di G adalah q. Pelabelan sisi titik ajaib (vertex-magic edge labeling) pada graph G adalah fungsi bijektif l dari E pada himpunan {1, 2, 3, …, q} sehingga untuk sebarang titik x di G berlaku

= k

untuk suatu konstanta k. Selanjutnya k disebut bilangan ajaib pada G dan G disebut sisi titik ajaib.

d.      Misalkan G graph dengan himpunan titik V dan himpunan sisi E. Banyak titik di G adalah p dan banyak sisi di G adalah q. Pelabelan total sisi ajaib (edge-magic total labeling) pada graph G adalah fungsi bijektif l dari V È E pada himpunan 

{1, 2, 3, …, p + q}

sehingga untuk sebarang sisi (x, y) di G berlaku

l(x) + l(xy) + l(y) = k

untuk suatu konstanta k. Selanjutnya k disebut bilangan ajaib pada G dan G disebut total sisi ajaib.

 

Pelabelan total sisi ajaib yang memetakan V ke {1, 2, 3, …, p} disebut pelabelan super sisi ajaib (super edge magic labeling).

 

Sum Graph

Graph G = (V, E) disebut sum graph jika terdapat bijeksi f dari V ke himpunan bilangan bulat positif S sedemikian hingga xy Î E jika dan hanya jika f(x) + f(y) Î S. Pada sum graph pasti memuat titik terisolasi.

 

Prime Labeling

Pelabelan prima pada graph G dengan p titik adalah fungsi injektif f dari V ke {1, 2, …, p} sehingga untuk masing-masing sisi xy, maka label titik x dan titik y relative prima.

8 Responses to “Graph Labelings”

  1. thanks infonya, membantu bget

  2. doni said

    aq mw tanya,, syarat perlu suatu graf dikatakan sebagai pelabelan harmonious tu gmn??
    thanx aq butuh itu

  3. yuyun said

    makasih ya….

    ini yg dicari…

  4. yas said

    artikelnya sgt membantu..,
    mas ada junal/artike ttg Odd Graceful Labeling
    mohon bantuannya
    email: yez_163@yahoo.co.id

    • abdussakir said

      Silahkan Browsing judul “Dynamic Survey of Graph Labeling” e-Journal Joseph Gallian, edisi 2009 sudah ada di internet. Yang Anda cari ada di jurnal tersebut.

  5. wheny said

    thx untuk pembahasan macam2 dari labeling grafnya,,

  6. rayaveila said

    maaf, kuk yg “vertex-magic edge labeling” kaya’ ada bagian yg kepotong ya..?
    ruas kiri sebelum “= k” itu apa..? sya gugling ndak nemu2.
    mohon penjelasannya..
    trima kasih banyak..

    • abdussakir said

      Terima kasih, mungkin karena tidak kompatibelnya sistem pengolah kata. Memang ada yang hilang, termasuk di atasnya.
      Untuk melihat lengkapnya, silahkan browsing judul “Dynamic Survey of Graph Labeling” e-Journal Joseph Gallian.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: