TITIK DAN SISI PENUTUP MINIMAL PADA GRAF BINTANG ���� ��� DAN GRAF RODA ���� �� Nurul Hijriyah1) dan Wahyu H. Irawan2) 1) Mahasiswa Pascasarjana Jurusan Matematika Universitas Brawijaya Malang 2)Jurusan Matematika UIN Maulana Malik Ibrahim Malang e-mail: 1)n.hijriyah@gmail.com ABSTRAK Suatu titik dan sisi dikatakan saling menutup pada graf G jika titik dan sisi tersebut berinsiden di G. Titik penutup di G merupakan himpunan dari titik-titik yang menutup semua sisi di G dan sisi penutup pada graf G merupakan himpunan sisi-sisi yang menutup semua titik di G. Himpunan titik dan sisi penutup di katakan minimal karena banyaknya anggota paling sedikit atau himpunan yang kardinalnya terkecil. Titik penutup minimal dilambangkan dengan ��� dan sisi penutup minimal dilambangkan dengan 1���. Skripsi ini bertujuan untuk mengetahui rumusan umum titik dan sisi penutup minimal pada graf bintang � �� ��� dan graf roda � �����. Hasil dari penelitian ini adalah titik dan sisi penutup minimal pada graf bintang � �� ��� dan graf roda � �����. Kemudian dirumuskan menjadi suatu lemma dan dibuktikan kebenarannya secara umum. 1. Graf bintang � �� ��� dengan � � �, � � 3. maka rumusan titik dan sisi penutup minimal masing- masing adalah ���� � 1 dan ����� � �, �� �� ���� � dan ��� �� ���� � � �, �� �� ���� � � 12 �� " 1# ; %�&%� � '(�)* 12 ��� " 1� " 1# ; %�&%� � ')�+,- . ��� �� ���� � /01 02 3� 12 � " 1#4 ; %�&%� � '(�)* 12 ��� " 1� " 1# ; %�&%� � ')�+,- . 2. Graf roda � ����� dengan � � �, � � 3. maka rumusan titik dan sisi penutup minimal masing-masing adalah ���� � 5 �6 � " 1 ; %�&%� � '(�)*�6 �� " 1� " 1 ; %�&%� � ')�+,-. dan ����� � 5 �6 � " 1 ; %�&%� � '(�)*�6 �� " 1� ; %�&%� � ')�+,-. �� ������ � 7 8 �6 � " 19 ; %�&%� � '(�)* 8�6 �� " 1� " 19 ; %�&%� � ')�+,-. dan ��� ������ � 7 8�6 � " 19 ; %�&%� � '(�)* �6 �� " 1�# ; %�&%� � ')�+,-. �� ������ :)� ��� �� ���� ;� /01 02 312 �2�� " � " 2�4 ; � '(�)*, � '(�)* 312 �2�� " � " 3�4 ; � ')�+,-, � '(�)* . �� ������ � < ��� " 1�. :)� ��� �� ���� � = >��� " 1�?; � ')�+,- :)� � � �, � � 3. Kata Kunci: Titik Penutup, Sisi Penutup, Minimal, Graf Bintang, Graf Roda PENDAHULUAN Teori graf merupakan salah satu cabang dari ilmu matematika yang masih sangat menarik untuk dibahas karena teori-teorinya masih aplikatif sampai saat ini dan dapat diterapkan untuk memecahkan masalah dalam kehidupan sehari-hari. Dengan mengkaji dan menganalisis model atau rumusan, teori graf dapat diperlihatkan peranan dan kegunaannya dalam memecahkan berbagai masalah. Permasalahan yang dirumuskan dengan teori graf dibuat sederhana, yaitu diambil aspek-aspek yang diperlukan dan dibuang aspek-aspek lainnya (Purwanto, 1998:1). Graf telah dikembangkan sejak tahun 1960- an yang didefinisikan sebagai himpunan titik (vertex) yang tidak kosong dan himpunan garis atau sisi (edge) yang mungkin kosong. Graf itu menghubungkan pasangan dari suatu himpunan, dalam Alquran bisa kita hubungkan dengan Hablum min An-Nas dan Hablum min Allah. Hubungan antara Allah dengan manusia dapat dijelaskan bahwa secara umum seluruh alam ini ta’at dan tunduk kepada Allah SWT, sehingga berfungsi maksimal dan saling memberikan manfaat kepada bagian alam lainnya Titik dan Sisi Penutup Minimal pada Graf Bintang � �� ��� dan Graf Roda � �� ��� Jurnal CAUCHY – ISSN: 2086-0382 97 m v1 m v3 m v4m v5 m v6 m v7 m v8 mv9 m vn m v2 1 v1 1 v3 1 v41 v5 1 v6 1 v7 1 v8 1v9 1 vn 1 v2 2 v1 2 v3 2 v42 v5 2 v6 2 v7 2 v8 2v9 2 vn 2 v2 1 v7 1 v8 1 v9 1 vn 1 v1 1 v2 1 v3 1 v41 v5 1 v6 1 v1 1 v3 1 v41 v5 1 v6 1 v7 1 v8 1v9 1 vn 1 v2 1 v7 1 v8 1 v9 1 vn 1 v1 1 v2 1 v3 1 v41 v5 1 v6 2 v2 2 v3 2 v42 v5 2 v6 2 v7 2 v8 2 v9 2 vn 2 v1 m v4 m v3 m v2 m v1 m vn m v5 m v6 m v7 m v8 m v9 1 vn 1 v1 1 v2 1 v3 1 v41 v5 1 v6 1 v7 1 v8 1 v9 m v1 m vn m v2 m v3 m v4m v5 m v6 m v7 m v8 v9 m 1 vn 1 v1 1 v2 1 v3 1 v41 v5 1 v6 1 v7 1 v8 1 v9 2 vn 2 v1 2 v2 2 v3 2 v42 v5 2 v6 2 v7 2 v8 v9 2 bahkan tahu cara bertasbih dan sholatnya. Secara khusus ternyata seluruh alam semesta ini juga berhijab atau memakai penutup atau pelindung agar berjalan sesuai fungsinya dan selamat dari hal-hal yang membahayakan. Contoh kecil seperti pena tanpa penutup maka tintanya akan menjadi kering, seperti rumah juga perlu adanya penutup yakni atap dan dinding. Suatu titik dan sisi dikatakan saling menutup pada graf G jika titik dan sisi tersebut terkait langsung di G. Titik penutup di G merupakan himpunan dari titik-titik yang menutup semua sisi di G dan sisi penutup pada graf G (tanpa titik terisolasi) merupakan himpunan sisi-sisi yang menutup semua titik di G (Chartrand dan Lesniak, 1986: 243). Berdasarkan latar belakang diatas, maka penelitian ini dapat dirumuskan bagaimana rumus umum titik dan sisi penutup minimal pada graf bintang � �� ��� dan graf roda � �� ���. Tujuan dari penelitian ini adalah untuk mengetahui rumus umum titik dan sisi penutup minimal pada graf bintang � �� ��� dan graf roda � �� ���. Dalam penelitian ini penulis mendefinisikan untuk beberapa istilah yang digunakan agar tidak terjadi penafsiran ganda terhadap istilah-istilah tersebut yaitu, �� adalah graf bintang dengan � titik, selanjutnya �� ditulis sebagai ���, � �� ��� diperoleh dari ��� sebanyak kali dengan @AB @ABC� sisi di � �� ��� , ��� adalah setiap anting graf bintang �� yang diberi � titik, sehingga � �� ��� diperoleh dari ��� sebanyak kali dengan @AB @ABC� sisi di � �� ���. D��1�� ���� � <@A�, @��, … , @��F D��2�� ���� � <@A�, @��, … , @��F G <@A6, @�6, … , @�6F D�� H 1������ G <@AI, @�I, … , @�IF �� : graf bintang dengan � titik. Gambar 1a. Graf Bintang �� Selanjutnya �� ditulis sebagai ��� sehingga, � �� ���: graf bintang ��� sebanyak kali dan @AB @ABC� sisi di� �� ���. Gambar 1b. Graf Bintang � �� ��� ���: setiap anting graf bintang �� yang diberi � titik. Gambar 1. Graf Bintang ��� � �� ���: graf bintang �� sebanyak kali yang setiap anting graf bintang �� yang memiliki � titik dan @AB @ABC� sisi di� �� ���. Gambar 2. Graf Bintang � �� ��� Selanjutnya �� adalah graf roda dengan � titik, selanjutnya �� ditulis sebagai ���, � �� ��� diperoleh dari ��� sebanyak kali dengan @AB @ABC� sisi di � �� ��� ,��� adalah setiap sisi graf roda �� yang diberi � titik, sehingga � �� ��� diperoleh dari ��� sebanyak kali dengan @AB @ABC� sisi di � �� ���. D��1�� ����� � <@A�, @��, … , @��F D��2�� ���� � <@A�, @��, … , @��F G <@A6, @�6, … , @�6F D�� H 1������ G <@AI, @�I, … , @�IF �� ; graf roda dengan � titik Gambar 3. Graf Roda �� Selanjutnya �� ditulis sebagai ���: � �� ���: graf roda ��� sebanyak kali dan @AB @ABC� sisi di � �� ���. Gambar 4. Graf Roda � �� ��� ��� : setiap sisi yang ada pada graf roda �� diberi � titik. Nurul Hijriyah dan Wahyu H. Irawan 98 Volume 2 No. 2 Mei 2012 1 vn 1 v1 1 v2 1 v3 1 v41 v5 1 v6 1 v7 1 v8 1 v9 1 vn 1 v1 1 v2 1 v3 1 v41 v5 1 v6 1 v7 1 v8 1 v9 2 vn 2 v1 2 v2 2 v3 2 v42 v5 2 v6 2 v7 2 v8 2 v9 m vn m v1 m v2 m v3 m v4m v5 m v6 m v7 m v8 m v9 Gambar 5. Graf Roda ��� � �� ���: graf roda ��� sebanyak kali dan @AB @ABC� sisi di� �� ���. Gambar 6. Graf Roda � �� ��� KAJIAN TEORI Covering di dalam Al-Qur’an Dalam Al-Quran kata “penutup” itu diartikan sebagai “Hijab dan Himar” yang memiliki arti sebagai penutup (aurat) baik laki-laki maupun perempuan dan penutup kepala. Memakai hijab yang benar akan mendatangkan kebaikan. Dalam kajian matematika khususnya dalam teori graf ada juga kata penutup yaitu penutup (covering) yang di dalam Alquran Allah SWT berfirman dalam surat al-Ahzab/33 ayat 53: #sŒ Î)uρ £ èδθßϑçGø9r'y™ $Yè≈ tFtΒ �∅èδθ è= t↔ ó¡sù  ÏΒ Ï!#u‘ uρ 5>$pg Éo 4 öΝ à6 Ï9≡sŒ ã� yγ ôÛ r& öΝ ä3 Î/θ è= à) Ï9 £ Îγ Î/θ è= è% uρ 4 $tΒ uρ šχ% x. öΝ à6 s9 β r& (#ρ èŒ ÷σ è? š^θ ß™ u‘ «! $# Iω uρ β r& (# þθ ßs Å3Ζs? … çµy_≡uρ ø— r& . ÏΒ ÿÍν ω ÷è t/ # ´‰ t/ r& 4 ¨βÎ) öΝ ä3 Ï9≡sŒ tβ% Ÿ2 y‰ΖÏã «! $# $̧ϑŠ Ïà tã ∩∈⊂∪ Artinya: “Apabila kamu meminta sesuatu (keperluan) kepada mereka (isteri- isteri Nabi), Maka mintalah dari belakang tabir. cara yang demikian itu lebih suci bagi hatimu dan hati mereka. dan tidak boleh kamu menyakiti (hati) Rasulullah dan tidak (pula) mengawini isteri- isterinya selama-lamanya sesudah ia wafat. Sesungguhnya perbuatan itu adalah Amat besar (dosanya) di sisi Allah”. (QS. al-Ahzab/33: 53) Ini adalah ayat hijab yang di dalamnya mengandung beberapa hukum dan beberapa adat syar’i, di mana sebab turunnya adalah menyetujui perkataan ‘Umar ra. Dan aku berkata: ‘Ya Rasulullah, sesungguhnya orang yang baik dan orang yang buruk, terkadang masuk kepada isteri-isterimu, maka kiranya engkau memberikan mereka hijab, lalu Allah menurunkan ayat hijab. Dalam surat diatas jika di pandang dalam segi matematika yang dimaksud sebagai hijab/khimar adalah suatu covering. Covering pada suatu graf menjadi bukti bahwa dengan mengamati petunjuk Allah, yang berupa penutup (hijab) tersebut dapat diperoleh suatu formula yang luar biasa yang bermanfaat bagi manusia yaitu dalam bentuk penutup. Teori Dasar Definisi 1. Graf J Graf G adalah pasangan himpunan (V,E) dengan V adalah himpunan tidak kosong dan berhingga dari objek-objek yang disebut sebagai titik dan E adalah himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di V yang disebut sebagai sisi (Chartrand dan Lesniak, 1986:4). Definisi 2. Adjacent dan Incident Sisi ( � <%, @F dikatakan menghubungkan titik % dan @. Jika ( � <%, @F adalah sisi pada graf G, maka % dan @ adalah titik yang terhubung langsung (adjacent), sementara itu % dan ( sama halnya dengan @ dan ( disebut terkait langsung (incident). Lebih jauh, jika (� dan (6 berbeda pada � terkait langsung (incident) dengan sebuah titik bersama, maka (� dan (6 disebut sisi adjacent (Chartrand dan Lesniak, 1986:4). Definisi 3. Jalan Misalkan % dan @ (yang tidak harus berbeda) adalah titik pada graf �. Jalan %-@ pada graf � adalah barisan berhingga yang berselang-seling, % � %A, (�, %�, (6, … , %�K�, (�, %� � @ antara titik dan sisi, yang dimulai dari titik % dan diakhiri di titik @, dengan (B � %BK�%B untuk , � 1, 2, … , � (Chartrand dan Lesniak, 1986:26). Definisi 4. Trail Jalan %-@ yang tidak mengulang sisi atau semua sisinya berbeda disebut trail %-@ (Chartrand dan Lesniak, 1986:26). Definisi 5. Lintasan Jalan %-@ yang semua titiknya berbeda disebut path (lintasan) %-@. Dengan demikian, semua lintasan adalah trail. Contoh pada gambar 2.4 yaitu jalan @L, (6, @6, (�, @�, (M, @N, (O, @O, (P, @P adalah lintasan (Chartrand dan Lesniak, 1986: 26). Definisi 6. Sirkuit Trail tertutup (closed trail) dan tak trivial pada graf � disebut sirkuit �. Contoh pada gambar 2.4 yaitu jalan @O, (O, @N, (M, @�, (�, @6, (6, @L, (L, @O adalah sirkuit (Chartrand dan Lesniak, 1986:28). Definisi 7. Sikel Sirkuit @�, @6, . . , @�, @��� � 3� memiliki � titik dengan @B adalah titik-titik berbeda untuk Titik dan Sisi Penutup Minimal pada Graf Bintang � �� ��� dan Graf Roda � �� ��� Jurnal CAUCHY – ISSN: 2086-0382 99 1 R , R � disebut sikel (Cycle). Contoh pada gambar 2.4 yaitu jalan @O, (O, @N, (N, @6, (6, @L, (L, @O adalah contoh sikel (Chartrand dan Lesniak, 1986:28). Definisi 8. Keterhubungan Pasangan titik % dan @ dapat dikatakan terhubung (connected), jika terdapat lintasan %-@ di �. Suatu graf � dapat dikatakan terhubung (connected) jika untuk setiap titik % dan @ di � terhubung (Chartrand dan Lesniak, 1986:28). Definisi 9. Gabungan (union) Gabungan (union) dari �� dan �6, ditulis � � �� G �6, adalah graf dengan D��� � D���� GD��6� dan S��� � S���� G S��6�. Jika graf � merupakan gabungan dari sebanyak � graf T, � � 2, maka ditulis � � �T (Abdussakir, 2009:33). Definisi 10. Penjumlahan (join) Penjumlahan (join) dari �� dan �6, ditulis � � �� " �6, adalah graf dengan D��� � D���� GD��6� dan S��� � S���� G S��6� G <%@|% �D���� .dan @ � D��6�F (Abdussakir, 2009:33). Definisi 11. Graf Bintang Graf bipartisi komplit V�,� disebut graf bintang (star) dan dinotasikan dengan ��. Jadi, �� mempunyai order �� " 1� dan ukuran � (Abdussakir, 2009:21-22). Definisi 12. Graf Roda Graf roda ���� adalah graf yang memuat satu sikel yang setiap titik pada sikel terhubung langsung dengan titik pusat. Graf roda �� diperoleh dengan operasi penjumlahan graf sikel W� dengan graf komplit V�. Jadi, �� � W� "V�, � X 2 (Chartrand dan Lesniak, 1996:8). Penutup pada Graf Definisi 10. Titik Penutup Titik penutup dari graf � adalah Y Z D��� sedemikian sehingga semua titik di Y menutup semua sisi di �, artinya setiap sisi dari � adalah terhubung langsung untuk setidaknya salah satu di titik Y (Bondy dan Murty, 2008:420). Titik penutup minimal dari graf � dinotasikan ��� adalah bilangan kardinal terkecil dari himpunan titik penutup yang paling sedikit. Definisi 11. Sisi Penutup Sisi penutup dari graf � adalah Y Z D��� sedemikian hingga semua sisi di Y menutup semua titik di �, artinya adalah setiap titik di � berinsiden dengan setidaknya satu sisi di Y (Bondy dan Murty, 2008:420). Sisi penutup minimal dari graf � dinotasikan ���� adalah bilangan kardinal terkecil dari himpunan sisi penutup yang paling sedikit. Titik dan Sisi Penutup Minimal pada Graf Lintasan Titik penutup minimal dari graf lintasan [� �� � 2) adalah: �[�� � � 12 �; %�&%� � '(�)*12 �� H 1�; %�&%� � ')�+,- . Sisi penutup minimal dari graf lintasan [� �� � 2) adalah: ��[�� � � 12 �; %�&%� � '(�)*12 �� " 1�; %�&%� � ')�+,- . Titik dan Sisi Penutup Minimal pada Graf Sikel Titik penutup minimal dari graf sikel W� �� � 3) adalah: �[�� � � 12 �; %�&%� � '(�)*12 �� " 1�; %�&%� � ')�+,- . Sisi penutup minimal dari graf sikel W� �� � 3) adalah: ��[�� � � 12 �; %�&%� � '(�)*12 �� " 1�; %�&%� � ')�+,- . PEMBAHASAN Suatu titik dan sisi dikatakan saling penutup pada graf G jika titik dan sisi tersebut inciden di G. Titik penutup di G merupakan himpunan dari titik-titik yang menutup semua sisi di G dan sisi penutup pada graf G (tanpa titik terisolasi) merupakan himpunan sisi-sisi yang menutup semua titik di G. Di katakan minimal karena banyaknya anggota paling sedikit atau himpunan penutup yang kardinalnya terkecil. Titik dan Sisi Penutup pada Graf Bintang �� dan ������\ Perhatikan tabel di bawah ini: Tabel 1. Titik dan Sisi Penutup Minimal pada Graf Bintang � �� ��� Simpul ]���� ]\���� ]����� ��\� ]\����� ��\� S3 1 3 1 � 3 � S4 1 4 1 � 4 � S5 1 5 1 � 5 � S6 1 6 1 � 6 � S7 1 7 1 � 7 � S8 1 8 1 � 8 � S9 1 9 1 � 9 � S10 .. Sn 1 . . 1 10 . . � 1 � . . 10 � . . � � Nurul Hijriyah dan Wahyu H. Irawan 100 Volume 2 No. 2 Mei 2012 Berdasarkan Tabel 1 maka diperoleh lemma berikut: Lemma 1: Titik penutup minimal pada graf bintang �� adalah 1. Bukti: Misal titik pusat adalah @A. Karena semua sisi (B insidensi dengan @A sehingga @A menutup semua sisi di ��, atau @A berinsiden dengan (B �, � 1, 2, … , �� maka @A adalah satu-satunya titik yang menutup semua sisi. Jadi titik penutup minimal graf bintang ���� adalah 1. Lemma 2: Sisi penutup minimal pada graf bintang �� adalah �. Bukti: Misal D���� � <@A, @�, @6, @L, … , @�F. Titik @�, @6, @L, … , @� tidak terhubung langsung tetapi titik @�, @6, @L, … , @� terhubung langsung dengan @A sehingga sisi �@B, @A� menutup titik @B :)� @A �, � 1, 2, … , ��. Maka sisi penutup minimal pada graf bintang �� terbukti sebanyak �. Lemma 3; Titik penutup minimal pada graf bintang � �� ��� adalah . Bukti: Pada graf � �� ��� masing-masing titik pusat yang berurutan adalah terhubung langsung, yaitu �@AB , @ABC��. Dari lemma 1 titik penutup minimal ��� adalah 1. Sehingga diperoleh titik penutup minimal pada graf bintang � �� ��� adalah . Lemma 4 Sisi penutup minimal pada graf bintang � �� ��� adalah � �. Bukti: Pada graf � �� ��� masing-masing titik pusat yang berurutan adalah terhubung langsung, yaitu �@AB , @ABC��. Berdasarkan lemma 2, sisi penutup minimal pada graf bintang �� adalah �. Sehingga diperoleh sisi penutup minimal pada graf bintang � �� ��� adalah � �. Titik dan Sisi Penutup pada Graf Bintang ���� ��� Lemma 5 Titik penutup minimal pada graf bintang � �� ��� adalah: �� ������ ;� 7 8�6 �� " 19 ; %�&%� � '(�)* 8�6 ��� " 1� " 19 ; %�&%� � ')�+,-. Berlaku untuk � � �, � � 3. Bukti: 1. Untuk � genap Ambil @A sebagai titik penutup. Maka anting graf ��� berupa lintasan [�C�, dengan �� " 1� bilangan ganjil. Jadi �[�C�� � �6 �. Karena terdapat sebanyak � anting maka diperoleh ����� � 1 " �6 ���� � �6 �� " 1. 2. Untuk � ganjil Ambil @A sebagai titik penutup. Maka anting graf ��� berupa lintasan [�C�, dengan �� " 1� bilangan genap. Jadi �[�C�� � �6 �� " 1�. Karena terdapat sebanyak � anting maka diperoleh ����� � �6 ��� " 1� " 1. Dari 1 dan 2, karena � �� ��� terdiri dari ��� yang titik pusat berurutan dihubungkan langsung maka titik penutup minimal pada graf bintang � �� ��� ditunjukkan pada gambar 4 sehingga: �� �� ���� ;� � 12 �� " 1# ; %�&%� � '(�)* 12 ��� " 1� " 1# ; %�&%� � ')�+,- . Berlaku untuk � � �, � � 3. Lemma 6 Sisi penutup minimal pada graf bintang � �� ��� adalah: ��� �� ���� ;� 7 � 8�6 � " 19# ; %�&%� � '(�)* 8�6 ��� " 1� " 19 ; %�&%� � ')�+,- . Berlaku untuk � � �, � � 3. Bukti: 1. Untuk � genap Pada graf ��� pandang lintasan 1 anting berikut: @A 1 2 � @6 Gambar 9. Lintasan [�C6 Graf ini berupa [�C6 dengan �� " 2� adalah genap, sehingga ��[�C6� � �6 �� " 2� � �6 � " 1. Dengan mengambil �@A, ��� sebagai sisi penutup. Anting lainnya berupa [�C� dengan �� " 1� adalah ganjil maka ��[�C�� � �6 >�� " 1� " 1? ��6 � " 1. Karena lintasan [�C� sebanyak �� H 1� lintasan maka sisi penutup minimalnya 8�6 � " 19 �� H 1�. Sehingga diperoleh ������ � 8�6 � " 19 " 8�6 � " 19 �� H 1� � 8�6 � " 19 �. 2. Untuk � ganjil Pada graf ��� pandang lintasan 1 anting berikut: @A 1 2 3 � @6 Gambar 10. Lintasan [�C6 Graf ini berupa [�C6 dengan �� " 1� adalah ganjil, maka ��[�C�� � �6 >�2 " 1� " 1? � �6 �� " 3� ��6 �� " 1� " 1. Dengan mengambil �@A, ��� sebagai Titik dan Sisi Penutup Minimal pada Graf Bintang � �� ��� dan Graf Roda � �� ��� Jurnal CAUCHY – ISSN: 2086-0382 101 sisi penutup. Anting lainnya berupa [�C� dengan �� " 1� genap maka ��[�� � �6 �� " 1�. Karena lintasan [� sebanyak �� H 1� lintasan maka sisi penutup minimalnya 8�6 �� " 1�9 �� H 1�. Sehingga diperoleh ������ � �6 �� " 1� " 1 "8�6 � " 19 �� H 1� � �6 ��� " 1� " 1. Dari 1 dan 2, karena � �� ��� terdiri dari ��� yang titik pusat berurutan dihubungkan langsung maka titik penutup minimal pada graf bintang � �� ��� ditunjukkan pada gambar 4 sehingga: ��� �� ���� ;� /01 02 3� 12 � " 1#4 ; %�&%� � '(�)* 12 ��� " 1� " 1# ; %�&%� � ')�+,- . Berlaku untuk � � �, � � 3. Titik dan Sisi Penutup pada Graf Roda � dan ���� �\ Perhatikan tabel di bawah ini: Tabel 2. Titik dan Sisi Penutup Minimal pada Graf Roda � �� ��� Berdasarkan Tabel 2 maka diperoleh lemma berikut: Lemma 9 Titik penutup minimal pada graf roda �� adalah ���� � � 12 � " 1 ; %�&%� � '(�)*12 �� " 1� " 1; %�&%� � ')�+,- . Bukti: Misal @A titik pusat pada �� dan �@�, @6, @L, … , @�� adalah titik pada sikel luar. Karena @A akan menutup semua sisi di selain sikel luar dan �W�� � � 12 � ; %�&%� � '(�)*12 �� " 1�; %�&%� � ')�+,- . Maka diperoleh: ���� � � 12 � " 1 ; %�&%� � '(�)*12 �� " 1� " 1; %�&%� � ')�+,- . Lemma 10: Sisi penutup minimal pada graf roda �� adalah ����� � � 12 � " 1 ; %�&%� � '(�)*12 �� " 1�; %�&%� � ')�+,- . Bukti: Misal @A titik pusat pada �� dan �@�, @6, @L, … , @�� adalah titik pada sikel luar. Ambil �@A, @�� sebagai sisi penutup, maka pada W�: @�, @6, @L, … , @�, @� titik @� sudah tertutup oleh �@A, @��. ��W�� � �6 �, untuk � genap dan tidak terpengaruh oleh tertutupnya @�. ��W�� � �6 �� " 1�, untuk � ganjil dan terpengaruh oleh tertutupnya @�, sehingga harus dikurangi 1. Maka diperoleh: ����� � � 12 � " 1 ; %�&%� � '(�)*12 �� " 1�; %�&%� � ')�+,- . Lemma 11: Titik penutup minimal pada graf roda � �� ��� adalah: �� �� ���� � � 12 � " 1 # ; %�&%� � '(�)* 12 �� " 1� " 1# ; %�&%� � ')�+,- . Bukti: Pada graf � �� ��� masing-masing titik pusat yang berurutan adalah terhubung langsung, yaitu �@AB , @ABC��. Berdasarkan lemma 9, titik penutup minimal pada graf roda �� adalah adalah �6 � " 1; untuk � genap dan �6 �� " 1� " 1; untuk � ganjil. Sehingga diperoleh titik penutup minimal pada graf roda� �� ��� adalah: �� �� ���� � � 12 � " 1 # ; %�&%� � '(�)* 12 �� " 1� " 1# ; %�&%� � ')�+,- . Lemma 12: Sisi penutup minimal pada graf roda � ����� adalah: ��� �� ���� � /01 02 12 � " 1 # ; %�&%� � '(�)* 312 �� " 1�4 ; %�&%� � ')�+,- . Bukti: Pada graf � �� ��� masing-masing titik pusat yang berurutan adalah terhubung langsung, yaitu �@AB , @ABC��. Berdasarkan lemma 10, sisi penutup minimal pada graf roda �� adalah adalah �6 � " 1; untuk � genap dan �6 �� " 1�; untuk � ganjil. Sehingga diperoleh sisi penutup minimal pada graf roda� �� ��� adalah: ��� �� ���� � /01 02 12 � " 1 # ; %�&%� � '(�)* 312 �� " 1�4 ; %�&%� � ')�+,- . Simpul ]� �� ]\� �� ]����� �\� ]\����� �\� W3 3 2 3 � 2 � W4 3 3 3 � 3 � W5 4 3 4 � 3 � W6 4 4 4 � 4 � W7 5 4 5 � 4 � W8 5 5 5 � 5 � W9 6 5 6 � 5 � W10 6 6 6 � 6 � Nurul Hijriyah dan Wahyu H. Irawan 102 Volume 2 No. 2 Mei 2012 1 vn 1 v1 1 v2 1 v3 1 v41 v5 1 v6 1 v7 1 v8 1 v9 1 vn 1 v1 1 v2 1 v3 1 v41 v5 1 v6 1 v7 1 v8 1 v9 1 vn 1 v1 1 v2 1 v3 1 v41 v5 1 v6 1 v7 1 v8 1 v9 Titik dan Sisi Penutup pada Graf Roda ���� �� Lemma 13: Titik penutup minimal pada graf roda � �� ��� adalah: �� �� ���� ;� /0 1 02 312 �2�� " � " 2�4 ; � '(�)* :)� � '(�)* 312 �2�� " � " 3�4 ; � ')�+,- :)� � '(�)* ��� " 1��; %�&%� � ')�+,-, � � �, � � 3 . Bukti: 1. Untuk � genap Pada graf ��� pandang sikel luarnya: Gambar 11. Graf Sikel W���C�� Graf tersebut berupa W���C��. Jika � ganjil maka ��� " 1� adalah ganjil, dan jika �genap maka ��� " 1� adalah genap. Sehingga >W���C��? ��6 ���� " 1� " 1� untuk � ganjil dan >W���C��? ��6 >��� " 1�? untuk � genap. Selanjutnya pandang graf bintang tanpa titik terluarnya: Gambar 12. Graf Bintang ���K� Graf ��� tanpa titik terluar ini sama dengan graf ���K�. Karena � genap maka � H 1 ganjil. Sesuai bukti lemma 5, diperoleh: ����K��: � �6 �>�� H 1� " 1? " 1 � �6 �� " 1 Jadi, �����: � /0 1 02 �6 >��� " 1�? " �6 �� " 1� �6 �2�� " � " 2�; untuk � genap�6 ���� " 1� " 1� " �6 �� " 1� �6 �2�� " � " 3�; untuk � ganjil . 2. Untuk � ganjil Pada graf ��� pandang sikel luarnya: Gambar 13. Graf Sikel Cr�sC�� Graf tersebut berupa W���C��. Karena � ganjil maka �� " 1� genap, sehingga ��� " 1� selalu genap. Jadi >W���C��? � �6 >��� " 1�?. Selanjutnya pandang graf bintang tanpa titik terluarnya: Gambar 14. Graf Bintang ���K� Graf ��� tanpa titik terluar ini sama dengan graf ���K�. Karena � ganjil maka � H 1 genap. Sesuai bukti lemma 5, maka: ����K��: � �6 ��� H 1� " 1 Jadi diperoleh, ����� � 12 >��� " 1�? " 12 ��� H 1� " 1 � �6 �2�� " 2� � �� " 1 Dari 1 dan 2, karena � �� ��� terdiri dari ��� yang titik pusat berurutan dihubungkan langsung maka titik penutup minimal pada graf roda � �� ��� ditunjukkan pada gambar 8 sehingga: �� �� ���� ;� /0 1 02 312 �2�� " � " 2�4 ; � '(�)* :)� � '(�)* 312 �2�� " � " 3�4 ; � ')�+,- :)� � '(�)* ��� " 1��; %�&%� � ')�+,-, � � �, � � 3 . Lemma 14: Sisi penutup minimal pada graf roda � �� ��� adalah: ��� �� ���� ;� /0 1 02 312 �2�� " � " 2�4 ; � '(�)* :)� � '(�)* 312 �2�� " � " 3�4 ; � ')�+,- :)� � '(�)* ���� " 1��; %�&%� � ')�+,-, � � �, � � 3 . Bukti: 1. Untuk � genap Pada graf ��� pandang sikel luarnya: Gambar 15. Graf Sikel W���C�� Graf tersebut berupa W���C��. Jika � ganjil maka ��� " 1� adalah ganjil, dan jika �genap maka ��� " 1� adalah genap. Sehingga 8W�>�"1?9 �12 >�>� " 1? " 1? untuk � ganjil dan 8W�>�"1?9 �12 8�>� " 1?9 untuk � genap. Selanjutnya pandang graf bintang tanpa titik terluarnya: Titik dan Sisi Penutup Minimal pada Graf Bintang � �� ��� dan Graf Roda � �� ��� Jurnal CAUCHY – ISSN: 2086-0382 103 1 vn 1 v1 1 v2 1 v3 1 v41 v5 1 v6 1 v7 1 v8 1 v9 Gambar 16. Graf Bintang ���K� Graf ��� tanpa titik terluar ini sama dengan graf ���K�. Karena � genap maka � H 1 ganjil. Sesuai bukti lemma 6, diperoleh: �����K��: � �6 �>�� H 1� " 1? " 1 � �6 �� " 1 Jadi, ������: � /0 1 02 �6 >��� " 1�? " �6 �� " 1� �6 �2�� " � " 2�; untuk � genap�6 ���� " 1� " 1� " �6 �� " 1� �6 �2�� " � " 3�; untuk � ganjil . 2. Untuk � ganjil Pada graf ��� pandang sikel luarnya: Gambar 17. Graf Sikel W���C�� Graf tersebut berupa W���C��. Karena � ganjil maka �� " 1� genap, sehingga ��� " 1� selalu genap. Jadiá>W���C��? � �6 >��� " 1�?. Selanjutnya pandang graf bintang tanpa titik terluarnya: Gambar 18. Graf Bintang ���K� Graf ��� tanpa titik terluar ini sama dengan graf ���K�. Karena � ganjil maka � H 1 genap. Sesuai bukti lemma 6, maka: �����K��: � 12 ���� H 1� " 1� " 1 Jadi diperoleh, ������ � 12 >��� " 1�? " 12 ���� H 1� " 1� " 1 � ��� " 1�; � � �, � � 3 Dari 1 dan 2, karena � �� ��� terdiri dari ��� yang titik pusat berurutan dihubungkan langsung maka sisi penutup minimal pada graf roda � �� ��� ditunjukkan pada gambar 8 sehingga: ]\>���� ��? ;� /0 1 02� 3\u �u�� " � " u�4 ; � vw�xy zx� � vw�xy � 3\u �u�� " � " {�4 ; � vx�|}~ zx� � vw�xy����� " \��; � vx�|}~, � � �, � � { . PENUTUP Berdasarkan penelitian yang telah dilaksanakan, dapat disimpulkan bahwa: 1. Graf bintang � �� ��� dengan � � �, � � 3. maka rumusan titik dan sisi penutup minimal masing-masing adalah: a. ���� � 1 dan á����� � �. b. �� �� ���� � dan ��� �� ���� � � �. c. �� �� ���� � 7 8�6 �� " 19 ; %�&%� � '(�)* 8�6 ��� " 1� " 19 ; %�&%� � ')�+,-. ��� �� ���� � /01 02 3� 12 � " 1#4 ; %�&%� � '(�)* 12 ��� " 1� " 1# ; %�&%� � ')�+,- . 2. Graf roda � ����� dengan � � �, � � 3. maka rumusan titik dan sisi penutup minimal masing-masing adalah: a. ���� � 5 �6 � " 1 ; %�&%� � '(�)*�6 �� " 1� " 1 ; %�&%� � ')�+,-. ����� � 5 �6 � " 1 ; %�&%� � '(�)*�6 �� " 1� ; %�&%� � ')�+,-. b. �� ������ � 7 8 �6 � " 19 ; %�&%� � '(�)* 8�6 �� " 1� " 19 ; %�&%� � ')�+,-. ��� ������ � /01 02 12 � " 1# ; %�&%� � '(�)* 312 �� " 1�4 ; %�&%� � ')�+,- . c. �� ������: � � 12 �2�� " � " 2�# ; � '(�)*, � '(�)* 12 �2�� " � " 3�# ; � ')�+,-, � '(�)* . ��� ������: � /01 02 312 �2�� " � " 2�4 ; � '(�)*, � '(�)* 312 �2�� " � " 3�4 ; � ')�+,-, � '(�)* . �� ������ � < ��� " 1�. dan ��� �� ���� �= >��� " 1�?; �. ganjil dan � � �, � � 3 DAFTAR PUSTAKA [1] Abdullah Bin Muhammad.2007. Tafsir Ibnu Katsir Jilid 6. Bogor: Pustaka Imam Asy-Syafii [2] Abdussakir, dkk. 2009. Teori Graf. Malang: UIN Press [3] Al-Maragi, Ahmad Musthafa.1992. Tafsir Al- Maraghi Juz 18 dan 22 . Semarang:Toha Putra [4] Al-Qurthubi, Syaikh Imam. 2009. Tafsir Al- Qurthubi. Penj. Fathurrahman Abdul Hamid dkk. Jakarta: Pustaka Azzam Nurul Hijriyah dan Wahyu H. Irawan 104 Volume 2 No. 2 Mei 2012 [5] Balakrishnan.V.K. 1995. Schaum’s Outline of Theory and Problems of Combinatorics. New York: Mc Graw Hill. Inc [6] Chatrand, Gery and Lesniak, Linda. 1986. Graphs and Digraphs Second Edition. California: a Division of Wadsworth.Inc. [7] Gallian, J. A. 2007. "A Dynamic Survey of GraphLabeling.(Online:http//www.Combinat orics.org/Surveys/dr6.pdf). Diakses 11 Oktober 2011 [8] Purwanto. 1998. Teori Graph. Malang: IKIP MALANG [9] Rosen, Kenneth H. 2003. Discrete Mathemathics ang Its Application: Fifth Edition. Singapore: Mc. Graw-Hill [10] Wilson, Robin J dan Watkins. 1990. Graph and Introductory Approach. Singapore: Open Universitycourse. Lembar Kosong (5).pdf 2.Dewan Editor.pdf 0 Lembar Kosong (1).pdf 3. Pengantar Redaksi.pdf Lembar Kosong (6).pdf 4. Daftar Isi.pdf 5.1. Elva Ravita Sari - STUDI TENTANG PERSAMAAN FUZZY _54-65.pdf