BILANGAN KROMATIK GRAF COMMUTING DAN NONCOMMUTING

## GRUP DIHEDRAL
1 Handrini Rahayuningtyas, 2 Abdussakir, 3 Achmad Nashichuddin
1 Jurusan Matematika, Universitas Islam Negeri Maulana Malik Ibrahim Malang
2 jurusan Matematika, Universitas Islam Negeri Maulana Malik Ibrahim Malang 3 jurusan Matematika, Universitas Islam Negeri Maulana Malik Ibrahim Malang
Email: handrienie05@gmail.com

## ABSTRAK
Graf commuting adalah graf yang memiliki himpunan titik X dan dua titik berbeda akan terhubung langsung  jika  saling  komutatif  di 𝐺 .  Misal 𝐺 grup  non  abelian  dan 𝑍(𝐺) adalah  center  dari 𝐺 .  Graf noncommuting adalah suatu graf yang mana titik-titiknya merupakan himpunan dari 𝐺\𝑍(𝐺) dan dua titik x dan y terhubung langsung jika dan hanya jika 𝑥𝑦 ≠ 𝑦𝑥 . Pewarnaan titik pada graf 𝐺 adalah pemberian sebanyak k warna pada titik sehingga dua titik yang terhubung langsung tidak diberi warna yang sama. Pewarnaan sisi pada graf 𝐺 adalah dua sisi yang berasal dari titik yang sama diberi warna yang berbeda. Bilangan  terkecil k sehingga  suatu  graf  dapat  diberi k warna  pada  titik  dan  sisi  inilah  yang  dinamakan bilangan kromatik. Pada artikel ini didapatkan rumus umum bilangan kromatik dari graf commuting dan noncommuting yang dibangun dari suatu grup yaitu grup dihedral.
Kata  kunci :  bilangan  kromatik,  pewarnaan  titik,  pewarnaan  sisi,  graf  commuting  dan  noncommuting, grup dihedral.

## ABSTRACT
Commuting graph is a graph that has a set of points  X and two different vertices to be connected directly if each commutative in 𝐺 . Let 𝐺 non abelian group and 𝑍(𝐺) is a center of 𝐺 . Noncommuting graph is a graph which the the vertex is a set of 𝐺\𝑍(𝐺) and two vertices x and y are adjacent if and only if 𝑥𝑦 ≠ 𝑦𝑥 . The vertex colouring of 𝐺 is giving k colour at the vertex, two vertices that are adjacent not given the same colour. Edge colouring of G is two edges that have common vertex are coloured with different colour. The  smallest  number  k  so  that  a  graph  can  be  coloured  by  assigning 𝑘 colours  to  the  vertex  and  edge called  chromatic  number.  In  this  article,  it  is  available  the  general  formula  of  chromatic  number  of commuting and noncommuting graph of dihedral group.
Keywords :  chromatic  number,  vertex  colouring,  edge  colouring,  commuting  and  noncommuting  graph, dihedral group.

## PENDAHULUAN
Graf G adalah  pasangan (𝑉(𝐺), 𝐸(𝐺)) dengan 𝑉(𝐺) adalah  himpunan  tidak  kosong  dan berhingga dari objek-objek yang disebut titik, dan 𝐸(𝐺) adalah  himpunan  (mungkin  kosong) pasangan  tak  berurutan  dari  titik-titik  berbeda  di 𝑉(𝐺) yang  disebut sisi .  Banyaknya  unsur  di 𝑉(𝐺) disebut  order  dari G dan  dilambangkan  dengan 𝑝(𝐺), dan  banyaknya  unsur  di 𝐸(𝐺) disebut ukuran dari G dan dilambangkan dengan 𝑞(𝐺). Jika graf  yang  dibicarakan  hanya  graf 𝐺 ,  maka  order dan ukuran dari 𝐺 masing-masing cukup ditulis 𝑝 dan 𝑞. Graf  dengan  order 𝑝 dan  ukuran 𝑞 dapat disebut graf (𝑝, 𝑞) [1]. Sisi e =  ( u,v )  dikatakan  menghubungkan titik u dan v .  Jika e =  ( u,v )  adalah  sisi  di  graf G , maka u dan v disebut  terhubung  langsung (adjacent) , v dan e serta u dan e disebut  terkait langsung (incident) , dan titik u dan v disebut ujung dari e .  Dua  sisi  berbeda e 1 dan e 2 disebut
terhubung  langsung  ( adjacent ),  jika  terkait langsung  pada  satu  titik  yang  sama.  Untuk selanjutnya, sisi e = ( u, v ) akan ditulis e = uv [2]. Perkembangan  terbaru  teori  graf  yaitu membahas  graf  yang  dibangun  oleh  suatu  grup. Misal 𝐺 grup  berhingga  dan 𝑋 adalah  subset  dari 𝐺 .  Graf commuting 𝐶(𝐺, 𝑋) adalah  graf  yang memiliki  himpunan  titik 𝑋 dan  dua  titik  berbeda akan  terhubung  langsung  jika  saling  komutatif  di 𝐺 .  Jadi,  titik x dan y akan  terhubung  langsung  di 𝐶(𝐺, 𝑋) jika dan hanya jika 𝑥𝑦  =  𝑦𝑥 di 𝐺 (Vahidi & Talebi, 2010:123). Sebaliknya, Misal 𝐺 grup non abelian  dan 𝑍(𝐺) adalah  center  dari 𝐺 .  Graf noncommuting Γ 𝐺 adalah  suatu  graf  yang  mana titik-titiknya  merupakan  himpunan  dari 𝐺\𝑍(𝐺) dan dua titik 𝑥 dan 𝑦 terhubung langsung jika dan hanya jika 𝑥𝑦 ≠ 𝑦𝑥 [3]. Perkembangan berikutnya muncul bilangan kromatik  pewarnaan  titik  dan  pewarnaan  sisi pada  graf.  Pewarnaan  titik  pada  graf 𝐺 adalah pemberian  sebanyak 𝑛 warna  pada  titik  sehingga
dua  titik  yang  saling  terhubung  langsung  tidak diberi warna yang sama. Pewarnaan sisi pada graf 𝐺 adalah  pemberian  sebanyak 𝑛 warna  pada  sisi sehingga  dua  sisi  yang  saling  terkait  langsung tidak diberi warna yang sama. Bilangan 𝑛 terkecil sehingga  graf 𝐺 dapat  diwarnai  dengan  cara tersebut  dinamakan  bilangan  kromatik.  Bilangan kromatik titik ditulis 𝜒(𝐺) dan  bilangan kromatik sisi ditulis 𝜒′(𝐺) [1].

## KAJIAN TEORI
1. Graf 𝑮
Graf G adalah pasangan ( V ( G ) , E ( G )) dengan V ( G ) adalah himpunan tidak kosong dan berhingga dari  objek-objek  yang  disebut  titik,  dan E ( G ) adalah  himpunan  (mungkin  kosong)  pasangan takberurutan  dari  titik-titik  berbeda  di V ( G ) yang disebut sisi [1].
Sehingga  jika 𝐺 = (𝑉(𝐺), 𝐸(𝐺)) ,  maka 𝑉(𝐺) = {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 } dan 𝐸(𝐺) = {𝑒 1 , 𝑒 2 , … , 𝑒 𝑛 } , dimana 𝑣 𝑖 ∈ 𝑉(𝐺), 𝑖 = 1,2, … , 𝑛 disebut  titik (vertex) dan 𝑒 𝑗 = 1,2, … , 𝑚 disebut sisi (edge) .

## 2. Derajat Titik
Jika v adalah  titik  pada  graf 𝐺 ,  maka himpunan  semua  titik  di 𝐺 yang  terhubung langsung dengan 𝑣 disebut lingkungan dari v dan ditulis 𝑁𝐺(𝑣) . Derajat dari titik 𝒗 di graf 𝐺 , ditulis deg 𝐺 (𝑣) ,  adalah  banyaknya  sisi  di 𝐺 yang  terkait langsung dengan v .  Derajat total G adalah jumlah derajat  semua  titik  dalam  G.  Dalam  konteks pembicaraan  hanya  terdapat  satu  graf G ,  maka tulisan deg 𝐺 (𝑣) disingkat  menjadi deg ( v )  dan N G ( v )  disingkat  menjadi N ( v ).  Jika  dikaitkan dengan konsep lingkungan, derajat titik v di graf G adalah banyaknya anggota dalam N ( v ) [2].
Gambar 1. Graf 𝑮 dengan Himpunan
Titik 𝑽(𝑮) Berdasarkan gambar, diperoleh bahwa: 𝑁(𝑎) = {𝑏, 𝑐, 𝑑} 𝑁(𝑏) = {𝑎, 𝑐} 𝑁(𝑐) = {𝑎, 𝑏, 𝑑} 𝑁(𝑑) = {𝑎, 𝑐}.
Dengan demikian, maka deg(𝑎) = 3
deg(𝑏) = 2 deg(𝑐) = 3 deg(𝑑) = 2

## 3. Graf Terhubung
Suatu  graf G dikatakan  terhubung  jika untuk setiap titik u dan v di G terdapat lintasan u-v di G .  Sebaliknya,  jika  ada  dua  titik u dan v di G , tetapi  tidak  ada  lintasan u-v di G ,  maka G dikatakan tak terhubung ( disconnected ) [2].

## 4. Bilangan Kromatik
Pewarnaan  titik  pada  graf  G  adalah pemberian  sebanyak  n  warna  pada  titik  sehingga dua  titik  yang  saling  terhubung  langsung  tidak diberi warna yang sama. Pewarnaan sisi pada graf G  adalah  pemberian  sebanyak  n  warna  pada  sisi sehingga  dua  sisi  yang  saling  terkait  langsung tidak diberi warna yang sama. Bilangan n terkecil sehingga  graf  G  dapat  diwarnai  dengan  cara tersebut  dinamakan  bilangan  kromatik.  Bilangan kromatik titik ditulis 𝜒(𝐺) dan  bilangan kromatik sisi ditulis 𝜒′(𝐺) [1].

## 5. Grup Dihedral
Grup  adalah  suatu  struktur  aljabar  yang dinyatakan  sebagai (𝐺,∗) dengan 𝐺 adalah himpunan tak kosong  dan ∗ adalah operasi biner di 𝐺 yang memenuhi sifat-sifat berikut:
1. (𝑎 ∗ 𝑏) ∗= 𝑎 ∗ (𝑏 ∗ 𝑐) , untuk semua 𝑎, 𝑏, 𝑐 ∈ 𝐺 (yaitu assosiatif ).
2. Ada suatu elemen 𝑒 di 𝐺 sehingga 𝑎 ∗ 𝑒 = 𝑒 ∗ 𝑎 = 𝑎 , untuk semua 𝑎 ∈ 𝐺 ( 𝑒 disebut identitas di 𝐺 ).
3. Untuk setiap 𝑎 ∈ 𝐺 ada suatu element 𝑎 −1 di 𝐺 sehingga 𝑎 ∗ 𝑎 −1 = 𝑎 −1 ∗ 𝑎 = 𝑒 ( 𝑎 −1 disebut invers dari 𝑎 ) Adapun  grup (𝐺,∗) disebut abelian (grup komutatif) jika 𝑎 ∗ 𝑏 = 𝑏 ∗ 𝑎 untuk semua 𝑎, 𝑏 ∈ 𝐺 [4]. Grup  dihedral  adalah  grup  dari  himpunan simetri-simetri
dari segi- n beraturan,
dinotasikan 𝐷 2𝑛 ,  untuk  setiap 𝑛 bilangan  bulat positif  dan 𝑛 ≥ 3 .  Dalam  buku  lain  ada  yang menuliskan grup dihedral dengan 𝐷 𝑛 [5].
Adapun  himpunan  anggota  grup  dihedral 𝐷 2𝑛 yaitu 𝐷 2𝑛 = {1, 𝑟, 𝑟 2 , … , 𝑠, 𝑠𝑟, 𝑠𝑟 2 , … , 𝑠𝑟 𝑛−1 } .
6. Graf Commuting dan Noncommuting
Misal 𝐺 adalah grup berhingga dan 𝑋 adalah subset dari 𝐺 , graf commuting 𝐶(𝐺, 𝑋) adalah graf dengan 𝑋 sebagai himpunan titik dan dua elemen berbeda  di 𝐶(𝐺, 𝑋) terhubung  langsung  jika
keduanya  adalah elemen yang  saling komutatif di 𝐺 [6].
Misal 𝐺 grup  non  abelian  dan 𝑍(𝐺) adalah center dari 𝐺 . Graf non commuting Γ 𝐺 adalah suatu graf  yang  mana  titik-titiknya  merupakan himpunan  dari 𝐺\𝑍(𝐺) dan  dua  titik 𝑥 dan 𝑦 terhubung  langsung  jika  dan  hanya  jika 𝑥𝑦 ≠ 𝑦𝑥 [3].

## PEMBAHASAN
Pewarnaan  titik  pada  graf  G  adalah pemberian  sebanyak  n  warna  pada  titik  sehingga dua  titik  yang  saling  terhubung  langsung  tidak diberi warna yang sama. Pewarnaan sisi pada graf G  adalah  pemberian  sebanyak  n  warna  pada  sisi sehingga  dua  sisi  yang  saling  terkait  langsung tidak  diberi  warna  yang  sama.  Dari  pewarnaan titik  dan  sisi  inilah  dapat  diketahui  bilangan kromatiknya,  baik  graf commuting maupun  graf noncommuting.
Bilangan Kromatik Pewarnaan Titik dan Sisi Graf Commuting Grup Dihedral
Perhatikan tabel di bawah ini:
Tabel 1. Bilangan Kromatik Pewarnaan Titik dan Sisi Graf Commuting Grup Dihedral 𝐶(𝐷 2𝑛 ) 𝜒(𝐶(𝐷 2𝑛 )) 𝜒 ′ (𝐶(𝐷 2𝑛 )) 𝐷 6 3 5
𝐷 8
4 7
𝐷 10 . . . 5 . .
.
9 . . . 𝐷 2𝑛 𝑛 2𝑛 − 1
Sumber: penulis Berdasarkan  Tabel  1,  didapatkan  teorema berikut:
Teorema 1
Misal 𝐶(𝐷 2𝑛 ) adalah  graf commuting dari grup  dihedral-2n (𝐷 2𝑛 ) .  Maka  bilangan  kromatik pewarnaan  titik  graf commuting dari  grup dihedral-2n (𝐷 2𝑛 ) adalah 𝜒(𝐶(𝐷 2𝑛 )) = 𝑛 .
Bukti: Untuk 𝑛 ganjil  dan  genap,  misal  diketahui 𝑣 = {1, 𝑟, 𝑟 2 , … , 𝑟 𝑛−1 } di 𝐷 2𝑛 ,  untuk 𝑖 ≠ 𝑗 .  Kemudian 𝑟 𝑖 ∘ 𝑟 𝑗 = 𝑟 𝑗 ∘ 𝑟 𝑖 untuk 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 di 𝐷 2𝑛 ,
maka 𝑟 𝑖 dan 𝑟 𝑗 saling  terhubung  langsung  di 𝐶(𝐷 2𝑛 ) .  Karena 𝑟 𝑖 dan 𝑟 𝑗 saling  komutatif,  maka terdapat (𝑟 𝑖 , 𝑟 𝑗 ) ∈ 𝐶(𝐷 2𝑛 ) yang  membentuk subgraf komplit- 𝑛 . Sehingga dibutuhkan sebanyak 𝑛 warna, atau dengan kata lain bilangan kromatik pewarnaan titik 𝑟 𝑖 dan 𝑟 𝑗 yaitu 𝑛 . Misal 𝑤 = {𝑠, 𝑠𝑟, 𝑠𝑟 1 , … , 𝑠𝑟 𝑛−1 } dimana 𝑤 hanya komutatif  dengan 1 di 𝐷 2𝑛 .  Artinya 𝑠𝑟 𝑖 dan 𝑠𝑟 𝑗 , 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 tidak  saling  komutatif. Karena  tidak  saling  komutatif,  maka  dapat  diberi warna yang sama. Pada 𝑛 ganjil, 𝑠𝑟 𝑖 tidak  komutatif  dengan 𝑟 𝑗 , 𝑗 = 1,2, … , 𝑛 − 1 . 𝑠𝑟 ∘ 𝑟 = 𝑠𝑟 1+1 = 𝑠𝑟 2 𝑟 ∘ 𝑠𝑟 = 𝑠𝑟 1−1 = 𝑠
Karena 𝑠𝑟 𝑖 tidak  komutatif  dengan 𝑟 𝑗 , 𝑗 = 1,2, … , 𝑛 − 1 ,  maka  warna  titik 𝑠𝑟 𝑖 berlaku  sama dengan titik 𝑟 𝑗 , 𝑗 = 1,2, … , 𝑛 − 1 . Pada 𝑛 genap,  terdapat 𝑠𝑟 𝑛 2 ∘ 𝑟 𝑛 2 = 𝑟 𝑛 2 ∘ 𝑠𝑟 𝑛 2 , sehingga warna titik 𝑠𝑟 𝑛 2 tidak boleh sama dengan 𝑟 𝑛 2 . Selain itu, terdapat 𝑠𝑟 𝑛 2 ∘ 𝑟 𝑖 = 𝑟 𝑖 ∘ 𝑠𝑟 𝑛 2 , sehingga warna titik 𝑠𝑟 𝑛 2 boleh sama dengan warna titik 𝑟 𝑖 , atau dengan kata lain 𝑠𝑟 𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1 dapat diberi  warna  yaitu  memilih  dari 𝑛 2 warna.  Jadi, diperoleh 𝜒(𝐶(𝐷 2𝑛 )) = 𝑛 ,  untuk 𝑛 ganjil  maupun genap.

## Teorema 2
Misal 𝐶(𝐷 2𝑛 ) adalah  graf commuting dari  grup dihedral-2n (𝐷 2𝑛 ) .  Maka  bilangan  kromatik pewarnaan sisi graf commuting dari grup dihedral- 2n (𝐷 2𝑛 ) adalah 𝜒′(𝐶(𝐷 2𝑛 )) = 2𝑛 − 1
Bukti: Untuk 𝑛 ganjil,  diketahui  bahwa 𝑟 𝑖 ∘ 𝑟 𝑗 = 𝑟 𝑗 ∘ 𝑟 𝑖 , untuk 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 di 𝐷 2𝑛 , untuk 𝑖 ≠ 𝑗 . Jadi, 𝑟 𝑖 dan 𝑟 𝑗 saling  terhubung  langsung  di 𝐺 .  Di samping itu, 1 komutatif dengan semua elemen 𝑟 𝑖 dan 𝑠𝑟 𝑖 ,  sehingga  1  terhubung  langsung  dengan semua  elemen 𝑟 𝑖 dan 𝑠𝑟 𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1 di 𝐺 . Karena  1  terhubung  langsung  dengan 2𝑛 − 1 elemen di 𝐺 , maka minimal warna yang digunakan pewarnaan  sisinya  yaitu  sebanyak 2𝑛 − 1 warna. Berdasarkan  aturan  pewarnaannya,  setiap  sisi yang  terkait  dengan  1  titik  yang  sama  diberi warna  yang  berbeda.  Adapun 𝑟 𝑖 dan 𝑟 𝑗 , 𝑖 = 0,1,2, … ,2𝑛 − 1 yang  saling  terhubung  langsung dapat  diberi  warna  dari 2𝑛 − 1 warna  yang  telah digunakan  sebelumnya.  Sehingga  didapatkan bilangan  kromatik  sisinya  yaitu 𝜒′(𝐶(𝐷 2𝑛 )) = 2𝑛 − 1 , untuk 𝑛 ganjil. Untuk 𝑛 genap,  diketahui  bahwa    Untuk 𝑛 ganjil, diketahui  bahwa 𝑟 𝑖 ∘ 𝑟 𝑗 = 𝑟 𝑗 ∘ 𝑟 𝑖 ,  untuk 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 di 𝐷 2𝑛 ,  untuk 𝑖 ≠ 𝑗 .  Jadi, 𝑟 𝑖 dan 𝑟 𝑗 saling  terhubung  langsung  di 𝐺 .  Walaupun 𝑟 𝑛 2
komutatif  dengan 𝑠𝑟 𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1 ,  tetapi 𝑠𝑟 𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1 tidak  komutatif  dengan 𝑟 𝑗 untuk 𝑗 selain 𝑛 2 . Elemen 1 komutatif dengan 𝑟 𝑖 dan 𝑠𝑟 𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1 yaitu  sebanyak 2𝑛 − 1 elemen. Karena 1 komutatif dengan semua elemen 𝑟 𝑖 dan 𝑠𝑟 𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1 yaitu sebanyak 2𝑛 − 1 elemen, maka  1  memiliki  derajat  tertinggi  di 𝐺 . Artinya,  minimal  warna  yang  dibutuhkan  adalah sebesar derajat tertinggi di 𝐺 yaitu 1. 1 terhubung langsung  dengan 2𝑛 − 1 elemen,  maka  minimal warna yang digunakan dalam pewarnaan sisi di 𝐺 sebanyak 2𝑛 − 1 warna.  Jadi,  diperoleh  bilangan kromatik sisinya yaitu 𝜒′(𝐶(𝐷 2𝑛 )) = 2𝑛 − 1 , untuk 𝑛 genap.
Bilangan Kromatik Pewarnaan Titik dan Sisi Graf Noncommuting Grup Dihedral
Perhatikan tabel berikut:
Tabel 2 . Bilangan Kromatik Graf Noncommuting Graf Noncommuting Grup Dihedral
Γ(𝐷 2𝑛 ) 𝜒(Γ(𝐷 2𝑛 )) 𝜒 ′ (Γ(𝐷 2𝑛 ))
Γ(𝐷 6 ) 4 5 Γ(𝐷 8 ) 3 5 Γ(𝐷 10 ) 6 9 Γ(𝐷 12 ) 4 9 Γ(𝐷 14 ) 8 13 Γ(𝐷 16 ) . . . 5 . .
.
13 . . .
Γ(𝐷 2𝑛 ) 𝑛 + 1, 𝑛 ganjil 𝑛 2 + 1, 𝑛 genap
2𝑛 − 1 , n ganjil
2𝑛 − 3 , n genap
Sumber: penulis Berdasarkan  Tabel  2,  diperoleh  teorema  sebagai berikut:
Teorema 3
Misal Γ(𝐷 2𝑛 ) adalah graf noncommuting dari grup dihedral-2n (𝐷 2𝑛 ) ,  maka  bilangan  kromatik  dari pewarnaan  titik  graf noncommuting pada  grup dihedral-2n (𝐷 2𝑛 ) adalah 𝜒(Γ(𝐷 2𝑛 )) = 𝑛 + 1 untuk 𝑛 ganjil  dan 𝜒(Γ(𝐷 2𝑛 )) = 𝑛
2 + 1 untuk 𝑛 genap.
Bukti: Untuk 𝑛 ganjil,  diperoleh  himpunan 𝑆 = {𝑟, 𝑠, 𝑠𝑟, … , 𝑠𝑟 𝑛−1 } saling  tidak  komutatif  di 𝐷 2𝑛 , untuk 𝑖 ≠ 𝑗 .  Dapat  dikatakan  bahwa 𝑟 𝑖 dan 𝑠𝑟 𝑗 , untuk 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 saling  terhubung
langsung. Dengan demikian, 𝑆 = {𝑟, 𝑠, 𝑠𝑟, … , 𝑠𝑟 𝑛−1 } akan  membentuk  subgraf  komplit  terbesar  di 𝐺 . Karena 𝑆 = {𝑟, 𝑠, 𝑠𝑟, … , 𝑠𝑟 𝑛−1 } membentuk subgraf terbesar  di 𝐺 ,  maka  bilangan  clique  atau  order subgraf komplit terbesar graf 𝐺 adalah 𝑛 + 1 , yaitu kardinalitas  himpunan 𝑆 .  Karena  order  dari subgraf  komplit  terbesarnya  adalah 𝑛 + 1 ,  maka pewarnaan  titik  pada  graf 𝐺 membutuhkan minimal  warna  sebanyak 𝑛 + 1 warna.  Dengan demikian didapatkan bilangan kromatik titik pada graf noncommuting grup dihedral yaitu 𝜒(Γ(𝐷 2𝑛 )) = 𝑛 + 1 , untuk 𝑛 ganjil.
Untuk 𝑛 genap,  diketahui  bahwa 𝑍(𝐺) = {1, 𝑟 𝑛 2 } . Karena 𝑟 𝑖 dan 𝑠𝑟 𝑗 , untuk 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 tidak saling  komutatif,  maka 𝑟 𝑖 dan 𝑠𝑟 𝑗 ,  untuk 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 terhubung langsung di 𝐺 , untuk 𝑖 ≠ 𝑗 .  Karena 𝑠𝑟 𝑖 , 𝑖 = 0,1,2, … , 𝑛 2 saling  komutatif dengan 𝑠𝑟 𝑗 , 𝑗 = 𝑛 2 , 𝑛 2 + 1, 𝑛 2 + 2, … , 𝑛 − 1 ,  maka 𝑠𝑟 𝑖 tidak  terhubung  langsung  dengan 𝑠𝑟 𝑗 .  Namun demikian, 𝑠𝑟 𝑖 , 𝑖 = 0,1,2, … , 𝑛 2 tidak  komutatif  satu sama lain. Maka 𝑠𝑟 𝑖 , 𝑖 = 0,1,2, … , 𝑛 2 akan membentuk  subgraf  komplit.  Karena 𝑠𝑟 𝑖 , 𝑖 = 0,1,2, … , 𝑛 2 terhubung  langsung  dengan 𝑟 ,  maka diperoleh  subgraf  komplit  terbesar  yang  memuat 𝑛 2 + 1 titik.  Dengan  kata  lain,  bilangan  clique  atau order  subgraf  komplit  terbesar  graf 𝐺 adalah 𝑛 2 + 1 .  Karena  order  dari  subgraf  komplit  terbesar 𝐺 adalah 𝑛 2 + 1 ,  maka  pewarnaan  titik  pada  graf 𝐺 membutuhkan  minimal  warna  sebanyak 𝑛 2 + 1 warna.  Dengan  demikian,  dapat  disimpulkan bahwa bilangan kromatik titik graf noncommuting grup  dihedral  yaitu 𝜒(Γ(𝐷 2𝑛 )) = 𝑛 2 + 1 ,  untuk 𝑛 genap.

## Teorema 4
Misal Γ(𝐷 2𝑛 ) adalah graf noncommuting dari grup dihedral-2n (𝐷 2𝑛 ) ,  maka  bilangan  kromatik  dari pewarnaan  sisi  graf noncommuting pada  grup dihedral- 2𝑛 (𝐷 2𝑛 ) adalah 𝜒 ′ (Γ(𝐷 2𝑛 )) = 2𝑛 − 1 untuk 𝑛 ganjil  dan 𝜒 ′ (Γ(𝐷 2𝑛 )) = 2𝑛 − 3 untuk 𝑛 genap.
Bukti: Untuk 𝑛 ganjil,  diketahui 𝑟 𝑖 dan 𝑠𝑟 𝑗 , 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 tidak  komutatif,  artinya 𝑟 𝑖 dan 𝑠𝑟 𝑗 , 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 saling terhubung langsung  di 𝐷 2𝑛 ,  untuk 𝑖 ≠ 𝑗 .  Karena 𝑟 𝑖 dan 𝑠𝑟 𝑗 saling  terhubung  langsung,  maka  membentuk subgraf komplit di Γ(𝐷 2𝑛 ) . Misal 𝑣 merupakan titik di Γ(𝐷 2𝑛 ) .  Diketahui  bahwa  banyaknya  titik berderajat  ganjil  pada  sebuah  graf  adalah  genap, dapat  ditulis ∑ 𝑑𝑒𝑔(𝑣) = 2𝑛 𝑣∈Γ(𝐷 2𝑛 ) .  Pada  graf noncommuting, pada 𝑛 ganjil  banyaknya
∑(𝑍(𝐷 2𝑛 )) adalah  1.  Karena  pada  graf noncommuting center  grup  tidak  dimunculkan, maka dapat ditulis
𝐷(Γ(𝐷 2𝑛 )) = ∑ deg(𝑣)
𝑣∈Γ(𝐷 2𝑛 ) − ∑(𝑍(𝐷 2𝑛 ))
= 2𝑛 − 1. Dengan  demikian,  minimum  warna  yang digunakan  yaitu 2𝑛 − 1 .  Sehingga  didapatkan (Γ(𝐷 2𝑛 )) = 2𝑛 − 1 untuk 𝑛 ganjil.
Untuk 𝑛 genap,  diketahui 𝑟 𝑖 dan 𝑠𝑟 𝑗 , 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 tidak saling komutatif, maka 𝑟 𝑖 dan 𝑠𝑟 𝑗 , 𝑖, 𝑗 = 0,1,2, … , 𝑛 − 1 terhubung  langsung  di Γ(𝐷 2𝑛 ) , 𝑖 ≠ 𝑗 . Diketahui bahwa banyaknya derajat titik pada sebuah graf adalah dua kali banyak sisi. Misal 𝑣 merupakan  titik  di Γ(𝐷 2𝑛 ) ,  maka  dapat ditulis ∑ 𝑑𝑒𝑔(𝑣) = 2𝑛 𝑣∈Γ(𝐷 2𝑛 ) . Diketahui pada graf noncommuting
𝑍(𝐷 2𝑛 ) = {1, 𝑟 𝑛
2 } , maka ∑(𝑍(𝐷 2𝑛 )) = 2 .  Dari  banyaknya  titik  dan  center grup  di Γ(𝐷 2𝑛 ) ,  dapat  dikatakan 𝐷(Γ(𝐷 2𝑛 )) = 2𝑛 − 2 .  Karena 𝑠𝑟 𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1 saling komutatif dengan 𝑠𝑟 𝑗 , 𝑗 = 𝑛 2 , 𝑛 2 + 1, 𝑛 2 + 2, … , 𝑛 − 1 , maka 𝑠𝑟 𝑖 , 𝑖 = 0,1,2, … , 𝑛 − 1 tidak  terhubung langsung  dengan 𝑠𝑟 𝑗 , 𝑗 = 𝑛 2 , 𝑛 2 + 1, 𝑛
2 + 2, … , 𝑛 − 1 ,
sehingga 𝐷(Γ(𝐷 2𝑛 )) = 2𝑛 − 3 .
Karena 𝐷(Γ(𝐷 2𝑛 )) = |𝑁(𝑣 ∈ 𝐷 2𝑛 )| yaitu 2𝑛 − 3 ,  maka dapat  dikatakan  minimal    warna  yang  digunakan sebanyak 2𝑛 − 3 warna.  Dengan  demikian (Γ(𝐷 2𝑛 )) = 2𝑛 − 3 untuk 𝑛 genap.

## KESIMPULAN
Berdasarkan pembahasan pada penelitian ini, maka dapat diambil kesimpulan mengenai bilangan kromatik graf commuting dan noncommuting dari grup dihedral yaitu sebagai berikut:
1. Bilangan kromatik dari pewarnaan titik graf commuting grup dihedral yaitu 𝜒(𝐶(𝐷 2𝑛 )) = 𝑛 , untuk 𝑛 ganjil dan genap.
2. Bilangan kromatik dari pewarnaan sisi graf commuting grup dihedral ialah 𝜒 ′ (C(𝐷 2𝑛 )) = 2𝑛 − 1 , untuk 𝑛 ganjil dan genap.
3. Bilangan kromatik dari pewarnaan titik graf noncommuting grup dihedral ialah:
𝜒(Γ(𝐷 2𝑛 )) = { 𝑛 + 1, 𝑛 𝑔𝑎𝑛𝑗𝑖𝑙 𝑛 2 + 1, 𝑛 𝑔𝑒𝑛𝑎𝑝 4. Bilangan kromatik dari pewarnaan sisi graf noncommuting grup dihedral ialah:
𝜒′(Γ(𝐷 2𝑛 )) = { 2𝑛 − 1, 𝑛 𝑔𝑎𝑛𝑗𝑖𝑙 2𝑛 − 3,
𝑛 𝑔𝑒𝑛𝑎𝑝

## DAFTAR PUSTAKA
[1] G. Chartrand and L. Lesniak, Graph and Digraph 2nd Edition, California: Wadsworth, Inc, 1986.
[2]   Abdussakir, N. Azizah and F. Novandika, Teori Graf, Malang: UIN Malang Press, 2009.
[3]   A. Abdollahi, S. Akbari and H. Maimani, "Noncommuting Graph of a Group," Journal of Algebra, pp. 468-492, 2006.
[4]   M. Raisinghania and R. Aggrawal, Modern Algebra, New Delhi: S. Chand & Company Ltd, 1980.
[5]   D. Dummit and R. Foote, Abstract Algebra, New Jersey: Prentice Hall, Inc, 1991.
[6]   A. Nawawi and Preeley, On Commuting Graphs for Element of Order 3 in Symetry Groups, Manchester: The Mims Secretary, 2012.
[7]   A. G. Parlos, "Linearization Of Nonlinear Dynamics," 2014. [Online]. Available: http://parlos.tamu.edu/MEEN651/Lineari zation.pdf. [Accessed 17 Agustus 2014].
[8]   R. C. Robinson, An Introduction Dynamical System Continuous and Discrete, New Jersey: Pearson Education, 2004.
[9]   W. E. Boyce and R. C. DiPrima, Elementary Differential Equations and Boundary Value Problems, New York: John Wiley & Sons, Inc, 2009.
[10]   R. O. Kwofie, "A mathematical model of a suspension bridge – case study: Adomi bridge, Atimpoku, Ghana," Global Advanced Research Journal of Engineering, Technology, and Innovation, vol. 1(3), pp. 047-062, 2012.
[11]   G. Vries, T. Hillen, M. Lewis, J. Müller and M. Schönfisch, A Course in Mathematical Biology: Quantitative Modeling with Mathematical and Computational Methods, Alberta: SIAM, 2006.
[12]   M. Bulmer and J. Eccleston, Photocopier Reliability Modeling Using Evolutianary Algorithm., John Wiley & Sons, 2003.
[13]   P. Bhattacharya and R. Bhattacharjee, "A Study on Weibull Distribution for Estimating the Parameters," Journal of Applied Quantitative Methods, vol. 2, p. 5,
2010.
[14]   I. P. Kinasih, "Penaksiran Parameter Distribusi Weibull Bivariat Menggunakan Algoritma Genetika," Tesis, 2012.
[15]   R. d. S. D. Bartle, Introduction to Real Analysis, 3rd edition, New York: JohnWiley,
2000.
[16]   J. D. T. L. Lindenstrauss, Classical Banach Spaces II, Berlin: Springer-Verlag, 1977.
[17]   J. Diestel, Sequences and Series in Banach Spaces, New York: Springer-Verlag, 1984.
[18]   P. Meyer-Nieberg, Banach Lattices, Berlin: Springer-Verlag, 1991.
[19]   F. d. K. N. Albiac, Topics in Banach Space Theory, New York: Springer-Verlag, 2006.
[20]   J. Yeh, Real Analysis: Theory of Measure and Integration, 2nd edition, Singapore: World Scientific Publishing, 2006.
[21]   H. Dales, Introduction Banach Algebras, Operators, and Harmonic Analysis, Cambridge: Cambridge University Press, 2003.
[22]   S. Darmawijaya, "Calculus on the Family of Continuous Functions," in Seminar Nasional KNM XVI , Universitas Padjadjaran
Sumedang, 2012.
[23]   F. Chorlton, Textbook of fluid dynamics, Princeton: D. Van Nostrand Company LTD, 1967.
[24]   B. R. Munson, Fundamentals of fluid mechanics, John Wiley and Sons, Inc, 2002.
[25]   R. M. Olson, Dasar-dasar mekanika fluida, Jakarta: PT Gramedia Pustaka Utama, 1993.
[26]   B. K. Shivamoggi, Theoretical fluid dynamics, Boston: Martinus Nijhoff Publisher, 1985.
[27]   L. Wiryanto, "A Solitary-like wave generated by flow passing a bump," in ICMSA 2010 , Kuala Lumpur, 2010.
[28]   T. Akylas, "On the excitation of long nonlinear water waves by a moving pressure distribution," J. Fluid Mech, pp.
455-466, 1984.
[29]   S. Cole, "Transient Waves Produces By Flow Past a Bump," Wave Motion, pp. 579-587, 1985.
[30]   R. P. C. Steven C. Chapra, Numerical Methods for Engineers, Boston: Mc Graw Hill.
[31]   R. L. Burden, Numerical Analysis, Boston: Brooks/Cole CENGAGE Learning, 2011.
[32]   L. Lapidus, Numerical Solution of Partial Differential Equations in Science and Engineering, Canada: John Wiley & Sons, 1982.
[33]   Z. D.-H. R.H.J. Grimshaw, "Generation of solitary waves by transcritical flow over a step," J. Fluid Mech, pp. 235-254, 2007.
[34]   B. -F. F. a. T. Mitsui, "A finite Difference
Method for KdV and KP equations," J. Comp. Applied Maths., , pp. 95-116, 1998.
[35]   P. D. &. R. S. Johnson, Solitons: an introduction, Britain: Cambridge university press, 1993.
[36]   F. E. Camfield, Tsunami Engineering, Belvoir USA: Coastal Engineering Research Center, 1980.
[37]   J. Park, "Numerical Simulation of Wave Propagation using the Shallow Water Equation," Harvey Mudd College, 2007.
[38]   L. H. Holthuijsen, Waves in Oceanic and Coastal Waters, Cambridge: Cambridge University Press, 2007.
[39]   K. Satake, Tsunamis: Case Studies and Recent Development, Netherland: Springer, 2005.
[40]   J. Kampf, Ocean Modelling for Beginners, New York: Springer, 2009.