Graf Garis dari Graf Komplit dan Graf Katerpillar

06.39 |

aduh lama dah gagh menjamah blogh ku nech.....ini qu punya jurnal bikinan qu sendiri semoga bisa bermanfaaaatttt....amien mengenai @graf garis nech temen-temen tentang @Aljabar ......asyiiiiikkk

Graf Garis dari Graf Bintang dan Graf Caterpillar

Abstrak, Teori graf adalah salah satu cabang ilmu matematika yang mengkaji tentang sifat-sifat graf. Teori graf banyak membantu manusia dalam merepresentasikan masalah-masalah yang ada di dunia nyata. Dalam makalah ini penulis bertujuan untuk mencari graf garis dari beberapa macam graf yakni graf lintasan, graf bintang dan graf caterpillar. Berdasarkan hasil dari perhitungan dan percobaan yang dilakukan oleh penulis dalam pembahasan diperoleh rumusan umum untuk graf garis dari graf bintang dengan order n

adalah

dan graf garis dari graf caterpillar dengan q

dengan q adalah badan dan mempunyai 2 kaki pada tiap badannya dengan q adalah bilangan asli diperoleh L(P_q)= K_Pq-1, dimana K_Pq=3(q)+2

Kata kunci : graf, graf garis, graf bintang, graf caterpillar.

Pendahuluan

Menurut penulis matematika adalah ilmu pengetahuan yang mengkaji tentang berbagai hal yang ada disekeliling kita dan dituangkan berdasarkan logika manusia secara konsep matematis. Teori graf merupakan salah satu cabang ilmu matematika yang membahas tentang sifat-sifat graf. Banyak sekali masalah-masalah disekeliling kita yang dapat diselesaikan dengan bantuan graf karena banyak struktur yang bisa direpresentasikan dengan graf, seperti contoh jaringan persahabatan pada facebook yang dapat direpresentasikan dengan graf, dimana simpul-simpulnya adalah para pengguna facebook dan ada sisi-sisi antar penggunanya dengan syarat mereka berteman. Selain itu graf juga dapat diaplikasikan untuk menentukan jarak terpendek, waktu tempuh tersingkat, ongkos termurah antar dua buah kota, pembangunan jembatan dan lain sebagainya.

Dalam Al-qur’an teori graf di singgung dalam suatu konsep, dimana ada titik-titik yang dihubungkan oleh sebuah sisi. Dikatakan dalam Al-Qur’an surat Ar-Ra’d ayat 13 dan An-nisa’ ayat 140 :

tûïÏ%©!$#ur tbqè=ÅÁtƒ !$tB ttBr& ª!$# ÿ¾ÏmÎ/ br& Ÿ@|¹qãƒ šcöqt±øƒs†ur öNåk®5u‘ tbqèù$sƒs†ur uäþqß™ É>$|¡Ïtø:$# ÇËÊÈ

“Dan orang-orang yang menghubungkan apa-apa yang Allah perintahkan supaya dihubungkan, dan mereka takut kepada Tuhannya dan takut kepada hisab yang buruk”. (QS. Ar-Ra’d : 13)

Dalam ayat tersebut jelas dikatakan bahwa Allah perintahkan manusia supaya menghubungkan apa yang dihubungkan, dalam konsep graf, titik-titik yang dihubungkan oleh sisi melambangkan hubungan erat silaturahmi yang ada pada kehidupan manusia, sehingga graf memberikan bentuk kecil suatu kondisi dalam kehidupan manusia.

ô‰s%ur tA¨“tR öNà6ø‹n=tæ ’Îû É=»tGÅ3ø9$# ÷br& #sŒÎ) ÷Läê÷èÏÿxœ ÏM»tƒ#uä «!$# ãxÿõ3ãƒ $pkÍ5 é&t“öktJó¡ç„ur $pkÍ5 Ÿxsù (#rß‰ãèø)s? óOßgyètB 4Ó®Lym (#qàÊqèƒs† ’Îû B]ƒÏ‰tn ÿ¾ÍnÎŽöxî 4 ö/ä3¯RÎ) #]ŒÎ) óOßgè=÷VÏiB 3 ¨bÎ) ©!$# ßìÏB%y` tûüÉ)Ïÿ»uZßJø9$# tûïÌÏÿ»s3ø9$#ur ’Îû tL©èygy_ $·èŠÏHsd ÇÊÍÉÈ

“Dan sungguh Allah telah menurunkan kekuatan kepada kamu di dalam Al Quran bahwa apabila kamu mendengar ayat-ayat Allah diingkari dan diperolok-olokkan (oleh orang-orang kafir), Maka janganlah kamu duduk beserta mereka, sehingga mereka memasuki pembicaraan yang lain. karena Sesungguhnya (kalau kamu berbuat demikian), tentulah kamu serupa dengan mereka. Sesungguhnya Allah akan mengumpulkan semua orang-orang munafik dan orang-orang kafir di dalam Jahannam”. (QS. An-Nisa’ : 40)

Al-Qur’an menganjurkan untuk bersilaturrahmi antar sesama muslim, namun diperjelas dalam Al-Qur’an pula apabila engkau berhubungan / besilaturahim dengan orang kafir maka kalian termasuk pada golongan orang-orang yang tidak di sukai Allah. Hal ini tergambar jelas dalam graf garis bahwasannya sisi-sisi pada sebuah graf akan berubah menjadi titik-titk pada graf garisnya, yang berarti pula hubungan timbal balik yang baik antara seorang muslim akan dibalas dengan baik pula dengan orang muslim.

Sekarang ini teori graf semakin berkembang dan banyak dikaji karena keunikan dan daya tarik yang tinggi dalam membantu menyelesaikan masalah yang ada di sekitar kita. Oleh karena itu penulis tertarik untuk membahas graf garis dari beberapa macam graf yang ada untuk mendapatkan suatu rumusan umum yang diharapkan dapat membantu memecahkan masalah-masalah yang ada di sekitar kita. Berdasarkan latar belakang tersebut penulis dapat merumuskan masalah untuk mencari rumus umum graf garis dari graf bintang dan graf caterpillar.

Kepustakaan

Definisi 1

Graf G adalah pasangan (V(G), E(G)) dengan V(G) adalah himpunan tidak kosong dan berhingga dari objek-objek yang disebut titik, dan E(G) adalah himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di V(G) yang disebut sisi (Abdussakir, 2009: 4).

Definisi 2

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 (Chartrand dan Lesniak dalam Fifi Framelia Nofandika : 2009).

Definisi 3

Misal G adalah graf dengan n titik berlabel 1, 2, 3, ..., n. Matriks adjacency M(G) adalah matriks n x n yang unsur pada baris i dan kolom j adalah banyaknya sisi yang menghubungkan titik i dan j (Wilson dan Watkins dalam Fifi Framelia Nofandika, 2009).

Definisi 4

Graf komplit (Complete Graph) adalah graf dengan setiap pasang titik yang berbeda dihubungkan oleh satu sisi. Graf komplit dengan n titik dinyatakan dengan Kn (Purwanto dalam Fifi Framelia Nofandika, 2009).

Definisi 5

Misal graf G dengan himpunan titik V(G) dan himpunan sisi E(G). Graf garis (Line Graph) L(G) adalah graf dengan

V(L(G)) = E(G)

dan titik di L(G) akan terhubung langsung jika dan hanya jika sisi yang bersesuaian terhubung di G (Abdussakir, 2009: 37).

Definisi 6

Graf bintang (Star Graph) adalah graf bipartit komplit yang berbentuk K1,n, dengan n adalah bilangan asli (Fifi Framelia Nofandika : 2009).

Definisi 7

Graph ulat (caterpillars) adalah suatu garaph terhubung yang jika titik ujungnya dipotong/ dibuang akan membentuk lintasan (Akhmad Fathoni, 2009).

Definisi 8

Misalkan G terhubung, G memuat tepat satu titik ujung yang terkait langsung dengan badan bagian depan dan belakang maka masing-masing bagian disebut dengan kepala dan ekor, sedangkan yang disebut badan yaitu jika berderajat lebih dari 2 atau tepatnya berderajat 3 dan 4, dan disebut kaki jika memuat tepat satu titik ujung yang terkait langsung dengan badan bagian kanan dan kiri (Akhmad Fathoni, 2009).

Kajian Keagamaan

Surat Al-Israa’ ayat 7 dan Ar-Rad ayat 25:

÷bÎ) óOçFY|¡ômr& óOçFY|¡ômr& ö/ä3Å¡àÿRL{ ( ÷bÎ)ur öNè?ù'y™r& $ygn=sù 4 #sŒÎ*sù uä!%y` ß‰ôãur ÍotÅzFy$# (#qä«ÿ½Ý¡uŠÏ9 öNà6ydqã_ãr (#qè=äzô‰u‹Ï9ur y‰Éfó¡yJø9$# $yJŸ2 çnqè=yzyŠ tA¨rr& ;o§tB (#rçŽÉi9tFãŠÏ9ur $tB (#öqn=tã #·ŽÎ6÷Ks? ÇÐÈ

“ Jika kamu berbuat baik (berarti) kamu berbuat baik bagi dirimu sendiri dan jika kamu berbuat jahat, Maka (kejahatan) itu bagi dirimu sendiri, dan apabila datang saat hukuman bagi (kejahatan) yang kedua, (kami datangkan orang-orang lain) untuk menyuramkan muka-muka kamu dan mereka masuk ke dalam mesjid, sebagaimana musuh-musuhmu memasukinya pada kali pertama dan untuk membinasakan sehabis-habisnya apa saja yang mereka kuasai.” (QS. Al-Israa’ :7)

tûïÏ%©!$#ur tbqàÒà)Ztƒ y‰ôgtã «!$# .`ÏB Ï‰÷èt/ ¾ÏmÉ)»sV‹ÏB šcqãèsÜø)tƒur !$tB ttBr& ª!$# ÿ¾ÏmÎ/ br& Ÿ@|¹qãƒ tbrß‰Å¡øÿãƒur ’Îû ÇÚö‘F{$# y7Í´¯»s9'ré& ãNßgs9 èpoY÷è¯=9$# öNçlm;ur âäþqß™ Í‘#¤$!$# ÇËÎÈ

“Orang-orang yang merusak janji Allah setelah diikrarkan dengan teguh dan memutuskan apa-apa yang Allah perintahkan supaya dihubungkan dan Mengadakan kerusakan di bumi, orang-orang Itulah yang memperoleh kutukan dan bagi mereka tempat kediaman yang buruk (Jahannam).” (QS. Ar-rad : 25)

Pembahasan

Teori graf memiliki banyak macam diantaranya graf lintasan, graf bintang, graf sikel, graf caterpillar dan lain sebagainya. Dalam penulisan makalah ini penulis ingin mengetahui perbedaan graf garis dari masing-masing graf. Penulis membatasi tulisan ini untuk menunjukkan graf garis dari graf bintang dan graf caterpillar.

· Graf Garis dari Graf Bintang

Graf bintang dengan order n

dengan n bilangan asli yang dinotasikan dengan Sn.

Gambar graf bintang (

V(G) = {

}

E(G) = {

}

Karena graf

memiliki dua sisi yaitu

dan

sehingga graf

memiliki graf garis. Sisi

dan

akan menjadi titik di dalam graf garis. Matriks keterhubungan sisinya dapat dituliskan sebagai berikut:

Maka graf garisnya L(

dapat digambarkan

2. Graf bintang dengan order n

dengan n bilangan asli yang dinotasikan dengan

Gambar Graf bintang

V(G) = {

}

E(G) = {

}

e₁

e₂

e₃

Karena graf

memiliki sisi yaitu

dan

sehingga graf

memiliki graf garis. Sisi

dan

akan menjadi titik di dalam graf garis. Matriks keterhubungan sisinya dapat dituliskan sebagai berikut:

Maka graf garisnya L(

dapat digambarkan

Graf bintang dengan order n

dengan n bilangan asli yang dinotasikan dengan

Gambar Graf bintang

V(G) = {

}

E(G) = {

}

e₁

e₂

e₃

e₄

Karena graf

memiliki sisi yaitu

dan

sehingga graf

memiliki graf garis. Sisi

dan

akan menjadi titik di dalam graf garis. Matriks keterhubungan sisinya dapat dituliskan sebagai berikut:

Maka graf garisnya L(

dapat digambarkan

4. Graf bintang dengan order n

dengan n bilangan asli yang dinotasikan dengan

Gambar Graf bintang

V(G) = {

}

E(G) = {

}

Karena graf

memiliki sisi yaitu

dan

sehingga graf

memiliki graf garis. Sisi

dan

akan menjadi titik di dalam graf garis. Matriks keterhubungan sisinya dapat dituliskan sebagai berikut:

e₁ e₂ e₃ e₄ e₅

e₁

e₂

e₃

e₄

e₅

Maka graf garisnya L(

dapat digambarkan

Dari beberapa contoh di atas dapat disajikan dalam bentuk tabel

Graf	Graf Garis
S₃	K₂
S₄	K₃
S₅	K₄
S₆	K₅

Berdasarkan tabel di atas, maka dapat diambil kesimpulan sementara bahwa graf garis dari graf bintang (Sn) dengan order n

3 adalah graf komplit (Kn-1) dengan n adalah bilangan asli.

Teorema 1

Suatu graf bintang (Sn) dengan order n (n

3) memiliki graf garis yang berbentuk Graf Komplit (Kn-1) dengan n adalah bilangan asli.

Bukti :

Graf bintang dengan order n

dengan n bilangan asli yang dinotasikan dengan

V(G) = {

}

E(G) = {

…,

}

Karena graf

memiliki sisi yaitu

…,

sehingga graf

memiliki graf garis. Sisi

…,

akan menjadi titik di dalam graf garis. Matriks keterhubungan sisinya dapat dituliskan sebagai berikut:

e₁

e₂

e₃

e₄

e₅

…

e_n

e₁ e₂ e₃ e₄ e₅ … e_n

Maka graf garisnya L(

dapat digambarkan

· Graf Garis dari Graf Caterpillar

Untuk menunjukkan bentuk umum graf garis dari graf caterpillar penulis mengambil bentuk sederhana dari graf caterpillar dimana tiap badan mempunyai 2 kaki, tiap badan pada graf caterpillar dilambangkan dengan q, dan tiap order nya dilambangkan dengan n, dimana n dan q adalah bilangan asli.

Graf caterpillar dengan badan q=1 order n

dengan q dan n bilangan asli yang dinotasikan dengan

Gambar Graf Caterpillar

V(G) = {

}

E(G) = {

}

e₁

e₂

e₃

e₄

Karena graf

memiliki sisi yaitu

dan

sehingga graf

memiliki graf garis. Sisi

dan

akan menjadi titik di dalam graf garis. Matriks keterhubungan sisinya dapat dituliskan sebagai berikut:

e₁ e₂ e₃ e₄

Maka graf garisnya L(

dapat digambarkan

2. Graf caterpillar dengan badan q=2 order n

dengan q dan n bilangan asli yang dinotasikan dengan

Gambar Graf Caterpillar

V(G) = {

}

E(G) = {

}

e₁ e₂ e₃ e₄ e₅ e₆ e₇ e₅

e₁

e₂

e₃

e₄

e₅

e₆

e₇

Karena graf

memiliki sisi yaitu

dan

sehingga graf

memiliki graf garis. Sisi

dan

akan menjadi titik di dalam graf garis. Matriks keterhubungan sisinya dapat dituliskan sebagai berikut:

Maka graf garisnya L(

dapat digambarkan

Graf caterpillar dengan badan q=3 order n

dengan q dan n bilangan asli yang dinotasikan dengan

Gambar Graf Caterpillar

V(G) = {

}

E(G) = {

}

Karena graf

memiliki sisi yaitu

dan

sehingga graf

memiliki graf garis. Sisi

dan

akan menjadi titik di dalam graf garis. Matriks keterhubungan sisinya dapat dituliskan sebagai berikut:

e₁ e₂ e₃ e₄ e₅ e₆ e₇ e₈ e₉ e₁₀ e₅

e₁

e₂

e₃

e₄

e₅

e₆

e₇

e₈

e₉

e₁₀

Maka graf garisnya L(

dapat digambarkan

Dari beberapa contoh di atas dapat disajikan dalam bentuk tabel

Graf	Order n (K_Pq)	Graf Garis
C_p1	5	K₄
C_p2	8	K₇
C_p3	11	K₁₀
Cp_q	3(q)+2	K_Pq-1

Berdasarkan tabel di atas, maka dapat diambil kesimpulan sementara bahwa graf garis dari graf Caterpillar (C_pq) dengan badan q

1 dan tiap badan memiliki 2 kaki dalah graf komplit (K_Pq-1) dengan mencari K_Pq= 3(q)+2 order dari C_pqadalah bilangan asli.

Teorema 1

Suatu graf caterpillar (C_pq) dengan badan q (q

1) dan tiap badan memiliki 2 kaki memiliki graf garis yang berbentuk Graf Komplit (K_Pq-1) dimana K_Pq= 3(q)+2 dengan q adalah bilangan asli.

Bukti

Graf caterpillar dengan badan q dan order n dengan q dan n bilangan asli yang dinotasikan dengan

Untuk order sederhana pada graf caterpillar adalah 5, sehingga n

, untuk mencari order pada setiap badan caterpillar

. Rumus tersebut diperoleh karena pada graf caterpillar sederhana dengan tiap badan 2 kaki membentuk suatu pola barisan bilangan dengan penambahan 3.

V(G) = {

}

E(G) = {

}

e₁ e₂ e₃ e₄ e₅ e₆ e₇ e₈ e₉ e₁₀ e₁₁ … e_n+1e_n+2e_n+3

e₁

e₂

e₃

e₄

e₅

e₆

e₇

e₈

e₉

e₁₀

… e_n+1 e_n+2

e_n+3

Maka graf garisnya L(

dapat digambarkan

Kajian Agama

Ç`¨B 3“y‰tF÷d$# $yJ¯RÎ*sù “Ï‰tGöku‰ ¾ÏmÅ¡øÿuZÏ9 ( `tBur ¨@|Ê $yJ¯RÎ*sù ‘@ÅÒtƒ $pköŽn=tæ 4 Ÿwur â‘Ì“s? ×ou‘Î—#ur u‘ø—Ír 3“t÷zé& 3 $tBur $¨Zä. tûüÎ/Éj‹yèãB 4Ó®Lym y]yèö6tR Zwqß™u‘ ÇÊÎÈ

“Barangsiapa yang berbuat sesuai dengan hidayah (Allah), Maka Sesungguhnya Dia berbuat itu untuk (keselamatan) dirinya sendiri; dan Barangsiapa yang sesat Maka Sesungguhnya Dia tersesat bagi (kerugian) dirinya sendiri. dan seorang yang berdosa tidak dapat memikul dosa orang lain, dan Kami tidak akan meng'azab sebelum Kami mengutus seorang rasul.” (QS. Al-Israa’ :15)

“Barangsiapa yang mengerjakan kebaikan seberat dzarrahpun, niscaya Dia akan melihat (balasan)nya. Dan Barangsiapa yang mengerjakan kejahatan sebesar dzarrahpun, niscaya Dia akan melihat (balasan)nya pula.” (QS. Al-Zalzalah : 7-8)

Graf garis merupakan suatu graf yang menjadikan sisi-sisi pada suatu graf menjadi titik-titik pada bentuk graf lainnya namun tetap terhubung langsung jika dan hanya jika sisi yang bersesuaian terhubung. Hal ini menjadikan keterbalikan dari sisi menjadi titik, dalam Al-Qur’an fenomena seperti ini terlihat dalam surat Al-Israa’ bahwasannya Allah telah berfirman manusia akan menerima apa yang telah dikerjakan sesuai dengan apa yang mereka kerjakan, kebaikan sekecil apapun akan menerima balasannya pula, begitu pula sebaliknya apabila kita melakukan keburukan sekecil apapun akan kembali kepada kita keburukan itu. Ilmu matematika telah memberikan gambaran sedemikian itu untuk menggambarkannya dalam kehidupan dunia, pentingnya berbuat baik terhadap orang lain dengan adanya hubungan harmonis yang dilambangkan dengan simpul-simpul antara titik-titik graf yang disebut sisi. Kemudian adanya graf garis yang menjadikan sisi-sisinya menjadi suatu titik yang akan dihubungkan kembali, sehingga tidak akan terputus hubungan baik antar sesama muslim, namun sebaliknya jika seorang muslim berhubungan dengan orang kafir maka Allah tidak menyukai perbuatan tersebut, karena mereka akan membawamu dalam golongan orang yang dibenci Allah.

Kesimpulan

Dari pembahasan yang telah dipaparkan oleh penulis, penulis dapat menyimpulkan

Bentuk umum Graf Garis dari:

1. Graf Bintang (Sn) dengan order n (n

3) memiliki graf garis yang berbentuk Graf Komplit (Kn-1) dengan n adalah bilangan asli.

2. Graf caterpillar (C_pq) Suatu graf caterpillar (C_pq) dengan badan q (q

1) dan tiap badan memiliki 2 kaki memiliki graf garis yang berbentuk Graf Komplit (K_Pq-1) dimana K_Pq= 3(q)+2 dengan q adalah bilangan asli.

Daftar Pustaka

Abdussakir, Nilna Niswatin Azizah, Fifi Framelia Nofandika. 2009. Teori Graf. Malang: UIN Malang Press.

Fathoni, Akhmad.2009.Pelabelan Super Sisi Ajaib Pada Graf Caterpillar. UIN Malang: Skripsi, tidak diterbitkan.

Framelia, Fifi Nofandika. 2009. Graf Garis (Line Graf) dari Graf Lintasan, Graf Sikel dan Graf Bintang. UIN Malang: Skripsi, tidak diterbitkan.