Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
2 Oktober 2023 e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 263-269 DOI: https://doi.
org/10.
55606/jurrimipa.
Bilangan Kromatik Dari Graf Hasil Operasi Korona Pada Graf Bintang Dan Graf Ligkaran Shindy Sagita Br Ginting Universitas Negeri Medan Mulyono Mulyono Universitas Negeri Medan Korespondensi penulis: shindysagita@gmail.
Abstract: Two graphs are operated with various operations, one of which is Operation Corona.
The graphs that are operated in this paper are circle graphs and star graphs.
Both graphs are operated with Operation Corona.
The graph resulting from the operation is then colored using the Greedy Algorithm.
The Chromatic Number obtained from the results of the Corona Operation on a graph (Cn Oo S.
is NC_nOoS_m = 3 for every m,n Ou 3, .
,n OO N}.
Because the graph resulting from the corona operation is non-commutative, the chromatic number obtained from the graph (Cn Oo S.
is different from the graph (Sm Oo C.
The chromatic number from the corona operation on the graph (Sm Oo C.
is divided into 2, namely: NS_mOoC_n = 3 for every odd n, and NS_mOoC_n = 4 for every even n, m Ou 3, n Ou 4, .
, n OO N}.
Keywords: Greedy Algorithm.
Graph.
Star Graph.
Circle Graph.
Corona Operation.
Graph Coloring.
Abstrak: Dua buah graf dioperasikan dengan berbagai operasi, salah satunya adalah Operasi Korona.
Graf yang dioperasikan pada tulisan ini adalah Graf Lingkaran dan Graf Bintang.
Kedua graf tersebut dioperasikan dengan Operasi Korona.
Graf hasil operasi tersebut kemudian dilakukan pewarnaan graf menggunakan Algoritma Greedy.
Bilangan Kromatik yang diperoleh dari hasil Operasi Korona pada graf (Cn Oo S.
adalah yueyaycu Oo ycIyco = 3 untuk setiap m,n Ou 3, .
,n OO N}.
Karena graf hasil operasi korona bersifat tidak komutatif, maka hasil bilangan kromatik yang diperoleh dari graf (Cn Oo S.
berbeda dengan Graf (Sm Oo C.
Bilangan Kromatik dari hasil operasi korona pada graf (Sm Oo C.
terbagi 2, yaitu : yueycIyco Oo yaycu = 3 untuk setiap n ganjil, dan yueycIyco Oo yaycu = 4 untuk setiap n genap, m Ou 3, n Ou 4, .
,n OO N}.
Kata kunci: Algoritma Greedy.
Graf.
Graf Bintang.
Graf Lingkaran.
Operasi Korona.
Pewarnaan Graf.
LATAR BELAKANG
Sebuah graf G terdiri dari suatu himpunan V yang merupakan vertex-vertex .
impul Ae simpu.
dan suatu himpunan E dari sisi-sisi sedemikian rupa sehingga setiap sisi dikaitkan dengan pasangan simpul yang tak terurut.
Jika terdapat sebuah sisi e yang menghubungkan simpul v dan w, dapat dinyatakan dengan e = .
atau e = .
Dalam konteks ini, .
menyatakan sebuah sisi antara simpul v dan simpul w dalam sebuah graf dan bukan sebuah pasangan terurut.
Dua buah graf dapat dioperasikan dengan berbagai macam operasi, antara lain operasi joint (G H), darab Cartesius (G y H), darab korona (G Oo H), darab tensor (G O H), komposisi (G[F]) dan Amalgamation.
Pada penelitian ini, operasi graf yang digunakan yaitu operasi korona yang dinotasikan dengan (G Oo H).
Operasi korona pada dua buah graf G dan H, didefenisikan sebagai graf yang diperoleh dari salinan p-simpul dari graf G dan p salinan H1.
H2, .
Hp dari H, yang kemudian bergabung dengan i-simpul dari G untuk setiap simpul dari H.
Received Juni 30, 2023.
Revised Juli 18, 2023.
Accepted Agustus 01, 2023 * Shindy Sagita Br Ginting, shindysagita@gmail.
Bilangan Kromatik Dari Graf Hasil Operasi Korona Pada Graf Bintang Dan Graf Ligkaran Pada pembahasan graf, topik yang sering muncul adalah tentang pewarnaan graf.
Dalam teori graf, pewarnaan graf merupakan suatu bentuk pelabelan graf, yaitu dengan memberikan warna pada elemen graf yang akan dijadikan subjek dalam memahami constraint Ada tiga macam persoalan pewarnaan graf .
raph colourin.
, yaitu pewarnaan simpul, pewarnaan sisi dan pewarnaan wilayah .
Bilangan Kromatik dari Graf G adalah jumlah warna minimum yang dapat digunakan untuk mewarnai simpul .
ertex / V).
[] Bilangan Kromatik yang dinotasikan sebagai N(G), adalah bilangan bulat terkecil k sehingga graf G mempunyai pewarnaan titik sejati dengan kwarna.
Penerapan bilangan kromatik untuk suatu graf sangat beragam, diantaranya adalah masalah pengaturan jadwal, masalah penempatan bahan kimia dan penempatan barang dari beberapa objek yang berbeda.
Untuk melakukan pewarnaan graf, ada beberapa algoritma yang dapat digunakan, seperti Algoritma Welch Powell.
Algoritma Genetika.
Algoritma Greedy, dan Penelitian yang berkaitan dengan Operasi Korona antara lain dengan judul AuDimensi Metrik pada Hasil Operasi Korona Dua Buah GrafAy.
Graf yang digunakan pada penelitian tersebut adalah Graf Lintasan (P.
Graf Lingkaran (C.
dan Graf Bintang (K1,.
Hasil dari penelitian tersebut adalah nilai Dimensi Metrik dari Graf (Pn o C.
dengan n Ou 2 dan m Ou 5 dan Graf (Pn o K1,.
dengan n Ou 2 dan m Ou 3.
Selanjutnya, penelitian yang berkaitan dengan Operasi Korona dan Bilangan Kromatik antara lain dengan judul AuBilangan Kromatik-Total Hasil Kali Korona Dua GrafAy.
Hasil dari penelitian tersebut adalah Bilangan Kromatik dari beberapa graf yang telah dioperasikan dengan operasi korona.
KAJIAN TEORITIS
Teori graf merupakan salah satu cabang ilmu matematika yang banyak diaplikasikan dalam kehidupan nyata, seperti pada penjadwalan, pembuatan peta serta pengaturan lampu lalu Teori graf pertama kali diperkenalkan pada tahun 1736 melalui tulisan Euler yang berisi tentang upaya pemecahan masalah jembatan Konigsberg di Eropa, yakni membuktikan kemungkinan melewati empat daerah yang terhubung dengan tujuh jembatan tersebut dalam sekali waktu.
Euler merepresentasikan masalah tersebut dalam graf dan menyatakan keempat daerah itu sebagai titik, sedangkan ketujuh jembatan sebagai sisi yang menghubungkan pasangan titik yang sesuai.
Dari percobaan yang ia lakukan, disimpulkan bahwa tidak mungkin bisa melalui setiap jembatan dan kembali lagi ke tempat semula dalam sekali waktu, maka untuk itu jumlah jembatan yang menghubungkan setiap daratan harus genap.
JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 263-269 Setelah lebih dari 100 tahun tulisan tersebut tidak mendapatkan perkembangan yang berarti, pada tahun 1847.
Kirchoff .
berhasil mengembangkan teori pohon yang digunakan dalam persoalan jaringan listrik.
Kemudian.
Coyley .
1 Ae 1.
menggunakan konsep yang sama untuk menjelaskan permasalahan kimia sepuluh tahun Graf dapat dikelompokkan menjadi beberapa kategori bergantung pada sudut pandang Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, digolongkan menjadi graf sederhana dan graf tak-sederhana.
Graf tak sederhana terdiri dari 2 jenis yaitu, graf ganda dan graf semu.
Berdasarkan orientasi arah pada sisi, maka secara umum graf dapat dibedakan menjadi 2 jenis yaitu, graf tak-berarah dan graf berarah.
Selain itu, juga ada Graf Planar yaitu graf yang dapat digambarkan pada bidang datar sedemikian sehingga tidak ada sisinya yang saling berpotongan.
Graf Bintang merupakan graf bipartisi lengkap yang berbentuk Sn dengan n Ou 3.
Dimana V (S.
= { v1, v2, .
, v.
dengan titik v1 disebut sebagai titik pusat dan titik-titik lain yang berhubungan langsung dengan titik pusat disebut sebagai daun.
Graf Lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua.
Graf lingkaran dengan n simpul dilambangkan dengan Cn.
Misalkan G1 dan G2 adalah dua buah graf sebarang.
G1 Korona G2 (G1 o G.
adalah graf yang terbentuk dari Graf G1 dan Graf G2 dengan Graf G2 sebanyak order G1, dengan cara menghubungkan semua titik di (G.
i ke satu titik xi di G1 dengan i = 1, 2, .
|G.
Graf hasil operasi korona memiliki banyak himpunan simpul |V| = |V.
|V1 | |V.
dan banyak anggota himpunan sisi |E| = |E.
|V.
y |E.
|V.
y |V.
Dalam teori graf, pewarnaan graf merupakan suatu bentuk pelabelan graf, yaitu dengan menberikan warna pada elemen graf yang akan dijadikan subjek dalam memahami constraint Ada tiga macam pewarnaan graf, yaitu pewarnaan simpul, pewarnaan sisi dan pewarnaan wilayah.
Pewarnaan simpul adalah pemberian warna pada simpul-simpul di dalam graf sedemikian sehingga setiap dua simpul bertetangga mempunyai warna yang berbeda.
Jumlah warna yang digunakan harus sesedikit mungkin.
Bilangan Kromatik dari Graf G dinyatakan dengan N(G) merupakan bilangan k terkecil sehingga Graf G dapat diwarnai dengan k-warna.
Warna-warna yang digunakan untuk mewarnai dapat dinyatakan dengan bilangan 1, 2, 3, .
, k.
Jelas bahwa N(G) O |V(G)|, sedangkan cara mudah untuk mencari batas bawah adalah dengan mencari graf bagian konplit terbesar di Bilangan Kromatik Dari Graf Hasil Operasi Korona Pada Graf Bintang Dan Graf Ligkaran Pada Salah satunya adalah Algoritma Greedy.
Algoritma Greedy ini berarti memberikan warna untuk beberapa cacah derajat simpul berurutan dimulai dari derajat terbesar untuk memperoleh cacah pewarnaan paling minimum.
Dalam algoritma ini simpul-simpul dari graf yang akan diwarnai diurutkan terlebih dahulu menurut aturan tertentu.
METODE PENELITIAN
Penelitian dilakukan di Digital Library Universitas Negeri Medan yang memiliki beberapa buku yang berkaitan dengan graf dan operasi korona.
Waktu penelitian kurang lebih dua bulan.
Metode penelitian yang digunakan pada penulisan penelitian ini adalah riset Informasi yang diperlukan dalam penelitian ini didapatkan dari buku referensi, jurnal, maupun dokumen-dokumen lain yang berkaitan dengan topik pembahasan.
Adapun prosedur pada penelitian ini adalah sebagai berikut.
Mengumpulkan teori-teori pendukung mengenai materi yang dibahas dalam Menggambarkan Graf Lingkaran (C.
dan Graf Bintang (S.
Mengoperasikan Graf Bintang (S.
dan Graf Lingkaran (C.
dengan operasi korona.
Mewarnai setiap titik pada graf yang dihasilkan dengan pewarnaan graf.
Menemukan bilangan kromatik dari graf yang dihasilkan dan kemudian Membuktikan pola yang terbentuk.
Menarik kesimpulan.
HASIL DAN PEMBAHASAN
Penelitian ini bertujuan untuk menentukan bilangan kromatik dari graf hasil operasi korona pada graf bintang dan graf lingkaran dan kemudian membuktikan pola yang telah Graf Bintang yang digunakan mulai dari S3 sampai S6 dan Graf Lingkaran yang digunakan adalah C3 dan C4.
Operasi graf yang digunakan adalah operasi korona.
Graf Bintang dioperasikan dengan Operasi Korona terhadap Graf Lingkaran.
Kemudian, graf yang dihasilkan diwarnai dengan menggunakan Algoritma Greedy yaitu, dengan mengurutkan vertex dengan jumlah derajat tertinggi dan kemudian ditentukan bilangan kromatik dari pewarnaan graf tersebut.
Langkah tersebut terus diulangi hingga ditemukan pola yang JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 263-269 Berdasarkan hasil operasi korona dari graf bintang dan graf lingkaran, maka pola yang terbentuk yaitu :
No.
Cn o S m C3 o S3 C3 o S4 C3 o S5 C3 o S6 C4 o S3 C4 o S4 C4 o S5 C4 o S6 NCn o Sm Dari hasil penelitian diatas, dapat ditemukan bahwa NCn o Sm = 3 untuk .
,n Ou .
Akan dibuktikan jika m,n < 3 maka NCn o Sm O 3.
Graf Bintang memiliki jumlah simpul terkecil Maka, jika nilai m < 3 tidak dapat dilakukan operasi korona antara Graf Bintang dan Graf Lingkaran.
Jadi, jika m,n < 3 maka NCn o Sm O 3 terbukti.
Operasi Korona tidak bersifat komutatif.
Maka akan dilakukan operasi korona dari Graf Lingkaran terhadap Graf Bintang.
Graf Lingkaran yang digunakan adalah Graf C3 sampai Graf C6 dan Graf Bintang yang digunakan adalah Graf S3 dan Graf S4.
Adapun hasil bilangan kromatik yang diperoleh dari kedua graf yang telag dioperasikan dengan operasi korona adalah sebagai berikut.
No.
Sm o Cn S3 o C3 S3 o C4 S3 o C5 S3 o C6 S4 o C3 S4 o C4 S4 o C5 S4 o C6 NSm o Cn Dari hasil penelitian diatas, diperoleh :
NSm o Cn = 4 untuk setiap n ganjil, m,n Ou 3 NSm o Cn = 3 untuk setiap n genap, m Ou 3, n Ou 4 Akan dibuktikan jika NSm o Cn O 4 untuk setiap n tidak ganjil, m,n Ou 3 dan NSm o Cn O 3 untuk setiap n tidak genap, m Ou 3, n Ou 4.
Untuk n tidak ganjil Nilai NSm = 2.
Misalkana C = s1, s2 merupakan himpunan warna untuk graf Sm.
Selanjutnya m copy graf Cn dimana n tidak ganjil dapat diwarnai dengan 2 warna.
Karena setiap simpul dari m copy graf Cn terhubung dengan salah satu titik di Sm, maka 1 warna dari C dapat digunakan untuk mewarnai titik di Cn.
Sebuah titik harus Bilangan Kromatik Dari Graf Hasil Operasi Korona Pada Graf Bintang Dan Graf Ligkaran diwarnai dengan warna ketiga, yaitu s3.
Jadi.
NSm o Cn O 4 untuk setiap n tidak ganjil, m,n Ou 3 terbukti.
Untuk n tidak genap Nilai NSm = 2.
Misalkana C = s1, s2 merupakan himpunan warna untuk graf Sm.
Selanjutnya m copy graf Cn dimana n tidak genap dapat diwarnai dengan 3 warna.
Karena setiap simpul dari m copy graf Cn terhubung dengan salah satu titik di Sm, maka 1 warna dari C dapat digunakan untuk mewarnai titik di Cn.
Dua buah titik harus diwarnai dengan warna ketiga dan warna keempat, yaitu s3 dan s4.
Jadi.
NSm o Cn O 3 untuk setiap n tidak genap, m Ou 3, n Ou 4 terbukti.
KESIMPULAN DAN SARAN
Berdasarkan uraian hasil dan pembahasan diatas, diperoleh kesimpulan bahwa NCn o Sm = 3 untuk m,n Ou 3.
Karena operasi korona bersifat tidak komutatif, maka dilakukan juga penelitian dengan hasil NSm o Cn = 4 untuk setiap n ganjil, m,n Ou 3 dan NSm o Cn = 3 untuk setiap n genap, m Ou 3, n Ou 4.
Penelitian ini membahas mengenai operasi korona pada Graf Bintang dan Graf Lingkaran.
Penelitian ini dapat dikembangkan lagi dengan mengubah dan/atau menambah operasi atau jenis graf yang akan digunakan.
Selain itu, juga dapat dilakukan pewarnaan graf dengan menggunakan algoritma yang berbeda.
DAFTAR REFERENSI
Apriyanto .
Pewarnaan Graph Berbasis Algoritma Welch Powell dalam Pengaturan Jadwal Praktikum.
Jurnal Penelitian Matematika dan Pendidikan Matematika, 1.
Astuti.
Penyusunan Jadwal Ujian Mata Kuliah dengan Algoritma Pewarnaan Graf Welch Powel.
Jurnal Dian, 68 Ae 74 Barathi.
, .
A Study on Graph Coloring.
International Journal of Scientific and Engineering Research, 8.
, 20 Ae 30 Ellania.
Bilangan Kromatik-Total Hasil Kali Korona Dua Graf.
Jurnal Ilmiah Matematika, 8.
, 17-24 Fatimah.
, dkk.
Pelabelan L.
pada Operasi Beberapa Kelas Graf.
Jurnal Ilmiah Matematika dan Terapan, 13.
, 73 Ae 84 Heny.
, dan Dwi.
Aplikasi Pewarnaan Graf untuk Optimalisasi Pengaturan Traffic Light di Sukoharjo.
Jurnal IPTEK, 7.
, 25 Ae 34.
Maya.
Dimensi Metrik pada Hasil Operasi Korona Dua Buah Graf.
Jurnal Buana Matematika, 7.
, 93 Ae 98 Saif.
, .
Penerapan Greedy Coloring Algorithm pada Peta Kotamadya Berbasis FourColour Theorem.
Kaunia.
XI.
, 1-13 JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 263-269 Vasudev.
Graph Theory with Application.
Karanataka New Age International (P) Ltd.
Welyyanti.
Beberapa Syarat Cukup untuk Bilangan Kromatik Lokasi hingga pada Graf tak Terhubung.
Eksakta, 19.
, 76-82