BILANGAN KROMATIK GRAF COMMUTING DAN

Bilangan Kromatik Graf Commuting dan Noncommuting Grup Dihedralkeduanya adalah elemen yang saling komutatif di𝐺 [6].Misal 𝐺 grup non abelian dan 𝑍(𝐺) adalahcenter dari 𝐺. Graf non commuting Γ𝐺 adalah suatugraf yang mana titik-titiknya merupakanhimpunan dari 𝐺\𝑍(𝐺) dan dua titik 𝑥 dan 𝑦terhubung langsung jika dan hanya jika 𝑥𝑦 𝑦𝑥[3].PEMBAHASANPewarnaan titik pada graf G adalahpemberian sebanyak n warna pada titik sehinggadua titik yang saling terhubung langsung tidakdiberi warna yang sama. Pewarnaan sisi pada grafG adalah pemberian sebanyak n warna pada sisisehingga dua sisi yang saling terkait langsungtidak diberi warna yang sama. Dari pewarnaantitik dan sisi inilah dapat diketahui bilangankromatiknya, baik graf commuting maupun grafnoncommuting.maka 𝑟 𝑖 dan 𝑟 𝑗 saling terhubung langsung di𝐶 (𝐷2𝑛 ). Karena 𝑟 𝑖 dan 𝑟 𝑗 saling komutatif, makaterdapat (𝑟 𝑖 , 𝑟 𝑗 ) 𝐶 (𝐷2𝑛 ) yang membentuksubgraf komplit-𝑛. Sehingga dibutuhkan sebanyak𝑛 warna, atau dengan kata lain bilangan kromatikpewarnaan titik 𝑟 𝑖 dan 𝑟 𝑗 yaitu 𝑛.Misal 𝑤 {𝑠, 𝑠𝑟, 𝑠𝑟1 , , 𝑠𝑟 𝑛 1 } dimana 𝑤 hanyakomutatif dengan 1 di 𝐷2𝑛 . Artinya 𝑠𝑟 𝑖 dan𝑠𝑟 𝑗 , 𝑖, 𝑗 0,1,2, , 𝑛 1 tidak saling komutatif.Karena tidak saling komutatif, maka dapat diberiwarna yang sama.Pada 𝑛 ganjil, 𝑠𝑟 𝑖 tidak komutatif dengan 𝑟 𝑗 , 𝑗 1,2, , 𝑛 1.𝑠𝑟 𝑟 𝑠𝑟1 1𝑟 𝑠𝑟 𝑠𝑟1 12 𝑠𝑟 𝑠Karena 𝑠𝑟 𝑖 tidak komutatif dengan 𝑟 𝑗 , 𝑗 1,2, , 𝑛 1, maka warna titik 𝑠𝑟 𝑖 berlaku samadengan titik 𝑟 𝑗 , 𝑗 1,2, , 𝑛 �� 2 𝑟 2 𝑟 2 𝑠𝑟 2 ,sehingga warna titik 𝑠𝑟 2 tidak boleh sama denganBilangan Kromatik Pewarnaan Titik dan SisiGraf Commuting Grup DihedralPerhatikan tabel di bawah ini:Tabel 1. Bilangan Kromatik Pewarnaan Titik danSisi Graf Commuting Grup Dihedral′𝐶 (𝐷2𝑛 ) 𝜒(𝐶 (𝐷2𝑛 )) 𝜒 (𝐶(𝐷2𝑛 ))𝐷635𝐷847𝐷1059.𝐷2𝑛𝑛2𝑛 1Sumber: penulisBerdasarkan Tabel 1, didapatkan teoremaberikut:Teorema 1Misal 𝐶 (𝐷2𝑛 ) adalah graf commuting darigrup dihedral-2n (𝐷2𝑛 ). Maka bilangan kromatikpewarnaan titik graf commuting dari grupdihedral-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𝑛 ,CAUCHY – ISSN: 2086-0382/E-ISSN: 2477-3344𝑛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 maupungenap.Teorema 2Misal 𝐶 (𝐷2𝑛 ) adalah graf commuting dari grupdihedral-2n (𝐷2𝑛 ). Maka bilangan kromatikpewarnaan sisi graf commuting dari grup dihedral2n (𝐷2𝑛 ) adalah 𝜒′(𝐶 (𝐷2𝑛 )) 2𝑛 1Bukti:Untuk 𝑛 ganjil, diketahui bahwa 𝑟 𝑖 𝑟 𝑗 𝑟 𝑗 𝑟 𝑖 ,untuk 𝑖, 𝑗 0,1,2, , 𝑛 1 di 𝐷2𝑛 , untuk 𝑖 𝑗. Jadi,𝑟 𝑖 dan 𝑟 𝑗 saling terhubung langsung di 𝐺. Disamping itu, 1 komutatif dengan semua elemen 𝑟 𝑖dan 𝑠𝑟 𝑖 , sehingga 1 terhubung langsung dengansemua elemen 𝑟 𝑖 dan 𝑠𝑟 𝑖 , 𝑖 0,1,2, , 𝑛 1 di 𝐺.Karena 1 terhubung langsung dengan 2𝑛 1elemen di 𝐺, maka minimal warna yang digunakanpewarnaan sisinya yaitu sebanyak 2𝑛 1 warna.Berdasarkan aturan pewarnaannya, setiap sisiyang terkait dengan 1 titik yang sama diberiwarna yang berbeda. Adapun 𝑟 𝑖 dan 𝑟 𝑗 , 𝑖 0,1,2, ,2𝑛 1 yang saling terhubung langsungdapat diberi warna dari 2𝑛 1 warna yang telahdigunakan sebelumnya. Sehingga didapatkanbilangan 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 𝑟 218

Handrini Rahayuningtyaskomutatif 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𝑛 1elemen. 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 adalahsebesar derajat tertinggi di 𝐺 yaitu 1. 1 terhubunglangsung dengan 2𝑛 1 elemen, maka minimalwarna yang digunakan dalam pewarnaan sisi di 𝐺sebanyak 2𝑛 1 warna. Jadi, diperoleh bilangankromatik sisinya yaitu 𝜒′(𝐶 (𝐷2𝑛 )) 2𝑛 1, untuk𝑛 genap.Bilangan Kromatik Pewarnaan Titik dan SisiGraf Noncommuting Grup Dihedrallangsung. Dengan demikian, 𝑆 {𝑟, 𝑠, 𝑠𝑟, , 𝑠𝑟 𝑛 1 }akan membentuk subgraf komplit terbesar di 𝐺.Karena 𝑆 {𝑟, 𝑠, 𝑠𝑟, , 𝑠𝑟 𝑛 1 } membentuk subgrafterbesar di 𝐺, maka bilangan clique atau ordersubgraf komplit terbesar graf 𝐺 adalah 𝑛 1, yaitukardinalitas himpunan 𝑆. Karena order darisubgraf komplit terbesarnya adalah 𝑛 1, makapewarnaan titik pada graf 𝐺 membutuhkanminimal warna sebanyak 𝑛 1 warna. Dengandemikian didapatkan bilangan kromatik titik padagraf noncommuting grup dihedral yaitu𝜒(Γ(𝐷2𝑛 )) 𝑛 1, untuk 𝑛 ganjil.𝑛Untuk 𝑛 genap, diketahui bahwa 𝑍(𝐺 ) {1, 𝑟 2 }.Karena 𝑟 𝑖 dan 𝑠𝑟 𝑗 , untuk 𝑖, 𝑗 0,1,2, , 𝑛 1 tidaksaling komutatif, maka 𝑟 𝑖 dan 𝑠𝑟 𝑗 , untuk 𝑖, 𝑗 0,1,2, , 𝑛 1 terhubung langsung di 𝐺, untuk 𝑖 𝑛𝑗. Karena 𝑠𝑟 𝑖 , 𝑖 0,1,2, ,saling komutatif𝑛 𝑛Perhatikan tabel berikut:Tabel 2. Bilangan Kromatik Graf NoncommutingGraf Noncommuting Grup Dihedral𝜒(Γ(𝐷2𝑛 ))𝜒 ′ (Γ(𝐷2𝑛 ))Γ(𝐷2𝑛 )Γ(𝐷6 )45Γ(𝐷8 )35Γ(𝐷10 )69Γ(𝐷12 )49Γ(𝐷14 )813Γ(𝐷16 ).5.13.𝑛 1, 𝑛 ganjil2𝑛 1, n ganjilΓ(𝐷2𝑛 )𝑛2 1, 𝑛 genap2𝑛 3, n genapSumber: penulisBerdasarkan Tabel 2, diperoleh teorema sebagaiberikut:Teorema 3Misal Γ(𝐷2𝑛 ) adalah graf noncommuting dari grupdihedral-2n (𝐷2𝑛 ), maka bilangan kromatik daripewarnaan titik graf noncommuting pada grupdihedral-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 terhubung19𝑛2dengan 𝑠𝑟 𝑗 , 𝑗 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 akanmembentuk subgraf komplit. Karena 𝑠𝑟 𝑖 , 𝑖 𝑛0,1,2, , 2 terhubung langsung dengan 𝑟, makadiperoleh subgraf komplit terbesar yang memuat𝑛 1 titik. Dengan kata lain, bilangan clique atau2𝑛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 1warna. Dengan demikian, dapat disimpulkanbahwa bilangan kromatik titik graf noncommuting𝑛grup dihedral yaitu 𝜒(Γ(𝐷2𝑛 )) 2 1, untuk 𝑛genap.Teorema 4Misal Γ(𝐷2𝑛 ) adalah graf noncommuting dari grupdihedral-2n (𝐷2𝑛 ), maka bilangan kromatik daripewarnaan sisi graf noncommuting pada grupdihedral-2𝑛 (𝐷2𝑛 ) adalah 𝜒 ′ (Γ(𝐷2𝑛 )) 2𝑛 1untuk 𝑛 ganjil dan 𝜒 ′ (Γ(𝐷2𝑛 )) 2𝑛 3 untuk 𝑛genap.Bukti:Untuk 𝑛 ganjil, diketahui 𝑟 𝑖 dan 𝑠𝑟 𝑗 , 𝑖, 𝑗 0,1,2, , 𝑛 1 tidak komutatif, artinya 𝑟 𝑖 dan𝑠𝑟 𝑗 , 𝑖, 𝑗 0,1,2, , 𝑛 1salingterhubunglangsung di 𝐷2𝑛 , untuk 𝑖 𝑗. Karena 𝑟 𝑖 dan 𝑠𝑟 𝑗saling terhubung langsung, maka membentuksubgraf komplit di Γ(𝐷2𝑛 ). Misal 𝑣 merupakan titikdi Γ(𝐷2𝑛 ). Diketahui bahwa banyaknya titikberderajat ganjil pada sebuah graf adalah genap,dapat ditulis 𝑣 Γ(𝐷2𝑛) 𝑑𝑒𝑔(𝑣) 2𝑛. Pada grafnoncommuting, pada 𝑛 ganjil banyaknyaVolume 4 No.1 November 2015

Bilangan Kromatik Graf Commuting dan Noncommuting Grup Dihedral (𝑍 (𝐷2𝑛 )) adalah 1. Karena pada grafnoncommuting center grup tidak dimunculkan,maka dapat ditulis𝐷(Γ(𝐷2𝑛 )) [1]deg(𝑣) (𝑍(𝐷2𝑛 ))𝑣 Γ(𝐷2𝑛) 2𝑛 1.Dengan demikian, minimum warna yangdigunakan 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 derajattitik pada sebuah graf adalah dua kali banyak sisi.Misal 𝑣 merupakan titik di Γ(𝐷2𝑛 ), maka dapatditulis 𝑣 Γ(𝐷2𝑛) 𝑑𝑒𝑔(𝑣) 2𝑛. Diketahui pada grafnoncommutingDAFTAR PUSTAKA𝑛𝑍(𝐷2𝑛 ) {1, 𝑟 2 },maka (𝑍 (𝐷2𝑛 )) 2. Dari banyaknya titik dan centergrup 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, , 𝑛 1tidak terhubung𝑛 𝑛𝑛langsung dengan 𝑠𝑟 𝑗 , 𝑗 2 , 2 1, 2 2, , 𝑛 1,sehingga𝐷(Γ(𝐷2𝑛 )) 2𝑛 3.Karena𝐷(Γ(𝐷2𝑛 )) 𝑁(𝑣 𝐷2𝑛 ) yaitu 2𝑛 3, makadapat dikatakan minimal warna yang digunakansebanyak 2𝑛 3 warna. Dengan demikian(Γ(𝐷2𝑛 )) 2𝑛 3 untuk 𝑛 n pembahasan pada penelitian ini,maka dapat diambil kesimpulan mengenaibilangan kromatik graf commuting dannoncommuting dari grup dihedral yaitu sebagaiberikut:1. Bilangan kromatik dari pewarnaan titik grafcommuting grup dihedral yaitu𝜒(𝐶 (𝐷2𝑛 )) 𝑛, untuk 𝑛 ganjil dan genap.2. Bilangan kromatik dari pewarnaan sisi grafcommuting grup dihedral ialah𝜒 ′(C(𝐷2𝑛 )) 2𝑛 1, untuk 𝑛 ganjil dangenap.3. Bilangan kromatik dari pewarnaan titik grafnoncommuting grup dihedral ialah:𝑛 1,𝑛 𝑔𝑎𝑛𝑗𝑖𝑙𝜒(Γ(𝐷2𝑛 )) {𝑛 1,𝑛 𝑔𝑒𝑛𝑎𝑝24. Bilangan kromatik dari pewarnaan sisi grafnoncommuting grup dihedral ialah:𝜒′(Γ(𝐷2𝑛 )) {2𝑛 1,2𝑛 3,𝑛 𝑔𝑎𝑛𝑗𝑖𝑙𝑛 𝑔𝑒𝑛𝑎𝑝[10][11][12][13][14][15]CAUCHY – ISSN: 2086-0382/E-ISSN: 2477-3344G. Chartrand and L. Lesniak, Graph andDigraph 2nd Edition, California:Wadsworth, Inc, 1986.Abdussakir, N. Azizah and F. Novandika,Teori Graf, Malang: UIN Malang Press,2009.A. Abdollahi, S. Akbari and H. Maimani,"Noncommuting Graph of a Group," Journalof Algebra, pp. 468-492, 2006.M. Raisinghania and R. Aggrawal, ModernAlgebra, New Delhi: S. Chand & CompanyLtd, 1980.D. Dummit and R. Foote, Abstract Algebra,New Jersey: Prentice Hall, Inc, 1991.A. Nawawi and Preeley, On CommutingGraphs for Element of Order 3 in SymetryGroups, Manchester: The Mims Secretary,2012.A. G. Parlos, "Linearization Of NonlinearDynamics," 2014. [Online]. tion.pdf. [Accessed 17 Agustus 2014].R. C. Robinson, An Introduction DynamicalSystem Continuous and Discrete, NewJersey: Pearson Education, 2004.W. E. Boyce and R. C. DiPrima, ElementaryDifferential Equations and Boundary ValueProblems, New York: John Wiley & Sons,Inc, 2009.R. O. Kwofie, "A mathematical model of asuspension bridge – case study: Adomibridge, Atimpoku, Ghana," Global AdvancedResearch Journal of Engineering,Technology, and Innovation, vol. 1(3), pp.047-062, 2012.G. Vries, T. Hillen, M. Lewis, J. Müller and M.Schönfisch, A Course in MathematicalBiology: Quantitative Modeling withMathematical and Computational Methods,Alberta: SIAM, 2006.M. Bulmer and J. Eccleston, PhotocopierReliability Modeling Using EvolutianaryAlgorithm., John Wiley & Sons, 2003.P. Bhattacharya and R. Bhattacharjee, "AStudy on Weibull Distribution forEstimating the Parameters," Journal ofApplied Quantitative Methods, vol. 2, p. 5,2010.I. P. Kinasih, "Penaksiran ParameterDistribusi Weibull Bivariat MenggunakanAlgoritma Genetika," Tesis, 2012.R. d. S. D. Bartle, Introduction to RealAnalysis, 3rd edition, New York: JohnWiley,20

Handrini [25][26][27][28][29][30][31][32][33][34]212000.J. D. T. L. Lindenstrauss, Classical BanachSpaces II, Berlin: Springer-Verlag, 1977.J. Diestel, Sequences and Series in BanachSpaces, New York: Springer-Verlag, 1984.P. Meyer-Nieberg, Banach Lattices, Berlin:Springer-Verlag, 1991.F. d. K. N. Albiac, Topics in Banach SpaceTheory, New York: Springer-Verlag, 2006.J. Yeh, Real Analysis: Theory ofMeasure and Integration, 2ndedition, Singapore: WorldScientific Publishing, 2006.H. Dales, Introduction Banach Algebras,Operators, and Harmonic Analysis,Cambridge: Cambridge University Press,2003.S. Darmawijaya, "Calculus on the Family ofContinuous Functions," in Seminar NasionalKNM XVI, Universitas PadjadjaranSumedang, 2012.F. Chorlton, Textbook of fluid dynamics,Princeton: D. Van Nostrand Company LTD,1967.B. R. Munson, Fundamentals of fluidmechanics, John Wiley and Sons, Inc, 2002.R. M. Olson, Dasar-dasar mekanika fluida,Jakarta: PT Gramedia Pustaka Utama, 1993.B. K. Shivamoggi, Theoretical fluiddynamics, Boston: Martinus NijhoffPublisher, 1985.L. Wiryanto, "A Solitary-like wavegenerated by flow passing a bump," inICMSA 2010, Kuala Lumpur, 2010.T. Akylas, "On the excitation of lon

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 noncom