5.2 Fuad Adi Saputra - Bilangan Rainbow Connection dari Hasil Operasi Penjumlahan dan Perkalian Kartesius Dua BILANGAN RAINBOW CONNECTION DARI HASIL OPERASI PENJUMLAHAN DAN PERKALIAN KARTESIUS DUA GRAF Fuad Adi Saputra Mahasiswa Jurusan Matematika UIN Maulana Malik Ibrahim Malang e-mail: tee_fu@yahoo.com ABSTRAK Graf � dengan pewarnaan sisi disebut pelangi sisi terhubung, jika setiap titik pada graf � dihubungkan oleh lintasan yang memiliki sisi-sisi dengan warna yang berbeda. Rainbow connection pada graf � yang terhubung, disimbolkan oleh ����� yaitu bilangan terkecil dari warna yang dibutuhkan untuk membuat graf � menjadi pelangi sisi terhubung. Sedangkan graf � dengan pewarnaan titik adalah pelangi titik terhubung, jika setiap titik pada graf � dihubungkan oleh lintasan yang memiliki titik-titik interior dengan warna yang berbeda. Rainbow vertex-connection pada graf � yang terhubung disimbolkan oleh ������ yaitu bilangan terkecil dari warna yang dibutuhkan untuk membuat graf � menjadi pelangi titik terhubung. Penelitian ini menganalisis besarnya bilangan ����� dan ������ dari graf hasil penjumlahan dan perkalian kartesius dua sebarang graf. Penjumlahan dua graf ��dan �� yang dinotasikan � �� �� mempunyai himpunan titik ���� ����� � ����� dan himpunan sisi ��� ���� � ���� � ���|� � �������� � � ������. Bilangan rainbow connection dari graf � adalah: 1) ����� 1, �� dan �� adalah graf komplit, dan 2) ����� � 2, ��atau �� adalah bukan graf komplit sedangkan bilangan rainbow vertex-connection dari graf � adalah: ������ �0, ��dan �� adalah graf komplit1, ��atau �� adalah bukan graf komplit � Graf � hasil kali kartesius adalah graf yang dinotasikan � �� �� dan mempunyai titik ���� ����� �����, dan dua titik ���,��� dan ���,��� dari graf � terhubung langsung jika dan hanya jika �� �� dan ���� � ���� atau �� �� dan ���� � ����. Bilangan rainbow connection dari graf � adalah: �"�# ���� �"�# ���� $ ����� $ ������ ������ sedangkan bilangan rainbow vertex- connection dari graf � adalah: �"�# ���� �"�# ���� % 1 $ ������ $ ������� ������� 1 Kata kunci: Graf Penjumlahan, Graf Perkalian Kartesius, Rainbow Connection, Rainbow Vertex-Connection ABSTRACT An edge-colored graph � is rainbow edge-connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph �, denoted by �����, is the smallest number of colors that are needed in order to make � rainbow edge-connected. A vertex- colored graph � is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph �, denoted by ������, is the smallest number of colors that are needed in order to make � rainbow vertex-connected. This research was analysis about number of ����� and ������ from the join and cartesian product of two graphs. The join � �� �� has ���� ����� � ����� and ��� ���� � ���� � ���|� � ����� ��� � � ������. The number of rainbow connection from graph � is: 1) ����� 1, ��and �� are complete graph, and 2) ����� � 2, ��or �� are non-complete graph and then the number of rainbow vertex- connection from graph � is: ������ �0, ��and �� are complete graph1, ��or �� ��' non % complete graph � The cartesian product � �� �� has ���� ����� �����, and two vertices ���,��� and ���,��� of � adjecent if only if either �� �� and ���� � ���� or �� �� and ���� � ����. The number of rainbow connection from graph � is: �"�# ���� �"�# ���� $ ����� $ ������ ������ and then the number of rainbow vertex-connection from graph � is: �"�# ���� �"�# ���� % 1 $������ $ ������� ������� 1 Keywords: Cartesian Product, Join Graph, Rainbow Connection, Rainbow Vertex-Connection Fuad Adi Saputra 126 Volume 2 No. 3 November 2012 PENDAHULUAN Matematika merupakan raja dan pelayan bagi disiplin ilmu lain atau pun dalam lini kehidupan. Teori graf merupakan salah satu cabang matematika yang penting dan banyak manfaatnya karena teori-teorinya dapat diterapkan untuk memecahkan masalah dalam kehidupan sehari-hari. (Purwanto, 1998:1). Graf G adalah pasangan himpunan (V, E) dengan V adalah himpunan tidak kosong dari obyek-obyek yang disebut sebagai titik dan E adalah himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di V yang disebut sebagai sisi. Himpunan titik di G dinotasikan dengan V(G) dan himpunan sisi dinotasikan dengan E(G) (Chartrand dan Lesniak, 1986: 4). Pewarnaan pada graf � adalah pemetaan warna-warna ke titik atau sisi dari � sedemikian hingga titik atau sisi yang terhubung langsung mempunyai warna-warna yang berbeda. Dalam teori graf konsep pewarnaan terus mengalami perkembangan, salah satunya adalah tentang rainbow connection. Rainbow connection dibagi menjadi 2 jenis, yang pertama adalah pelangi sisi terhubung (rainbow edge-connected) yang didefinisikan sebagai pewarnaan sisi pada graf � jika setiap titik pada graf � dihubungkan oleh lintasan yang memiliki sisi-sisi dengan warna yang berbeda, sedangkan yang kedua adalah pelangi titik terhubung (rainbow vertex- connected) yang didefinisikan sebagai pewarnaan titik pada graf � jika setiap titik pada graf � dihubungkan oleh lintasan memiliki titik-titik interior dengan warna yang berbeda. Bilangan rainbow connection pada graf terhubung disimbolkan oleh ����� yaitu bilangan warna terkecil pada sisi yang dibutuhkan untuk membuat � menjadi pelangi sisi yang terhubung. Bilangan rainbow vertex-connection pada graf terhubung disimbolkan oleh ������ yaitu bilangan warna terkecil pada titik yang dibutuhkan untuk membuat � menjadi pelangi titik terhubung (Krivelevich dan Yuster, 2010:1) Jurnal yang ditulis oleh Michael Krivelevich dan Raphael Yuster (2010) menjelaskan mengenai bilangan rainbow connection yang dibangun oleh derajat terkecil dari suatu graf umum. Mereka mengembangkan dari kajian yang ditulis oleh Y. Caro, A. Lev, Y. Roditty, Z. Tuza, dan R. Yuster (2008) dalam jurnalnya yang berjudul On Rainbow Connection. Dalam jurnal On Rainbow Connection hasil dari bilangan rainbow connection ����� dan ������ masih dibatasi oleh suatu variabel yang belum jelas, misalkan ����� $ て�/*, dimana + adalah variabel. Kemudian oleh Krivelevich dan Yuster dikembangkan lagi dan berhasil menentukan nilai variabelnya menjadi ����� $ 20�/* sehingga batas nilai + menjadi lebih jelas. Selain itu juga dijelaskan bahwa bilangan ����� ��"�#��� Penelitian yang dilakukan oleh Krivelevich dan Yuster menggunakan objek graf yang umum. Sedangkan untuk graf dari hasil operasi belum diteliti, khususnya pada operasi penjumlahan dan perkalian kartesius, sehingga perlu dilakukan penelitian lagi untuk objek graf tersebut. KAJIAN TEORI 1. Graf Graf G adalah pasangan himpunan (V,E) dengan V adalah himpunan tidak kosong dari obyek-obyek yang disebut sebagai titik, dan E adalah himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di V yang disebut sebagai sisi. Himpunan titik di G dinotasikan dengan V(G) dan himpunan sisi dinotasikan dengan E(G). 2. Adjacent dan Incident 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), u dan e serta v dan e disebut terkait langsung (incident). Untuk selanjutnya, sisi e = (u,v) akan ditulis e = uv. Derajat titik v di graf G, ditulis degG (v), adalah banyaknya sisi di G yang terkait langsung dengan v (Chartrand dan Lesniak, 1986:4). Contoh: Gambar 2.1 Graf G Gambar 1. Contoh adjacent dan incident Dari Gambar 1 titik v4 dan sisi e2, e3 dan e4 adalah terkait langsung. Sedangkan titik v3 dan v4 adalah terhubung langsung tetapi v3 dan v2 tidak. 3. Graf Terhubung Suatu jalan (walk) u-v pada graf G adalah barisan berhingga (tak kosong) W : u = u0, e1, u1, e2, . . ., un-1, en, un = v yang berselang seling antara titik dan sisi, yang dimulai dari titik u dan diakhiri dengan titik v, dengan iii uue 1−= untuk i = 1, 2, . . ., n adalah sisi di G. u0 disebut titik awal, un disebut titik akhir, u1, u2, ..., un-1 disebut titik internal, dan n menyatakan panjang dari W (Chartrand dan Lesniak, 1986:26). Jalan u-v yang semua sisinya berbeda disebut trail u-v. Jalan u-v yang semua sisi dan titiknya berbeda disebut lintasan (path) u-v. P : u 4v 3v 1v 2v e3 e2 e4 e1 Bilangan Rainbow Connection dari Hasil Operasi Penjumlahan dan Perkalian Kartesius Dua Graf Jurnal CAUCHY – ISSN: 2086-0382 127 = u0, e1, u1, e2, . . ., un-1, en, un = v, u0 disebut titik awal, un disebut titik akhir. Sedangkan u1, u2, ..., un- 1 disebut titik internal, dan n menyatakan panjang dari P. Dengan demikian, semua lintasan adalah trail. Graf lintasan dengan � titik dinotasikan dengan ,- (Chartrand dan Lesniak, 1986:26). Contoh: G: Gambar 2. Graph Terhubung Dari graf di atas v1, e1, v2, e5, v5, e6, v4, e4, v2, e2, v3 adalah trail, sedangkan v1, e1, v2, e5, v5, e6, v4 adalah lintasan. Misalkan u dan v titik berbeda pada graf G. Maka titik u dan v dapat dikatakan terhubung (connected), jika terdapat lintasan u–v di G. Sedangkan suatu graf G dapat dikatakan terhubung (connected), jika untuk setiap titik u dan v di G terhubung (Chartrand dan Lesniak, 1986:28). Misalkan u dan v titik berbeda pada graf G, maka jarak antara dua titik di � adalah panjang lintasan terpendek antara kedua titik tersebut yang dinotasikan dengan �"./0��,��. Sedangkan eksentrisitas titik � � ���� adalah '����� max ��"./0��,��:� � ����. Radius dari � adalah ���� min �'�����:� � ����� dan diameter dari � adalah �"�#��� max �'�����:� � ����� (Chartrand dan Lesniak, 1986:29). 4. Operasi pada Graf Penjumlahan dua graf ��dan �� yang dinotasikan � �� �� mempunyai himpunan titik ���� ����� � ����� dan himpunan sisi ��� ���� � ���� � ���|� � �������� � �������(Chartrand dan Lesniak, 1986: 11). Perhatikan contoh di bawah ini. G1: G2: G: Gambar 3. Penjumlahan Graf � �� �� Hasil kali kartesius adalah graf yang dinotasikan � �� �� dan mempunyai titik ���� ����� �����, dan dua titik ���,��� dan ���,��� dari graf � terhubung langsung jika dan hanya jika �� �� dan ���� � ���� atau �� �� dan ���� � ����(Chartrand dan Lesniak, 1986: 11). Perhatikan contoh berikut, G1: G2: G1 x G2: Gambar 4. Graf Hasil Kali Kartesius 5. Jenis Graf a. Graf komplit (Complete Graph) adalah graf dengan setiap pasang titik yang berbeda dihubungkan langsung oleh satu sisi. Graf komplit dengan � titik dinyatakan dengan Kn (Purwanto, 1998:21). b. Graf bipartisi komplit (complete bipartite graph) adalah graf bipartisi dengan himpunan partisi X dan Y sehingga masing-masing titik di X dihubungkan dengan masing-masing titik di Y oleh tepat satu sisi. Jika |X| = m dan |Y| = n, maka graf bipartisi tersebut dinyatakan dengan Km,n. (Purwanto, 1998:22). c. Graf sikel Cn adalah graf terhubung n titik yang setiap titiknya berderajat 2. Misal graf sikel Cn mempunyai himpunan titik V(Cn) = , maka graf tersebut mempunyai himpunan sisi E(Cn) = dimana untuk setiap i=1,2,…,n. d. Graf roda adalah graf yang dibentuk dari operasi penjumlahan antara graf sikel (+-) dan graf komplit dengan satu titik (5-�. Graf roda dinotasikan dengan 6- dan � � 3 (Harary, 1969:46) e. Graf kipas dibentuk dari penjumlahan graf komplit (5�� dan graf lintasan (,-� yaitu 8- 5� ,-. Dengan demikian graf kipas mempunyai (� 1� titik dan (2� % 1) sisi ( Gallian, 2007: 16) f. Graf Kipas Ganda dibentuk dari penjumlahan antara gabungan dua graf komplit (5�� dan graf lintasan (,-� yaitu 〰8- 25� ,-. Dengan demikian graf kipas mempunyai (� 2� titik dan (3� % 1) sisi. g. Graf tangga yang dinotasikan sebagai 9- adalah suatu graf yang dibentuk dari operasi hasil kali kartesius antara graf lintasan dengan dua titik dan graf lintasan dengan n titik yaitu 9- ,�: ,- (Galian, 2007:12) 6. Pewarnaan Graf Pewarnaan titik dari graf G adalah suatu proses pemberian warna pada titik-titik suatu graf sehingga tidak ada dua titik yang terhubung langsung pada graf tersebut berwarna sama. Graf },...,,{ 21 nvvv },...,,{ 21 neee 1+= iii vve v1 v2 v3 e1 e2 e5 v5 v4 e6 e3 e4 u u v v v v v v u u (u2,v2) (u1,v2) (u1,v3) (u2,v3) (u1,v1) (u2,v1) vv vu u Fuad Adi Saputra 128 Volume 2 No. 3 November 2012 G berwarna n jika terdapat pewarnaan dari G yang menggunakan n warna (Chartrand dan Lesniak, 1986:271). Suatu pewarnaan sisi-k untuk graf G adalah suatu penggunaan k warna untuk mewarnai semua sisi di G sehingga setiap pasang sisi yang mempunyai titik persekutuan diberi warna yang berbeda. Jika G mempunyai pewarnaan sisi-n, maka dikatakan sisi-sisi di G diwarnai dengan n warna. Indeks kromatik G dinotasikan dengan adalah bilangan n terkecil sehingga sisi di G dapat diwarna dengan n warna (Purwanto, 1998:80). 7. Rainbow Connection Pewarnaan sisi pada graf � disebut pelangi sisi terhubung (rainbow edge-connected) jika setiap titik pada graf � dihubungkan oleh lintasan yang memiliki sisi-sisi dengan warna yang berbeda. Rainbow connection pada graf � yang terhubung (connected graph) disimbolkan oleh ����� yaitu bilangan terkecil dari warna yang dibutuhkan untuk membuat graf G menjadi pelangi sisi terhubung (rainbow edge-connected) ( Krivelevich dan Yuster, 2010:1). Lintasan pelangi (rainbow path) adalah lintasan antara dua titik sehingga tidak ada dua sisi pada lintasan tersebut yang memiliki warna yang sama. Jika lintasan pelangi tersebut ada di setiap antara dua titik maka pewarnaan tersebut dinamakan pewarnaan pelangi (rainbow colouring). Sedangkan bilangan minimum pada warna yang diinginkan dinamakan bilangan pelangi yang terhubung (rainbow connection number rc(G)). ( L. Sunil Chandran,2011:3). Pewarnaan titik pada graf � adalah Pelangi titik terhubung (rainbow vertex-connected) jika setiap titik pada graf � dihubungkan oleh lintasan memiliki titik-titik interior dengan warna yang berbeda. Rainbow vertex-connection pada graf � yang terhubung (connected graph) disimbolkan oleh ������ yaitu bilangan terkecil dari warna yang dibutuhkan untuk membuat graf G menjadi pelangi titik terhubung (rainbow vertex- connected) ( Krivelevich dan Yuster, 2010: 2). Misalkan graf � memiliki � titik, maka ����� $ � % 1. Kemudian jika graf sikel +- dengan � � 3 maka ����� $ ;-�<. Sedangkan jika dihubungkan dengan �"�# ���, maka ����� � �"�# ��� dan ������ � �"�# ��� % 1 ( Krivelevich dan Yuster, 2010:1-2). 1 1 1 2 3 3 3 4 5 5 5 ? ? ? @ @ @ A A A Gambar 5. Graf Pelangi Sisi Terhubung dan Pelangi Titik Terhubung Gambar 5 merupakan contoh dari graf pelangi sisi terhubung dan pelangi titik terhubung dengan 5 warna sisi dan 3 warna titik. Pada gambar di atas mempunyai bilangan ����� 5 dan ������ 3. PEMBAHASAN Dalam pembahasan ini, sebelum mengkaji inti permasalahan yaitu mengkaji bilangan rainbow connection dan bilangan rainbow vertex-connection pada graf hasil operasi penjumlahan dan perkalian kartesius dua graf dengan menggunakan sebarang graf, maka akan dibahas terlebih dahulu �����dan ������ dari jenis graf yang dihasilkan oleh operasi penjumlahan dan perkalian kartesius. 1. Bilangan Rainbow Connection pada Jenis Graf Hasil Penjumlahan Pada graf khusus hasil penjumlahan akan diberikan 5 contoh graf yaitu graf komplit, graf bipartisi komplit, graf roda, graf kipas, dan graf Kipas Ganda. a. Graf Komplit Tabel 1. Pola Bilangan ���5-� dan ����5-� No Jenis Graf BC�DE� BFC�DE� 1. 5� 0 0 2. 5� 1 0 3. 5G 1 0 4. 5H 1 0 5. 5I 1 0 6. 5J 1 0 �. 5- 1 0 Dari pola yang ditunjukan oleh bilangan rainbow connection dan bilangan rainbow vertex- connection di atas dapat diperoleh teorema sebagai berikut: Teorema 1 Pada graf komplit 5- banyak titik � � 2, bilangan rainbow connection ���5-� 1, dan bilangan rainbow vertex-connection ����5-� 0. b. Graf Bipartisi Komplit Secara umum graf 5-,K dapat dibentuk menjadi pelangi sisi terhubung hanya dengan menggunakan 4 warna. Hal ini dapat dijelaskan dengan model lintasan antara 2 titik sebagai berikut: �" �" 1 �" 2 �" �" 1 1 3 4 2 �" 2 �" 1 1 3 4 2 dan �" 1 �" 3 �" 2 Gambar 6. Model Lintasan Graf Bipartisi 5K,- )(' Gχ Bilangan Rainbow Connection dari Hasil Operasi Penjumlahan dan Perkalian Kartesius Dua Graf Jurnal CAUCHY – ISSN: 2086-0382 129 Teorema 2 Graf bipartisi komplit 5-,K dengan � $ # dan �,# � L, maka bilangan rainbow connection pada graf 5-,K adalah: ��M5-,KN O #, jika � 12, jika 2- � #3, jika 2- R # $ 3-4, jika lainnya � bilangan rainbow vertex-connection pada graf 5-,K adalah: ����5-,K� 1 Bukti: Graf bipartisi komplit 5-,K terdiri dari 2 partisi, yaitu : dan U, dengan |:| # dan |U| �.Misalkan �V � ��:�, " 1,2, . . . ,# dan �V � ��U�, " 1,2,…,�. Maka setiap dua titik �V dan setiap dua titik �V tidak terhubung langsung, akan tetapi setiap titik �V dengan �V akan dihubungkan dengan satu sisi. Terdapat 4 kasus, yaitu: (i) jika � 1, maka ��M5�,KN #. Andaikan ��M5�,KN R #, maka ada dua sisi di 5�,K yang berwarna sama. Misal��V,��� dan M�X,��N dengan " Y Z. Akibatnya lintasan �V % �X bukan lintasan pelangi karena hanya ada 1 warna. Jadi 5�,K bukan pelangi sisi yang terhubung, jadi ��M5�,KN � #. Karena pewarnaan sisi dengan # warna menghasilkan 5�,K graf pelangi sisi, maka ��M5�,KN $ #. Disimpulkan ��M5�,KN #. (ii) ��M5-,KN 2 jika 2- � #. Akan dibuktikan jika 2- � #, maka ��M5-,KN 2, deg��V� � dan deg��V� # Jika ��M5-,KN 2 maka setiap dua titik, maksimal ada lintasan dengan 2 warna sisi yang berbeda. Untuk itu jika setiap lintasan �V % �X dan setiap lintasan �V % �X terbentuk lintasan pelangi maka susunan warna yang dikenakan pada sisi yang terkait langsung pada �V berbeda dengan �X, begitu juga pada �V berbeda dengan �X. Selanjutnya karena deg��V� � $ deg��V� #, maka jika setiap susunan warna yang dikenakan pada sisi yang terkait langsung dengan �V berbeda, maka susunan warna yang dikenakan pada sisi yang terkait langsung dengan setiap �V juga berbeda. Sehingga cukup dianalisis susunan warna pada sisi yang terkait langsung dengan titik �V � ��:�, " 1,2,…,#. Diketahui ��M5-,KN 2 dan deg��V� , jadi dari 2 warna tersebut akan disusun ke-� tempat dengan perulangan, sehingga diperoleh banyaknya susunan 2� 2� 2G … 2- 2-.Kemudian susunan tersebut diberikan pada setiap titik �V dan �X dengan " Y Z. Jika banyaknya susunan sebanyak 2- lebih banyak dari banyaknya titik �V yang sebanyak #, maka setiap �V mempunyai susunan warna sisi yang terkait langsung berbeda dengan �X. Sehingga lintasan �V % �X akan membentuk lintasan pelangi. Jadi terbukti jika 2- � # maka ��M5-,KN 2. (iii) Jika ��M5-,KN 3 jika 2- $ # $ 3- Akan dibuktikan jika 2- $ # maka ��M5-,KN � 3 dan jika # $ 3- maka ��M5-,KN 3. Ambil ��M5-,KN 2, jika 2- $ # maka akan dibuktikan ada dua titik yang semua lintasannya mempunyai warna sisi yang sama. Banyak susunan warna 2-, artinya ��,��,… . ,��[ susunan warna sisi yang terkait langsung berbeda. Karena 2- $ # maka ada titik ��[\] yang mempunyai susunan warna yang sama dengan �^, dengan 1 $ � $ �# % 2-� dan 1 $ _ $2-.Misalkan ada fungsi �: M5-,KN ` �1,2�, maka ����[\],�V� ���^,�V�, sehingga lintasan �^ % ��[\] tidak membentuk lintasan pelangi, karena semua lintasannya pasti mempunyai warna sisi yang sama. Sehingga terbukti jika 2- $ # maka ��M5-,KN � 3. Sekarang ��M5-,KN 3 dan deg��V� �, jadi dari 3 warna tersebut akan disusun ke-� tempat dengan perulangan, sehingga diperoleh banyaknya susunan 3� 3� 3G … 3- 3-. Kemudian susunan tersebut diberikan pada setiap titik �V dan �X dengan " Y Z. Jika banyaknya susunan sebanyak 3- lebih banyak dari banyaknya titik �V yang sebanyak #, maka setiap �V mempunyai susunan warna sisi yang terkait langsung berbeda dengan �X. Sehingga lintasan �V % �X akan membentuk lintasan pelangi. Jadi terbukti jika # $ 3- maka ��M5-,KN 3. (iv) ��M5-,KN 4, jika lainnya Jika sudah tidak memenuhi semua ketentuan di atas, untuk membentuk graf 5K,- menjadi pelangi sisi terhubung, maka graf 5K,- dapat diwarnai minimal mengunakan 4 warna. Misalkan ada fungsi pewarnaan sisi �: M5-,KN ` �1,2,3,4� maka: �M�V,�XN 1, " Y Z �'�a�� " a��Z"b, Z a��Z"b, �M�V,�XN 3, " Y Z �'�a�� " a'��c,Z a��Z"b, Fuad Adi Saputra 130 Volume 2 No. 3 November 2012 �M�V,�XN 2, " Y Z �'�a�� " a��Z"b, Z a'��c, �M�V,�XN 4, " Y Z �'�a�� " a'��c,Z a'��c, dengan pewarnaan di atas maka setiap dua titik pada graf 5K,- terdapat lintasan dengan warna sisi yang berbeda, sehingga graf 5K,- akan membentuk graf pelangi sisi terhubung, jadi dengan demikian terbukti ��M5K,- N 4. (v) ���M5K,- N 1 Akan dibuktikan ���M5K,- N � 1 dan ���M5K,- N $ 1. Diketahui �"�#M5K,-N 2, sehingga ���M5K,- N � 2 % 1 1. Untuk membuktikan ���M5K,- N $ 1, maka akan dibuktikan bahwa dengan 1 warna titik, dapat membentuk pelangi titik yang terhubung, artinya setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Ambil ���M5K,- N 1,misalkan ada fungsi pewarnaan �:�M5-,KN ` �1� maka: ���V� 1, dan ���V� 1, sehingga setiap lintasan �V % �X akan melewati titik interior �V dimana ���V� 1, sedangkan setiap lintasan �V % �X akan melewati titik interior �V dimana ���V� 1, dengan demikian setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Jadi terbukti ���M5K,- N $ 1. Karena ���M5K,- N � 1 dan ���M5K,- N $ 1, maka ���M5K,- N 1. c. Graf Roda Secara umum graf 6- dapat dibentuk menjadi graf pewarnaan sisi yang terhubung, dengan warna sisi minimal 3, dan juga graf 6- dapat dibentuk menjadi graf pewarnaan titik yang terhubung, dengan warna titik minimal 1, yang ditampilkan dalam model pewarnaan berikut: �1 �1 ��%1 �5 �4 �3 �2 1 2 1 1 2 2 3 1 ? ? ? ? ? ? �� ? 3 3 3 3 3 1 dE: Gambar 7. Graf roda 6- Teorema 3 Graf � adalah graf roda 6- dengan � � L, maka bilangan rainbow connection pada graf � adalah: ���6-� e1, jika � 32, jika 4 $ � $ 63, jika � � 7� bilangan rainbow vertex-connection pada graf 6- adalah: ����6-� 1, jika � � 4 Bukti: Graf roda 6- dengan � � 3adalah graf yang terbentuk dari operasi penjumlahan antara graf sikel (+-) dan graf komplit dengan satu titik (5��. Misalkan �V � ��+-�, " 1,2,…,�, maka �-\1 ��,dan � � ��5��, serta untuk semua �V terhubung langsung dengan �. (i) Jika � 3, akan dibuktikan 6G adalah graf 5H. Untuk semua ��,��,�G � �+G� terhubung langsung dengan �,sehingga diperoleh deg���� deg���� deg��G� deg��� 3. Karena graf 6G dengan 4 titik beraturan%3 maka 6G adalah graf komplit, jadi terbukti dengan � 3 maka ���6G� 1. (ii) Jika 4 $ � $ 6 maka ���6-� 2 Akan dibuktikan ���6-� � 2 dan ���6-� $ 2 Graf 6- dengan 4 $ � $ 6 bukan merupakan graf komplit, karena deg��V� 3 sedangkan jumlah titiknya 5 $ |6-| $ 7, sehingga ����� � 2. Kemudian untuk membuktikan ����� $ 2 maka akan dibuktikan bahwa dengan 2 warna dapat membentuk 6- menjadi pelangi sisi yang terhubung, sehingga setiap dua titik terdapat lintasan dengan warna sisi yang berbeda. Fungsi pewarnaan sisi �: �6-� `�1,2� yang didefinisikan oleh ���V,�� 1 jika " ganjil, ���V,�� 2 jika " genap, ���V,�V\1� 1 jika " ganjil, ���V,�V\1� 2 jika " genap. Setiap lintasan �V % � atau � % �V hanya terdapat satu warna sisi. Kemudian lintasan �V % �X, jika " genap dan �V dan Z ganjil pasti berbentuk lintasan pelangi 2 warna. Sedangkan untuk lintasan �V % �X dengan " dan Zsama-sama genap atau "dan Z sama- sama ganjil. Jika �V % �V\2 maka membentuk lintasan pelangi yang sisi-sinya +-.Tetapi jika lintasan �V % �V\h, dengan 4 $ � $ � % 2 maka � 4, karena � 6 diperoleh 4 $ � $ 6 % 2.Untuk " 1, dengan lintasan �� % �I, maka dapat dibentuk lintasan pelangi melewati titik �J, sedangkan untuk " 2 dengan lintasan �� % �J, maka dapat dibentuk lintasan pelangi melewati titik ��, terbukti setiap dua titik terdapat lintasan dengan warna sisi yang berbeda, sehingga diperoleh ����� $ 2. Jadi terbukti untuk 4 $ � $ 6 maka ����� 2. Bilangan Rainbow Connection dari Hasil Operasi Penjumlahan dan Perkalian Kartesius Dua Graf Jurnal CAUCHY – ISSN: 2086-0382 131 (iii) Jika � � 7 maka ����� 3 Akan dibuktikan ����� � 3 dan ����� $ 3. Dibuktikan ����� $ 3 maka akan dibuktikan bahwa dengan 3 warna dapat membentuk 6- menjadi pelangi sisi yang terhubung, sehingga setiap dua titik terdapat lintasan dengan warna sisi yang berbeda. Jika fungsi pewarnaan sisi �: �6-� ` �1,2,3� yang didefinisikan oleh ���V,�� 1 jika " ganjil, ���V,�� 2 jika " genap, dan ��i� 3,ji � �+-� maka akan membentuk pelangi sisi terhubung, sehingga ���6-� $ 3. Selanjutnya dibuktikan ����� � 3, dari hasil di atas didapat 6- bukan graf komplit sehingga ����� � 2. Ambil ����� 2 Misalkan fungsi pewarnaan sisi �: �6k� `�1,2� didefinisikan �� �,�� 1,maka ���H,�� 2 dan ���I,�� 2,karena tidak mungkin menggunakan lintasan sisi +- yang panjangnya 3. Kemudian jika ���V,�V\1� 1 dengan " ganjil, ���V,�V\1� 2 dengan " genap, maka ���-l1,�� 1 membentuk lintasan pelangi, karena panjang lintasan dengan sisi +- sama dengan 2 dan warnanya berbeda. Tetapi jika ���G,�� 1,lintasan �G % �-l1 warnanya akan sama dan kalau lintasannya menggunakan sisi +k juga tidak mungkin karena panjangnya � 3, jadi haruslah ���G,�� 2. Selanjutnya ����,�� harus sama dengan 1, karena ���I,�� 2, akan tetapi pewarnaan demikian akan membuat antara titik �� dan �-l1 semua lintasannya akan mempunyai warna yang sama, sehingga haruslah ����,�� 3, hal tersebut berlaku jika � � 7 karena lintasan �� % �-l1 minimal mempunyai panjang 3, sehingga ���6-� � 3. Karena ���6-� � 3 dan ���6-� $ 3 maka terbukti ���6-� 3, dengan � � 7. (iv) Jjika � � 4 maka ����6-� 1 Akan dibuktikan ����6-� � 1dan ����6-� $ 1. Diketahui �"�#�6-� 2, sehingga ����6-� � 2 % 1 1. Untuk membuktikan ����6-� $ 1, maka akan dibuktikan bahwa dengan 1 warna titik, dapat membentuk pelangi titik yang terhubung, artinya setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Ambil ����6-� 1, misalkan ada fungsi pewarnaan �:�M5-,KN ` �1� maka: ���� 1, sehingga setiap lintasan �V % �X akan melewati titik interior � dimana ���� 1, sedangkan setiap lintasan �V % � tidak ada titik interior karena terhubung langsung, dengan demikian setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Jadi terbukti ����6-� $ 1. Karena ����6-� � 1dan ����6-� $ 1, maka ����6-� 1. d. Graf Kipas Secara umum graf 8- dapat dibentuk menjadi graf pewarnaan sisi yang terhubung, dengan warna sisi minimal 3, dan juga graf 8- dapat dibentuk menjadi graf pewarnaan titik yang terhubung, dengan warna titik minimal 1, yang ditampilkan dalam model pewarnaan berikut: �1 1 2 �1 �2 �3 �4 ��%1 1 2 2 3 ? ? ? ? ? ? 3 3 3 ? �� 1 mE: Gambar 8. Graf Kipas 8- Teorema 4 Graf kipas 8- dengan � � L, maka bilangan rainbow connection pada graf 8- adalah: ���8-� e1, Z"n� � 22, Z"n� 3 $ � $ 63, Z"n� � � 7� bilangan rainbow vertex-connection pada graf 8- adalah: ����8-� 1, Z"n� � � 2 Bukti: Graf kipas 8- dibentuk dari penjumlahan graf komplit (5�� dan graf lintasan (,-� yaitu 8- 5� ,-. Dengan demikian graf kipas mempunyai (� 1� titik dan (2� % 1) sisi. Misalkan �V � ��,-�, " 1,2,… ,�, dan � � ��5��, serta untuk semua �V terhubung langsung dengan �. (i) Jika � 2, akan dibuktikan 8� adalah graf 5G. Untuk semua ��,�� � �,�� terhubung langsung dengan �,sehingga diperoleh deg���� deg���� deg��� 2. Karena graf 8� dengan 3 titik beraturan%2 maka 8� adalah graf komplit, jadi terbukti dengan � 2 maka ����� 1. (ii) Jika 3 $ � $ 6 maka ����� 2 Akan dibuktikan ����� � 2 dan ����� $ 2. Graf 8- dengan 4 $ � $ 6 bukan merupakan graf komplit, karena deg��V� $ 3 sedangkan jumlah titiknya 4 $ |8-| $ 7, sehingga ����� � 2. Kemudian untuk membuktikan ����� $ 2 maka akan dibuktikan bahwa dengan 2 warna dapat membentuk 8- menjadi pelangi sisi yang terhubung, sehingga setiap dua titik terdapat lintasan dengan warna sisi yang berbeda. Fungsi Fuad Adi Saputra 132 Volume 2 No. 3 November 2012 pewarnaan sisi �: �8-� ` �1,2� yang didefinisikan oleh ���V,�� 1 jika 1 $ " $o-�p, ���V,�� 2 jika o-�p $ " $ �, ���V,�V\1� 1 jika " ganjil, ���V,�V\1� 2 jika " genap. Setiap lintasan �V % � atau � % �V hanya terdapat satu warna sisi. Kemudian lintasan �V % �X, dengan 1 $ " $ ;-�< dan ;-�< $ Z $ � pasti berbentuk lintasan pelangi 2 warna. Sedangkan untuk lintasan �V % �X dengan " dan Z sama-sama 1 $ " $ ;-�< atau dengan " dan Z sama-sama ;-�< $ " $ �. Lintasan terpanjang adalah �� % �h dengan � ;-�< , karena � $ 6 maka lintasan terpanjangnya �� % �G dan �H % �J maka membentuk lintasan pelangi 2 warna yang sisi-sinya anggota ,-, sehingga terbukti setiap dua titik terdapat lintasan dengan warna sisi yang berbeda, sehingga diperoleh ����� $ 2. Jadi terbukti untuk 3 $ � $ 6 maka ����� 2. (iii) Jika � � 7 maka ����� 3 Akan dibuktikan ����� � 3 dan ����� $ 3. Dibuktikan ����� $ 3 maka akan dibuktikan bahwa dengan 3 warna dapat membentuk 8- menjadi pelangi sisi yang terhubung, sehingga setiap dua titik terdapat lintasan dengan warna sisi yang berbeda. Jika fungsi pewarnaan sisi �: �8-� ` �1,2,3� yang didefinisikan oleh ���V,�� 1 jika " ganjil, ���V,�� 2 jika " genap, dan ��i� 3,ji � �,-� maka akan membentuk pelangi sisi terhubung, sehingga ���8-� $ 3. Selanjutnya dibuktikan ���8-� � 3, dari hasil di atas didapat 8- bukan graf komplit sehingga ���8-� � 2.Ambil ���8-� 2 Misalkan fungsi pewarnaan sisi �: �8-� `�1,2� didefinisikan ����,�� 1, maka ����\h,�� 2,dengan 3 $ � $ � % 1 karena tidak mungkin menggunakan lintasan sisi ,- yang panjangnya � 3. Sedangkan jika ���V,�V\1� 1 dengan " ganjil, ���V,�V\1� 2 dengan " genap, maka ����,�� ���G,�� 1 membentuk lintasan pelangi, karena panjang lintasan dengan sisi ,- sama dengan 2 dan warnanya berbeda. Pewarnaan demikian akan membuat antara titik ��\h dengan � 3 dan ��\h dengan � � % 1 semua lintasannya akan mempunyai warna yang sama, karena ���H,�� ���-,�� 2 dan lintasan dengan sisi ,-dengan � � 7 panjangnya lebih dari sama dengan 3, maka terbukti ���8-� � 3. Karena ���8-� � 3 dan ���8-� $ 3 maka terbukti ���8-� 3, dengan � � 7. (iv) Jika � � 2 maka ����8-� 1 Akan dibuktikan ����8-� � 1 dan ����8-� $ 1. Diketahui �"�#�8-� 2, sehingga ����8-� � 2 % 1 1. Untuk membuktikan ����8-� $ 1, maka akan dibuktikan bahwa dengan 1 warna titik, dapat membentuk pelangi titik yang terhubung, artinya setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Ambil ����8-� 1,misalkan ada fungsi pewarnaan �:��8-� ` �1� maka: ���� 1, sehingga setiap lintasan �V % �X akan melewati titik interior � dimana ���� 1, sedangkan setiap lintasan �V % � tidak ada titik interior karena terhubung langsung, dengan demikian setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Jadi terbukti ����8-� $ 1. Karena ����8-� � 1 dan ����8-� $ 1, maka ����8-� 1. e. Graf Kipas Ganda Secara umum graf �8- dapat dibentuk menjadi graf pewarnaan sisi yang terhubung, dengan warna sisi minimal 3, dan juga graf �8- dapat dibentuk menjadi graf pewarnaan titik yang terhubung, dengan warna titik minimal 1, yang ditampilkan dalam model pewarnaan berikut: �1 �2 �1 �3 �4 �6 �5 1 �2 1 1 2 3 3 3 2 2 2 3 3 3 qmE: 2 2 3 3 3 3 1 1 1 2 2 2 2 2 �7 �8 �9 �10 ��%1 �� 2 2 2 2 2 2 Gambar 9. Graf Kipas Ganda �8- Teorema 5 Graf kipas ganda �8- dengan jumlah titik � � 2, maka bilangan rainbow connection pada graf �8- adalah: ����8-� t2, � $ 123, � � 13� bilangan rainbow vertex-connection pada graf �8- adalah: �����8-� 1 Bukti: Graf kipas ganda dibentuk dari penjumlahan antara gabungan dua graf komplit (25�� dan graf lintasan (,-� yaitu �8- 25� ,-. Dengan demikian graf kipas mempunyai (� 2� titik dan (3� % 1) sisi. Bilangan Rainbow Connection dari Hasil Operasi Penjumlahan dan Perkalian Kartesius Dua Graf Jurnal CAUCHY – ISSN: 2086-0382 133 (i) ����8-� 2 jika 2 $ � $ 12. Akan dibuktikan ����8-� � 2, dan ����8-� $ 2. Diketahui �"�# ��8-� 2,karena ����� � �"�#��� maka diperoleh ����8-� � 2. Misalkan �V � ��,-� dengan 2 $ � $ 12, " 1,2,… ,� dan �V � ��25�� dengan " 1,2, terdapat fungsi pewarnaan sisi �: ��8-� `�1,2� yang didefinisikan oleh ���V,��� 1 jika 1 $ " $ ;-�< , ���V,��� 2 jika o-�p R " $12, ���V,�V\1� 1 jika " ganjil, ���V,�V\1� 2 jika " genap, serta ���V,��� 1 jika 1 $ " $ ;-H< dan ;-�< R " $ ;Gu-H <, kemudian ���V,��� 2 jika o-Hp R " $ ;-�< dan ;Gu-H < R " $ �, maka akan membentuk graf �8- menjadi graf pelangi sisi yang terhubung dimana setiap dua titik terdapat lintasan dengan warna sisi yang berbeda. Hal ini membuktikan bahwa ����8-� $ 2, jadi diperoleh dengan 2 $ � $ 12 maka ����8-� 2. (ii) ����8-� 3 jika � � 13. Akan dibuktikan ����8-� � 3, dan ����8-� $ 3. Pertama dibuktikan ����8-� � 3, ambil ����8-� 2, maka dibuktikan dengan menggunakan 2 warna sisi akan ada 2 titik yang semua lintasannya memiliki warna yang sama. Misalkan �V � ��,-� dengan � � 13, " 1,2,…,� dan �V � ��25�� dengan " 1,2, terdapat fungsi pewarnaan sisi �: ��8-� ` �1,2�, akan dibentuk setiap dua titik dihubungkan oleh lintasan pelangi. Misalkan lintasan �V % �X,karena ���V,�V\1� 1 jika " ganjil, ���V,�V\1� 2 jika " genap, maka Z � " 3. Jika ���V,��� 1 agar lintasan �V % �X terbentuk lintasan pelangi maka 〳M�X,��N 2. Kemudian lintasan �V % �X\1, �V % �X\2, �V % �X\3 maka haruslah �M�X\1,��N �M�X\�,��N �M�X\3,��N 2,kemudian untuk lintasan �X % �X\3, karena �M�X,��N �M�X\3,��N 2 dan panjang lintasan dengan sisi ,- sama dengan 3 pasti lintasan tersebut memiliki warna yang sama, sehingga �M�X,��N 1 dan �M�X\3,��N 2. Selanjutnya lintasan �X % �X\4, �X % �X\5, �X % �X\6 maka haruslah �M�X\4,��N �M�X\5,��N �M�X\6,��N 2. Pewarnaan demikian akan membuat lintasan �X\3 % �X\6 memiliki warna sisi yang sama, sehingga dengan 2 warna sisi saja maksimal cukup untuk titik �X sampai �X\5. Begitu juga untuk �V sampai �V\5. Sehingga dengan 2 warna sisi berlaku untuk 12 titik, sedangkan untuk � � 13 tidak bisa membuat �8- menjadi graf pelangi sisi yang terhubung. Jadi terbukti ����8-� � 3. Selanjutnya jika fungsi pewarnaan sisi �: ��8-� ` �1,2,3� yang didefinisikan oleh ���V,��� 1 jika " ganjil, ���V,��� 2 jika " genap, ���V,��� 2 dan ��i� 3,ji � �,-� maka akan membentuk pelangi sisi terhubung, sehingga ����8-� $ 3.Terbukti dengan � � 13 maka ����8-� 3. (iii) Jika � � 2 maka �����8-� 1 Akan dibuktikan �����8-� � 1 dan �����8-� $ 1. Diketahui �"�#��8-� 2, sehingga �����8-� � 2 % 1 1. Untuk membuktikan �����8-� $ 1, maka akan dibuktikan bahwa dengan 1 warna titik, dapat membentuk pelangi titik yang terhubung, artinya setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Ambil �����8-� 1, misalkan ada fungsi pewarnaan �:���8-� ` �1� maka: ����� 1, sehingga setiap lintasan �V % �X akan melewati titik interior �� dimana ����� 1, untuk lintasan �� % �� jika ���V� 1, maka akan melewati titik interior �V dimana ���V� 1, sedangkan setiap lintasan �V % �� dan �V % �� tidak ada titik interior karena terhubung langsung, dengan demikian setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Jadi terbukti �����8-� $ 1.Karena �����8-� � 1 dan �����8-� $ 1, maka �����8-� 1. 2. Bilangan Rainbow Connection pada Jenis Graf Hasil Perkalian Kartesius Pada graf khusus hasil perkalian kartesius akan ditampilkan 1 contoh graf yaitu graf tangga. Graf tangga dibentuk dari perkalian kartesius graf lintasan dengan 2 titik (,�) dengan graf lintasan dengan n titik (,-�. Tabel 2. Pola bilangan ���9-� dan ����9-� No Jenis Graf BC�vE� BFC�vE� 1. 9� 2 1 2. 9G 3 2 3. 9H 4 3 4. 9I 5 4 5. 9J 6 5 �. 9- � � % 1 Teorema 6 Pada graf tangga 9- dengan banyak titik � �2,bilangan rainbow connection ���9-� �,dan Fuad Adi Saputra 134 Volume 2 No. 3 November 2012 bilangan rainbow vertex-connection ����9-� � % 1. Bukti: Graf tangga yang dinotasikan sebagai 9- adalah suatu graf yang dibentuk dari operasi hasil kali kartesius antara graf lintasan dengan dua titik dan graf lintasan dengan n titik yaitu 9- ,�: ,-, dengan �V � ��,-�, " 1,2,…,� dan �V � ��,��, " 1,2. (i) Akan dibuktikan ���9-� � �, dan ����9-� � � % 1. Diketahui graf tangga 9- memiliki panjang diameter �"�#�9-� �. Karena ����� � �"�#��� dan ������ � �"�#��� %1, maka terbukti ����� � � dan ������ �� % 1. (ii) Akan dibuktikan ���9-� $ �, dan ����9-� $ � % 1. Misalkan graf 9- dibagi 2 himpunan titik : dan U. Di mana ��V,��� � ��:� dan ��V,��� � ��U�, terdapat fungsi pewarnaan sisi �: �9G� ` �1,2,…,��, maka: �M��V,���,��V\�,���N ", dengan " �1,2,…,� % 1�, �M��V,���,��V,���N � �M��V,���,��V\�,���N ", dengan " �1,2,…,� % 1�. Pewarnaan sisi demikian akan membuat graf 9- menjadi pelangi sisi yang terhubung, sehingga ���9-� $ �. Selanjutnya misal fungsi pewarnaan titik �w:��9J� ` �1,2,…,� % 1�, maka: �w��V,��� ", dengan " �1,2,…,� % 1�, �w��V,��� ", dengan " �1,2,…,� % 1�, �w��-,��� �w��-,��� 1 Pewarnaan titik demikian akan membuat graf 9- menjadi pelangi titik yang terhubung, sehingga ����9-� $ � % 1. Dari (i) dan (ii) terbukti ���9-� � dan ����9-� � % 1. 3. Bilangan Rainbow Connection pada Sebarang Graf Pada pembahasan ini, telah didapat model atau teorema dari bilangan rainbow connection dan bilangan rainbow vertex- connection pada jenis graf dari hasil penjumlahan dan perkalian kartesius dua graf. Dengan berpikir induktif, maka dari pola-pola tersebut dapat disimpulkan ����� dan ������ pada sebarang graf. Graf disini merupakan sebarang graf berhingga dan jika dioperasikan akan menghasilkan graf yang terhubung. Kemudian dengan berpikir deduktif maka pola-pola bilangan rainbow connection dan bilangan rainbow vertex-connection pada sebarang graf tersebut dapat dibuktikan kebenarannya. a. Bilangan Rainbow Connection pada Graf Hasil Penjumlahan Untuk menentukan bilangan rainbow connection pada graf hasil penjumlahan dengan obyek sebarang graf yaitu dengan cara menganalisis bilangan rainbow connection dari jenis graf hasil penjumlahan dua graf yang telah ditampilkan di atas. Terdapat 5 contoh graf, yaitu graf komplit, graf bipartisi komplit, graf roda, graf kipas, dan graf kipas ganda. Dari kelima graf tersebut dibagi menjadi dua bagian. Bagian pertama adalah graf hasil dari penjumlahan dua graf komplit, sedangkan yang kedua adalah graf hasil dari penjumlahan dua bukan graf komplit. Untuk bagian pertama yaitu graf hasil dari penjumlahan dua graf komplit dicontohkan oleh graf komplit 5-, sedangkan bagian kedua yaitu graf hasil dari penjumlahan dua bukan graf komplit dicontohkan oleh graf bipartisi komplit 5K,- , graf roda 6-, graf kipas 8- dan graf kipas ganda �8-. Graf komplit 5- bilangan ���5-� 1, sedangkan ����5-� 0. Pada graf bipartisi 5K,- komplit bilangan ��M5K,-N � 2 dan ���M5K,-N 1. Untuk graf roda 6- bilangan ���6-� � 2 dan bilangan ����6-� 1. Graf kipas 8- bilangan ���8-� � 2 dan ����8-� 1. Sedangkan pada graf kipas ganda �8- bilangan ����8-� � 2 dan �����8-� 1. Melihat hasil di atas diperoleh suatu teorema bilangan rainbow connection dan bilangan rainbow vertex-connection pada graf hasil dari penjumlahan dua sebarang graf sebagai berikut: Teorema 7 Misalkan graf � adalah graf hasil penjumlahan sebarang graf �� dan sebarang graf ��, maka bilangan rainbow connection dari graf � adalah: ����� 1, �� dan �� adalah graf komplit ����� � 2, ��atau �� adalah bukan graf komplit sedangkan bilangan rainbow vertex-connection dari graf � adalah: ������ e0, ��dan �� adalah graf komplit1, ��atau �� adalah bukan graf komplit � Bukti: Penjumlahan dua graf ��dan �� yang dinotasikan � �� �� mempunyai himpunan titik ���� ����� � ����� dan himpunan sisi ��� ���� � ���� � ���|� � �������� � �������. [1] Jika �� dan �� adalah graf komplit. Misalkan �� 5K dan �� 5- maka banyak titik dari graf � adalah # �. Anggap � � �����dan � � ������, sebelum dioperasikan deg��� # % 1, sedangkan deg��� � % 1. Kemudian dioperasikan penjumlahan antara �� dan ��, diperoleh Bilangan Rainbow Connection dari Hasil Operasi Penjumlahan dan Perkalian Kartesius Dua Graf Jurnal CAUCHY – ISSN: 2086-0382 135 setiap titik pada graf ��terhubung langsung dengan setiap titik pada ��, ����|� � �������� � � �������. Sehingga derajat setiap titik � bertambah sebanyak � menjadi deg��� # � % 1 dan derajat setiap titik � bertambah sebanyak # menjadi deg��� # � % 1. Artinya setiap titik � ,� � ���� beraturan-�# � % 1� sehingga graf � adalah graf 5K\-. Terbukti bahwa graf dari penjumlahan dua graf komplit mempunyai bilangan rainbow connection dan bilangan rainbow vertex-connection berturut-turut sebesar 1 dan 0. [2] Jika �� atau �� adalah graf bukan komplit dan � �� ��. Misalkan �V,�X � �����, dengan ", Z 1,2,…,�, serta ��,�������, dengan �,. 1,2,…,# maka �,�,�,� � ����. Akan dibuktikan �"�#��� 2, ada 3 kemungkinan: 1) �� graf komplit dan �� bukan graf komplit. Jika �� graf komplit maka �"�#���� 1. �� bukan graf komplit maka �"�#���� n � 0. Misalkan lintasan �� % �� adalah lintasan dengan panjang kurang dari sama dengan n. Karena �� terhubung langsung dengan �V dan �� juga terhubung langsung dengan �V. Maka lintasan �� % �� dapat dibuat melewati �V, sehingga panjang lintasannya menjadi 2. Dengan demikian �"�#��� 2. 2) �� bukan graf komplit dan �� graf komplit. Jika �� graf komplit maka �"�#���� 1. �� bukan graf komplit maka �"�#���� b � 0. Misalkan lintasan �V % �X adalah lintasan dengan panjang kurang dari sama dengan b. Karena �V terhubung langsung dengan �� dan �X juga terhubung langsung dengan ��. Maka lintasan �V % �X dapat dibuat melewati ��, sehingga panjang lintasannya menjadi 2. Dengan demikian �"�#��� 2. 3) �� bukan graf komplit dan �� bukan graf komplit. �� bukan graf komplit maka �"�#���� b �0. Misalkan lintasan �V % �X adalah lintasan dengan panjang kurang dari sama dengan b. Karena �V terhubung langsung dengan �� dan �X juga terhubung langsung dengan ��. Maka lintasan �V % �X dapat dibuat melewati ��, sehingga panjang lintasannya menjadi 2. �� bukan graf komplit maka �"�#���� n �0. Misalkan lintasan �� % �� adalah lintasan dengan panjang kurang dari sama dengan n. Karena �� terhubung langsung dengan �V dan �� juga terhubung langsung dengan �V. Maka lintasan �� % �� dapat dibuat melewati �V, sehingga panjang lintasannya menjadi 2. Dengan demikian �"�#��� 2. Dari 3 kasus di atas disimpulkan jika � �� �� kemudian ��atau �� adalah bukan graf komplit maka �"�# ��� 2. Karena ����� � �"�# ��� maka terbukti ����� � 2. Selanjutnya dibuktikan ������ � 1. Akan dibuktikan �����8-� � 1 dan �����8-� $ 1. Diketahui �"�#��� 2, sehingga ������ � 2 % 1 1. Untuk membuktikan ������ $ 1, maka akan dibuktikan bahwa dengan 1 warna titik, dapat membentuk pelangi titik yang terhubung, artinya setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Ambil ������ 1, misalkan ada fungsi pewarnaan �:���� ` �1� maka: ���V� 1, sehingga setiap lintasan �� % �� akan melewati titik interior �V dimana ���� 1, untuk lintasan �V % �X jika ����� 1, maka akan melewati titik interior �V dimana ����� 1, sedangkan setiap lintasan �� % �V tidak ada titik interior karena terhubung langsung, dengan demikian setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Jadi terbukti ������ $ 1. Karena ������ � 1dan ������ $ 1, maka ������ 1. b. Bilangan Rainbow Connection pada Graf Hasil Perkalian Kartesius Untuk menentukan bilangan rainbow connection graf hasil perkalian kartesius dengan sebarang graf yaitu dengan cara menganalisis bilangan rainbow connection dari graf khusus hasil perkalian kartesius dua graf yang dengan contoh graf tangga 9-. Dari hasil pembahasan mengenai bilangan rainbow connection dan bilangan rainbow vertex-connection pada graf tangga 9-, diperoleh bilangan ����� � dan bilangan ������ � % 1. Kedua pola tersebut dipengaruhi oleh bilangan ����� dan ������ dari graf sebelum dioperasikan oleh perkalian kartesius, yaitu ,� dengan ,-. Untuk ����� �, didapat dari penjumlahan antara ����� pada ,� dengan ����� pada ,- yang masing besarnya 1 dan � % 1, dimana penjumlahan kedua akan menghasilkan ����� 1 �� % 1� �. Sedangkan untuk ������ � % 1, didapat dari penjumlahan antara ������ pada ,� dengan ������ pada ,- yang masing besarnya 0 dan � % 2 yang kemudian dijumlah lagi dengan 1, sehingga akan dihasilkan ������ 0 �� % 2� 1 � % 1. Fuad Adi Saputra 136 Volume 2 No. 3 November 2012 Dengan menggunakan contoh sebarang graf lainnya, misalkan graf sikel +H dikalikan kartesius dengan graf bipartisi 5�,�. X Graf +4 ����� = 2 ������ = 1 Graf 51,2 ����� = 2 ������ = 1 Graf +4 x 51,2 ����� = 2 + 2 = 4 ������ = 1 + 1 + 1 = 3 X Gambar 10. Perkalian Kartesius antara Graf +H dengan Graf 5�,� Dari hasil di atas diperoleh bahwa �฀��� pada graf +H 5�,� adalah 4, yang didapat dari penjumlahan ����� pada graf +H yang bernilai 2 dengan ����� pada graf 5�,� yang juga bernilai 2. Sedangkan ������ pada graf +H 5�,� adalah 3, yang didapat dari penjumlahan ������ pada graf +H yang bernilai 1 dengan ������ pada graf 5�,� yang juga bernilai 1 dan ditambah dengan 1. Hasil ini bukanlah suatu kebetulan yang muncul dari contoh-contoh yang telah ditampilkan. Akan tetapi ini adalah suatu pola yang terdapat pada setiap graf dari hasil perkalian kartesius dua graf. Setiap sebarang graf �� jika dikalikan dengan sebarang graf ��, maka hasilnya akan isomorfik dengan graf �� yang titik-titiknya adalah graf ��. Begitu juga sebaliknya hasilnya akan isomorfik dengan graf �� yang titik-titiknya adalah graf ��. Dari contoh di atas, misalnya graf �� adalah graf sikel +H akan dikalikan kartesius dengan �� yaitu graf bipartisi 5�,�. Maka menghasilkan graf dengan graf bipartisi 5�,� akan menggantikan titik-titik pada graf sikel +H. Graf �2 Graf �2 Graf �2 Graf �2 Gambar 11. Graf +H�5�,� Dengan memperhatikan hasil-hasil di atas diperoleh sebagai berikut: Teorema 8 Graf � adalah graf hasil perkalian kartesius sebarang graf terhubung �� dan sebarang graf terhubung ��. Bilangan rainbow connection dari graf � adalah: �"�# ���� �"�# ���� $ �����$ ������ ������ sedangkan bilangan rainbow vertex-connection dari graf � adalah: �"�# ���� �"�# ���� % 1 $ ������$ ������� ������� 1 Bukti: Graf � graf hasil kali kartesius adalah graf yang dinotasikan � ��� �� dan mempunyai titik ���� ������ �����, dan dua titik ���,��� dan ���,��� dari graf � terhubung langsung jika dan hanya jika �� �� dan ���� � ���� atau �� �� dan ���� � ����. �i� Akan dibuktikan jika � ��� �� maka ����� � �"�# ���� �"�# ���� dan ����� $ ������ ������ Diketahui jika � ��� �� maka �"�# ��� �"�# ���� �"�# ����,karena ����� � �"�# ��� maka ����� ��"�# ���� �"�# ����. Selanjutnya misalkan ������ n, artinya dengan bilangan warna sisi minimum sebanyak n akan membuat graf �� menjadi graf pelangi sisi yang terhubung, dan ������ b, artinya dengan bilangan warna sisi minimum sebanyak b akan membuat graf �� menjadi graf pelangi sisi yang terhubung. Kemudian �V,�X � �����, dengan ", Z 1,2,…,�,serta ��,�� � �����, dengan �,. 1,2,…,# maka ��V,���,M�X,��N � ����. Jika lintasan �V % �X membentuk lintasan pelangi dengan � warna sisi maka � $ n, dan jika �� %て� membentuk lintasan pelangi dengan _ warna sisi maka _ $ b. Akan dibuktikan lintasan ��V,��� % ��X,��� membentuk lintasan pelangi dengan warna sisi $ n b. Ada 4 kemungkinan, yaitu: 1) Lintasan ��V,��� % ��X,��� dengan " Z ��� � Y .. Himpunan dari titik-titik ��V,���,��X,��� dengan " Z ��� � Y . akan membentuk graf yang isomorfik dengan graf ��. Dua titik tersebut bisa terhubung langsung dan juga bisa tidak terhubung langsung akan tetapi keduanya pasti dihubungkan oleh lintasan. Karena setiap �� % �� membentuk lintasan pelangi dengan _ warna sisi di mana _ $ b. Maka Lintasan ��V,��� % ��V,��� juga akan membentuk lintasan pelangi dengan _ warna sisi di mana _ $ b. 2) Lintasan ��V,��� % ��X,��� dengan " YZ dan � . Himpunan dari titik-titik ��V,���,��X,��� dengan " Y Z dan � . akan membentuk Bilangan Rainbow Connection dari Hasil Operasi Penjumlahan dan Perkalian Kartesius Dua Graf Jurnal CAUCHY – ISSN: 2086-0382 137 graf yang isomorfik dengan graf ��. Dua titik tersebut bisa terhubung langsung dan juga bisa tidak terhubung langsung akan tetapi keduanya pasti dihubungkan oleh lintasan. Karena setiap �V % �X membentuk lintasan pelangi dengan � warna sisi di mana � $ n. Maka Lintasan ��V,��� % ��V,��� juga akan membentuk lintasan pelangi dengan � warna sisi di mana � $ n. 3) Lintasan ��V,��� % ��X,��� dengan " Z dan � . Jika terdapat dua titik ��V,��� dan ��X,��� dengan " Z dan � ., maka kedua titik tersebut sama, sehingga panjang lintasan sama dengan 0. 4) Lintasan ��V,��� % ��X,��� dengan " YZ dan � Y . Jika terdapat dua titik ��V,��� dan ��X,��� dengan " Y Z dan � Y ., maka kedua titik tersebut tidak mungkin terhubung langsung. Sehingga kemungkinan lintasan dengan panjang sisi terbesar adalah antara kedua titik ini. Lintasan antara kedua titik ��V,��� dan ��X,��� akan membentuk lintasan ��V,��� %M�X,��N % M�X,��N, sehingga terdapat dua langkah. Pertama lintasan ��V,��� %��X,���, lintasan ini akan membentuk lintasan pelangi dengan � warna sisi di mana � $ n. Kemudian ditambah dengan lintasan M�X,��N% M�X,��N, yang membentuk lintasan pelangi dengan _ warna sisi di mana _ $ b. Sehingga Lintasan ��V,��� % ��X,��� akan membentuk lintasan pelangi dengan � _ warna sisi di mana � $ n dan _ $ b. Jadi terbukti ����� � _ $ n b ������ ������. (ii) Akan dibuktikan jika � ��� �� maka ������ � �"�# ���� �"�# ���� % 1 dan ������ $ ������� ������� 1 Diketahui jika � ��� �� maka �"�# ��� �"�# ���� �"�# ����, karena ������ � �"�# ��� % 1 maka ������ ��"�# ���� �"�# ���� % 1. Selanjutnya ������� � �"�# ���� % 1 dan ������� � �"�# ���� % 1, ini berakibat �"�# ���� $ ������� 1 dan �"�# ���� $������� 1. Karena ������ � �"�# ���� �"�# ���� % 1 maka ������ $ ������� 1 ������� 1 % 1 sehingga diperoleh: ������ $ ������� ������� 1. Jadi terbukti, jika � .� � �� maka : �"�# ���� �"�# ���� % 1 $ ������ $������� ������� 1. PENUTUP Berdasarkan hasil pembahasan, maka dapat diambil kesimpulan sebagai berikut : 1. Penjumlahan dua graf ��dan �� yang dinotasikan � �� ��, diperoleh bilangan rainbow connection dari graf � adalah: ����� 1, �� dan �� graf komplit ����� � 2, ��atau �� bukan graf komplit sedangkan bilangan rainbow vertex- connection dari graf � adalah: ������ �0, ��dan �� graf komplit1, ��atau �� bukan graf komplit� 2. Graf � graf hasil kali kartesius adalah graf yang dinotasikan � ��� ��, diperoleh bilangan rainbow connection dari graf � adalah: �"�# ���� �"�# ���� $ �����$ ������ ������ sedangkan bilangan rainbow vertex- connection dari graf � adalah: �"�# ���� �"�# ���� % 1 $ ������$ ������� ������� 1 DAFTAR PUSTAKA [1] Abdullah bin Muhammad. 2005. Tafsir Ibnu Katsir Jilid 8. Bogor: Pustaka Imam As-Syafi’i [2] Abdussakir. 2007. Ketika Kiai Mengajar Matematika. Malang: UIN Malang Press [3] Al-Hifnawi, M. I. 2009. Tafsir Al-Qurthubi. Jakarta: Pustaka Azam. [4] Al-Maraghi, A. M. 1989. Tafsir Al-Maraghi. Semarang: CV. Toha Putra. [5] Al-Qarni , ‘A. 2008. Tafsir Muyassar, jilid 3. Jakarta: Qitshi Press. [6] Alisah, E & Dharmawan, E. P. Filsafat Dunia Matematika. Jakarta: Prestasi Pustaka Publisher. [7] Bondy, J. A & Murty, U.S.R. 1976. Graph Theory With Applications. London: MacMillan Press [8] Chandran, L. Sunil. Rainbow Coloring of Graph. (Online: www.tcs.tifr.res.in/.../ nitk.../combinatore.pdf diakses pada tanggal 31 april 2012) [9] Chartrand, G. & Lesniak, L. 1986. Graphs and Digraphs Second Edition. California: a Division of Wadsworth, Inc. [10] Harary, F. 1969. Graph Theory. Amerika: Addison-Wesley Publishing Company, inc. Fuad Adi Saputra 138 Volume 2 No. 3 November 2012 [11] J. A. Gallian. 2007. A dynamic Survey of Graph Labeling. Electronic journal combinatorics. Dynamic Survey D#56 [12] Krivelevich, M. & Yuster, R. 2010. The Rainbow connection of a graph is (at most) reciprocal to its minimum degree, School of Mathematics, Tel Aviv University. [13] Purwanto. 1998. Matematika Diskrit. Malang: IKIP Malang. [14] Quthb, S. 2004. Tafsir Fi Zhilalil Qur’an. Jakarta: Gema Insani [15] Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster, On rainbow connection, Electronic Journal of Combinatorics 15 (2008), #R57