Prosiding Seminar Nasional Pendidikan Sains Tahun 2014 “Inovasi Pendidikan Sains dalam Menyongsong Pelaksanaan Kurikulum 2013” Surabaya, 18 Januari 2014
DIMENSI PARTISI SUBGRAF TERINDUKSI PADA GRAF TOTAL ATAS RING KOMUTATIF Dian Mustofani1), Subiono1) 1)
Jurusan Matematika, FMIPA, ITS, Surabaya e-mail:
[email protected] Abstract
The total graph of ring , denoted by is a graph with all elements of as vertices, and two distinct vertices , are adjacent if and only if , where denotes the set of zero-divisors of . The induced subgraph of with vertices on the regular elements denoted by be a regular graf with vertices on the regular elements Z . Ring that use ini this of ring , and other subgraph of research is ring of integers modulo. In this research, the partition dimention of subgraph will be formulated. Keywords: the total graph, regular graph, partition dimention Abstrak adalah ring komutatif. Graf total atas ring dinotasikan dengan adalah graf dengan semua Misal elemen simpul di , dan dua simpul berbeda terhubung jika dan hanya jika dengan dengan elemen simpul di adalah himpunan pembagi nol atas. Subgraf terinduksi atas graf merupakan graf regular atas ring , sedangkan subgraf terinduksi dalam graf total dinotasikan dengan yang lain yaitu subgraf terinduksi dengan elemen simpul di . Ring komutatif yang digunakan dalam penelitian ini adalah ring bilangan bulat modulo . Kemudian subgraf terinduksi atas ring komutatif ini dibuat partisi atas himpunan simpulnya sedemikian sehingga representasi setiap simpul terhadap himpunan partisi tersebut berbeda dengan kardinalitas partisi yang minimal. Hasil yang diperoleh dalam penentuan himpunan partisi tersebut tergantung pada sifat ring komutatif pembentuk graf tersebut. Kata Kunci: graf total, graf regular, dimensi partisi
PENDAHULUAN Penggabungan dua teori tentang struktur aljabar dan teori graf salah satunya dipelajari oleh (Anderson dan Badawi, 2008). Graf total atas ring dibentuk dari sebuah ring komutatif yang penyusunannya didasarkan pada himpunan pembagi nol . Sedangkan graf regular merupakan subgraf dengan simpul dalam elemen regularnya. Gagasan dari dimensi partisi untuk graf pertama kali dipelajari oleh (Gary Chartrand dan Zhang, 2000). Dalam penelitiannya simpul-simpul pada graf terhubung direpresentasikan oleh kriteria lain, yakni melalui partisi himpunan simpul dan jarak antara tiap simpul dengan himpunan bagian pada partisi tersebut. Banyaknya partisi himpunan simpul yang minimum disebut dengan dimensi partisi. Dalam tulisan ini akan dibahas tentang dimensi partisi atas subgraf terinduksi yang terdapat pada graf , yaitu subgraf terinduksi dengan elemen total yang kemudian disebut simpul pada himpunan Program Studi Pendidikan Sains, Program Pascasarjana Universitas Negeri Surabaya
sebagai graf regular atau dan subgraf terinduksi dengan elemen simpul di himpunan pembuat . Dalam tulisan ini ring komutatif yang nol atau Z digunakan adalah ring bilangan bulat modulo . METODE Pada aljabar ring merupakan suatu himpunan beserta dua operasi biner dan yang memenuhi sifat asosiatif terhadap penjumlahan, komutaif terhadap penjumlahan, ada yang merupakan elemen netral, punya invers terhadap penjumlahan, asosiatif terhadap perkalian, mempunyai elemen identitas terhadap perkalian, dan distributive. Bila semua elemen bersifat komutatif pada operasi , maka ring merupakan ring komutatif. Misal suatu ring komutatif, suatu elemen dikatakan suatu pembagi nol bila ada suatu elemen taknol yang memenuhi (Subiono,2012). dan bukan pembagi nol atas ring , Apabila maka .
ISBN: 978-602-14702-6-8 1130
Dimensi Partisi Subgraf Terinduksi Pada Graf… yang tersusun atas Sebuah graf himpunan berhingga dan . Elemen-elemen atas disebut simpul (node ), dan elemen atas disebut sisi. Sebuah subgraf atas adalah graf yang semua simpul dan sisinya berada di . Jika adalah subgraf atas , maka dapat dikatakan adalah supergraf atas (Gross dan Yellen, 2006). Graf atau graf lengkap, sedangkan graf bipartit lengkap . adalah sebuah graf, dan . Misal Jarak antara dan disimbolkan dengan adalah panjang lintasan terpendek dari simpul dan . Dengan kata lain dan jika tidak ada lintasan dari ke (Anderson dan Badawi, 2008). Bila Diberikan himpunan - partisi terurut dari , representasi dari terhadap adalah vector. Himpunan disebut partisi pembeda jika -vektor ) berbeda untuk setiap . Minimum dari – partisi pembeda dari disebut dimensi partisi dari , dinotasikan dengan (Amalia, 2013).
. Sedangkan graf atas ring merupakan subgraf terinduksi atas T dengan simpul-simpul dalam (Anderson dan Badawi, 2008). regular
Dalam penelitian Anderson dan Badawi (2008), bila ring adalah sebuah ring komutatif dengan adalah ideal atas , maka adalah sebuah graf lengkap dan dalam graf graf takterhubung dengan Reg . HASIL DAN PEMBAHASAN Dalam bagian ini akan dijelaskan penentuan dimensi partisi pada subgraf-subgraf terinduksi pada graf total, yaitu graf regular dan subgraf terinduksi dengan elemen simpul pada himpunan pembuat nol. Penentuan Dimensi Partisi pada Graf Regular Dalam penjelasan ini akan ditinjau penentuan dimensi partisi pada graf regular berdasarkan ring penyusunnya.
Gambar 1. Graf Misal
adalah graf seperti dalam Gambar 1 , dengan , , dan . Representasi terhadap adalah = (0, 1, 1), = (1, 0, 1), = (1, 1, 0), =(1, 2, 0), dan = (0, 2, 1). Maka adalah partisi pembeda dari , sebab berbeda untuk setiap dan minimum, sehingga . Dalam (Gary Chartrand dan Zhang, 2000) menyebutkan bahwa bila untuk setiap , maka simpul dan harus berada dalam partisi yang berbeda di . Sehingga untuk sebuah graf lengkap , maka dimensi partisi . Sebuah graf total atas ring komutatif dinotasikan dengan , merupakan graf takberarah dengan semua elemen atas sebagai simpul, dan untuk yang berbeda, dan terhubung jika dan hanya jika , dengan adalah himpunan pembagi nol atas disertai dengan elemen . Subgraf terinduksi atas dengan elemen simpul di dinotasikan dengan yang merupakan graf regular atas ring . Untuk selanjutnya dalam tulisan ini, disebut sebagai graf Program Studi Pendidikan Sains, Program Pascasarjana Universitas Negeri Surabaya
Gambar 2. Graf regular
,
Gambar 2(a), (b), (c), dan (d) berturut-turut, untuk . merupakan graf regular atas ring Dapat dilihat bahwa graf regular untuk merupakan graf yang tidak terhubung, sehingga tidak dapat ditentukan dimensi partisinya. dan , dapat diselidiki Untuk bahwa graf regular merupakan graf lengkap , dengan , sehingga . Simpulan tersebut dituliskan berikut ini : Teorema 1 : Misal atas ring , untuk
adalah graf regular dan , maka
Bukti : Karena pembuat nol dan
dan , maka himpunan adalah ideal. Dapat diperiksa untuk , adalah subgrup siklik yang ISBN: 978-602-14702-6-8
1131
Dimensi Partisi Subgraf Terinduksi Pada Graf… dibangkitkan oleh elemen dengan
atau dapat ditulis
, akibatnya
sedemikian sehingga banyaknya koset kiri yang
. Berdasarkan sifat terbentuk adalah yang ada dalam penelitian Anderson dan Badawi maka regular yang terbentuk (2008), untuk . Sehingga adalah graf lengkap , untuk dan .
dan bilangan genap dengan bilangan ganjil.
, karena adalah maka adalah
Sehingga adalah genap, maka .
, karena dan
Karena untuk setiap , dan , maka untuk setiap simpul di saling terhubung, dan graf regular yang terbentuk adalah graf lengkap dengan elemen simpul sebanyak elemen . Penentuan Dimensi Partisi pada Subgraf Terinduksi Dengan Elemen Simpul di Himpunan Pembuat Nol. Dalam bagian ini akan dibahas penentuan dimensi partisi pada subgraf terinduksi dengan elemen simpul di himpunan pembuat nol berdasarkan ring penyusunnya.
Gambar 4. Subgraf terinduksi Z
,
, dengan , maka Untuk setiap himpunan pembuat nol , sehingga subgraf terinduksi dengan elmen adalah graf dengan 1 simpul, seperti yang terlihat dalam Gambar 4. Maka . Gambar
3. Graf
,
regular dan
Dalam Gambar 3(a) dan (b) berturut=turut merupakan graf regular , untuk dan . Sedangkan Gambar 3(c) dan (d) merupakan graf regular , untuk . Karena untuk setiap , dan graf yang terbentuk merupakan graf regular tak terhubung, maka tidak dapat ditentukan dimensi partisinya. Untuk diselidiki bahwa graf regular graf lengkap , dengan . dituliskan berikut ini : Teorema 2 : Misal atas ring , untuk maka
dan
, dapat merupakan , sehingga Simpulan tersebut Gambar 5. Subgraf terinduksi Z adalah graf regular dan , .
Bukti : Akan dibuktikan untuk setiap . Ambil sebarang dan bilangan genap dengan bilangan ganjil.
maka : , karena adalah maka adalah
,
, dengan , maka Untuk setiap subgraf terinduksi dengan elmen adalah graf lengkap seperti yang terlihat dalam Gambar 5. Maka . Teorema 3 : Misal adalah ring dengan dengan . Maka
, .
Bukti : Karena himpunan pembuat nol merupakan ideal atas ring jika dan hanya jika , dengan
Program Studi Pendidikan Sains, Program Pascasarjana Universitas Negeri Surabaya
ISBN: 978-602-14702-6-8 1132
Dimensi Partisi Subgraf Terinduksi Pada Graf… . Dalam tulisan Anderson dan Badawi adalah ideal atas ring , (2008), merupakan sugrub terinduksi lengkap atas graf total . Sehingga dimensi partisi yang mungkin pada subgraf terinduksi = . Maka , dengan , .
yang
dibangun
adalah dalam himpunan pembuat nol , dan . Karena 1, maka salah satu himpunan partisi pembeda yang mungkin adalah , dengan , , dan . Maka representasi setiap simpul terhadap yaitu : ) =(0, 1, 1) ) =(1, 0, 1) ) =(0, 2, 2)
.
) =(1, 1, 0) Karena
Bukti : adalah ,
graf
dengan
order dimana
dan , , dan
SIMPULAN
Untuk
,
Untuk
,
Untuk Dan
andaikan untuk
, dan . Karena : entri ,
ke-1
entri ,
ke-2
untuk
,
untuk ,
dalam
ke-2
subgraf terinduksi dengan elmen simpul pada himpunan pembuat nolnya untuk maka , sedangkan untuk maka , kemudian untuk
dalam maka
Ini menunjukkan , kontradiksi, bukan partisi pembeda atas Sehingga
maka .
.
kemudian
maka untuk
maka . Dimensi partisi pada
dalam dalam
entri
Pada penelitian ini berhasil mendapatkan suatu formulasi dimensi partisi subgraf terinduksi pada graf total. Dimana dimensi partisi pada subgraf terinduksi yang diberikan. Dimensi ini bergantung pada nilai partisi pada graf regular untuk dengan , dan untuk dengan dan maka dimensi partisi pada tidak dapat ditentukan p, graf regular sedangkan
, entri ke,
, .
dan . Maka terdapat sedemikian sehingga , ini berarti bahwa , dan dapat diperiksa untuk . Andaikan juga partisi dimensinya adalah
misal
) berbeda untuk semua
jadi
. Dan misal
,
elemen
termuat
Teorema 4 : Misal adalah subgraf terinduksi atas ring , untuk dengan elemen simpula pada . Misal subgroup dan . Maka
Misal
oleh
.
Dalam penelitian ini ring komutatif yang digunakan adalah ring himpunan bilangan bulat modulo , untuk penelitian selanjutnya disanrankan untuk meneliti dimensi partisi pada ring selain himpunan bilangan bulat modulo . DAFTAR PUSTAKA Amalia, R. 2013. “Dimensi Partisi Bintang dari Graf Kincir yang Diperumum”. Tesis, Jurusan Matematika Institut Teknologi Sepuluh Nopember, Surabaya.
Gambar 6. Subgraf terinduksi Z
Anderson, D. F. dan Badawi, A. 2008. “The Total Graph of a Commutative Ring”. Journal of Algebra 320, 2706–2719.
.
Contoh permasalahan dalam Gambar 6, adalah , maka seperti sebagai berikut, bila dalam Gambar 6. Di mana elemen-elemen simpulnya adalah . Sub grup siklik Program Studi Pendidikan Sains, Program Pascasarjana Universitas Negeri Surabaya
Gary Chartrand, E. S. dan Zhang, P. 2000. “The Partition Dimention of a Graph”. Aequationes Mathematicae 59, 45–54.
ISBN: 978-602-14702-6-8 1133
Dimensi Partisi Subgraf Terinduksi Pada Graf… Gross, J. L. dan Yellen, J. 2006. Graph Theory and Its Applications. second edn, USA: Chapman and Hall =CRCTaylor& Francis Group. Herstein, I. N. 1996. Abstract Algebra. third edn. USA: Prentice Hall Inc. Sari, A. N. 2013. “Dimensi Partisi Graf Hasil Amalgamasi Dua Graf Terhubung”. Tesis, Jurusan Matematika Institut Teknologi Sepuluh Nopember, Surabaya. Subiono. 2012. “Aljabar Materi Kuliah Aljabar 2012”. Jurusan Matematika Institut Teknologi Sepuluh Nopember, Surabaya.
Program Studi Pendidikan Sains, Program Pascasarjana Universitas Negeri Surabaya
ISBN: 978-602-14702-6-8 1134
