GRAF DIVISOR CORDIAL Deasy Bunga Agustina1, YD. Sumanto2, Bambang Irawanto3 1,2,3
Jurusan Matematika FSM Universitas Diponegoro Jl. Prof. H. Soedarto, S.H. Tembalang Semarang
[email protected]
ABSTRACT.A Let = (V, E) be a graph and bijection map : → {1, 2, . . | |}. For every edge ∈ assign the label 1 if either ( ) divide out of ( ) or ( ) divide out of ( ) and assign the label 0 otherwise. A mapping is called divisor cordial labeling if the difference between the number of edges having labels 0 and the number of edges having labels 1 which is to equal or less one. A graph has a divisor cordial labeling is called divisor cordial graph. Some special classes of ( ) graphs such as full binary tree graph, * , graph, * , graph where even, =< , , ( ) ,
> graph, Keywords :
( )
( )
( )
=< , , , , , > graph and sun graph . are divisor cordial. divisor cordial labeling, full binary tree graph, * , graph, * , graph, ( ) ( ) ( ) ( ) ( ) =< , , , > graph, =< , , , , , > graph and sun graph
I.
PENDAHULUAN
Teori graf merupakan salah satu cabang ilmu matematika yang banyak digunakan untuk mempermudah suatu penyelesaian masalah. Banyak yang dapat
dipelajari dari suatu graf, salah satu diantaranya adalah pelabelan graf. Pelabelan merupakan pemetaan yang memetakan unsur himpunan titik dan unsur himpunan sisi ke bilangan bulat positif yang disebut label. Pertama kali diperkenalkan oleh Sadlàčk (1964), kemudian Stewart (1966), Kotzig dan Rosa (1970). Pemanfaatan teori pelabelan graf dapat dirasakan peranannya, terutama dalam sektor komunikasi dan transportasi, pembentukan molekul kimia, navigasi geografis, radar, pemancar frekuensi radio dan juga distribusi listrik. Hingga saat ini dikenal beberapa jenis pelabelan graf, salah satu diantaranya adalah pelabelan divisor cordial. II.
HASIL DAN PEMBAHASAN
Definisi 2.1. [6] Diberikan graf
= (V, E) dengan pemetaan bijektif
{1, 2, . . |
∈
|}. Untuk setiap sisi
diberikan label 1 jika
:
→
( )| ( ) atau
( )| ( ) dan diberikan label 0 jika ( ) ∤ ( ) dan ( )∤ ( ). Pemetaan f disebut pelabelan divisor cordial jika
(0) −
(1) ≤ 1. Suatu graf G disebut
graf divisor cordial jika memenuhi ketentuan pelabelan divisor cordial.
Teorema 2.2 [6] Diberikan bilangan bulat positif n ≥ 3, maka terdapat graf divisor cordial
dengan n titik.
Bukti: Kasus 1
n genap
Didefinisikan sebuah path yang mengandung + 2 titik yaitu {
,
,…,
yang masing-masing dilabelkan dengan 1, 2, . . . , + 2. Pelabelan sisi 1, karena ( )| (
). Sedangkan untuk sisi lainnya
memiliki label 0, karena ( ) ∤ ( {
,…,
, +3,
+ 4, … ,
adalah
(2 ≤ ≤ + 1)
) . Ditambahkan
} yang masing-masing adjacent ke
}
− 2 buah titik yaitu
, titik tersebut diberi label
( + 3 ≤ ≤ ) adalah 1, karena
. Label dari sisi
( )| ( ). Kasus 2
n ganjil
Didefinisikan sebuah path
+ 1 titik, yaitu { ,
masing dilabelkan dengan 1, 2, . . ., ( )│ (
} yang masing-
+ 1. Pelabelan sisi
adalah 1 karena
) . Sedangkan untuk sisi lainnya
memiliki label 0, karena ( ) ∤ ( {
,…,
,
, …,
diberi label dengan
) . Ditambahkan
dimana ( 2 ≤ ≤
− 1 buah titik yaitu
} yang masing-masing adjacent ke titik +2 ,
+ 3, … , . Label sisi
)
, titik tersebut
dimana (
+2 ≤
≤ ) adalah 1, karena ( )| ( ). Teorema 2.3 [6] Jika genap, maka
adalah graf divisor cordial yang banyak sisinya adalah
− juga merupakan divisor cordial untuk semua
∈ ( ).
Teorema 2.4 [6] Jika G adalah graf divisor cordial dengan banyak sisinya adalah ganjil, maka terdapat
∈ ( ) sehingga
− juga merupakan divisor cordial.
Teorema 2.5 Jika genap, maka (
+
adalah graf divisor cordial yang banyak sisinya adalah juga merupakan graf divisor cordial untuk semua
∈
) − ( ).
Bukti Diberikan suatu graf
yang mempunyai q sisi, dimana q genap. Karena
graf divisor cordial, maka
( 0) =
(1 ) =
.
Jika penambahan sisi menghasilkan pelabelan 1 maka
( 0) =
Jika penambahan sisi menghasilkan pelabelan 0 maka
(0) =
sehingga diperoleh
(0) −
adalah
(1) = 1 .Dengan demikian
(1) = + 1.
;
+1; +
(1) = ,
adalah graf
divisor cordial karena memenuhi ketentuan pelabelan divisor cordial yaitu ( 0) −
(1) ≤ 1.
Teorema 2.6 Jika (
adalah graf divisor cordial ganjil, maka terdapat
) − ( ) sedemikian sehingga
∈
+ juga merupakan divisor cordial.
Definisi 2.7 [6] Pohon biner penuh (full binary tree) adalah pohon biner yang setiap titik internalnya mempunyai tepat dua buah cabang. Teorema 2.8 [6] Setiap pohon biner penuh adalah graf divisor cordial. Diberikan T adalah pohon biner penuh dan v merupakan akar dari T yang selanjutnya disebut sebagai titik level ke nol. Level ke-i dari T mempunyai 2 titik. Jika T mempunyai
level, maka banyak titiknya adalah 2
sedangkan banyak sisinya adalah 2
− 1 titik,
− 2 sisi.
Untuk titik level ke-0 diberikan label 2, level ke-1 diberikan label 3 dan label 1. Selanjutnya untuk titik level ke-i dengan 2 ≤ ≤ 2 , 2 + 1, … , 2
− 1 dari kiri ke kanan secara berurutan.
Banyaknya pelabelan sisi graf 4+⋯+ 2
diberikan label
untuk m level adalah
= 2 − 1 sehingga
(0) −
penuh merupakan graf divisor cordial karena
( 0) =
( 1) = 1 + 2 +
(1) = 0 . Jadi, graf pohon biner ( 0) −
(1) ≤ 1.
Definisi 2.9 [6] Suatu graf yang dibentuk dengan cara menggabungkan graf divisor cordial
dengan graf bipartit lengkap ∗
Teorema 2.10 [6] Graf Misalkan
,
adalah graf divisor cordial dengan m titik. Titik dan
=
={ ,
⋃
,
pada titik
,…,
.
<
+
Kasus 1
yang masing-
,
≤
+ 1,
={ ,
dengan
,
+ 2, … ,
+
. } dan
berturut-turut
<2 untuk (1 ≤ ≤ ). Sisi
Kelipatan bilangan prima p tidak termasuk dalam label yang incident dengan titik
,
.
pada graf
sedemikian hingga
merupakan bipartisi dari
}. Kemudian dilabelkan
,…,
dan
pada graf bipartit lengkap
masing diberi label 1 dan bilangan prima terbesar Misalkan
,
merupakan graf divisor cordial.
,
berhimpit dengan titik
∗
disebut dengan graf
diberi label 1 dan yang incident dengan titik
diberi label 0. +
Kasus 2
≥
Misalkan q adalah bilangan prima terbesar sehingga
≤
+
yang dilabelkan
untuk beberapa
dengan
, yaitu p dan q
. Kemudian dengan menukar label ,
maka q tidak dapat membagi Karena graf 1 maka graf
∗
,…,
.
merupakan graf divisor cordial dengan
( 0) −
(1) ≤
juga divisor cordial.
,
Definisi 2.11 [6] Suatu graf yang dibentuk dengan cara menggabungkan graf divisor cordial
dengan graf bipartit lengkap
Teorema 2.12 [6] Graf
∗
,
∗
disebut dengan graf
,
.
dengan n genap merupakan graf divisor cordial.
,
Bukti: Diberikan suatu graf divisor cordial ,
Diketahui bahwa
dan
pada graf
1, 2, dan bilangan prima terbesar =
Misalkan ={ , pada
,
,
⋃ } dan
yang mempunyai titik sebanyak m. adalah titik yang mempunyai label
sedemikian hingga
merupakan bipartisi dari ={ ,
,…,
≤ ,
. sedemikian sehingga
} . Kemudian labeli titik
yang masing-masing berhimpit dengan
,
dan
,
dan
. Selanjutnya labeli
,
titik
,…,
+ 1,
berturut-turut dengan <
Kasus 1
+
+ 2, … ,
<2 untuk (1 ≤ ≤ ). Sisi-
Kelipatan bilangan prima p tidak termasuk dalam label sisi
,
yang incident dengan titik
dilabeli 1, dan yang incident dengan titik
dilabeli 0. Sedangkan sisi sehingga
+ .
hanya dapat membagi bilangan genap saja
sisi yang incident dengan
diberi label 1 dan
sisi yang tersisa
diberi label 0. +
Kasus 2
≥ ≤
Misalkan q adalah bilangan prima terbesar sehingga untuk beberapa
dengan
dan
. Pola pelabelan untuk titik
pelabelan pada Kasus 1. Sedangkan untuk
+
yang dilabelkan
sama seperti pola
dilabeli dengan cara menukar label
, yaitu p dengan q sehingga sisi
,
yang incident dengan titik
mempunyai label 0. Jadi, sisi-sisi pada ( 0) =
,
( 1) =
+ =
Karena graf 1 maka graf
meberikan jumlah pelabelan yang sama yaitu sebanyak
∗
. ( 0) −
merupakan graf divisor cordial dengan ,
(1) ≤
juga graf divisor cordial.
Definisi 2.13 [6] Diberikan dua buah graf star yaitu
( ) ,
dan
( ) , ,
suatu graf
yang diperoleh dengan menghubungkan kedua titik pusat (apex) dari dua buah graf star tersebut ke titik baru Teorema 2.14 [6] Graf
=<
disebut dengan graf ( ) ,
,
( ) ,
=<
( ) ,
,
( ) ,
>.
> merupakan graf divisor cordial.
Bukti: Misalkan
( )
,
( )
,…,
adalah titik pendant dari dari
( ) ,
dan
( ) , ,
( )
adalah titik pendant dari ( ) , .
Titik
dan
dan
( )
,
( )
,…,
( )
berturut-turut merupakan titik pusat
dimana titik-titik tersebut adjacent dengan titik baru yaitu .
Selanjutnya didefinisikan pelabelan titik
dengan 1 dan
adalah bilangan prima terbesar sedemikian sehingga pendant pada
( ) ,
dengan , dimana ≤ 2 + 3 . Titik-titik
dilabelkan dengan sebarang bilangan selain 1 dan
sehingga
( 0) −
diperoleh ( ) ,
=<
( ) ,
,
(1) = |( + 1) − ( + 1)| = 0 . Dengan demikian graf (0) −
> merupakan graf divisor cordial karena
(1) ≤ 1.
Definisi 2.15 [6] Diberikan salinan graf star sebanyak t. Suatu graf yang diperoleh dengan menghubungkan titik pusat dari beberapa graf star ke titik baru yaitu ,
,,…,
=<
Teorema 2.16 [6] Graf
( ) , ,
=<
disebut dengan graf
( ) , ,
( ) , ,
( ) , ,
( ) ,
( ) ,
...,
>.
> merupakan graf divisor
cordial. Bukti: ( )
Misalkan
( )
,
( ) , ,
pusat dari
,…,
( )
adalah titik pendant dari
untuk = 1,2,3. Titik pusat
sedangkan titik pusat ( ) , ,
( ) ,
dan
dan
( ) ,
dan
merupakan titik
adjacent dengan titik baru
adjacent dengan titik baru
. Graf
=<
( ) , ,
> mempunyai 3 + 5 titik dan 3 + 4 sisi. Selanjutnya didefinisikan
pelabelan titik
dengan 1, titik
dengan 2 dan titik
dengan , dengan
adalah bilangan prima terbesar
≤ 3 + 5. Titik-titik pendant pada
dengan bilangan selain 1, 2 dan
berdasarkan urutan bilangan ganjil genap.
dilabelkan
Kasus 1
Genap
Untuk
genap, banyaknya label genap = banyaknya label ganjil pada
( )
( )
,
,…,
( )
,
,
, dan setiap sisi yang incident dengan (0) dan
jumlah pelabelan yang sama untuk =<
( ) , ,
Kasus 2 Untuk
( ) , ,
( ) ,
( 0) =
> mempunyai
(1) yaitu
memberikan . Sehingga graf
( 1) = ( + 1 ) +
=
.
Ganjil ganjil, banyaknya label ganjil adalah
adalah
pada
( )
,
( )
,…,
memberikan jumlah pelabelan Sehingga graf dan
( 1) =
=<
( ) , ,
+1+
( )
,
,
, dan setiap sisi yang incident dengan
( 0) = ( ) , ,
=
dan banyaknya label genap
( ) ,
.
dan
( 1) =
> mempunyai
. ( 0) =
+1+
=
Berdasarkan Kasus 1 dan Kasus 2 dapat disimpulkan bahwa graf ( ) , ,
( ) , ,
( ) ,
( 0) −
> merupakan graf divisor cordial karena .
Definisi 2.17 [1] Suatu graf corona
=<
(1) ≤ 1.
yang mempunyai satu daun disebut .
dengan graf matahari (sun graph), yang dinotasikan dengan Sebelum membuktikan bahwa graf matahari
.
.
merupakan graf divisor
cordial, akan ditunjukkan bahwa graf path dan graf cycle merupakan graf divisor cordial. Teorema 2.18 [5] Graf path
adalah graf divisor cordial.
Bukti: ,
Misalkan
,
,…,
adalah himpunan titik dari path
. Didefinisikan
∶ ( ) → {1,2,3, … , | |} mengikuti pola:
pelabelan titik 1,
2,
2
…,
2 ,
3,
3 × 2,
3×2 ,
…,
3×2 ,
5,
5 × 2,
5×2 ,
…,
5×2 ,
…
…
…
…
…
Pola pelabelan titik pada graf path adalah
( )
2
⎧ ⎪ ⎪2 ⎨ ⎪ ⎪ ⎩
Kasus 1 Untuk
3.2
(2 − 1)
Untuk
∑
dengan
+
≤ ≤
+3
+
Genap = 2, 4, 6, 8, … ,2 dimana
dan 1 adalah Kasus 2
dengan 1 ≤ ≤ + 1 dengan + 2 ≤ ≤ + + 2 dengan + + 3 ≤ ≤ + + ⋮
( 1) =
dan
≥ 1 maka diperoleh banyak sisi berlabel 0
( 0) =
.
Ganjil = 3, 5, 7, 9, … ,2 + 1 dimana
0 dan 1 adalah
( 1) =
( 0) =
.
≥ 1 maka diperoleh banyak sisi berlabel
( 0) −
Berdasarkan Kasus 1 dan Kasus 2 diperoleh
(1) ≤ 1 . Jadi,
merupakan graf divisor cordial. Teorema 2.19 [5] Graf cycle
adalah graf divisor cordial.
Bukti: Misalkan
,
,
,…,
adalah himpunan titik dari cycle
, pelabelan titiknya
memiliki pola yang sama seperti pelabelan titik dalam pembuktian Teorema 2.18 pada graf path
, kecuali penukaran label
dan
, yaitu label 1 dan 2. Karena
titik awal pada graf cycle adalah genap yaitu 2, sedangkan titik
pasti berlabel
ganjil (bukan 1) maka graf cycle memenuhi ketentuan pelabelan divisor cordial ( 0) −
yaitu
(1) ≤ 1. Jadi, terbukti
Teorema 2.20 [6] Graf
.
adalah graf divisor cordial.
merupakan graf divisor cordial.
Bukti: .
Untuk pelabelan cycle pada graf matahari
sesuai pola pelabelan
pada graf cycle, sedangkan pola pelabelan untuk graf star sebagai berikut: Kasus 1
Untuk
genap = 2,4,6, … ,2 dan
Misalkan banyaknya titik pada graf cycle adalah bilangan bulat terbesar sedemikian sehingga 2
≤2
adalah
maka pola pelabelan
titiknya dapat dilihat pada Tabel 2.1 berikut: Tabel 2.1 Pola Pelabelan Graf Matahari
Titik pada Graf Star
.
dengan
Diberikan Label
yang Adjecent dengan
2
Pelabelan Sisi yang Incident
Titik Berlabel 1
Genap
dengan 2 ,2
≤2
Sebarang titik ganjil pada
1 0
graf star yang > 3 4
3. 2 , 3. 2
≤2
Sebarang titik ganjil pada
1 0
graf star yang > 5
5. 2 , 5. 2
≤2
1
6
0
Sebarang titik ganjil pada graf star yang >
⋮
⋮
⋮
2 −1
2(2 − 1)
1
Sebarang titik ganjil pada
0
2
graf star yang > .
Diperoleh pelabelan sisi pada graf matahari ( 1) = + = Kasus 2
( 0) −
sehingga
Untuk
(0) =
adalah
(1) = | − | = 0.
ganjil = 3,5,7, … ,2 + 1 maka pola
Misalkan banyaknya titik pada graf cycle adalah
pelabelan titiknya sama seperti Tabel 2.1 tetapi banyaknya pelabelan sisi pada graf matahari =
.
ganjil adalah (0) −
sehingga
(0) =
+
=
dan
(1) =
+
(1) = | − | = 0. .
Dengan demikian graf matahari
merupakan graf divisor cordial karena ( 0) −
memenuhi ketentuan pelabelan divisor cordial yaitu III.
(1) ≤ 1.
KESIMPULAN
Dari hasil pembahasan di atas dapat disimpulkan bahwa jika graf G merupakan graf divisor cordial dengan banyak sisi genap atau ganjil maka graf − dan graf
+ juga merupakan graf divisor cordial.
Beberapa Graf khusus seperti graf pohon biner penuh dengan *
,
( ) , ,
, graf * ( ) ,
,
dengan
> dan graf matahari IV.
genap, graf .
=<
( ) , ,
( ) ,
>, graf
level, graf =<
( ) , ,
merupakan graf divisor cordial.
UCAPAN TERIMA KASIH
Banyak pihak yang telah membantu dalam penyelesaian Tugas Akhir ini. Oleh karena itu, rasa hormat dan terimakasih penulis ingin sampaikan kepada : 1. Bapak Drs. YD. Sumanto, M.Si selaku dosen pembimbing I yang telah memberikan bimbingan, arahan, dan nasehat-nasehatnya selama ini.
2. Bapak Bambang Irawanto, S.Si, M.Si, selaku dosen pembimbing II yang juga telah membimbing dan mengarahkan penulis hingga selesainya Tugas Akhir ini. 3. Semua pihak yang telah membantu hingga selesainya tugas akhir ini, yang tidak dapat penulis sebutkan satu persatu. Semoga Allah SWT membalas segala kebaikan yang telah Anda berikan kepada penulis, Amin. V.
DAFTAR PUSTAKA
[1] Kasmawati, Vajar. 2008. “Pelabelan Total a-simpul Berurutan Busur Ajaib pada Gabungan Dua Graf yang Terdiri dari Graf Bintang dan Graf yang Mengandung Unicycle”. Skripsi. Jurusan Matematika. Universitas Indonesia. Depok. [2] Munir, Rinaldi. 2007. “Matematika Diskrit”. Bandung: Informatika Bandung. [3] Ramanjaneluyu, dkk. 2008. Antimagic Labeling of aClass of Plannar Graphs. Australian Journal of Combinatorics. Vol.41, No.59, Hal.283290. [4] Rosen, Kenneth H. 2007. Discrete Mathematics and Its Applications Sixth Edition. New York : Mcgraw-Hill Book Company. [5] Varatharajan, R, S. Navaneethakrishnan, and K. Nagarajan, Divisor Cordial
Graphs.
2011.
International
Journal
of
Mathematics
Combinatorics, Vol.4, Hal.15-25. [6] Varatharajan, R, S. Navaneethakrishnan, and K. Nagarajan, Special Classes of Divisor Cordial Graphs. 2012. International Mathematical Forum, Vol.7, Hal. 1737-1749. [7] Wilson, J. Robin and John J. Watkins. 1990. Graphs An Introductory Approach. New York : University Course Graphs, Network, and Design.
