Makalah
Teori Graf
Oleh :
Zaitun (19061018)
Eliza Maria (19061030)
Fitri Liani Putri (19061016)
Muhammad Arifudin Syah (19061022)
Ahmad Rodi (19061013)
Prodi Pendidikan Matematika
Fakultas Sains, Teknik Dan Terapan
Undikma Mataram
2022
Kata Pengantar
Atas Berkat Rahmat Tuhan yang maha esa, Atas segala karunia Taufik Hidayah dan inayahnya sehingga kami bisa meyelesaikan Makalah tentang Graf yang berfokus pada tiga pokok bahasan besar yaitu Graf Garis, Subgraf dan Cilque yang menjadi salah satu tugas kelompok kami dalam menjalankan UTS pada mata kuliah teori Graf.
Kami berterima kasih yang sebesar-besarnya kepada ibu dosen pembimbing mata kuliah teory graf yaitu ibu Eliska Juliangkary Mp.d yang telah selalu senantiasa membimbing kami untuk menyelesaikan makalah
Kami selaku penulis tentunya masuh banyak sekali kekurangan baik itu dari segi penyampaian materi, kerapian dan penyajian di bidang kenyamanan pembaca oleh karena itu kami memerlukan kritikan dan saran yang bersifat membangun dari para pembaca
Mataram, 5 Juni 2022
Penulis
Daftar Isi
Daftar Isi 3
Bab I Pendahuluan 4
1.1. Latar Belakang 4
1.2. Rumusan Masalah 4
1.3. Tujuan 4
Bab II Pembahasan 5
2.1.Graf Garis 5
2.2. Sub Graf 8
2.3. Cilque 10
Bab III Penutup 20
3.1. Kesimpulan 20
3.2. Saran 20
Daftar Pustaka 21
Bab I
Pendahuluan
Latar Belakang
Teori graf merupakan cabang ilmu matematika yang menarik dan banyak dikembangkan. Dengan mengkaji dan menganalisa model atau rumusan dapat diperlihatkan peranan dan kegunaan teori graf dalam memecahkan berbagai macam permasalahan. Permasalahan yang dirumuskan dengan teori graf dibuat sederhana, yaitu diambil aspek-aspek yang diperlukan dan dibuang aspek-aspek lainnya. Selain itu graf dapat juga digunakan untuk merepresentasikan obyek-obyek diskrit dan hubungannya antara obyek-obyek tersebut. Dari sekian banyak konsep yang ada, salah satunya adalah tentang grup dan graf. Salah satu konsep yang menarik dari gruf dan graf kali ini kita akan membahas tentang Graf garis, Sub graf dan qilqiew yang akan manjadi pembahasan yang cukup menarik pada makalah ini dan akan memantu kita menyelesaikan masalah dalamkehidupan sehari-hari terutama permasalahan-permasalahan yang menyakut dengan teori graf.
Rumusan Masalah
Apakah yang dimaksud dengan graf garis dan kegunaanya ?
Apakah yang dimaksud dengan sub graf serta pembagian dan kegunaan ?
Apakah yang dimaksud degan Cliue dan kegunaanya ?
Tujuan
Untuk mengatahui dan mengenal graf garis dan kegunaannya dalam kehidupan
Untuk mengetahui apa itu subgraf, pembagin dan kegunaannya
Untuk mengetahui apa itu Cliue dan kegunaanya
Bab II
Pembahasan
2.1.Graf Garis
Definisi 2.1. 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 G yang disebut sebagai sisi.
Definisi 2.2. Sisi e = uv dikatakan menghubungkan titik u dan v. Jika e = uv adalah sisi di graf G, maka u dan v disebut bertetangga ( adjacent). Selanjutnya, sisi e dikatakan terkait ( incident) dengan titik u dan v.
Definisi 2.3. Matriks ketetanggaan untuk suatu graf dengan n titik didefinisikan sebagai An×n = [aij ] dimana aij bernilai 1 jika titik vi dan vj bertetangga, dan bernilai 0 jika titik vi dan vj tidak bertetangga
Definisi 2.4. Graf bipartisi lengkap 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 lengkap dinyatakan dengan Km,n
Definisi 2.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 bertetangga jika dan hanya jika sisi-sisi yang bersesuaian saling terkait di G
Suatu graf G mempunyai graf lain sebagai graf garisnya, dinotasikan L(G), jika dan hanya jika graf G mempunyai minimal satu sisi yang akan dijadikan titik di L(G). Berikut adalah beberapa graf garis dari beberapa graf terhubung dengan struktur yang sederhana.
Definisi 3.1. Graf siklus Cn adalah graf terhubung sederhana yang setiap titiknya berderajat dua.
Teorema 3.2. Untuk n ≥ 3, graf garis dari Cn, dinotasikan dengan L(Cn) adalah graf Cn itu sendiri
Bukti. Misalkan himpunan titik dan himpunan sisi dari graf Siklus Cn, n ≥ 3 masing-masing dapat dituliskan sebagai berikut.
V (G) = {vi | 1 ≤ i ≤ n},
E(G) = {ei | ei = vivi+1, 1 ≤ i ≤ n − 1} ∪ {v1vn}.
Dari matriks ketetanggaan di atas terlihat bahwa v1 bertetangga dengan v2, v2 bertetangga dengan v3, v3 bertetangga dengan v4, v4 bertetangga dengan v5, begitu seterusnya hingga vn−1 bertetangga dengan vn, dan vn bertetangga dengan v1. Dengan demikian graf garis yang dibentuk dari graf siklus Cn dengan orde n untuk (n ≥ 3) dapat dituliskan sebagai
L(Cn) ~ C
Definisi 3.3. Graf lengkap merupakan graf sederhana yang setiap titiknya terhubung dengan titik lainnya. Graf Garis untuk Siklus, Graf Lengkap dan Bintang 3
Definisi 3.4. Banyaknya sisi dalam suatu graf lengkap dengan n titik adalah
Teorema 3.5. Suatu graf lengkap Kn dengan orde n memiliki graf garis L(Kn) yang berbentuk graf 2(n − 2)− reguler, dengan n ≥ 3.
Bukti. Misalkan himpunan titik dan himpunan sisi dari graf lengkap Kn dapat dituliskan sebagai berikut.
V (G) = {vi | 1 ≤ i ≤ n},
E(G) = {vivj | 1 ≤ i, j ≤ n, i 6 = j}.
Jika terdapat dua titik yang dihubungkan oleh satu sisi, maka graf garisnya adalah didapatnya satu titik baru dengan dua sisi. Sehingga jumlah titik akan berkurang satu dari bentuk semula. Sehingga derajat setiap titik juga akan berkurang satu menjadi (n − 2). Karena satu titik baru tersebut terhubung oleh dua sisi yang berderajat sama, sehingga didapatlah graf garis L(Kn), dalam hal ini masingmasing titik mempunyai derajat (n − 2) + (n − 2) = 2(n − 2). Ini berarti graf garis L(Kn) adalah graf 2(n−2)-reguler. Dengan demikian graf garis yang dibentuk dari graf Siklus Kn dengan orde n untuk (n ≥ 3) dapat dituliskan sebagai,
L(Kn) ' 2(n − 2) − reguler.
Definisi 3.6. Graf Bintang merupakan graf bipartisi lengkap yang berbentuk Sn dengan n ≥ 3.
Teorema 3.7. Suatu graf bintang (Sn) dengan orde n ≥ 3 memiliki graf garis yang berbentuk L(Sn) ~Kn−1.
Bukti. Misalkan himpunan titik dan himpunan sisi dari graf bintang Sn tersebut masing-masing dapat dituliskan sebagai berikut.
V (G) = {v1, v2, v3, · · · , vn−1, vn},
E(G) = {e1, e2, e3, · · · , en−1}
Dari matriks ketetanggaan setiap sisi di atas terlihat bahwa v1 bertetangga dengan v2, v3, v4, vi , vn. v2 bertetangga dengan v1. v3 bertetangga dengan v1. v4 bertetangga dengan v1. vi bertetangga dengan v1. vn bertetangga dengan v1. Dengan demikian graf garis yang dibentuk dari graf bintang Sn dengan orde n merupakan graf lengkap Kn−1. Sehingga dapat dituliskan sebagai
L(Sn) ~ Kn−1.
2.2. Sub Graf
Sub Graf Terdukung
Graf disebut Subgraf dari G jika himpunan titik di H adalah subset dari himpunan titik-titik di G dan himpunan sisi-sisi di H adalah subset dari himpunan sisi-sisi di G.
Sub Graf Rentangan
Jalan, Jejak, Lintasan, siklus. Sebuah jalan (walk) dalam graf G adalah sebuah urutan tak nol W = v0e1v1e2v2...eivi ...ekvk, yang suku-sukunya bergantian antara simpul dan sisi sedemikian hingga 1 ≤ i ≤ k, ujung dari ei adalah vi-1 dan vi . v0 disebut simpul awal (simpul asal). vk disebut simpul akhir (simpul terminus). vi, 1 < i < k, disebut simpul internal. Panjang sebuah jalan adalah banyaknya sisi dalam jalan tersebut.
Jika semua sisi pada sebuah jalan berlainan, maka jalan tersebut disebut jejak (trail). Jejak yang simpul awal dan simpul akhirnya berlainan disebut jejak tertutup. Jika simpul-simpul dari v0e1v1e2v2...eivi ...ekvk dari jalan W berlainan, maka W disebut lintasan (path). Lintasan tertutup dinamakan siklus. Siklus dengan banyaknya simpul n, dinotasikan dengan Cn.
Siklus : Jejak tertutup yang simpul awal dan simpul internalnya berlainan
Sebuah graf adalah terhubung jika setiap dua buah titik di G dihubungkan oleh lintasan di G
Jika G adalah graf terhubung, maka dikatakan bahwa komponen dari G adalah 1, dinotasikan ω(G) = 1. Definisikan graf tidak terhubung!
Graf G disebut terhubung jika untuk setiap dua simpul yang berbeda terdapat lintasan yang menghubungkan simpul-simpul tersebut
Sebuah lintasan geodesic (geodesic path) antara titik u dan v dari graf G adalah lintasan u-v dengan panjang minimum.
Panjang lintasan geodesic antara simpul u dan v dinamakan jarak antara simpul u dan v. Dinotasikan d(u, v).
Misalkan G = (V, E) adalah sebuah graf. G1 = (V1, E1) adalah subgraf dari G jika V1 V dan E1 E.
Induced Subgraph.
Spanning subgraph.
2.3. Cilque
Berikut akan dibahas mengenai bilangan clique pada graf gear :
1. Graf Gear dengan
Berdasarkan teorema 2.4, Graf gear adalah graf gear yang mempunyai titik dan sisi.
Contoh :
Gambar 4.1 Graf Gear dengan
Selanjutnya untuk menentukan bilangan clique pada graf gear , caranya adalah mencari order dari subgraf komplit maksimum dari graf gear . Subgraf komplit dari graf gear adalah :
K1 : ● K2 :
Gambar 4.2 Subgraf komplit Graf Gear
Subgraf komplit maksimum dari graf gear adalah , karena subgraf komplit maksimum adalah , maka order dari adalah 2, sehingga .
2. Graf Gear dengan
Berdasarkan teorema 2.4, Graf Gear adalah graf gear yang memiliki 9 titik dan 12 sisi.
Contoh:
Gambar 4.3 Graf Gear dengan n = 4
Selanjutnya untuk menentukan bilangan clique pada graf gear , caranya adalah mencari order dari subgraf komplit maksimum dari graf gear . Subgraf komplit graf gear adalah:
K1: ● K2:
Gambar 4.4 subgraf komplit Graf gear
Subgraf komplit maksimum dari graf gear adalah , karena subgraf komplit maksimum adalah , maka order dari adalah 2, sehingga .
3. Graf Gear dengan
Berdasarkan teorema 2.4 Graf gear adalah graf gear yang memiliki 11 titik dan 15 sisi.
Contoh :
Gambar 4.5 Graf Gear dengan n = 5
Selanjutnya untuk menentukan bilangan clique pada graf gear , caranya adalah mencari order dari subgraf komplit maksimum dari graf gear . Subgraf komplit graf gear adalah:
K1: ● K2:
Gambar 4.6 Subgraf Komplit Graf Gear
Subgraf komplit maksimum dari graf gear adalah , karena subgraf komplit maksimum adalah , maka order dari adalah 2, sehingga .
4. Graf Gear dengan
Berdasarkan teorema 2.4, Graf gear adalah graf gear yang mempunyai 13 titik dan 18 sisi.
Contoh:
Gambar 4.7 Graf Gear dengan nn = 6
Selanjutnya untuk menentukan bilangan clique graf gear , caranya adalah mencari order dari subgraf komplit maksimum dari graf gear . Subgraf komplit graf gear adalah:
K1: ● K2: Gambar 4.8 Subgraf Komplit Graf Gear
Subgraf komplit maksimum dari graf gear adalah , karena subgraf komplit maksimum adalah , maka order dari adalah 2, sehingga . Berdasarkan beberapa penjelasan contoh diatas dapat dituliskan kembali sebagai berikut :
Tabel 4.1 Bilangan Clique Pada Graf Gear
Graf Gear
Bilangan Clique
.
.
.
.
.
.
Dari beberapa contoh yang di kerjakan dan berdasarkan tabel 4.1 maka dapat diambil kesimpulan sementara bahwa graf gear memiliki pola . Dengan demikian dapat dibuat teorema sebagai berikut:
Teorema 4.1
Jika G sebuah graf gear , maka bilangan clique pada graf gear adalah 2
Bukti :
Diketahui G adalah graf gear .
Andaikan artinya dan Kasus 1:
Hal ini berarti atau
Berdasarkan definisi 2.22 dan teorema 2.4, pada graf gear terdapat titik dan sebuah sisi. Berdasarkan definisi clique, maka pada graf gear terdapat subgraf komplit yaitu dan . Ditinjau dari definisi bilangan clique maka subgraf komplit maksimum dari graf gear tersebut adalah dan penyataan tersebut kontradiksi dengan pengandaian atau .
Kasus 2
Hal ini berarti
Sesuai definisi 2.22, graf gear adalah graf roda dengan penambahan satu titik diantara tiap-tiap pasangan titik pada sikel luar, ini berarti ada minimal 1 titik dimana titik itu tidak terhubung langsung dengan titik berbeda lainnya, hal tersebut kontradiksi dengan kenyataan graf komplit bahwa setiap 2 titik yang berbeda berhubungan langsung sehingga tidak terdapat subgraf komplit maksimum . Jadi pengandaian salah.
Dari kasus 1 dan kasus 2 maka dapat disimpulkan bahwa bilangan clique pada graf gear .
B. Bilangan Clique Pada Graf Barbel
Berikut akan dibahas mengenai bilangan clique pada graf barbel :
1. Graf Barbel dengan
Berdasarkan definisi 2.23, Graf barbel dengan adalah graf barbel yang disusun dari 2 graf komplit dan kedua graf tersebut dihubungkan dengan sebuah jembatan (sisi). Contoh:
Gambar 4.9 Graf Barbel Dengan
Selanjutnya untuk menentukan bilangan clique dari graf barbel , caranya adalah mencari order dari subgraf komplit maksimum dari graf barbel .
Subgraf komplit dari graf barbel adalah :
K1 : ●
K3 :
Gambar 4.10 Subgraf Komplit Graf Barbel Dengan
Subgraf komplit maksimum dari graf barbel adalah , karena subgraf komplit maksimum adalah , maka order dari adalah 3, sehingga
2. Graf Barbel dengan
Berdasarkan definisi 2.23,Graf barbel dengan adalah graf barbel yang disusun dari 2 graf komplit dan kedua graf tersebut dihubungkan dengan sebuah jembatan (sisi).
Contoh:
Gambar 4.11 Graf barbel Dengan
Selanjutnya untuk menentukan bilangan clique dari graf barbel , caranya adalah mencari order dari subgraf komplit maksimum dari graf barbel .
Subgraf komplit graf barbel adalah :
K1: ● K2 :
K3 : K4 :
Gambar 4.12 Subgraf Komplit Graf Barbel Dengan
Subgraf komplit maksimum dari graf gear adalah , karena subgraf komplit maksimum adalah , maka order dari adalah 4, sehingga .
3. Graf Barbel dengan
Berdasarkan definisi 2.23,Graf barbel dengan adalah graf barbel yang disusun dari 2 graf komplit dan kedua graf tersebut dihubungkan dengan sebuah jembatan (sisi).
Contoh:
Gambar 4.13 Graf Barbel Dengan
Selanjutnya untuk menentukan bilangan clique dari graf barbel , caranya adalah mencari order subgraf komplit maksimum dari graf barbel .
Subgraf komplit graf barbel adalah :
K1:● K2 :
K3 : K4 :
K5 :
Gambar 4.14 Subgraf Komplit Graf Barbel Dengan Subgraf komplit maksimum dari graf gear adalah , karena subgraf komplit maksimum adalah , maka order dari adalah 5, sehingga .
4. Graf barbel dengan
Berdasarkan definisi 2.23,Graf barbel dengan adalah graf barbel yang disusun dari 2 graf komplit maksimum dan kedua graf tersebut dihubungkan dengan sebuah jembatan (sisi). Contoh:
Gambar 4.15 Graf barbel Dengan
Selanjutnya untuk menentukan bilangan clique dari graf barbel , caranya adalah mencari order dari subgraf komplit maksimum graf barbel . Subgraf komplit graf barbel adalah:
K1: ● K2 :
K3 : K4 :
K5 : K6 :
Gambar 4.16 Subgraf Komplit Graf Barbel Dengan Subgraf komplit maksimum dari graf gear adalah , karena subgraf komplit maksimum adalah , maka order dari adalah 6, sehingga . Berdasarkan beberapa penjelasan contoh diatas dapat dituliskan kembali sebagai berikut:
Tabel 4.2 Bilangan Clique Pada Graf barbel
Graf Barbel
Bilangan Clique
3
4
5
6
.
.
.
.
.
.
Dari tabel 4.2 dapat diambil kesimpulan sementara bahwa bilangan clique pada graf barbel mempunyai rumusan , untuk setiap adalah bilangan asli.
Teorema 4.2
Jika G sebuah graf barbel , maka bilangan clique pada graf barbel
Bukti:
Subgraf yang mungkin dari graf Barbel adalah :
I. K1 : ●
K1 merupakan subgraf dari dan K1 subgraf komplit dari tetapi K1 bukan subgraf komplit maksimum dari
II.
Atau
Misal G1 dan G2 merupakan graf komplit yang sama dari graf barbel . G1 dan G2 merupakan subgraf dari .Subgraf komplit yang mungkin dari G1 atau G2 adalah , sehingga subgraf komplit maksimum dari G1 atau G2 adalah atau (graf G1 atau G2 itu sendiri).Jadi G1 atau G2 yaitu merupakan subgraf komplit maksimum
T
Graf T adalah subgraf dari , dengan G1 dan G2 merupakan graf komplit yang sama. Subgraf T tersebut bukan subgraf komplit dari , karena terdapat 2 titik berbeda yang tidak terhubung langsung. Sehingga T bukan subgraf komplit dari .
Berdasarkan pernyataan di atas, pernyataan II yang memenuhi syarat bilangan clique, sehingga dapat disimpulkan bahwa bilangan clique pada graf barbel adalah .
Bab III
Penutup
3.1. Kesimpulan
Graf garis dari siklus Cn dengan orde n ≥ 3 adalah siklus Cn, graf garis dari graf lengkap (Kn) dengan orde n ≥ 3 adalah graf 2(n − 2)−reguler, serta graf garis dari graf bintang (Sn) dengan orde n ≥ 3 adalah graf lengkap Kn−1.
Graf disebut Subgraf dari G jika himpunan titik di H adalah subset dari himpunan titik-titik di G dan himpunan sisi-sisi di H adalah subset dari himpunan sisi-sisi di G.
Bilangan Clique pada Graf Gear adalah 2, atau dapat ditulis, Bilangan Clique pada graf barbel adalah , atau dapat ditulis
3.2. Saran
Apabilal kita ingin menulis suatu materi pembelajaran ataupun pembuatan makalah hendaklah kita memiliki banyak referensi agar makalah ataupun buku yang dihasilkan memiliki kelengkapan dan tingkat galat yang sedikit.
Daftar Pustaka
Narwen, dkk, 2021. Graf Garis (Line Graph) Dari Graf Siklus, Graf Lengkap dan Graf Bintang. Jurnal Matematika UNAND Vol.3 No.2 Hal. 1-4
Abdussakir, Abdussakir (2008) Graf Garis (Line Graph). Matematika Fakultas UIN Maulana Malik Ibrahim Malang,. (Unpublished)
Yulianti, Kartika. 2008 Hand Out Mata Kuliah Teori Graf. Fakultas Mipa, UPI
Islamiah,Ruchil. 2011 Rank Minimum dari G pada Field Z2. FSTT UIN Maulana Malik Ibrahim Malang
