## GRAF PRIMA PADA RING
Nurahmi Purnamasari 1 , Ganesha Lapenangga Putra 1* , Keristina Br. Ginting 1
1. Program Studi Matematika, Fakultas Sains dan Teknik, Universitas Nusa Cendana,
Kupang, Nusa Tenggara Timur
ABSTRAK
Graf prima pada ring yang dinotasikan dengan
  PG R merupakan graf yang terdiri
atas  pasangan  terurut  (V,E)  di  mana  himpunan  sisinya  adalah V R  dan  himpunan titiknya adalah 
 | 0 0, E xy xRy yRx x y      . Untuk R ring prima, maka   PG R
merupakan graf bintang atau dapat pula dikatakan untuk n bilangan prima,   n PG Zn graf  bintang.  Selain  mendefinisikan  graf  prima,  pada  tulisan  ini  akan    dijelaskan karakteristik dari graf prima pada ring seperti bentuk graf jika R adalah ring domain dengan R   , jika S R adalah ring semiprima, maka S R juga merupakan ring prima dimana graf yang dibentuk adalah graf bintang yang juga merupakan graf pohon dan jika   PG R adalah graf pohon maka S R adalah ring prima, serta menentukan jumlah subgraf 3 C yang berbeda pada graf   n PG Z . Selanjutnya tulisan ini dapat dilanjutkan untuk  melihat  bentuk  graf  dan  banyaknya  segitiga  pada  ring n Z dengan n adalah sebarang bilangan bulat.
Kata Kunci : Graf prima, ring prima, ring domain, ring semiprima, graf bintang

## 1. PENDAHULUAN
Matematika  merupakan  salah  satu  cabang  ilmu  yang  sangat  penting  di  mana matematika mempunyai sebuah kelebihan yang bisa diaplikasikan ke dalam beberapa aspek  tak  terkecuali  teknologi.  Matematika  menjadi  dasar  terkuat  bagi  terciptanya dunia teknologi dan segala kemajuan didalamnya, terbukti dengan tidak ada satupun teknologi  yang  luput  dari  peran  matematika  didalamnya.  Matematika  terbagi  atas berbagai  bidang  diantaranya  ada  Teori  Graf.  Teori  graf  diperkirakan  pertama  kali diperkenalkan  pada  tahun  1936  oleh  seorang  matematikawan  Swiss,  Leonhard  Euler yang  menulis  artikel  ilmiah  di  bidang  teori  graf  dengan  judul  “Seven  Bridges  of Königsberg”.  Graf  sendiri  merupakan  pasangan  terurut  (V,E)  dimana  V  adalah himpunan  tak  kosong  dari  objek  yang  disebut  titik  (vertex  atau  node)  dan  E  adalah himpunan yang anggotanya dibentuk oleh dua titik yang disebut sisi (edge) [1]. Selain
Teori Graf, di Matematika masih terdapat berbagai macam bidang yang menarik untuk dipelajari  salah  satu  diantaranya  adalah  Aljabar.  Secara  umum,  aljabar  sendiri merupakan  ilmu  yang  mempelajari  simbol-simbol  matematika  dan  aturan  untuk memanipulasi  simbol-simbol  tersebut.  Aljabar  juga  terdiri  atas  beberapa  struktur seperti grup, grup abelian, dan ring
Sejak  pertengahan  abad  ke-19,  Matematika  terus  mengalami  perkembangan seiring  dengan  perkembangan  zaman.  Pada  tahun  1983,  aljabar  graf  diperkenalkan oleh  Mcnulty  dan Shallon  sebagai cara  untuk  memberikan  struktur  aljabar  pada graf berarah  yang  sejak  saat  itu  telah  banyak  digunakan  dr  bidang  aljabar.  Hal  ini membuktikan  bahwa  ada  keterkaitan  antara  aljabar  secara  umum  dengan  teori  graf. Sesuai  dengan  penjelasan  di  atas  dan  dengan  melihat  berbagai  keterkaitan  antara bidang matematika yang satu dengan lainnya, maka penulis tertarik untuk membahas definisi  dan  karakteristik  “Graf  Prima  pada  Ring”  yang  juga  merupakan  keterkaitan lainnya antara teori graf dengan salah satu unsur pada aljabar yaitu ring.

## 2. METODE
Penulisan  dalam  kajian  ini  menggunakan  metode  studi  literature,  dimana  beberapa sumber  referensi  akan  dikumpulkan  lalu  kemudian  dilakukan  kajian  khusus  terkait graf  prima  pada  ring.  Sumber  yang  digunakan  dalam  pengkajian  dan  penulisan  ini diambil dari beberapa buku referensi, jurnal-jurnal ilmiah serta artikel web lainnya.

## 3. HASIL PENELITIAN
Pada bagian ini akan diberikan pembahasan lebih lanjud terkait graf prima pada ring berdasarkan  jurnal  yang  dipublikasikan  pertama  kali  oleh  Dr.  Bhavanari Satyanarayana, Dasari Nagaraju, dan Kuncham Syam Prasad [2]–[4].

## 3.1 Definisi
Misalkan  R  adalah  suatu  ring.  Sebuah  Graf   ,
G V E dikatakan  sebagai  graf  prima pada ring (yang dinotasikan dengan   PG R ), jika V R 
dan  
| 0 0, E xy xRy yRx x y      [5].
Untuk  setiap  graf   , PG R dimana ,1 5 n R n 
  Z .  Maka  Graf  tersebut  adalah  graf bintang, yang dimana tidak terdapat segitiga didalamnya. Hal ini juga berlaku untuk setiap graf   , PG R dimana , n R n  Z adalah bilangan prima. Selanjudnya dijelaskan lebih lanjud pada Teorema 3.2.

## 3.2 Teorema
Misalkan   , ,. R  suatu  ring  dengan R   .  jika  r  adalah  ring  domain,  maka   PG R adalah graf bintang 1, 1 1 R R K S    [5].
Bukti :
Diketahui bahwa     , PG R V E  dengan V R  . Ambil sebarang , x y V R   dengan 0 x  dan 0 y  .
Pandang   | xR xr r R   .  Perhatikan  bahwa  karena R ring  domain,  maka  untuk
0 y  , 0 xy xR   akibatnya   0 xR  .
Pandang , xRy xy xR  dan 0 xy  .  Perhatikan  bahwa  karena R ring  domain,  maka   . 0 xy y  dengan   . xy y xRy  .
Diperoleh   0 xRy  .
Selanjutnya,  pandang
  | yR yr r R   .  Perhatikan  bahwa  karena R ring  domain, maka untuk 0 x  , 0 yx yR   sehingga akibatnya   0 yR  .
Pandang , yRx yx yR  dan 0 yx  .  Perhatikan  bahwa  karena R ring  domain,  maka   . 0 yx x  dengan   . yx x yRx  .
Diperoleh   0 yRx 
Jadi,  untuk setiap , x y R  dengan 0 x  dan 0 y  maka     xy PG R  . Perhatikan  jika 0 R x  dan 0 y R   ,  maka   0 xR  dan     0 xr y  ,  sehingga
   
0 R y PG R  .  Perhatikan  juga  bahwa  karena  ini  berlaku  untuk  sebarang
0 y R   ,  maka   0 1 R d R   dan  untuk  sebarang 0 x R   ,  maka   1 d x  akibatnya   PG R adalah graf dengan ciri satu titik berderajat 1 R  dan titik lainnya
berderajat 1.
Sehingga diperoleh   1 R PG R S   .
Akibat 3.3 : Untuk n bilangan prima,   n PG Zn adalah graf bintang.
Bukti :
Diketahui bahwa n Z merupakan suatu ring dengan n adalah  bilangan prima.
Ambil sebarang , n x y  Zn dengan 0 x  dan 0 y  .
Untuk mod xy xy n  , n tidak  habis  membagi x dan n tidak  habis  membagi y sehingga n pun tidak habis membagi xy .
Akibatnya 0 xy  diperoleh n Z ring domain   1 n n PG S   Z .
3.4 Teorema
Misalkan S R adalah ring semiprima, maka pernyataan berikut ekuivalen.
a) S R adalah ring prima
b)   PG R adalah graf bintang
c)   PG R adalah graf pohon
(Satyanarayana, 2012)
Bukti :
) )
a b  : misalkan     e xy E PG R   . Berdasarkan definisi dari Graf   PG R pada 4.1, x y  . Selanjutnya jika 0 xRy  atau 0 yRx  maka 0 x  atau 0 y  . Karena R merupakan  ring  prima,  Akibatnya e adalah  sisi  yang  terbentuk  dari  salah  satu anggota  pada R dengan  titik  ujungnya  adalah 0 .  Hal ini menunjukan  bahwa  setiap sisi  yang  terbentuk  pada  graf   PG R hanya  bertetangga  dengan  titik 0 ,  sehingga terbukti  jika S R adalah ring prima maka   PG R adalah graf bintang.
) ) b c  :   PG R adalah graf bintang, sehingga setiap sisi yang terbentuk pada graf   PG R hanya  bertetangga  dengan  titik  u 0 ,  sehingga  terbukti,  jika   PG R adalah graf bintang maka   PG R merupakan graf pohon.
) ) c a  : (Dibuktikan dengan metode kontradisksi) Andaikan terdapat , , 0, 0 x y R x y    sehingga   0 xRy  ,  akibatnya
    xy E PG R  .  Selanjutnya, perhatikan sisi 0 R x , xy dan 0 R y , terdapat siklus pada Graf   PG R .
Hal ini kontradiksi dengan fakta bahwa   PG R merupakan graf pohon.
Sehingga terbukti, jika   PG R adalah graf pohon maka S R adalah ring prima.

## 3.5 Teorema
Misalkan n Z suatu  ring.  Jika 2 n p  untuk p bilangan  prima,  maka  terdapat  tepat   1 p  subgraf 3 C yang berbeda pada graf   n PG Z .
Bukti :
Misalkan n Z suatu ring dan 2 n p  dengan p adalah bilangan prima.
Perhatikan bahwa     
 2 0,1, 2,..., 2 1 P V PG p   Z ,sehingga :
a) 0 bertetangga dengan i untuk setiap   1, 2, 3,..., 2 1 i p   Karena   2 0 0 P i  Z
b) Pandang   2, 4, 6,..., 2 2 A p   Perhatikan bahwa untuk setiap x A  , maka :   2 2 | P p x p x y p y   Z Z   2 | p xy p y   Z     2 0 | 0 p y y    Z Sehingga diperoleh bahwa     2 P x p E PG  Z .
c) Selanjudnya  dibuktikan  bahwa    jika     2 P ab E PG  Z dengan 0 a  dan
0 b  maka  salah  satu  dari keduanya  adalah p dan  yang lainnya adalah  anggota dari A .
Bukti:
Diketahui bahwa     2 P ab E PG  Z , maka berdasarkan definisi :
    2 0 ,1 , 2 ,3 ,..., 2 1 p a b ab ab ab ab p ab   Z       0, , 2 , 3 ,..., 2 1 0 ab ab ab p ab
 

Artinya, dapat diperoleh bahwa 0 ab  atau   2 ; ab p k k   Z .
Oleh karena 2 p habis membagi ab , maka p habis membagi ab .
Sehingga  untuk p bilangan  prima,  maka p habis  membagi a atau p habis membagi b . Tanpa mengurangi keumuman, misalkan p habis membagi a .
Karena   1, 2, 3,..., 2 1 a p   , maka diperoleh a p  .
Sehingga  untuk 2 habis  membagi b ,  dapat  dikatakan  bahwa b adalah  bilangan
genap.  Oleh  karena   2, 4, 6,..., 2 2 A p   , 2 p b  Z ,  dan 0 b  ,  maka diperoleh b A  .
Setelah diperlihatkan a), b), dan c), perhatikan untuk setiap
 
2, 4, 6,..., 2 2, x A p   
Diperoleh :
 
          2 2 2 0 0 p p p x E PG x p E PG
p E PG
  
Z
Z
Z Sehingga dapat dilihat bahwa 0 0 x p    merupakan subgraf dari   2 p PG Z . Akibatnya terdapat tepat   1 p  subgraf 3 C yang berbeda pada   2 p PG Z .

## 3.6 Teorema
Misalkan n Z suatu  ring.  Jika . n p q  untuk p dan q bilangan  prima,  maka  terdapat tepat    1 1 p q   subgraf 3 C yang berbeda pada graf   n PG Z .
Bukti :
Misalkan n Z suatu ring dan n pq  dengan p dan q adalah bilangan prima.
Perhatikan bahwa         0,1, 2,3, 4,5, 6,..., 1 pq V PG pq   Z ,sehingga : a) 0 bertetangga dengan i untuk setiap     1, 2, 3,..., 1 i pq  
Karena   0 0 pq i  Z .
b) Pandang     , 2 , 3 ,..., 1 A p p p q p   dan     , 2 , 3 ,..., 1 B q q q p q  
Perhatikan bahwa untuk setiap x A  dan y B  sebarang, maka :
  0 pq x y  Z
Diketahui berdasarkan definisi  :
    0, , 2 ,..., 1 pq x y xy xy pq xy   Z Karena telah diketahui bahwa   0 pq x y  Z maka 0 x y  .
Sehingga diperoleh bahwa
    pq x y E PG  Z .
c) Selanjudnya  dibuktikan  bahwa    jika
    pq ab E PG  Z dengan 0 a  dan
0 b  maka salah satu dari a atau b adalah anggota A dan lainnya adalah anggota B .
Bukti:
Diketahui bahwa
    pq ab E PG  Z
Akibatnya
  0 pq a b  Z , sebab berdasarkan definisi:
      0 ,1 , 2 , 3 ,..., 1 pq a b ab ab ab ab pq ab   Z
        0, , 2 , 3 ,..., 1 0 ab ab ab pq ab  

Yang artinya, 0 ab  atau   ab pq s  dengan s  Z , sehingga pq habis membagi ab . Oleh karena 0 a  dan 0 b  maka pq tidak habis membagi a dan pq tidak habis  membagi b .  Selanjudnya  karena p dan q adalah  bilangan  prima,  maka dapat  diperoleh  bahwa p habis  membagi a dan q habis  membagi b atau p habis  membagi b dan q habis  membagi a ,  sehingga  tanpa  mengurangi keumuman  jika p habis  membagi a dan q habis  membagi b maka  diperoleh p a A   dan q b B   .
Setelah diperlihatkan a), b), dan c), perhatikan bahwa untuk setiap           0 | pq pq E PG x x V PG
  Z Z dan
      | , pq V PG
ab a A b B    Z terdapat    1 1 p q   segitiga berbeda, yaitu :
0 0 p q    , 0 2 0 p q    , 0 3 0 p q    , 0 4 0 p q    , . . . ,   0 1 0 p p q     , 0 2 0 p q    , 0 2 2 0 p q    , 0 2 3 0 p q    , . . . ,   0 2 1 0 p p q     0 3 0 p q    , 0 3 2 0 p q    , 0 3 3 0 p q    , . . . ,   0 3 1 0 p p q    
. . .
  0 1
0 q p q     ,   0 1 2 0 q p q     , . . . ,     0 1 1 0 q p p q      Akibatnya terdapat tepat    1 1 p q
  subgraph 3 C yang berbeda pada   pq PG Z .

## 4. SIMPULAN
Dari beberapa pembahasan diatas, dapat disimpulkan bahwa :
1. Graf prima pada ring merupakan graf yang terdiri atas pasangan terurut  (V,E) di  mana  himpunan  sisinya  adalah V R  dan  himpunan  titiknya  adalah
 
| 0 0, E xy xRy yRx x y      . Graf ini dinotasikan dengan   PG R .
2. Berikut merupakan karakteristik dari graf prima pada ring, yaitu :
a) Untuk R ring  prima, maka   PG R merupakan graf  bintang  atau  dapat  pula dikatakan untuk n bilangan prima,   n PG Zn graf bintang.
b) Misalkan   , ,. R  suatu ring dengan R   . Jika R adalah ring domain, maka   PG R adalah graf bintang 1, 1 1 R R K S    .
c) Misalkan S R adalah ring semiprima, maka S R juga merupakan ring prima di mana graf yang dibentuk adalah graf bintang yang juga merupakan graf pohon dan  jika   PG R adalah graf pohon maka S R adalah ring prima.
d) Misalkan n Z suatu ring. Jika 2 n p  untuk p bilangan prima, maka terdapat
tepat   1 p  subgraf 3 C yang berbeda pada graf
  n PG Z .
e) Misalkan n Z suatu  ring.  Jika . n p q  untuk , p q bilangan  prima,  maka terdapat tepat    1 1 p q   subgraf 3 C yang berbeda pada graf   n PG Z .

## DAFTAR PUSTAKA
[1]  G.  Chartrand  and  P.  Zhang,  A  First  Course  in  Graph  Theory.  Dover  Publications, 2012. [Online]. Available: https://books.google.co.id/books?id=ocIr0RHyI8oC
[2]  M.  S.  Dra.  Anggraini  and  M.  S.  Drs.  Gandung  Sugita,  Buku Ajar Struktur Aljabar.
Deepublish, 2020. [Online]. Available:
https://books.google.co.id/books?id=ZdEOEAAAQBAJ
[3]  E.  R.  Persulessy,  H.  M.  Abdullah,  and  D.  Nagaraju,  “Ring  Prima  dan  Ring Semiprima,” Jurnal Ilmu Matematika dan Terapan, pp. 1–4, 2013.
[4]  K. H. Rosen and K. Krithivasan, Discrete Mathematics and Its Applications. McGraw-
Hill,
2013.
[Online]. Available:
https://books.google.co.id/books?id=ZO8iMAEACAAJ
[5]  D. B. Satyanarayana, K. Prasad, and D. Nagaraju, “Prime Graph of a Ring,” Journal of Combinatories, Informations & Systems Sciences, vol. 35, pp. 27–42, Jan. 2010.