JMP : Vol. 9 No. 1, Juni 2017, hal. 37-44            ISSN 2085-1456
PEWARNAAN PADA GRAF BINTANG SIERPINSKI

## Siti Khabibah
Departemen Matematika, FSM Undip khabibah.undip@gmail.com
ABSTRACT. This paper discuss about Sierpinski star graph
, which its construction based  on  the  Sierpinski  triangle.  Vertex  set  of  Sierpinski  star  graph    is  a  set  of  all triangles in Sierpinski triangle; and the edge set of Sierpinski star  graph is a set  of  all sides  that  are  joint  edges  of    two  triangles  on  Sierpinski  triangle.  From  the  vertex  and edge  coloring  of  Sierpinski  star  graph,  it  is  found  that  the  chromatic  number  on  vertex coloring  of  graph is  1  for  n  =  1  and  2  for
; while  the  chromatic  number  on edge coloring of graf is 0 for n = 1 and
for
Keyword : Sierpinski star graph, Sierpinski triangle, edge, vertex, chromatic number
ABSTRAK. Pada  makalah  ini  dibahas  mengenai  graf  bintang  Sierpinski yang dikonstruksi berdasarkan segitiga Sierpinski. Himpunan titik dari graf bintang Sierpinski adalah himpunan semua segitiga pada segitiga Sierpinski; sedangkan himpunan sisi dari graf  bintang  Sierpinski  adalah  himpunan  semua  sisi  yang  merupakan  persekutuan  dua segitiga  pada  segitiga  Sierpinski.  Dari  pewarnaan  titik  dan  pewarnaan  sisi,  diperoleh bilangan kromatik untuk pewarnaan titik pada Graf
adalah 1 untuk dan 2 untuk ; sedangkan bilangan kromatik untuk pewarnaan sisi pada Graf adalah 0 untuk dan untuk
Kata kunci : Graf bintang Sierpinski, segitiga Sierpinski, titik, sisi, bilangan kromatik

## 1. PENDAHULUAN
Salah  satu  kajian  menarik  dalam  fraktal  adalah  pembahasan  mengenai segitiga  Sierpinski.  Segitiga  Sierpinski  merupakan    fraktal  yang  serupa  dengan dirinya  atau  disebut  dengan self  similar  fractal. Untuk  membangun  segitiga Sierpinski diperlukan sebuah segitiga sama sisi yang selanjutnya dibagi menjadi 4 buah  segitiga  yang  kongruen  dengan  skala  setengah  dari  segitiga  sebelumnya, selanjutnya  segitiga  yang  dihasilkan  secara  berulang  dibagi  lagi  menjadi  4  buah segitiga  dengan  skala  setengahnya  untuk  semua  segitiga  kecuali  untuk  segitiga yang tepat berada di tengah, yang dalam paper ini disebut segitiga pusat (triangle center ).  Pada  tahun  1997  Klavzar  dan  Milutinovic  memperkenalkan  graf Sierpinski yang  merupakan  generalisasi  dari  masalah  Tower  Hanoi (Klavzar  dan  Milutinovic,1997).  Sifat-sifat  graf  Sierpinski  dapat  dijumpai  dalam (Teguia  dan  Godbole,  2006).  Selain  graf  Sierpinski,  terdapat  graf Sierpinski
gasket yang  bentuknya  identik  dengan  segitiga  Sierpinski,  dengan  himpunan titik dan sisi dari graf adalah titik sudut dan sisi segitiga-segitiga dari segitiga Sierpinski.  Klavzar (2008) menulis mengenai pewarnaan pada graf Sierpinski dan Sierpinski  gasket ,  sedangkan  Jacovac  dan  Klavzar  (2009)  membahas  mengenai pewarnaan titik, sisi, dan pewarnaan total pada graf Sierpinski dan graf Sierpinski gasket . Selain graf Sierpinski yang berupa segitiga, ada juga graf Sierpinski yang berupa  bujursangkar.  Graf  ini  dikenal  dengan  nama  graf Square  Sierpinski . Pewarnaan pada graf Square Sierpinski dibahas dalam (Xue, Zuo dan Li, 2015).
Pada  makalah  ini,  akan  dibahas  mengenai  salah  satu  jenis  graf  yang dikonstruksi  berdasarkan  segitiga  Sierpinski,  yaitu  graf  bintang  Sierpinski.  Graf ini  dinotasikan  dengan , dan  dibatasi  hanya  untuk n berhingga.  Bagian pertama  makalah  membahas  mengenai  konstruksi  graf beserta  penghitungan banyaknya  titik  dan  sisi.  Selanjutnya,  pewarnaan  titik  dan  sisi  pada  graf  ini dibahas  pada  bagian  kedua.  Dari  pewarnaan  titik  dan  sisi  tersebut  diperoleh bilangan kromatik untuk pewarnaan titik dan sisi pada graf .

## 2. GRAF BINTANG SIERPINSKI ( Sierpinski Star Graph )
Secara  geometris  graf  bintang  Sierpinski dengan merupakan graf  yang  dikonstruksi  dari  segitiga  Sierpinski.  Himpunan  titik  dari  graf  bintang Sierpinski merupakan himpunan semua segitiga dari segitiga Sierpinski hasil iterasi  ke- n, dan  titik  yang  mewakili  segitiga  pusat  disebut  titik  pusat  ( center vertex );  sementara  itu,  himpunan  sisinya  merupakan  himpunan  semua  sisi  yang merupakan  persekutuan  dari  dua  segitiga  dalam  segitiga  Sierpinski.  Banyaknya titik  dan sisi  dari  graf dinotasikan  dengan | | dan | | Banyaknya  titik  dan sisi  dari  graf disajikan  pada  Proposisi  1.  Untuk  memberikan  ilustrasi,  pada gambar  berikut  disajikan  segitiga  Sierpinski  hasil  iterasi  ke-4  dan  graf  Bintang Sierpinski iterasi ketiga ( ).
Gambar 1a. Segitiga Sierpinski iterasi ke-4 Gambar 1b. Graf
Proposisi 1 . Graf bintang Sierpinski mempunyai titik untuk dan ∑ sisi untuk
.
Bukti. Karena  Graf dikonstruksi  dari  segitiga  Sierpinski  dengan  banyaknya titik  pada diperoleh  dari  jumlah  segitiga  pada
,  maka  untuk
banyaknya titik pada adalah 1 karena hanya terdapat satu segitiga pada segitiga sierpinski  untuk  iterasi  pertama.  Untuk  iterasi  selanjutnya  banyaknya  titik  pada graf diperoleh dari persamaan
| |    | | untuk .
Karena | | , maka
| |   ∑
Oleh  karena  itu | | yang  berarti  banyaknya  titik  Graf  Bintang
Sierpinski hasil iterasi ke- n adalah adalah sebanyak
Selanjutnya,  banyaknya  sisi  pada  graf  bintang  Sierpinski berpadanan banyaknya  sisi  pada  segitiga  Sierpinski  yang  merupakan  persekutuan  dari  dua segitiga  pada  segitiga  Sierpinski  (yang  selanjutnya  disebut  sisi  persekutuan).
Karena hanya ada satu segitiga untuk maka tidak terdapat sisi persekutuan
sehingga  banyaknya  sisi  pada adalah  nol.  Untuk
ada  empat  segitiga
kongruen  dan  segitiga  pusat      menyinggung  ketiga  sisi  segitiga  yang  lain.  Jadi, terdapat  3  sisi  persekutuan  yang  berarti  jumlah  sisi  pada adalah  3.  Untuk selanjutnya, banyaknya sisi persekutuan pada segitiga Sierpinski hasil iterasi ke – adalah  3  kali  banyaknya  sisi  persekutuan  pada  iterasi  ke- n ditambah dengan banyaknya sisi persekutuan dari segitiga pusat, yang berjumlah 2 kali lipat dari  iterasi  sebelumnya.  Oleh  karena  itu,  banyaknya  sisi  pada diperoleh  dari persamaan
| |     | | untuk .
Karena | | , maka
| |     | |
| | | | | | | |   ∑
Jadi, | |   ∑ yang berarti banyaknya titik graf Bintang Sierpinski hasil iterasi ke- n adalah adalah sebanyak ∑ untuk

## 3. PEWARNAAN PADA GRAF BINTANG SIERPINSKI
Pada  paper ini pembahasan mengenai  pewarnaan  pada Graf meliputi pewarnaan  titik  dan  sisi.    Untuk  pewarnaan  titik  menggunakan  algoritma  Welch and Powell yang mendahulukan titik dengan derajat  terbesar. Selanjutnya derajat maksimum  titik  dari  suatu  graf G dinotasikan  dengan Dua  teorema  yang terkait  dengan  pewarnaan  titik  pada  graf  secara  umum  diberikan  pada  teorema berikut:
Teorema 1. ( Deo, N., 1994) Suatu graf G tidak memiliki sikel yang panjangnya ganjil jika hanya jika G dapat diwarnai dengan dua warna .
Teorema 2.  ( Deo, N., 1994) Bilangan kromatik dari graf G tidak dapat lebih satu dari derajat maksimum titik-titik di G.
Dalam  paper  ini  bilangan  kromatik  untuk  pewarnaan  titik  dan  sisi  pada dinotasikan dengan dan . Pertama-tama akan dikaji mengenai pewarnaan titik pada . Untuk hanya terdapat satu  warna karena banyaknya titik adalah 1 atau dengan kata lain . Selanjutnya dapat dibuktikan  bahwa bilangan kromatik untuk pewarnaan titik graf adalah 2 untuk . Teorema 3. Untuk , bilangan kromatik untuk pewarnaan titik graf bintang Sierpinski adalah . Bukti. Untuk graf
identik  dengan  graf  bintang    dengan  banyaknya titik  adalah  4  dan  terdapat  satu  titik  berderajat  3  serta  3  titik  berderajat  1.  Oleh karena  itu  jumlah  warna  minimum  yang  bisa  diterapkan  adalah  2.  Sedangkan untuk , graf tidak memiliki sikel dengan panjang ganjil, menggunakan Teorema  1  maka  diperoleh  graf dapat  diwarnai  dengan  dua  warna.  Jadi terbukti bahwa untuk
Sebelum  dibahas  mengenai  pewarnaan  sisi  pada  graf terlebih  dahulu diberikan sebuah teorema terkait dengan pewarnaan sisi  dikenal  sebagai  teorema Vizing sebagai berikut
Teorema 4. Untuk setiap graf G , berlaku
Teorema  Vizing  tersebut  digunakan  dalam  pembuktian  teorema  mengenai pewarnaan sisi  pada  graf Untuk
graf hanya terdiri atas satu titik dan tidak mempunyai  sisi. Jadi,  bilangan kromatik  pada pewarnaan sisi  graf adalah  nol Akan  ditunjukkan  bahwa  untuk bilangan kromatik  untuk  pewarnaan  sisi  graf adalah ,  yang  merupakan  derajat maksimum titik graf
.
Teorema  5. Untuk  setiap , bilangan  kromatik  untuk  pewarnaan  sisi  graf bintang Sierpinski adalah
Bukti. Untuk graf
identik  dengan  graf  bintang    dengan  4  titik  dan derajat  maksimum  titiknya  adalah  3.  Jadi,  jumlah  warna  minimal  yang  dapat diaplikasikan  adalah  sebanyak  3.  Selanjutnya  untuk ,  titik  pusat  dari merupakan  satu-satunya  titik  dengan  derajat  terbesar  yaitu  6  yang  berarti  derajat maksimum titik dari adalah 6. Karena tidak ada titik lain yang berderajat 6, maka Pada  graf derajat  maksimum  titik    menunjukkan  jumlah sisi pada titik pusat graf yaitu sejumlah dengan titik pusat merupakan
satu-satunya  titik  yang  mempunyai  derajat  maksimum.  Dengan  demikian, banyaknya  warna  minimal  yang  diaplikasikan  pada  graf adalah  sebanyak Jadi terbukti bahwa .
Ilustrasi  mengenai  hasil  pewarnaan  titik  dan  sisi  pada  graf disajikan pada gambar berikut.
Gambar 2a. Pewarnaan titik graf Gambar 2b. Pewarnaan sisi graf

## 4. KESIMPULAN
Graf  bintang  Sierpinski  merupakan  graf  yang  serupa  dengan  dirinya  atau self  similar .  Banyaknya  titik  dan  sisi  dari  graf  ini  bisa  diperoleh  menggunakan fungsi  rekursif.  Untuk  bilangan  kromatik  pada  pewarnaan  titik  diperoleh  nilai yang sama, yaitu 2, kecuali pada graf . Sementara itu, bilangan kromatik pada pewarnaan sisi sama dengan derajat maksimum titik.

## DAFTAR PUSTAKA
Deo, N., Graph Theory with Application to Engineering and a Computer Science .
Prentice-Hall International, Inc., New Delhi, 1994.
Jakovac,  M.  dan  Klavžar,  S .,  Vertex-,  Edge-,  and  Total-Coloring  of  Sierpiński- like Graphs, Discrete Math., 309 (2009), 1548–1556.
Klavzar,  S., Coloring  Sierpinski  Graphs  and  Sierpinski  Gasket  Graphs , Taiwanese Journal of Mathematics, 12 (2) (2008), 513-522.
Klavžar, S., Milutinović, U., Graphs S(n,k) and a Variant of the Tower of Hanoi Problem , Czechoslovak Math. J., 47 (122) (1997), 95–104.
Teguia,  A.M.  dan  Godbole,  A.P., Sierpinski  Gasket  Graphs  and  Some  of  Their Properties , Australas. J. Combin., 35 (2006), 181-192.
Xue,  B.,  Zuo,  L.  dan  Li,  G., Coloring  the  Square  of  Sierpinski  Graphs ,  Graphs and Combinatorics, 31 (5) (2015), 1795-1805.
44                                                                                                                  Siti Khabibah