Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
2 Oktober 2023 p-ISSN: 2828-9382.
e-ISSN: 2828-9390.
Hal 147-161 DOI: https://doi.
org/ 10.
55606/jurrimipa.
Pelabelan Total Titik Ajaib Pada Graf Tangga Riandy Fauzi Manik Jurusan Matematika.
Fakultas Matematika dan Ilmu Pengetahuan Alam.
Universitas Negeri Medan E-mail: riandi.
123@gmail.
Marlina Setia Sinaga Jurusan Matematika.
Fakultas Matematika dan Ilmu Pengetahuan Alam.
Universitas Negeri Medan E-mail: Marlinasetiasinaga222@gmail.
Jalan Willem Iskandar Pasar V Medan Estate.
Kotak Pos No.
1589 Medan 20221 A.
Sumatera Utara Abstract.
The labeling of a graph is a mapping that pairs the elements in the graph into positive In this thesis, it discusses how the magic total point labeling algorithm on the , ladder graph and the , ladder graph and how the magic total point labeling on the , ladder graph and the , adder graph uses the magic square matrix modification using the durer method.
Where the elements of the result of this magic square matrix modification will be used as point labels on the , ladder graph and the , ladder graph.
Keywords: Ladder graphs , magic total dot labeling, modified square matrix, durer Abstrak.
Pelabelan suatu graf merupakan suatu pemetaan yang memasangkan elemen-elemen yang ada pada graf menjadi bilangan bulat positif.
Didalam skripsi ini membahas bagaimana algoritma pelabelan total tiik ajaib pada graf tangga L , dan graf tangga L , serta bagaimana pelabelan total titik ajaib pada graf tangga L , dan graf tangga L , menggunakan modifikasi matriks bujur sangkar ajaib dengan menggunakan metode durer.
Dimana elemen-elemen hasil dari modifikasi matriks bujursangkar ajaib ini akan digunakan sebagai label titik pada graf tangga L , dan graf tangga L , .
Kata kunci: Graf tangga metode durer.
, , pelabelan total titik ajaib, modifikasi matriks bujur sangkar.
Received Mei 30, 2023.
Revised Juni 30, 2023.
Accepted Juli 15, 2023 * Riandy Fauzi Manik, riandi.
123@gmail.
Pelabelan Total Titik Ajaib Pada Graf Tangga
LATAR BELAKANG
Didalam studi matematika terdapat topik tentang pelabelan graf, dimana objek yang dibahas berupa teori graf yang digambarkan dalam bentuk titik dan sisi dan terdiri dari bilangan asli yang disebut label yang pertama kali diperkenalkan oleh Sadlysk pada tahun 1964.
Stewart pada tahun 1966, serta Kotzig dan Rosa pada tahun 19701.
Ada banyak jenis-jenis pelabelan, diantaranya adalah pelabelan sisi, pelabelan titik, dan pelabelan ajaib.
Dimana saat graf diberi label berfokus dipenemuan graf-graf tertentu yang dapat digunakan untuk melabelkan graf.
Pelabelan total titik ajaib dapat diaplikasikan ke macam-macam graf, diantaranya adalah pelabelan total titik ajaib pada graf tangga yang berjudul Total Vertex Irregularity Strength Of Ladder Related Graphs (Slamin dkk, 2.
Vetex Polinomial Of Ladder Graphs, (Ahmad dkk, 2.
, dan pelabelan jumlah eksklusif pada graf tangga Ln (Debby dan Peter, 2.
serta Vertex-magic Total Labeling of Generalized Petersen Graphs and Convex Polytopes (Miller dkk, 2.
Graf tangga Ln didefinisikan sebagai produk kartesian dari P2 dan Pn.
Ketika dibentuk kelihatan seperti tangga dengan n anak tangga.
Dengan cara yang sama kita dapat mengatakan bahwa terdapat dua himpunan dari simpul Pn pada setiap sisi tangga dan kedua sisi dari tangga dihubungkan dengan anak tangga.
Dalam pembentukan graf tangga dengan kali kartesius antara dua graf lintasan, terdapat beberapa bentuk yang dihasilkan dari graf tangga.
Menurut M.
Regees dkk, dalam penelitiannya yang berjudul Edge magic and bimagic harmonious labeling of ladder graphs tahun 2020 terdapat bentuk graf tangga yaitu graf tangga melingkar dengan nilai k =55, menurut V.
Jeba Rani dkk, didalam penelitiannya yang berjudul Vertex Polynomial Of Ladder Graphs terdapat juga bentuk graf tangga yang lain dimana penggunaan fungsi polynomial terhadap graf tangga, dan menurut A.
Durai Baskar pada penelitiannya yang berjudul Logarithmic Mean Labeling of Some Ladder Related Graphs pada tahun 2020 melabeli graf tangga dengan algoritma rata-rata sehingga membentuk sebuah graf tangga bentuk yang baru.
Aldous.
M dan Wilson.
: Graphand Aplications An introductory Approach, 4th ed.
Open University 2000.
Great Britain.
Di akses dari https://w.
com/Magic-Graphs-Alison-MMarr/dp/0817683909.
Kotzig.
A, dan Rosa.
Magic valuations of finite graphs.
Canada.
Math.
Bull.
13, 451-461.
Debby.
Peter.
M,H, .
: Pelabelan jumlah eksklusif pada graf tangga Ln.
Prosiding SeminarNasional Penelitian.
Pendidikan dan Penerapan MIPA.
JURRIMIPA: Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam - Vol.
No.
2 Oktober 2023 p-ISSN: 2828-9382.
e-ISSN: 2828-9390.
Hal 147-161 Adapun matriks bujur sangkar ialah matriks persegi dimana entri-entrinya adalah bilangan bulat non negatif, sehingga mempunyai nomor baris yang sama dengan nomor kolom, contohnya 2 x 2, 3 x 3, 4 x 4 dan seterusnya.
Artinya pada matriks ini tidak bisa berordo berbeda.
Jika 2y2 maka dia mempunyai 2 baris dan 2 kolom dan jika 3y3 maka mempunyai 3 baris dan 3 kolom.
Matriks bujur sangkar juga disebut dengan matriks persegi karena terdapat jumlah dan kolom yang sama dan membentuk sebuah persegi.
Pada matris bujur sangkar ini biasanya dikenal dengan istilah elemen diagonal yang terdapat pada baris dan kolom.
Matriks bujur sangkar ajaib berukuran n x n dengan n bilangan ganjil dan Ou 3 adalah menggunakan elemen-elemen matriks tersebut dari 1 sampe n2 sedemikian sehingga setiap baris, kolom dan diagonal utama mempunyai jumlah yang sama.
Berdasarkan latar belakang masalah yang telah disajikan, maka penulis mengusulkan untuk melakukan penelitian yang berjudul AuPELABELAN TOTAL TITIK AJAIB PADA GRAF TANGGAAy.
KAJIAN TEORITIS
Pengertian Graf Pada tahun 1736 konsep tentang teori graf diperkenalkan oleh seorang matematikawan bernama Leonard Euler.
Pada teorinya euler memecahkan misteri permasalahan Jembatan Konigsberg.
Pada jembatan tersebut terdapat sebuah sungai yang mengalir yang bernama Pregel dan mengelilingi sebuah pulau.
Sungai pregel ini terbagi dua dan membentuk dua aliran sungai dimana ada sebanyak tujuh jembatan penghubungnya.
Teori ini dibuktikan bahwa seseorang tidak mungkin dapat menyebrangi ketujuh jembatan sekali saja dan kemudian kembali lagi ke asalnya.
Gambar 1.
hasil penggambaran teori euler Lee.
Michael, 2006.
Liniear Algebra of Magic Square.
Central Micigan University.
Pelabelan Total Titik Ajaib Pada Graf Tangga Terminologi Dasar Graf Di bawah ini terdapat beberapa terminologi atau definisi yang berkaitan pada graf yang biasa digunakan.
- Bertetangga (Adjacen.
Titik dikatakan bertetangga dengan titik , jika ( , ) merupakan sisi pada graf G.
Gambar 2.
contoh graf sederhana a Bersisian (Inciden.
Bersisian .
adalah sisi sembarang sisi bersisisan, untuk = ( , ).
Gambar 3.
contoh graf sederhana b Lintasan (Pat.
Pada gambar dibawah ini contoh graf mengandung sebuah lintasan .
Dari gambar 4 terdapat lintasan 1, 2, 3, 4 dengan barisan sisi e2, e4,e5.
Gambar 4.
contoh graf sederhana c Munir.
R, .
: Matematika Diskrit.
Informatika.
Bandung.
JURRIMIPA: Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam - Vol.
No.
2 Oktober 2023 p-ISSN: 2828-9382.
e-ISSN: 2828-9390.
Hal 147-161 Siklus(Cycl.
atau Sirkuit (Circui.
Pada gambar 4 merupakan contoh siklus (Cycl.
atau sirkuit (Circui.
Terlihat digambar 4 diatas, diawali dengan titik 1, 2, 5, 1 adalah sirkuit.
Jumlah sisi di dalam sirkuit merupakan panjang sirkuit dan pada gambar 4 panjang sirkuitnya adalah 3.
Terhubung (Connecte.
Keterhubungan dua buah titik adalah penting di dalam graf, dimana titik u dan v terhubung jika titik u terdapat lintasan ke titik v.
Gambar 5.
Graf terhubung dan tak terhubung Pada gambar 5 diatas graf A adalah gambar untuk graf terhubung dan mempunyai lintasan dari ke titik dan diantara titik yang dihubungkan sebuah sisi, dan graf B adalah gambar graf yang tidak terhubung karena terdapat titik dan sisi pada graf yang tidak dihungkan oleh sebuah Upgraf (Sup Grap.
Misalkan dari , jika jenis graf.
= ( , ) adalah sebuah graf
= ( ,
) merupakan upgraf .
ub grap.
Dibawah ini merupakan contoh upgraf .
ub grap.
dari sebuah Gambar 6.
( ) Contoh Graf dan ( ) Contoh Subgraf dari Pelabelan Total Titik Ajaib Pada Graf Tangga Lingkaran Contoh dari graf lingkaran dapat dilihat pada gambar di bawah ini.
Gambar 7.
Graf Lingkaran Jenis Jenis Graf Graf Sederhana Graf sederhana merupakan graf yang tidak memiliki loop ataupun sisi ganda pada grafnya.
Sisi-sisi pada graf sederhana ialah pasangan takterurut .
nourde redpair.
Graf tak sederhana(Unsimple Grap.
Graf tak sederhana memiliki dua jenis graf yaitu graf ganda dan graf semu.
Jika sebuah graf terdiri dari sisi ganda atau loop dinamakan Graf Tak Sederhana (Unsimple Grap.
Produk Graf Untuk mendefinisikan produk hasil perkalian graf lintasan dipertimbangkan ada dua titik Graf tangga ) dan =( , dari dua graf Graf tangga dapat dibentuk dengan mencari dari hasil kali kartesius sebuah graf lintasan terhadap dua titik kemudian graf lintasan yang memiliki n titik.
Penulisan notasi untuk graf tangga ini dilambangkan dengan Pelabelan Graf , maka didapatkan (Joseph, 2.
Pemetaan dengan memasang unsur-unsur dari graf dengan menggunakan bilangan bulat positif disebut pelabelan graf.
Bilangan tersebutlah yang dikatakan label.
Apabila domain pemetaan titik.
Maka pelabelan dinamakan pelabelan titik.
Apabiladomainnyasisi.
Maka dinamakan pelabelan isi, dan dikatakan pelabelan total apabila domainnya titik dan sisi.
Miller.
Ryan.
Ryjacek.
: Characterisation of graphs with exclusive sum labelling.
Australasian Journal Of Combinatorics, 69.
, 334Ae348.
Di akses dari https://ajc.
au/pdf/69/ajc_v69_p334.
JURRIMIPA: Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam - Vol.
No.
2 Oktober 2023 p-ISSN: 2828-9382.
e-ISSN: 2828-9390.
Hal 147-161 Pelabelan berkaitan dengan graf yang sering digunakan, yakni pelabelan titik.
Pelabelan Titik Pelabelan titik merupakan suatu pemetaan apabila domainnya berupa himpunan titik.
Sehingga diberikan suatu graf G yang memiliki himpunan titik : ( ) Ie .
,2,3,4,.
Ie .
OO Definisi Modifikasi matriks Bujur sangkar Ajaib Matriks yang bujursangkar ajaib yang bilangan-bilangannya 1, 2.
A .
bujur sangkar ajaib klasik.
Banyak bagian baris, kolom dan disebut juga sebagai juga dua diagonalnya dapat disimbolkan dengan d diartikan juga dengan banyaknya jumlah ajaib, dan n merupakan indeks matriksnya dapat dirumuskan kedalam rumus matematika :
Oc atau 1 2 3 A A .
METODE PENELITIAN
Metode penelitian ini adalah studi pustaka dimana data yang diperlukan adalah kumpulan berbagai literatur pelabelan graf dari buku buku dan jurnal jurnal yang ada.
Peneliti melakukan penelitiannya bertempat di Digital Library universitas negeri medan dan waktu yang diperlukan dalam penyelesaian penelitian ini dibutuhkan lebih kurang didalam waktu dua bulan.
HASIL DAN PEMBAHASAN
Algortima pelabelan total titik ajaib graf tangga , dan bujur sangkar ajaib dengan modifikasi matriks Metode yang digunakan untuk menyusun pelabelan total titik ajaib pada graf tangga Ln adalah metode durer dengan modifikasi matriks bujur sangkar ajaib.
Beberapa langkah yang akan dilakukan untuk melakukan modifikasi matriks bujur sangkar Terdapat lima matriks berordo 4 Matriks 4 misal terdiri dari angka 1, 2, 3.
A .
Dimulai dari Lee.
Michael, 2006.
Liniear Algebra of Magic Square.
Central Micigan University.
,A ,
Pelabelan Total Titik Ajaib Pada Graf Tangga Matriks terdiri dari elemen nondiagonal dari dan elemen diagonalnya diberi nilai Matriks Matriks berisikan 1, 2, 3.
A .
OO .
ang dimulai dari dibentuk dari dua diagonal dari , sampai dan elemen nondiagonalnya diberi nilai Matriks merupakan gabungan matriks , dan hasil Ini adalah matriks bujur sangkar ajaib.
Dari hasil modifikasi matriks bujursangkar ajaib ini maka akan didapatkan nilai konstanta ajaib untuk pelabelan total titik ajaib pada graf tangga.
Kemudian dibentuk graf tangga matriks bujursangkar Ajaib.
untuk dilabeli menggunakan hasil dari modifikasi Maka hasil modifikasi matriks bujur sangkar ajaib pada pelabelan total titik ajaib pada graf tangga Ln akan memenuhi.
Dapat dirumuskan Algoritma pelabelan total titik ajaib pada graf tangga .
Diambil graf tangga , yang akan dilabeli.
Menyajikan matriks bujur sangkar dari graf tangga , 2, 3.
A ,
Matriks bujur sangkar dari , .
, dengan entri-entrinya akan dimodifikasi dengan metode durer , untuk mendapatkan matriks bujur sangkar ajaib.
Matriks dari graf defenisi (Michael Lee, 2006 ) dikatakan sebagai matriks bujur sangkar ajaib Sesuai .
Hasil dari matriks bujur sangkar ajaib akan digunakan untuk melabeli graf defenisi pelabelan graf ) .
Kemudian graf dilabeli dengan hasil modifikasi matriks bujur sangkar ajaib.
Dari algoritma pelabelan total titik ajaib Ln maka akan didapatkan konstanta ajaib untuk pelabelan graf tangga Ln.
JURRIMIPA: Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam - Vol.
No.
2 Oktober 2023 p-ISSN: 2828-9382.
e-ISSN: 2828-9390.
Hal 147-161 Pelabelan total titik ajaib pada graf tangga L4,4 Graf tangga L 4,4 ini adalah hasil kali kartesius graf lintasan P4 dan P4.
Gambar 8.
graf lintasan P 4 Pelabelan total titik ajaib pada graf L 4,4 dengan modifikasi matriks bujur sangkar ajaib orde genap menggunakan metode durer.
Langkah-langkah metode durer didalam proses menyelesaikan permasalah matriks yang bujursangkar ajaib dengan = 4.
Matriks berisikan bilangan 1, 2, 3.
A , n2 .
imulai ,A .
Matriks berisikan elemen non diagonal dari Matriks yang berisikan bilangan 1, 2, 3.
A , ( yang dimulai dari A.
Matriks yang berisikan bilangan 1, 2, 3.
A , ( yang dimulai dari A.
dan elemen diagonalnya diberi nilai nol.
Pelabelan Total Titik Ajaib Pada Graf Tangga Matriks berisikan elemen kedua diagonal dari Matriks yang merupakan kombinasi dan elemen non diagonalnya diberi nilai nol.
Dari hasil modifikasi matrik bujur sangkar ajaib maka dapat dilabeli grafik L 4,4 sebagai Hasil pelabelan total titik ajaib pada graf L 4,4 dengan modifikasi matrik bujur sangkar ajaib Pelabelan total titik ajaib pada graf tangga L 8,8.
Graf tangga L 8,8 ini adalah hasil kali kartesius graf lintasan P8 dan P8.
Gambar 9.
graf lintasan P 8.
Hasil perkalian kartesius graf lintasan P 8 dan P 8 .
JURRIMIPA: Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam - Vol.
No.
2 Oktober 2023 p-ISSN: 2828-9382.
e-ISSN: 2828-9390.
Hal 147-161 Gambar 10.
Graf Tangga L 8,8 Dengan mengikuti metode durer untuk melabeli graf tangga L 8,8 maka dapat diselesaikan.
merupakan bilangan positif ( 1, 2, 3.
A .
yang akan dibagi menjadi sub matriks 4 x 4.
merupakan sub matriks terdiri dari bilangan 1, 2, 3.
A , 64 .
etapi tersusun mulai dari terdiridari sub matriks diagonal utama dan kedua diberi nilai nol.
Diagonal utama dan kedua diberi nilai nol.
Pelabelan Total Titik Ajaib Pada Graf Tangga Matriks merupakan gabungan matriks , dan hasil ini adalah matriks bujur sangkar ajaib.
Hasil pelabelan total titik ajaib pada graf L 8,8 dengan modifikasi matriks bujur sangkar ajaib didapatkan.
Pelabelan total titik ajaib pada graf tangga , ,dengan bilangan genap dan 1, 2, 3, .
n2 dengan modifikaasi konstruksi bujur sangkar ajaib orde genap.
Hasil modiAkasi matriks bujur
sangkar ajaib ini akan digunakan untuk melabelkan titik ajaib dari graf tangga
, , ,
dimana jumlah elemen diagonal utama dan jumlah elemen setiap baris untuk label titik adalah bernilai yaitu graf memiliki konstanta ajaib 34 dan graf , ,memiliki konstanta ajaib 260.
JURRIMIPA: Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam - Vol.
No.
2 Oktober 2023 p-ISSN: 2828-9382.
e-ISSN: 2828-9390.
Hal 147-161
KESIMPULAN DAN SARAN
Berdasarkan hasil dan pembahasan maka dapat disimpulkan hasil pelabelan total titik ajaib pada graf tangga menggunakan algoritma durer.
Adapun algoritma yang digunakan adalah sebagai berikut: .
Diambil graf tangga matriks bujur sangkar dari graf tangga .
Matriks bujur sangkar dari yang akan dilabeli, .
Menyajikan dengan entri-entrinya .
, 2, 3.
A , akan dimodifikasi dengan metode durer , untuk mendapatkan matriks bujur sangkar ajaib, .
Matriks dari graf dikatakan sebagai matriks bujur sangkar ajaib Sesuai defenisi (Michael Lee, 2006 ), .
Hasil dari matriks bujur sangkar ajaib akan digunakan untuk melabeli graf Kemudian graf ( defenisi pelabelan graf ), .
dilabeli dengan hasil modifikasi matriks bujur sangkar ajaib.
Pelabelan Total Titik Ajaib Pada Graf Tangga
DAFTAR REFERENSI
Afrianto.
I, dan Jamilah.
: Penyelesaian Masalah Minimum Spanning Tree (MST) Menggunakan Ant Colony System (ACS).
Jurnal Ilmiah Komputer dan Informatika (KOMPUTA), 1.
, 35Ae40.
Ahmad.
Bokhary.
Hasni.
Slamin.
: Total Vertex Irregularity Strength Of Ladder Related Graphs.
International Journal Science, 26.
, 1-5.
Diakses dari http://w.
com/pdf/8025771011--1--5--Ashfaq--co--Imran-0025-Math--Final Revised.
Ahmad.
Raj Sunder.
Isaac Shyla.
: Vetex Polinomial Of Ladder Graphs.
Info Kara Research, 8.
, 1-3, darihttps://w.
org/articles/MJM08010035.
Aldous.
M dan Wilson.
: Graphand Aplications An introductory Approach, 4th ed.
Open University 2000.
Great Britain.
Di akses dari https://w.
com/MagicGraphs-Alison-M-Marr/dp/0817683909.
Anton.
Dasar-Dasar Aljabar Linier.
Edisi Ketujuh.
Jilid 1.
Batam Center: Interaksar Atmadja.
: Pelabelan Harmonis Pada Graf Tangga Segitiga Pita.
Jurnal Sains dan Matematika Unpam, 4.
, 1-6, http://openjournal.
id/index.
php/jsmu/article/view/10334/7350.
Bartle.
R & D.
Sherbert, .
: Introduction to Real Analysis.
Singapore: Jhon Wiley & Sons.
INC.
Debby.
Peter.
M,H, .
: Pelabelan jumlah eksklusif pada graf tangga Ln.
Prosiding SeminarNasional Penelitian.
Pendidikan dan Penerapan MIPA.
Durai.
: Logarithmic Mean Labeling of Some Ladder Related Graphs.
An International Journal, 15.
, 296-313.
Diakses dari https://w.
edu/aam/.
Farida.
Indah.
Sudibyo.
Conference Series: Magic covering and edge magic labelling and its application.
Journal of Physics, 1.
Di akses dari https://iopscience.
org/article/10.
1088/1742-6596/1657/1/012051/pdf.
Hasmawati, .
Bahan Ajar Teori Graf.
Makassar: Universitas Hasanuddin Joseph A.
Gallian,A dynamic survey of graph labeling of some graphs.
The Electronic Journal of Combinatorics, .
, #DS6 Kotzig.
A, dan Rosa.
Magic valuations of finite graphs.
Canada.
Math.
Bull.
13, 451461.
Lakshmi.
Sudhakar.
: Algorithms For Magic Labelling On Graphs.
Journal of Theoretical and Applied Information Technology, 66.
, 36-42.
Di akses dari http://w.
org/volumes/Vol66No1/6Vol66No1.
Lee.
Michael, 2006.
Liniear Algebra of Magic Square.
Central Micigan University.
Lipschutz, 2004.
Seymour.
Aljabar Linier.
Edisi Ketiga: Erlangga Marr.
M and Wallis.
D, .
: Magic Graphs,2nd ed .
Springer Science Business Media.
New York.
JURRIMIPA: Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam - Vol.
No.
2 Oktober 2023 p-ISSN: 2828-9382.
e-ISSN: 2828-9390.
Hal 147-161 Maryati.
Salman A.
N,M.
Baskoro.
T, .
Supermagic coverings of the disjoint union graphs and amalgamations.
Elsevier Journal.
, 397- 405
Miller.
Ryan.
Ryjacek.
: Characterisation of graphs with exclusive sum labelling.
Australasian Journal Of Combinatorics, 69.
, 334Ae348.
Di akses dari https://ajc.
au/pdf/69/ajc_v69_p334.
Munir.
R, .
: Matematika Diskrit.
Informatika.
Bandung.
Sanjaya.
John.
Haryono.
Me.
Pelabelan Jumlah Eksklusif pada graf tangga (L.
Prosiding Seminar Nasional.
UNY.
Yogyakarta.
M299-M302.
Di akses dari http://eprints.
Sedlysek.
Theory of graphs and its applications.
Publ.
House Czechoslovak Acad.
Sci.
Prague.
Di akses dari https://searchworks.