Bilangan Kromatik Graf Hasil Amalgamasi Dua Buah Graf

JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 2337-3520 (2301-928X Print)

1

Bilangan Kromatik Graf Hasil Amalgamasi Dua Buah Graf Ridwan Ardiyansah dan Darmaji Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 E-mail: [email protected] Abstrak—Sebuah graf dikatakan sebagai graf dengan -coloring jika dapat diwarnai dengan warna dan tidak terdapat simpul-simpul saling bertetangga yang memiliki warna sama. Lebih lanjut, bila menunjukkan jumlah minimum warna yang digunakan sehingga tetap dapat diwarnai dan tidak terdapat simpul bertetangga dengan warna yang sama, maka diakatakan sebagai bilangan kromatik dari yang dinotasikan dengan . Dalam tugas Akhir ini dilakukan analisis bilangan kromatik dari graf hasil amalgamasi dua buah graf terhubung. Operan yang digunakan dalam operasi amalgamasi ini berupa graf lengkap dengan graf siklus dan graf kincir dengan . Kata Kunci—amalgamasi, bilangan kromatik, graf kincir, graf lengkap, graf siklus, operasi graf.

I. PENDAHULUAN

P

ada abad ke-18 Euler mengenalkan pembahasan teori graf melalui penyelesaian sebuah masalah terkenal yang biasa disebut sebagai permasalahan Jembatan Konigsberg. Lebih lanjut, diantara pembahasan teori graf yang hingga kini masih menjadi sebuah topik yang menarik untuk dikaji adalah pembahsan mengenai pewarnaan graf. Alauddin [1] pada tahun 2009 telah melakukan penelitian mengenai bilangan kromatik graf prisma yang diperoleh dari hasil produk kartesian antara graf lintasan dengan graf siklus . Pada tahun 2010, Gross, dkk [2] telah melakukan penelitian mengenai distribusi genus dari amalgamasi graf. Akan tetapi, sampai saat ini penelitian mengenai bilangan kromatik graf hasil amalgamasi dua buah graf belum dilakukan. Oleh karena itu, muncul sebuah gagasan untuk melakukan analisis mengenai bilangan kromatik dari graf hasil amalgamasi dua buah graf. Operan yang digunakan dalam operasi amalgamasi ini adalah antara graf lengkap dengan graf siklus dan dua buah graf kincir yang berbeda dengan untuk dan merupakan anggota bilangan asli, sedangkan simpul yang diambil dari masingmasing graf adalah dua simpul yang saling bertetangga. II. PENGERTIAN GRAF

A. Teori Graf Sebuah graf adalah himpunan berhingga tak kosong dari objek yang disebut simpul, bersama himpunan (yang mungkin

kosong) pasangan tak terurut dari simpul yang berbeda pada yang disebut sebagai sisi. Himpunan simpul dari dinotasikan dengan , sedangkan himpunan sisi dinotasikan dengan [3]. Dalam teori graf, sebuah graf dinotasikan dengan menggunakan huruf kapital, sebuah simpul pada graf dinotasikan dengan huruf kecil dan direpresentasikan sebagai sebuah titik atau bundaran, sedangkan sisi dari graf dinotasikan dengan atau atau dan direpresentasikan sebagai sebuah garis. Banyaknya sisi yang melekat pada simpul disebut derajat simpul. Derajat dari simpul dinotasikan atau untuk memperjelas pembahasan. Derajat simpul terbanyak dalam graf dinotasikan . Graf disebut graf teratur apabila derajat setiap simpul di adalah sama. Jika terdapat dua buah graf dan , maka graf dikatakan subgraf dari graf , bila himpunan simpul dan sisi pada graf merupakan himpunan bagian dari . Hubungan antara graf dan ini dinotasikan dengan . Jika merupakan himpunan bagian dari , maka disebut sebagai independent-set, bila tidak ada pasangan simpul di yang merupakan simpul-simpul yang saling bertetangga. Lebih lanjut, jumlah simpul terbanyak pada independent-set diseb Dua buah graf dan dikatakan ismorfis jika terdapat fungsi sedemikian hingga setiap dua simpul dan saling bertetangga di jika dan hanya jika dan saling bertetangga di . Hubungan di atas dinotasikan dengan .

B. Beberapa Jenis Graf Dalam teori graf terdapat beberapa jenis graf yang memainkan peran penting. Pada bagian ini akan dijelaskan beberapa jenis dari graf yang banyak dibahas dalam teori graf. 1. Graf Lengkap (Complete Graph) Sebuah graf dikatakan lengkap jika setiap simpul dalam terhubung dengan setiap simpul selainnya dalam [4]. Dengan kata lain, untuk sebarang maka dan saling bertetangga. Sebuah graf lengkap umumnya dinotasikan dengan dan menyatakan order dari graf . Graf lengkap merupakan salah satu graf yang memainkan peran penting dalam dunia graf sehingga banyak pembahasan dalam teori gaf yang menggunakannya sebagai objek penelitian. Pada Gambar 1 ditunjukkan beberapa contoh graf lengkap.

JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 2337-3520 (2301-928X Print)

2

4. Graf Kincir (Windmill Graph) Graf kincir adalah graf yang diperoleh dengan mengambil sebuah simpul pusat yang dihubungkan dengan setiap simpul pada buah graf lengkap . Beberapa contoh graf lengkap ditunjukkan pada Gambar 3.

Gambar 1 Contoh graf lengkap dengan order 4,5, dan 6. 2. Graf Bipartite (Bipartite Graph) Sebuah graf dikatakan sebagai graf bipartite bila dapat dipartisi menjadi dua subgraf dan , sehingga setiap sisi di salah satu ujungnya melekat di dan ujung lainnya melekat di . Selanjutnya, bila dan merupakan partisi dari dengan dan maka graf bipartite secara umum dinotasikan dengan . Contoh dari graf bipartite ditunjukkan pada Gambar 2.7

Gambar 2.7 Graf

dan

3. Graf Siklus (Cycle Graph)

Gambar 3 Contoh graf kincir dengan order 5,7, dan 13. C. Amalgamasi Dalam membentuk sebuah graf baru, salah satu cara yang dapat dilakukan yaitu dengan menggunakan operasi amalgamasi. Amalgamasi simpul dari pasangan simpul graf bersama adalah graf yang diperoleh dengan menggabungkan simpul dan menjadi satu simpul [2]. Notasi yang digunakan untuk menyatakan operasi amalgamasi adalah “ ” (apabila hanya diambil satu simpul dari masingmasing graf) atau “ ” (apabila diambil dua simpul dari masing –masing graf). Selanjutnya, diberikan graf dan sebagaimana pada Gambar 4, jika dilakukan amalgamasi dari simpul dan , maka operasi amalgamasi dinotasikan dengan , dimana adalah graf baru yang terbentuk, sedangkan adalah anggota himpunan simpul dari graf yang diperoleh dari hasil amalgamasi simpul.

Disamping itu, graf lain yang banyak digunakan sebagai objek kajian dalam dunia graf adalah Graf siklus yang merupakan graf teratur yang masing-masing simpulnya berderajat 2 [5]. Graf siklus dinotasikan dengan menyatakan order dari graf. Pada graf siklus, order dan size memiliki jumlah yang sama. Diantara contoh dari graf siklus ditunjukkan pada Gambar 2. Gambar 4 Contoh operasi amalgamasi.

Gambar 2 Contoh graf siklus dengan order 4, 5, dan 6.

D. Pewarnaan Simpul Pewarnaan simpul yang selanjutnya disebut dengan pewarnaan dari sebuah graf adalah pemberian warna pada setiap simpul di sedemikian hingga tidak terdapat dua simpul bertetangga yang memiliki warna yang sama. Simpulsimpul yang memiliki warna yang sama pada satu graf disebut sebagai kelas warna. Jika adalah jumlah warna yang digunakan untuk memberi warna pada simpul di graf maka pewarnaan tersebut disebut dengan -coloring dari . Lebih

JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 2337-3520 (2301-928X Print) lanjut, bila merupakan jumlah warna minimum sehingga memiliki -coloring maka disebut sebagai bilangan kromatik dari graf dan dinotasikan . [6] Untuk memperjelas pembahasan mengenai pewarnaan dan bilangan kromatik dari suatu graf, berikut ini akan diberikan contoh sebuah graf dengan -coloring.

Gambar 5 Graf dengan -coloring Graf yang ditunjukkan pada Gambar 5 dapat diwarnai dengan dua warna untuk memastikan bahwa tidak ada dua simpul bertetangga yang memiliki warna sama. Bilangan dan pada graf menunjukkan warna yang diberikan. Karena graf dapat diwarnai dengan dua warna yang dengan kata lain graf merupakan graf dengan -coloring, maka didapat . Disisi lain, karena untuk setiap simpul yang bertetangga haruslah memiliki warna yang berbeda, maka hal ini berakibat jumlah warna minimal yang digunakan untuk mewarnai graf adalah . Sehingga, berdasarkan hal ini diperoleh bahwa atau dapat ditulis bahwa graf adalah graf dengan -kromatik. Berdasarkan contoh diatas, dapat diketahui bahwa bilangan kromatik dari graf pada Gambar 5 adalah . Hal ini diperoleh dengan menggunakan prinsip dasar dalam penentuan bilangan kromatik, yaitu dengan menentukan batas atas dan batas bawah dari bilangan kromatik tersebut. Untuk menentukan batas atas dan batas bawah dari bilangan kromatik suatu graf, dibutuhkan suatu algoritma dan teorema maupun proposisi-proposisi yang membantu untuk menyelesaikan permasalahan tersebut. Berikut ini akan diberikan beberapa proposisi, teorema, dan algoritma yang digunakan dalam menentukan bilangan kromatik. Proposisi 2.1[7] Jika adalah sebuah graf yang memiliki k simpul yang saling bertetangga maka . Berdasrkan proposisi diatas, dapat diperoleh keterkaitan antara simpul-simpul yang saling bertetangga dengan bilangan kromatiknya, untuk hubungan antara simpul-simpul yang tidak saling bertetangga dengan bilangan kromatiknya ditunjukkan dalam proposisi berikut ini. Proposisi 2.2[7] Jika adalah sebarang graf dengan adalah order dari graf dan adalah independence number, maka

Dalam teorema berikut ini akan ditunjukkan keterkaitan antara bilangan kromatik suatu graf dengan subgrafnya. Teorema 2.1[7] Jika adalah subgraf dari graf , maka berlaku .

3

Dalam pembahasan teori graf, dikenal beberapa algoritma yang digunakan untuk mewarnai sebuah graf sedemikian hingga tidak terdapat sisi yang bertetangga memiliki warna yang sama. Salah satunya adalah algoritma Welch-Powell. Algoritma Welch-Powell ini dapat digunakan untuk mewarnai sebuah graf secara efisien. Algoritma ini tidak selalu memberikan jumlah warna minimum yang diperlukan untuk mewarnai G, namun algoritma ini cukup praktis digunakan dalam pewarnaan simpul suatu graf. Oleh karena itu, algoritma Welch-Powell hanya dapat menentukan batas atas warna [8]. Adapun langkah-langkah algoritma tersebut adalah sebagai berikut : a) Urutkan simpul pada graf secara menurun berdasarkan derajat. b) Gunakan warna baru untuk mewarnai simpul pertama dalam barisan dan simpul yang tidak bertetangga dengan simpul tersebut. c) Hapus simpul yang telah diwarnai dari barisan dan urutkan kembali simpul-simpul pada graf secara menurun berdasarkan derajat. d) Kembali ke langkah b) hingga semua simpul telah diwarnai. Berikutnya, di bawah ini diberikan beberapa proposisi yang berguna dalam menentukan bilangan kromatik dari graf hasil amalgamasi yang dilakukan dalam penelitian ini. Proposisi 2.3[7] Sebuah graf bipartite memiliki , kecuali jika tidak memiliki sisi. Proposisi 2.4[7] Sebuah graf siklus order genap memiliki , dengan anggota bilangan asli.. Proposisi 2.5[7] Sebuah graf siklus order ganjil memiliki , dengan anggota bilangan asli. Proposisi 2.6[7] Untuk sebuah graf lengkap ber-order , dengan , maka . III. BILANGAN KROMATIK GRAF HASIL AMALGAMASI DENGAN ADALAH ANGGOTA HIMPUNAN BILANGAN ASLI. Teorema 3.1 Diberikan sebuah graf lengkap dan graf siklus dengan . Jika adalah graf hasil amalgamasi dua buah simpul terhubung dari dan , maka bilangan kromatik dari adalah . Bukti : Misalkan graf adalah graf hasil amalgamasi dua simpul dari graf dan , yaitu . Misalkan order dari graf lengkap dan graf siklus . Untuk menentukan batas atas dilakukakan konstruksi. Akan tetapi, karena pada graf terdapat subgraf yang isomorfis dengan graf siklus maka terdapat dua perlakuan untuk mewarnai graf . Perlakuan pertama adalah untuk genap dan kedua adalah untuk ganjil. Untuk perlakuan pertama yaitu untuk genap dilakukan konstruksi sebagai berikut.

JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 2337-3520 (2301-928X Print)

Gambar 6 Pewarnaan Graf dengan Adapun untuk langkah kedua yaitu untuk dilakukan konstruksi sebagai berikut.

Gambar 7 Pewarnaan Graf

dengan

4

genap. ganjil Gambar 8 Pewarnaan graf

ganjil.

Walaupun pada konstruksi di atas terdapat dua perlakuan, akan tetapi sebagaimana yang telah ditunjukkan pada Gambar 6 dan 7 bahwa pada graf terdapat subgraf yang isomorfis dengan graf lengkap , sehingga graf dapat diwarnai dengan warna dan tidak terdapat dua simpul saling bertetangga yang memiliki warna sama. Dengan demikian diperoleh bahwa graf merupakan graf denagn -coloring yang artinya atau dengan kata lain batas atas dari adalah . Selanjutnya, karena telah diketahui bahwa pada graf terdapat subgraf yang isomorfis dengan graf lengkap sehingga dengan memanfaatkan Teorema 2.1 diperoleh . Sementara itu diperoleh dari Proposisi 2.6 bahwa sehingga . Dengan kata lain batas bawah dari adalah . Karena batas atas dan batas bawah menunjukkan hasil yang sama maka

dengan

.

Berdasarkan konstruksi di atas, karena graf dapat diwarnai dengan atau warna, maka graf merupakan graf dengan -coloring yang berarti Dengan demikian batas atas dari adalah . Selanjutnya, berdasarkan Gambar 8 diketahui bahwa pada graf terdapat subgraf yang isomorfis dengan graf lengkap dan . Sehingga dengan menggunakan Teorema 2.1 diperoleh atau . Sementara itu, dari Proposisi 2.6 diperoleh bahwa dan . Karena maka , ini artinya batas bawah dari adalah . Karena batas atas dan batas bawah menunjukkan hasil yang sama, maka Karena operasi amalgamasi bersifat komutatif, sehingga untuk kasus memiliki hasil yang sama dengan . Kasus 3 : Misalkan . Untuk menentukan dilakukakan konstruksi sebagai berikut,

batas

atas

IV. BILANGAN KROMATIK GRAF HASIL AMALGAMASI DENGAN ANGGOTA HIMPUNAN BILANGAN ASLI

Teorema 4.2 Diberikan sebuah graf kincir dengan dan . Jika adalah graf hasil amalgamasi dua buah simpul terhubung dari graf kincir dan yang berbeda, maka bilangan kromatik dari adalah . Bukti : dalam menentukan bilangan kromatik terdapat 2 kasus yang berlaku. Kasus 1 : Misalkan dengan adalah bilangan bulat positif. Untuk menentukan batas atas dilakukakan konstruksi sebagai berikut,

Gambar 10 Pewarnaan graf

dengan

.

Berdasarkan konstruksi di atas, karena maka diperoleh bahwa graf adalah graf dengan coloring, ini berarti . Oleh karena itu batas atas dari adalah . Selanjutnya, berdasarkan Gambar 10 diketahui bahwa pada graf terdapat subgraf yang isomorfis dengan graf lengkap dan . Sehingga dengan menggunakan Teorema 2.1 didapat atau . Sementara itu, dari Proposisi 2.6

JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 2337-3520 (2301-928X Print) diperoleh bahwa dan . Karena maka . Dengan kata lain, batas bawah dari adalah . Karena batas atas dan batas bawah menunjukkan hasil yang sama maka V. SIMPULAN Berdasarkan analasis yang telah dilakukan untuk menentukan bilangan kromatik, dapat diambil beberapa kesimpulan bahwa bilangan kromatik graf hasil amalgamasi adalah . Sedangkan bilangan kromatik graf hasil amalgamasi adalah . DAFTAR PUSTAKA [1] Alauddin, Bilangan Kromatik Pada Graf Prisma, Tesis, Jurusan Matematika FMIPA Institut Teknologi Sepuluh Nopember. Surabaya (2009). [2] Gross, J.L, dkk, W.-K. Chen, “Genus Distribution of Graph Amalgamations: Pasting at Root-Vertices”.Ars Combinatorica. Vol 94 (2010) 33-353 [3] Chartrand, G dan L. Lesniak, Graphs and Digraphs, third edition, Chapman & Hall/CRC (1996). [4] Vasudev, C. (2006). Graph Theory with Apllication. New Age International (P) Limited, Publisher. [5] Wilson, R.J. (1998). Introduction to Graph Theory, fourth edition. Longman. [6] Capobianco, M dan John, C.M. (1978). Examples and Counterexamples in Graph Theory.North-Holland. [7] Gross, J. L dan Jay Yellen. (2006). Graph Theory and Its Applications, 2nd edition. Chapman & Hall/CRC. [8] As’ad, N. (2008). “Aplikasi Pewarnaan Graf pada Pemecahan Masalah Penyusunan Jadwal”. Makalah Striktur Diskrit, Vol.1, No.38.

5